Leetcode 每日一题练习

ninijia 2024-03-27 18:04 1

从今日起在leetcode上进行每日一题的训练，接受坛友的监督，也欢迎各位大佬交流指导。

今日题目：

713. 乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入： nums = [10,5,2,6], k = 100 输出： 8 解释： 8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

输入： nums = [1,2,3], k = 0 输出： 0

题解

本题要求返回的是连续的相邻子数组, 第一个想到的就是滑动窗口, 设置窗口的前后指针, 当窗口内的积<k时, 扩大窗口, 并增加计数, 当窗口内的积≥k时, 缩小窗口, 直到重新满足<k的条件为止. 这里增加计数的地方需要仔细考量, 并不是扩大窗口且积<k时, 就将计数加一, 因为该题是求积, 所以当两个数的积<k时, 其实已经包含了每个数都小于k在其中, 同理, 当三个数积<k时, 包含了任意两个的组合积都<k, 而本题只要求连续相邻的子序列. 故每次窗口扩大且符合条件时增加的计数应该为当前窗口的长度. (可以自己考虑一下从2个数扩大到3个数时默认新增了几种符合要求的子序列, 应该是包含新增加的数本身, 加上相邻一个数, 加上相邻两个数三种情况, 前面两个数的情况在之前已经计数过了)

代码

func numSubarrayProductLessThanK(nums []int, k int) int {

    front := 0

    back := 0

    sum := 1

    result := 0

     for front < len(nums){

        sum *= nums[front]

        if sum < k{

            front++

            result += front - back

        }else{

            if front == back{

                front++

                back++

                sum = 1

                continue

            }

            sum /= nums[back]

            sum /= nums[front]

            back++

        }

     }

     return result

}

总结

在查看速度更快的题解代码时, 发现可以通过内层循环一直缩小窗口到<k时, 才继续向下滑动窗口, 这样外层只需要不断向下遍历来扩大窗口即可. 这样写循环思路更清晰, 代码更简洁如下

func numSubarrayProductLessThanK(nums []int, k int) int {

    if k <= 1 {

        return 0

    }

    res := 0



    p := 1

    j := 0



    for i := 0; i < len(nums); i++ {

        p *= nums[i]

        for p >= k {

            p /= nums[j]

            j++

        }

        res += i -j + 1

    }



    return res

}

想到这, 忽然明白, 其实核心在于只需要考虑以某个位置为结尾的向前连续符合要求的数组长度作为该位置处应该增加的计数数目即可. 这样就把整个问题拆分成了独立不关联的小问题. 将每个位置应该增加的计数数目累积, 就是最终的结果.

最新回复 (19)

moinkhao 03-27 18:10

1楼

这不得出个合集
ninijia 楼主 03-27 18:12

2楼
其实昨天也做了 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

}
```
Google 03-27 18:12

3楼

可以加个 leetcode 标签
中国联通集团 03-27 18:27

4楼

这不得带上解析 ^-^
Megasoft 03-27 18:42

5楼

补上变量范围更严谨，很多时候根据数据规模可以猜时间复杂度
廖哈哈 03-27 18:44

6楼

关注了，一起刷题
lovexl 03-27 19:07

7楼

加油，一起打卡
Hua 03-27 19:17

8楼

#Leetcode添加
LeetCode 03-27 20:43

9楼

好好好终于看到这种帖子了
Lin Goo 03-27 20:49

10楼

学习了
pada 03-27 21:26

11楼

可以可以

ninijia 楼主 03-28 22:29

12楼

虽迟但到

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

}

jkl 03-28 22:38

13楼

学习，还挺厉害

ninijia 楼主 03-29 15:29

14楼

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

}

ink 03-29 17:12

15楼

这不得每天一贴么
ninijia 楼主 03-29 22:08

16楼

肯定每天一贴

ninijia 楼主 03-30 11:31

17楼

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

}

ninijia 楼主 03-31 13:32

18楼

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月份的奖章, 证明这个月每天都在坚持. 下个月希望能继续坚持下去.

ninijia 楼主 04-01 09:23

19楼

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

* 帖子来源Linux.do

附近帖子

飞读

ninijia

主题数
1

帖子数
1

注册排名
3

随机推荐

Leetcode 每日一题练习

713. 乘积小于 K 的子数组

题解

代码

总结

442. 数组中重复的数据

题解

代码

题解

代码

总结

题解

代码

总结

题解

代码

总结

题解

代码

总结

题解

代码

总结

ninijia