2022/5/5的每日一题

题目：

思路：

一开始想用回溯，发现不能使用【下面回溯结束的条件是<k，一开始就会满足结束退出函数】，如果是相等的情况【求可行解的情况】，使用回溯会很合适【如leetcode22/39题】。然后想到使用滑动窗口求合适的解。

?????

具体代码：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        //边界处理
        if (nums.length == 0 || k <= 1) {
            return 0;
        }
        int n = nums.length, res = 0;
        for (int i = 0,j = 0, cur = 1; i < n; i++) {
            //题目要求的计算逻辑
            cur *= nums[i];
            while (cur >= k) {
                //不满足条件，进行撤销
                cur /= nums[j++];
            }
            //以i位置结束的有多少个合理数组
            res += i - j + 1;
        }
        return res;
    }
}

延申同种类型的题目：leetcode438

题目：

思路：

因为题目给给出是字母，使用ASCII码映射位置，维持左右指针，如果满足则右组件移动一位，同时如果满足了字母异位词，那么就添加进数组里面；否则，将左边指针所指向的值复原，同时移动一位。

代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] cnt = new int[128];
        for (char c : p.toCharArray()) cnt[c]++;
        int lo = 0, hi = 0;
        List<Integer> res = new ArrayList<>();
        while (hi < s.length()) {
            if (cnt[s.charAt(hi)] > 0) {
                //先取0
                cnt[s.charAt(hi++)]--;
                if (hi - lo == p.length()) res.add(lo);
            } else {
                //记录索引，走了第几步，恢复原样
                cnt[s.charAt(lo++)]++;
            }
        }
        return res;
    }
}