Leetcode 每日一题练习

这不得出个合集

其实昨天也做了 po个昨天的热热帖

442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1：

输入： nums = [4,3,2,7,8,2,3,1] 输出：[2,3]

示例 2：

输入： nums = [1,1,2] 输出：[1]

示例 3：

输入： nums = [1] 输出：

题解

本题若想在O(n)时间复杂度内求解, 必须在遍历数组的时候充分利用遍历过的数据提供的信息, 在后续充分利用已有信息, 在本题中, 遍历过程中的每个位置处的数本身就是信息. 若使用O(n)的空间复杂度, 可以创建一个和目标数组长度相同的空数组, 将遍历到的元素的数作为下标, 设定对应空数组中下标所在位置的值作为标记. 这样后续遍历时看到标记则知道这个数是重复的. 若想空间复杂度为O(1), 因为本题并没有要求不修改数组, 可以修改数组中以这个数为下标处的数据, 这里可以将其取相反数来表明这个下标已经出现过. 这也是因为体重明确说明数组中的数的范围在1-数组长度之间, 因此可以采用这种方法来标记数据是否已经出现, 如果有数大小超过数组长度, 这种方案就不适用了, 则必须使用O(n)的空间.

代码```
func findDuplicates(nums []int) []int {
result := []int{}
for _, values := range nums{
if nums[int(math.Abs(float64(values)))-1] < 0{
result = append(result, int(math.Abs(float64(values))))
}
nums[int(math.Abs(float64(values)))-1] = -nums[int(math.Abs(float64(values)))-1]
}
return result
}

可以加个 leetcode 标签

这不得带上解析 ^-^

补上变量范围更严谨，很多时候根据数据规模可以猜时间复杂度

关注了，一起刷题

加油，一起打卡

#Leetcode添加

好好好 终于看到这种帖子了

学习了

可以可以

虽迟但到

2958. 最多 K 个重复元素的最长子数组

题解

拿到本题, 直接思路就是使用滑动窗口, 使用一个哈希表来存储每个数字对应的个数, 在滑动的过程中, 扩大窗口时增加窗口新增数字的计数并不断更新最大长度, 直到当前数字的计数达到上限k开始缩小窗口, 缩小至当前数字计数小于k(缩小过程中的数都在哈希表中对应减掉频率)即可继续扩大窗口. 如此直到遍历完整个数组. 其实从解题思路上与昨天的题内核是十分相似的.

代码```
func maxSubarrayLength(nums []int, k int) int {
count := map[int]int{}
end := 0
maxlength := 0
for front:=0;front < len(nums);front++{
_,exist := count[nums[front]]
if !exist{
count[nums[front]] = 1
}else{
count[nums[front]]++
}

if count[nums[front]] <= k{
maxlength = max(maxlength,front-end+1)
}else{
for nums[end] != nums[front]{
count[nums[end]]--
end++
}
// 将达到上限的数本身减掉
count[nums[end]]--
end++
}
}
return maxlength
}

查看前面10%更快的代码, 发现判断缩小窗口的结束可以用当前窗口前端达到上限的数在哈希表中对应的计数值来判断, 缩小窗口直到达到上限的数的计数值小于k即可结束, 这样整体代码更清晰, 更简洁, 如下```
func maxSubarrayLength(nums []int, k int) int {
    m := make(map[int]int)
    res := 0
    for l, r := 0, 0; r < len(nums); r++ {
        m[nums[r]]++
        for m[nums[r]] > k {
            m[nums[l]]--
            l++
        }

        if r-l+1 > res {
            res = r-l+1
        }
    }

    return res
}

学习，还挺厉害

2962. 统计最大元素出现至少 K 次的子数组

题解

本题感觉就是昨天那道题的姊妹+升级版, 现在要求找到数组中包含的最大值, 其在这个子数组中的出现次数至少为k次. 这里明确题目中需要解决的两个问题. 1. 找到数组中的最大值 2. 对这个值在子序列中出现的次数进行计数. 无疑, 仍然可以使用滑动窗口来解决, 思路和昨天的题类似, 这里在扩大窗口时, 一直扩大到最大值数目为k, 继续向后遍历时要每次增加从头开始到包含k个最大值的窗口的最左端的元素个数. 核心思路在于让滑动窗口中只保留k个最大值, 这样所有包含前面数据的子数组和包含后面不为最大值的子数组的所有子数组都符合条件.

代码```
func countSubarrays(nums []int, k int) int64 {
max := slices.Max(nums)
var result int64
left := 0
nextleft := 0
beforeadded := 0
frequency := 0
for _, value := range nums{
if value == max{
frequency++
if frequency >= k{
for nums[nextleft] != max{
nextleft++
}
beforeadded += nextleft - left + 1
result += int64(beforeadded)
left = nextleft+1
nextleft = left
}
}else if frequency >= k{
result += int64(beforeadded)
}

}

return result
}

查看他人的题解发现, 可以在保持窗口内最大值个数为k的思路下优化解题过程, 重复的加前面的元素是不必要的, 先将所有最大值的下标放入数组, 然后确定包含k个最大值的窗口的两端的下标, 将该窗口左侧前面的元素个数和窗口右侧后面的元素个数相乘即为该窗口对应的符合条件的解的个数, 切换到下一个包含k个最大值的窗口, 继续此操作, 直到窗口中最大值数目不足k为止. 用乘法操作减少了大量的加法操作，大大增加了效率。```
func countSubarrays(nums []int, k int) int64 {
	var m int
	for _, n := range nums {
		m = max(m, n)
	}
	var idxs []int
	for i := range nums {
		if nums[i] == m {
			idxs = append(idxs, i)
		}
	}
	start := 0
	count := int64(0)
	for i := range idxs {
		if i+k > len(idxs) {
			break
		}
		last := len(nums)
		if i+k < len(idxs) {
			last = idxs[i+k]
		}
		count += int64(idxs[i]-start+1) * int64(last-idxs[i+k-1])
	}
	return count
}

肯定每天一贴

992. K 个不同整数的子数组

题解

本题仍然使用滑动窗口, 这几天连续做滑动窗口的题, 总结了滑动窗口的"三要素": 1. 什么时候扩大窗口 2. 双么时候缩小窗口 3. 缩小和扩大窗口时执行哪些操作

对于本题, 题目中要求计数正好包含k个不同数的子数组的个数, 求精确包含k个这种问题往往比较困难, 可以转化为求解包含≤k个和≤k-1个不同数的子数组个数的差. 这种思路求解起来非常方便. 对于求解包含≤k个不同数的子数组的个数, 当数组中包含不同数个数不足k时, 扩大窗口同时将计数增加当前窗口的长度, 若为k+1, 则缩小窗口至正好完全去除了一个数(若某个数只出现了1次, 去掉后窗口内不同数个数就是k, 若不止一次, 则去掉了不同数个数也没有变化, 故要继续向下遍历). 最后求≤k和≤k-1情况的计数值做差即可.

代码```
func subarraysWithKDistinct(nums []int, k int) int {

return countk(nums, k) - countk(nums, k-1)
}

func countk(nums []int, k int) int {
count := map[int]int{}
different := 0
left := 0
result := 0
for index, value := range nums {
_, exist := count[value]
if !exist {
different++
count[value] = 1
} else {
count[value]++
}
if different <= k {
result += index - left + 1
}
if different == k+1 {
for count[nums[left]] > 1 {
count[nums[left]]--
left++
}
delete(count, nums[left])
left++
different--
result += index - left + 1
}
}
return result
}

解题时没有注意题目限制, 后来查看最快解法发现忽略了题目中的数的范围, 题目中的数组中的数的大小不超过数组的长度, 数的范围已知, 因此可以使用数组代替哈希表来计数这样可以大大加快解题速度.```
func subarraysWithKDistinct(nums []int, k int) (ans int) {
	f := func(k int) []int {
		n := len(nums)
		pos := make([]int, n)
		cnt := make([]int, n+1)
		s, j := 0, 0
		for i, x := range nums {
			cnt[x]++
			if cnt[x] == 1 {
				s++
			}
			for ; s > k; j++ {
				cnt[nums[j]]--
				if cnt[nums[j]] == 0 {
					s--
				}
			}
			pos[i] = j
		}
		return pos
	}
	left, right := f(k), f(k-1)
	for i := range left {
		ans += right[i] - left[i]
	}
	return
}

2444. 统计定界子数组的数目

庆祝一下三月奖章

题解

本题先求出数组中包含上下界的所有可行子区域, 可行子区域指所有连续的符合上下界要求的最长区域. 将这些区域的头尾下标保存到一个二维数组中. 对于每个可行区域, 使用该区域包含的全部子数组的个数减去不满足上下界要求的子数组个数, 不满足上下界要求的子数组个数求解使用滑动窗口是比较容易的, 从头开始滑动, 窗口内只能包含上界或者下届或者都不包含. 若直接求解该区域中包含的满足上下界的子数组个数则比较困难. 用子数组总个数和不满足上下界要求的子数组个数做差即可得到想求的满足上下界的子数组个数. 对于每个子区域都执行这样的操作, 并将求得的满足条件的子数组个数加和即可得到最终的结果, 注意处理上下界都是同一个数的边界情况.

代码```
func countSubarrays(nums []int, minK int, maxK int) int64 {
begin := 0
borders := [][]int{}
mincurrent := -1
maxcurrent := -1
var result int64
// 找到所有可行区间
for index, value := range nums{
border := []int{}
if value == minK {
mincurrent = 1
}
if value == maxK {
maxcurrent = 1
}
if value > maxK || value < minK || index == len(nums)-1{
if maxcurrent == -1 || mincurrent == -1{
mincurrent = -1
maxcurrent = -1
begin = index + 1
}else{
if value <= maxK && value >= minK && index == len(nums) - 1 {
index += 1
}
border = append(border, begin)
border = append(border, index)
borders = append(borders, border)
border = border[:0]
mincurrent = -1
maxcurrent = -1
begin = index + 1
}
}
}

// 求每个可行区间中解的数目并加和 求解可行区间已经保证区间内必有上下限存在
for _, region := range borders{
left := region[0]
right := region[1]
ismin := false
ismax := false
last := 0
allarray := (right - left + 1) * (right - left) / 2
left = 0
outrange := 0
for index, value := range nums[region[0]:right]{
if value != minK && value != maxK{
outrange += index - left + 1
}else if value == minK{
if value == maxK{
left = index + 1
continue
}
if ismax{
left = last + 1
ismax = false
ismin = true
}else if !ismin{
ismin = true
}
last = index
outrange += index - left + 1
}else{
if ismin{
left = last + 1
ismin = false
ismax = true
}else if !ismax{
ismax = true
}
last = index
outrange += index - left + 1
}
}
result += int64(allarray - outrange)
}
return result
}

本次解题代码的运行速度超过了100%的提交, 因此不再看他人的题解了, 同时庆祝一下自己拿到了3月份的奖章, 证明这个月每天都在坚持. 下个月希望能继续坚持下去.

58. 最后一个单词的长度

题解

本题是一道简单题, 直接从头开始遍历, 遇到空格结束当前单词计数, 再遇到新字符时重新计数, 直到遍历完整个字符串即可.

代码```
func lengthOfLastWord(s string) int {
length := 0
flag := false
for _, value := range s{
if value == ' ' {
flag = true
}
if value != ' ' {
if flag{
length = 1
flag = false
}else{
length++
}
}
}
return length
}

前面的题解大多用了go strings库中的函数来按空格分割字符串, 再返回最后一个分割出来的字符串长度. 一般实际应用中, 使用官方库是第一选择, 因为官方库大多对这些操作做了大量优化, 效率会高得多.