秋刀鱼在做梦

这个屌丝很懒，什么也没留下！

热门标签

Leetcode刷题记录2 子串+数组

作者：秋刀鱼在做梦 | 2024-07-08 18:06:55

踩

Leetcode刷题记录2 子串+数组

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
hot100
总结

前言

记录一些leetcode刷题中遇到的问题，共勉

hot100

4.子串

#560. 和为 K 的子数组

题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

方法一：暴力枚举

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        int sum=0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                sum += nums[j];
                if(sum==k){
                    count++;
                }
            }
            sum = 0;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：前缀和

class Solution {
    public int subarraySum(int[] nums, int k) {
        //  前缀和，这里的前缀和表示从索引为-1到后面某个元素的连续和
        //  从-1开始是假设索引为0的元素之前还存在一个元素0，为了后面计算方便
        //  (key,value)分别对应(某个前缀和，其前缀和对应个数)
        Map<Integer,Integer> map = new HashMap<>();
        int count  = 0;
        map.put(0,1);
        int sum = 0;
        int n = nums.length;
        for(int i=0;i<n;i++){
            sum += nums[i];
            if(map.containsKey(sum-k)){
                count += map.get(sum-k);
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        
        return count;
        



    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#239. 滑动窗口最大值

题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：

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

方法一：暴力枚举，不过超时了

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        
        int[] res = new int[n-k+1];
        for(int i=0;i<=n-k;i++){
            int max = nums[i];
            for(int j=i;j<i+k;j++){
                if(nums[j]>max){
                    max = nums[j];
                }
            }
            res[i] = max;
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：使用优先级队列，每次加入一个数字，优先级队列内部自动进行排序，当取出队头元素时候判断是否滑动窗口已经移出包含这个数字的窗口，若已经移出，则进行出队操作

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        
        int[] res = new int[n-k+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] arr1, int[] arr2){
                if(arr2[1]==arr1[1]) return arr1[0] - arr2[0];
                return arr2[1]-arr1[1];
            }
        });

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

        for(int i=k;i<n;i++){
            pq.add(new int[]{i,nums[i]});
            while(pq.peek()[0]<=i-k){
                pq.poll();
            }
            // System.out.println("i:"+i);
            // printPq(pq);
            res[i-k+1] = pq.peek()[1];
        }

        return res;
    }

    public void printPq(PriorityQueue<int[]> pq){
        for(int[] arr:pq){
            System.out.print(arr[0]+","+arr[1]+" ");
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

方法三：与方法二类似，不过使用的是队列，队列中保存当前或者是未来的下一是时刻可能成为最大值的元素，当取出队头元素时候同样进行判断是否滑动窗口已经移出包含这个数字的窗口，若已经移出，则进行出队操作

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

方法四：补充一个参考代码随想录的思路，通过自定义队列来实现

class Solution {
    class MyQueue{
        Deque<Integer> queue;

        public MyQueue(){
            queue = new ArrayDeque<>();
        }
        public void pop(int val){
            if(!queue.isEmpty()&&val==queue.peek()){
                queue.poll();
            }
        }

        public void push(int val){
            while(!queue.isEmpty()&&val>queue.getLast()){
                queue.removeLast();
            }
            queue.offer(val);
        }

        public int front(){
           return queue.peek();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        MyQueue mq = new MyQueue();
        for(int i=0;i<k;i++){
            mq.push(nums[i]);
        }
        list.add(mq.front());
        for(int i=k;i<n;i++){
            mq.pop(nums[i-k]);
            mq.push(nums[i]);
            list.add(mq.front());
        }
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }

        return res;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#76. 最小覆盖子串

题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

还是运用到了滑动窗口法，可参考滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();
        int lenS = s.length();
        int lenT = t.length();
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for(char c:charT){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0;
        int right = 0;
        int valid = 0;
        int startIndex = -1;
        int minLen = Integer.MAX_VALUE;
        // [left,right)
        while(right<lenS){
            char c = charS[right];
            right++;
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }

            while(valid==need.size()){
                    if(right-left<minLen){
                        minLen = right-left;
                        startIndex = left;
                    }
                    char d = charS[left];
                    if(need.containsKey(d)){
                        if(need.get(d).equals(window.get(d))){
                            valid--;
                        }
                        window.put(d,window.get(d)-1);
                    }
                    left++;
                
            }
        }

        return startIndex==-1?"":s.substring(startIndex,startIndex+minLen);



    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

5.数组

#53. 最大子数组和

题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

方法一：暴力枚举

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
            max = Math.max(max,sum);
            if(sum<0){
                sum=0;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        // dp[i]:下标i,包括i之前的连续最大子数组的和
        dp[0] = nums[0];
        int res = nums[0];
        for(int i=1;i<n;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            res = Math.max(res,dp[i]);
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#56. 合并区间

题目：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
方法一：

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals,new Comparator<int[]>(){
            @Override 
            public int compare(int[] arr1, int[] arr2){
                if(arr1[0]==arr2[0]) return arr1[1]-arr2[1];
                return arr1[0]-arr2[0];
            }
        });

        List<int[]> list = new ArrayList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];

        for(int i=1;i<n;i++){
            // 有交叠
            if(intervals[i][0]<=right){
                left = Math.min(intervals[i][0],left);
                right = Math.max(intervals[i][1],right);
            }
            else{
                list.add(new int[]{left,right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        list.add(new int[]{left,right});
        int[][] res = new int[list.size()][2];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

方法二：在原数组基础上进行合并，跟方法一一样，细节有所不同

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals,new Comparator<int[]>(){
            @Override 
            public int compare(int[] arr1, int[] arr2){
                if(arr1[0]==arr2[0]) return arr1[1]-arr2[1];
                return arr1[0]-arr2[0];
            }
        });

        List<int[]> list = new ArrayList<>();
      
        for(int i=1;i<n;i++){
            // 有交叠
            if(intervals[i][0]<=intervals[i-1][1]){
                intervals[i][0] = Math.min(intervals[i][0],intervals[i-1][0]);
                intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1]);
            }
            else{
                list.add(new int[]{intervals[i-1][0],intervals[i-1][1]});
            }
        }
        list.add(new int[]{intervals[n-1][0],intervals[n-1][1]});
        int[][] res = new int[list.size()][2];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#189. 轮转数组

题目：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

方法一：比较容易想到的思路，将数字依次向后挪动一位，进行count轮次挪动，不过超时了

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int count = k%n;
        // 超时
        while(count-->0){
            int temp = nums[n-1];
            for(int i=n-1;i>=1;i--){
                nums[i] = nums[i-1];
            }
            nums[0] = temp;
        }
    }

    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：反转法

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int count = k%n;
        reverse(nums,0,n-1);
        reverse(nums,0,count-1);
        reverse(nums,count,n-1);
    }

    public void reverse(int[] arr, int start, int end){
        while(start<end){
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法三：借助一个额外数组来存储后count个数，整体后移后再次进行拷贝

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int count = k%n;
        int[] temp = new int[count];
        for(int i=0;i<count;i++){
            temp[i] = nums[i+n-count];
        }
        for(int i=n-1;i>=count;i--){
            nums[i] = nums[i-count];
        }
        for(int i=0;i<count;i++){
            nums[i] = temp[i];
        }
    }

    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法四：借助一个额外的长度与之前相同的数组空间

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for(int i=0;i<n;i++){
            newArr[(i+k)%n] = nums[i%n];
        }
        for(int i=0;i<n;i++){
            nums[i] = newArr[i];
        }     
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12

方法五：参考leetcode[189]:轮转数组

class Solution {
    public void rotate(int[] nums, int k) {
        int size = nums.length;
        k = k % size;
        int count = 0; // 移动过的数字个数，每移动一个就 +1，当移动完 size 个数字后就退出
        // round 表示循环的轮数，第一次从最后一个数字开始，第二次从倒数第二个开始
        for (int round = 0; count != size; ++round) {
            // 当前轮次，开始的数字
            int start = size - 1 - round;
            // 暂存开始的数字，因为它最先被替换
            int tmp = nums[start];
            int cur = start;
            // 将要移动到 cur 上的数字的下标
            int next = (cur - k + size)%size;
            // 当下一个数字的下标是开始时的下标时退出
            while (next != start) {
                nums[cur] = nums[next];
                cur = next;
                next = (cur - k + size)%size;
                ++count;
            }
            // 读取暂存的数字
            nums[cur] = tmp;
            ++count;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#238. 除自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

方法：借助两个数组来分别存储某个数左右的连续数组之积（不包含这个数）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] leftProduct = new int[n];
        int[] rightProduct = new int[n];

        leftProduct[0] = 1;
        for(int i=1;i<n;i++){
            leftProduct[i] = leftProduct[i-1]*nums[i-1];
        }

        rightProduct[n-1] = 1;
        for(int i=n-2;i>=0;i--){
            rightProduct[i] = rightProduct[i+1]*nums[i+1];
        }
 
        for(int i=0;i<n;i++){
            res[i] = leftProduct[i]*rightProduct[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案

方法一：借助哈希表，不过空间复杂度为O(n),
nums中有n个数，未来出现的最小正整数一定在[1，n+1]之间
情况一：[1,n]之间的一个数字未出现
情况二：[1,n]的所有数字都有一个，都出现过一次，则最小正整数为n+1

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        for(int i=1;i<=n+1;i++){
            if(!set.contains(i)){
                return i;
            }
        }
        return -1;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：参考原地哈希（哈希函数为：f(nums[i]) = nums[i] - 1）

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){   
            while(nums[i]>=1&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){
                swap(nums,i,nums[i]-1);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }

    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

持续更新中

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/799661