LeetCode算法练习top100：（2）子串，普通数组

爱被打了一巴掌 2024-02-18 10:07 32阅读 0赞

package jz.top100;
    
    import java.util.*;
    
    public class Top1002 {
        
        //560. 和为 K 的子数组
        //方法1. 暴力计算
        public int subarraySum(int[] nums, int k) {
        
            int res = 0;
            for (int left = 0; left < nums.length; left++) {
        
                int sum = 0;
                for (int right = left; right < nums.length; right++) {
        
                    sum += nums[right];
                    if (sum == k) res++;
                }
            }
            return res;
        }
    
        //方法2：前缀和
        public int subarraySum(int[] nums, int k) {
        
            int n = nums.length;
            //前缀和:减少计算量
            int[] sum = new int[n + 1];
            for (int i = 0; i < n; i++) {
        
                sum[i + 1] = sum[i] + nums[i];
            }
            int res = 0;
            for (int i = 1; i <= n; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    //从j到i的字串和
                    if (sum[i] - sum[j] == k) res++;
                }
            }
            return res;
        }
    
        //239. 滑动窗口最大值
        public static int[] maxSlidingWindow(int[] nums, int k) {
        
            int n = nums.length;
            if (k > n) return new int[0]; //无法形成窗口
            int[] res = new int[n - k + 1];
            ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(); //对窗口内的数字从大到小排序，并删除上一个窗口的数字，添加当前窗口的数字
            //只需要保证最大数字在当前窗口就行
            for (int i = 0; i < n; i++) {
        
                //保证顺序:循环移除小于当前数字的值
                while (!arrayDeque.isEmpty() && nums[i] > nums[arrayDeque.peekLast()]) {
        
                    arrayDeque.pollLast();
                }
                //当前数字插入到队列尾部
                arrayDeque.addLast(i);
                //当前窗口的最大值是否有效
                if (arrayDeque.peekFirst() < i - k + 1) {
        
                    arrayDeque.pollFirst();
                }
                //计算当前窗口最大值
                if (i >= k - 1) {
        
                    res[i - k + 1] = nums[arrayDeque.peekFirst()];
                }
            }
            return res;
        }
    
        //76. 最小覆盖子串
        public String minWindow(String s, String t) {
        
            //hash表统计字符串t各个字符的频次
            HashMap<Character, Integer> need = new HashMap<>(); //需要覆盖的字符及数量
            HashMap<Character, Integer> window = new HashMap<>(); //窗口内的字符和数量
            for (Character c : t.toCharArray()) {
        
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            //各个字符可以被覆盖的个数
            int valid = 0; //窗口内可以覆盖字串的字符种类数量
            int left = 0, right = 0; //滑动窗口
            int start = 0, len = Integer.MAX_VALUE; //最小覆盖字串的长度和起点
            while (right < s.length()) {
        
                char c = s.charAt(right);
                //当前字符是否是被需要的
                if (need.containsKey(c)) {
        
                    //在窗口内统计字符频率
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    //当前字符是否覆盖
                    //注意：两个Integer类型的数据不能直接用< == >判断
                    if (window.get(c).equals(need.get(c))) {
         //当前窗口内字符c已经覆盖
                        valid++;
                    }
                }
                right++;
                //当覆盖时，寻找最优解
                while (valid == need.size()) {
        
                    //更新最小覆盖字串
                    if (right - left < len) {
        
                        len = right - left;
                        start = left;
                    }
                    //窗口第一个字符是否可以删掉
                    char d = s.charAt(left);
                    left++;
                    //当删掉的字符是有用的字符
                    if (need.containsKey(d)) {
        
                        //更新窗口频率
                        window.put(d, window.get(d) - 1);
                        //当前字符是否还可以覆盖
                        if (window.get(d) < need.get(d)) {
        
                            valid--;
                        }
                    }
                }
            }
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }
    
        //53
        public int maxSubArray(int[] nums) {
        
            int max = nums[0];
            int[] dp = new int[nums.length]; //已i为结尾的子数组的最大和(必须包含i,实现连续子数组要求)
            dp[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
        
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                max = Math.max(max, dp[i]);
            }
            return max;
        }
    
        //56. 合并区间
        public int[][] merge(int[][] intervals) {
        
            ArrayList<int[]> list = new ArrayList<>(); //记录无法被合并的区间
            Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]); //按照区间左边界从小到大排序
            int[] pre = intervals[0];
            for (int i = 1; i < intervals.length; i++) {
        
                if (pre[1] >= intervals[i][0]) {
         //可以合并的区间，pre合并到当前区间
                    pre[1] = Math.max(pre[1], intervals[i][1]);
                } else {
        
                    list.add(pre);
                    pre = intervals[i];
                }
            }
            //把pre加入数组
            list.add(pre);
            int[][] res = new int[list.size()][2]; //结果是两列
            for (int i = 0; i < list.size(); i++) {
        
                res[i] = list.get(i);
            }
            return res;
        }
    
        //
        public void rotate(int[] nums, int k) {
        
            k = k % nums.length;
            reverse(nums, 0, nums.length -1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length -1);
        }
        private void reverse(int[] num, int start, int end) {
        
            while (start < end) {
        
                int v = num[end];
                num[end] = num[start];
                num[start] = v;
                start++;
                end--;
            }
        }
    
        //238. 除自身以外数组的乘积
        public int[] productExceptSelf(int[] nums) {
        
            int n = nums.length;
            int[] left = new int[n];
            int[] right = new int[n];
            left[0] = 1;
            for (int i = 1; i < n; i++) {
        
                left[i] = left[i - 1] * nums[i - 1];
            }
            right[n - 1] = 1;
            for (int i = n - 2; i >= 0; i--) {
        
                right[i] = right[i + 1] * nums[i + 1];
            }
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
        
                res[i] = left[i] * right[i];
            }
            return res;
        }
    
        //41. 缺失的第一个正数
        //方法1：排序
        public int firstMissingPositive(int[] nums) {
        
            Arrays.sort(nums);
            int j = 1; //整数的第一个数
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] <= 0 || (i > 0 && nums[i] == nums[i - 1])) {
        
                    continue;
                }
                if (nums[i] != j) {
        
                    break;
                }
                j++;
            }
            return j;
        }
        //方法2：hashset
        public int firstMissingPositive(int[] nums) {
        
            HashSet<Integer> set = new HashSet<>();
            for (int num : nums) {
        
                set.add(num);
            }
            //从1开始搜索，如果从1开始，nums理论上的最大值是nums.length
            for (int i = 1; i <= nums.length; i++) {
        
                if (!set.contains(i)) {
        
                    return i;
                }
            }
            //如果正整数都存在,返回nums的最大正整数+1
            return nums.length + 1;
        }
    
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    }