LeetCode 12 / 100

2024-03-20 07:24:05
开发
41

滑动窗口

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

滑动窗口就是一个队列，队列（窗口）满足题目要求的时候，再进入一个元素不满足要求了，所以要移动这个队列
只要把队列左边的元素移除就行了，直到满足题目要求
一直维持这样的队列，找出队列出现最长的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> hm = new HashMap<>();
        int res = 0;
        int left = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (hm.containsKey(ch)) {
                left = Math.max(left, hm.get(ch) + 1);
            }
            hm.put(ch, right);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

因为字符串 p 的异位词的长度一定与字符串p 的长度相同，所以在字符串 s 中构造一个长度和 p 的长度相同的滑动数组，维护每种字母的数量，当每种字母的数量与字符串 p 中每种字母数量相同时，说明找到一个异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        if (s.length() < p.length()) return new ArrayList<>();

        int[] sArray = new int[26];
        int[] pArray = new int[26];

        for (int i = 0; i < p.length(); i++) {
            ++sArray[s.charAt(i) - 'a'];
            ++pArray[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sArray, pArray)) {
            list.add(0);
        }
        for(int i = 0; i < s.length() - p.length(); i++) {
            --sArray[s.charAt(i) - 'a'];
            ++sArray[s.charAt(i + p.length()) - 'a'];
            if (Arrays.equals(sArray, pArray)) {
                list.add(i + 1);
            }
        }
        return list;
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        if (s.length() < p.length()) return list;

        int[] count  = new int[26];
        for (int i = 0; i < p.length(); i++) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int differ = 0;

        for (int i = 0; i < count.length; i++) {
            if (count[i] != 0) {
                differ++;
            }
        }

        if (differ == 0) {
            list.add(0);
        }

        for (int i = 0; i < s.length() - p.length(); i++) {
            if (count[s.charAt(i) - 'a'] == 1) {
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {
                ++differ;
            }
            --count[s.charAt(i) - 'a'];
            if (count[s.charAt(i + p.length()) - 'a'] == -1) {
                --differ;
            } else if (count[s.charAt(i + p.length()) - 'a'] == 0) {
                ++differ;
            }
            ++count[s.charAt(i + p.length()) - 'a'];

            if (differ == 0) {
                list.add(i + 1);
            }
        }
        return list;
    }
}

子串

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

子数组是数组中元素的连续非空序列。

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

枚举
暴力求解 $O(n^2)$

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;
            for (int end = start; end >= 0; end--) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

前缀和 + 哈希表
- 初始化一个字典 prefix_sum_count，用于记录前缀和出现的次数，初始时包含 (0, 1)，表示前缀和为 0 的次数为 1。
- 初始化变量 count 记录和为 k 的子数组个数，初始化变量 prefix_sum 记录当前位置的前缀和。
- 遍历数组 nums，计算当前位置的前缀和并更新 count：
- 计算当前位置的前缀和：prefix_sum += num。
- 如果 prefix_sum - k 在 prefix_sum_count 中，说明之前有前缀和为 prefix_sum - k，则将对应的次数加到 count 上。
- 更新 prefix_sum_count[prefix_sum] 的次数。
- 返回 count 即为和为 k 的子数组个数。

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 定义 pre[i] 为 [0..i]里所有数的和
        // 那么「[j..i] 这个子数组和为 k 」可以表示为
        // pre[i] - pre[j-1] = k
        // pre[j - 1] = pre[i] - k

        HashMap<Integer, Integer> hm = new HashMap<>();

        int count = 0;
        int pre = 0;
        hm.put(0, 1);

        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (hm.containsKey(pre - k)) {
                count += hm.get(pre - k);
            }
            hm.put(pre, hm.getOrDefault(pre, 0) + 1);
        }
        return count;

    }
}

滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 最大堆，为了判断元素是否在滑动窗口里，需要把元素的位置一起维护
        // 当位置出了窗口左侧，就把这个元素从堆里移除
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });

        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i], i});
        }

        int[] ans = new int[nums.length - k + 1];

        ans[0] = pq.peek()[0];
        for (int i = k; i < nums.length; i++) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 单调队列
        // 和最大堆类似，这里用一个队列存储所有没被移除的下标
        // 维护两种秩序
        // 维护从小到大的元素位置
        // 维护从大到小的元素值
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        int[] ans = new int[nums.length - k + 1];
        ans[0] = nums[queue.peekFirst()];
        for (int i = k; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
            while (!queue.isEmpty() && queue.peekFirst() <= i - k) {
                queue.pollFirst();
            }
            ans[i - k + 1] = nums[queue.peekFirst()];
        } 
        return ans;
    }
}

76. 最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> hs = new HashMap<>();
        HashMap<Character,Integer> ht = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            ht.put(t.charAt(i), ht.getOrDefault(t.charAt(i), 0) + 1);
        }

        String ans = "";
        int len = Integer.MAX_VALUE, cnt = 0; // 有多少个元素符合
        for (int i = 0, j = 0; i < s.length(); i++) {
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) {
                cnt++;
            }
            while (j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))) {
                hs.put(s.charAt(j), hs.get(s.charAt(j)) - 1);
                j++;
            }
            if (cnt == t.length() && i - j + 1 < len) {
                len = i - j + 1;
                ans = s.substring(j, i+1);
            }
        }
        return ans;
    }
}

原文地址:https://blog.csdn.net/SUburbuia/article/details/136802185 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1770229784442441728.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部