第一题好像被rejudge掉了,麻了。
【枚举】删除字符使频率相同
题目
给你一个下标从 0 开始的字符串 word
,字符串只包含小写英文字母。你需要选择 一个 下标并 删除 下标处的字符,使得 word
中剩余每个字母出现 频率 相同。
如果删除一个字母后,word
中剩余所有字母的出现频率都相同,那么返回 true
,否则返回 false
。
注意:
- 字母
x
的 频率 是这个字母在字符串中出现的次数。 - 你 必须 恰好删除一个字母,不能一个字母都不删除。
示例 1:
|
|
示例 2:
|
|
提示:
2 <= word.length <= 100
word
只包含小写英文字母。
解题思路
这题情况有点多,没考虑全就容易WA
赛时WA了两发才过。今天看竟然被rejudge掉了。
赛后看其实暴力枚举就行了呀,也就不用考虑那么多情况了。
枚举删除第i种字符,再看剩余的是否合题意就行。
代码
|
|
【模拟】最长上传前缀
题目
给你一个 n
个视频的上传序列,每个视频编号为 1
到 n
之间的 不同 数字,你需要依次将这些视频上传到服务器。请你实现一个数据结构,在上传的过程中计算 最长上传前缀 。
如果 闭区间 1
到 i
之间的视频全部都已经被上传到服务器,那么我们称 i
是上传前缀。最长上传前缀指的是符合定义的 i
中的 最大值 。
请你实现 LUPrefix
类:
LUPrefix(int n)
初始化一个n
个视频的流对象。void upload(int video)
上传video
到服务器。int longest()
返回上述定义的 最长上传前缀 的长度。
示例 1:
|
|
提示:
1 <= n <= 10^5
1 <= video <= 10^5
video
中所有值 互不相同 。upload
和longest
总调用 次数至多不超过2 * 10^5
次。- 至少会调用
longest
一次。
解题思路
乐。赛时又用了线段树。
其实用一个数组一个指针就可以维护这个最长前缀了,这个最长前缀不会减小。
代码
|
|
线段树
|
|
【思维+位运算】所有数对的异或和
题目
给你两个下标从 0 开始的数组 nums1
和 nums2
,两个数组都只包含非负整数。请你求出另外一个数组 nums3
,包含 nums1
和 nums2
中 所有数对 的异或和(nums1
中每个整数都跟 nums2
中每个整数 恰好 匹配一次)。
请你返回 nums3
中所有整数的 异或和 。
示例 1:
|
|
示例 2:
|
|
提示:
1 <= nums1.length, nums2.length <= 10^5
0 <= nums1[i], nums2[j] <= 10^9
解题思路
主要利用异或的性质: a^a = 0
这题的答案与两个数组的奇偶性有关
两个数组都是偶数个时,答案为0
代码
|
|
【线段树+类逆序对】满足不等式的数对数目
题目
给你两个下标从 0 开始的整数数组 nums1
和 nums2
,两个数组的大小都为 n
,同时给你一个整数 diff
,统计满足以下条件的 数对 (i, j)
:
0 <= i < j <= n - 1
且nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff
.
请你返回满足条件的 数对数目 。
示例 1:
|
|
示例 2:
|
|
提示:
n == nums1.length == nums2.length
2 <= n <= 10^5
-10^4 <= nums1[i], nums2[i] <= 10^4
-10^4 <= diff <= 10^4
解题思路
根据nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff
移项得:nums1[i] - nums2[i] <= nums1[j]- nums2[j] + diff
这样研究对象就变成一个数组了
令a[i] = nums1[i] - nums2[i]
,要求a[i] <= a[j]+diff
且i<j
的数对个数。
和逆序对的思路类似。
倒序遍历数组,考虑a[i]时,就不会受下标小于i的数的影响。
再利用线段树/树状数组等结构维护a[j] + diff
,(其中)的值的分布情况,可在log(n)
时间复杂度内求得以i开头的数对(i,j)数目。
由于值可能出现负数,离散化一下即可。
总时间复杂度
代码
|
|