六月

3 连续数组🎈

image-20210603212532955

大佬思路

算法步骤：

创建一个哈希表，用 key 来储存 cur 值, value 来储存当前 index。

假设我们碰到 0 就将 cur 减一, 碰到 1 则 加一。
如果我们能在哈希表中找到当前的 cur 值, 则取出对应的 pos, 在看当前的 index - pos 是否比 ans 大, 取其中的最优解。

核心：由于以上碰1加一，碰0减一的操作，当0与1数量一致时(连续数组), 其连续数组的和为零。因此我们知道数组前面的 cur 值是什么，在到达该连续数组尾部时就不会变。因此我们只需要检查哈希表中是否存在其相同的 cur 值即可！(多读几遍)

作者：Xiaohu9527
链接：https://leetcode-cn.com/problems/contiguous-array/solution/dong-tu-yan-shi-qian-zhui-he-si-xiang-by-z2no/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

image-20210603214006741 
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
class Solution {
    public int findMaxLength(int[] nums) {
        int maxLength = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int counter = 0;
        map.put(counter, -1);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == 1) {
                counter++;
            } else {
                counter--;
            }
            if (map.containsKey(counter)) {
                int prevIndex = map.get(counter);
                maxLength = Math.max(maxLength, i - prevIndex);
            } else {
                map.put(counter, i);
            }
        }
        return maxLength;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/contiguous-array/solution/lian-xu-shu-zu-by-leetcode-solution-mvnm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

​

五月

1. 无重复字符的最长子串

image-20210504171538656

我的思路

偷懒直接看了评论…

大佬的思路

滑动窗口！！！

滑动窗口具体内容就不多说了，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 滑动窗口
        if (s.length() == 0) return 0;
        int l = 0, r = 0;
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (r < s.length()) {
            if (map.containsKey(s.charAt(r))) {
                l = Math.max(l, map.get(s.charAt(r)) + 1);
            }
            map.put(s.charAt(r), r);
            max = Math.max(max, r - l + 1);
            r++;
        }
        return max;
    }
}

2. 子数组异或查询

image-20210512172613337

我的思路

直接两层循环搞定

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int[] res = new int[queries.length];
        for (int k = 0; k < queries.length; k++) {
            int tmp = 0;
            for (int i = queries[k][0]; i <= queries[k][1]; i++) {
                tmp ^= arr[i];
            }
            res[k] = tmp;
        }
        return res;
    }
}

大佬的思路

题太简单，都差不多

3. 二叉树的堂兄弟节点

image-20210517213529650

我的思路

层序遍历二叉树，如果某一层的节点满足条件且不是相同父节点，则输出 true

有想法但是没有实现

大佬的思路

参考：FāKăL1

深度遍历，记录 x、y 两节点的深度与父节点，最后做判断即可

代码简单易懂

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
class Solution {
    
    // 保存 x、y 的深度与父节点
    int xpar, xdep, ypar, ydep;

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root.left, 1, x, y, root.val);
        dfs(root.right, 1, x, y, root.val);
        return (xpar != ypar) && (xdep == ydep);
    }
    
    public void dfs(TreeNode node, int dep, int x, int y, int par) {
        if (node == null) {
            return;
        }
        if (node.val == x) {
            xpar = par;
            xdep = dep;
        } else if (node.val == y) {
            ypar = par;
            ydep = dep;
        } else {
            dfs(node.left, dep+1, x, y, node.val);
            dfs(node.right, dep+1, x, y, node.val);
        }
    }
}

4. 前K个高频单词

image-20210520193745365

我的思路

遍历 words 数组，将每个 word 及其出现的频率加入到一个 map 中，最后对 map 进行排序，输出前 k 个到 List 中进行返回。

思路没问题，但是在对 map 排序的时候出现了问题：需要同时对 key 和 value 进行排序

大佬的思路

  • map.entrySet :
image-20210520194554863 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }
        List<String> rec = new ArrayList<String>();
        // Entry 可以建立起 key 与 value 一一对应的关系
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
            rec.add(entry.getKey());
        }
        Collections.sort(rec, new Comparator<String>() {
            public int compare(String word1, String word2) {
                // 两单词出现频率相同：按字母顺序排
                // 两单词出现频率不同：按单词频率排
                return cnt.get(word1) == cnt.get(word2) ? 
                    word1.compareTo(word2) : cnt.get(word2) - cnt.get(word1);
            }
        });
        return rec.subList(0, k);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/top-k-frequent-words/solution/qian-kge-gao-pin-dan-ci-by-leetcode-solu-3qk0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

四月

1 递增顺序搜索树

image-20210425210936999

我的思路

先用一个数组保存树的中序序列，再通过中序序列根据题目要求构建新的树

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public TreeNode increasingBST(TreeNode root) {
        ArrayList<Integer> vals = new ArrayList<>();
        inOrder(root, vals);
        TreeNode head = new TreeNode(-1);
        TreeNode cur = head;
        for (int value: vals) {
            cur.right = new TreeNode(value);
            cur = cur.right;
        }
        return head.right;
    }

    public void inOrder(TreeNode root, List<Integer> vals) {
        if (root == null) return;
        inOrder(root.left, vals);
        vals.add(root.val);
        inOrder(root.right, vals);
    }
}

大佬的思路

在中序遍历的过程中，修改树的左右子节点，使左子树为空，右子树为中序中序遍历的下一个节点

image-20210425211503346 image-20210425211522483 
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
class Solution {
    private TreeNode resNode;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyNode = new TreeNode(-1);
        resNode = dummyNode;
        inorder(root);
        return dummyNode.right;
    }

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);

        // 在中序遍历的过程中修改节点指向
        resNode.right = node;
        node.left = null;
        resNode = node;

        inorder(node.right);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/increasing-order-search-tree/solution/di-zeng-shun-xu-cha-zhao-shu-by-leetcode-dfrr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2. 在 D 天内送达包裹的能力

image-20210427200151926

我的思路

没有一点点挣扎

大佬的思路

采用二分查找

根据题意，结果一定落在 [max(weights), sum(weights)] 这个区间上

  • 左端点：船的运载能力不能小于单个包裹的重量

  • 右端点：一艘船一次性直接把所有货物拉走

在左右端点之间进行二分查找

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
class Solution {
    public int shipWithinDays(int[] weights, int D) {
        // 确定二分查找左右边界
        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = (left + right) / 2;
            // need 为需要运送的天数
            // cur 为当前这一天已经运送的包裹重量之和
            int need = 1, cur = 0;
            for (int weight : weights) {
                if (cur + weight > mid) {
                    ++need;
                    cur = 0;
                }
                cur += weight;
            }
            if (need <= D) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution/zai-d-tian-nei-song-da-bao-guo-de-neng-l-ntml/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3. 二叉搜索树的范围和

image-20210427191433608

我的思路

困难题唯唯诺诺，简单题重拳出击

遍历二叉树，遍历过程中判断每个节点的值是否在 low 与 high 之间，满足条件就把 sum 加上该值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int sum = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        inOrder(root, low, high);
        return sum;
    }

    public void inOrder(TreeNode root, int low, int high) {
        if (root == null) return;
        inOrder(root.left, low, high);
        if (root.val >= low && root.val <= high) sum += root.val;
        inOrder(root.right, low, high);
    }
}

但是考虑到题目中所给出的树是二叉搜索树，这一条件并没有被我用上，所以肯定可以通过这一条件对算法进行改进

大佬的思路

直接进行递归，不借用辅助中序遍历的函数

有用到二叉搜索树的性质

效率更高且代码更加优雅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val >= low && root.val <= high) {
            return root.val + 
                   rangeSumBST(root.left, low, high) + 
                   rangeSumBST(root.right, low, high);
        } else if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        } else {
            return rangeSumBST(root.left, low, high);
        }
    }
}

4. 两数相加

image-20210429203603745

我的思路

  1. 同时遍历两个链表，将对应位相加得 val，val % 10 存入新链表对应节点中，val / 10 作为进位与下一位相加

    思路没问题，但是最后的一位如果出现进位的的问题一直没能解决

  2. 先遍历链表得到两个整数，将两个整数相加后再转换为链表

    被测试用例教做人

    image-20210429204608148

大佬的思路

思路大致与我的思路一相同，但是在循环条件中加了一条判断进位是否为0的条件，完美解决了我的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(0);
        ListNode head = cur;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int num1 = l1 != null ? l1.val : 0; 
            int num2 = l2 != null ? l2.val : 0;
            int sum = num1 + num2 + carry;
            carry = sum / 10;

            ListNode sumNode = new ListNode(sum % 10);
            cur.next = sumNode;
            cur = sumNode;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return head.next;
    }
}

二月

1 公平的糖果棒交换

image-20210201222030150

自己家的解法

求出两个数组中个数的总和 sum，取其一半就是交换后各自数组中数的总和 val

原数组中数的总和 sumA、sumB与 val只差就是需要交换的数量，分别找出每个数组中的这个差值的位置

接下来就遇到问题卡住辽

别人家的解法

  • 哈希表
image-20210201224115760 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();
        int delta = (sumA - sumB) / 2;
        Set<Integer> rec = new HashSet<Integer>();
        for(int num: A) {
            rec.add(num);
        }
        int[] ans = new int[2];
        for(int y: B) {
            int x = y + delta;
            if(rec.contains(x)) {
                ans[0] = x;
                ans[1] = y;
                break;
            }
        }
       return ans;
    }
}

2 替换后的最长重复字符

image-20210203191952563

自己家的解法

None

别人家的解法

  • 本题是比较典型的滑动窗口问题
  • 这类问题一般通过一个滑动窗口就能在 O(N) 的时间复杂度下求解

本题可以先退化成考虑 K=0 的情况，此时题目就变成了求解字符串中最长连续子串长度问题了。
我们先可以通过这个特例先了解一下滑动窗口的求解过程

滑动窗口求解最长连续子串长度

上图的求解过程展示中，窗口从左至右不断扩张/滑动，当窗口触达字符串末尾字符时，运算结束，窗口的宽度为最终结果。初始窗口的宽度为 1，我们不断的通过向当前窗口覆盖的子串后面追加一个字符看是否能满足我们的要求，如果满足窗口扩张，如果不满足，窗口向右滑动。

当 K>0K>0 时，子串的条件变成了允许我们变换子串中的 KK 个字符使其变成一个连续子串

那么这个题的关键点就是我们如何判断一个字符串改变 KK 个字符，能够变成一个连续串

如果当前字符串中的出现次数最多的字母个数 +K+K 大于串长度，那么这个串就是满足条件的

我们维护一个数组 int[26] 来存储当前窗口中各个字母的出现次数，leftleft 表示窗口的左边界，rightright 表示窗口右边界

窗口扩张：left 不变，right++
窗口滑动：left++，right++
historyCharMax 保存滑动窗口内相同字母出现次数的 历史 最大值，通过判断窗口宽度 (right - left + 1) 是否大于 historyCharMax + k 来决定窗口是否做滑动，否则窗口就扩张。

作者：migoo
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/tong-guo-ci-ti-liao-jie-yi-xia-shi-yao-shi-hua-don/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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 {
    public int characterReplacement(String s, int k) {
        // 建立字符表，记录每个字符出现的次数
        int[] num = new int[26];
        int n = s.length();
        // 记录字符串中出现次数最多的字母出现的次数
        int historyCharMax = 0;
        // 双指针，记录滑动窗口的左右边界
        int left = 0, right = 0;
        while (right < n) {
            // 将新加入的字符加入字符表中
            num[s.charAt(right) - 'A']++;
            // 看新加入的字符是否会影响出现最多的字符
            maxn = Math.max(maxn, num[s.charAt(right) - 'A']);
            // 如果 滑动窗口宽度 大于 窗口内出现次数最多的字符与k之和，则窗口左边界移动
            // 既将其他字符中的k个字符全部进行替换以后窗口大小最长字串长度并不会增加
            if (right - left + 1 > historyCharMax + k) {
                num[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
        // 返回滑动窗口的大小
        return right - left;
    }
}

3 滑动窗口中位数

image-20210203233343603

自己家的解法

最朴素的暴力求法，不出所料了的超时了…

别人家的解法

直接挂链接吧：https://leetcode-cn.com/problems/sliding-window-median/solution/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6/

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        DualHeap dh = new DualHeap(k);
        for (int i = 0; i < k; ++i) {
            dh.insert(nums[i]);
        }
        double[] ans = new double[nums.length - k + 1];
        ans[0] = dh.getMedian();
        for (int i = k; i < nums.length; ++i) {
            dh.insert(nums[i]);
            dh.erase(nums[i - k]);
            ans[i - k + 1] = dh.getMedian();
        }
        return ans;
    }
}

class DualHeap {
    // 大根堆，维护较小的一半元素
    private PriorityQueue<Integer> small;
    // 小根堆，维护较大的一半元素
    private PriorityQueue<Integer> large;
    // 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
    private Map<Integer, Integer> delayed;

    private int k;
    // small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素
    private int smallSize, largeSize;

    public DualHeap(int k) {
        this.small = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2.compareTo(num1);
            }
        });
        this.large = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num1.compareTo(num2);
            }
        });
        this.delayed = new HashMap<Integer, Integer>();
        this.k = k;
        this.smallSize = 0;
        this.largeSize = 0;
    }

    public double getMedian() {
        return (k & 1) == 1 ? small.peek() : ((double) small.peek() + large.peek()) / 2;
    }

    public void insert(int num) {
        if (small.isEmpty() || num <= small.peek()) {
            small.offer(num);
            ++smallSize;
        } else {
            large.offer(num);
            ++largeSize;
        }
        makeBalance();
    }

    public void erase(int num) {
        delayed.put(num, delayed.getOrDefault(num, 0) + 1);
        if (num <= small.peek()) {
            --smallSize;
            if (num == small.peek()) {
                prune(small);
            }
        } else {
            --largeSize;
            if (num == large.peek()) {
                prune(large);
            }
        }
        makeBalance();
    }

    // 不断地弹出 heap 的堆顶元素，并且更新哈希表
    private void prune(PriorityQueue<Integer> heap) {
        while (!heap.isEmpty()) {
            int num = heap.peek();
            if (delayed.containsKey(num)) {
                delayed.put(num, delayed.get(num) - 1);
                if (delayed.get(num) == 0) {
                    delayed.remove(num);
                }
                heap.poll();
            } else {
                break;
            }
        }
    }

    // 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
    private void makeBalance() {
        if (smallSize > largeSize + 1) {
            // small 比 large 元素多 2 个
            large.offer(small.poll());
            --smallSize;
            ++largeSize;
            // small 堆顶元素被移除，需要进行 prune
            prune(small);
        } else if (smallSize < largeSize) {
            // large 比 small 元素多 1 个
            small.offer(large.poll());
            ++smallSize;
            --largeSize;
            // large 堆顶元素被移除，需要进行 prune
            prune(large);
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sliding-window-median/solution/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

4 子数组最大平均数 I

image-20210204202536643

自己家解法

楞头暴力求也没多想…

别人家解法

  • 先求出前 k 个数的和 sum
  • 接下来开始滑动窗口，每次滑动后 sum 的值变为 sum 加上新进入窗口的值，再减去从窗口中滑出的值
  • 使用变量 maxSum 记录每次滑动后 sum 的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i = k; i < nums.length; i++) {
            sum = sum + nums[i] - nums[i - k];
            maxSum = Math.max(sum, maxSum);
        }
        return 1.0 * maxSum / k;
    }
}

tips：

  • double 类型的变量进行运算会较慢，所以可以先求 int类型的和，最后求平均时再转为 double

13 找到所有数组中消失的数字

image-20210213213522841

自己家的解法

  • 一个思路

    既然要求没有出现的数字，那就把出现过的数字加入到一个 Set 中，从 1 到 n 开始遍历，不在 Set 中的数就是在数组中没有出现过的数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        ArrayList<Integer> list = new ArrayList<>();
        for(int num: nums) {
            set.add(num);
        }
        for(int i = 1; i <= nums.length; i++) {
            if(!set.contains(i)) list.add(i);
        }
        return list;
    }
}

  • 另一个思路

    从1 - n求和得到 sum1，再将数组中的数求和得到 sum2

    sum1 - sum2 就等于 没有出现的数减去重复出现的数

    具体就不知道怎么实现了…

别人家的解法

  1. 将数组元素对应为索引的位置 加n （置为负数）
  2. 遍历变化后得数组，若数组元素 小于n值（为负值），说明数组下标不存在，既为消失的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        ArrayList<Integer> res = new ArrayList<>();
        int n = nums.length;
        for(int num: nums) {
            nums[(num - 1) % n] += n;
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] <= n) res.add(i + 1);
        }
        return res;
    }
}

16 数组拆分 I

image-20210216231135883

自己家的解法

将所给数组排序，奇数位置的数之和就是题目中要求的最大总和

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

别人家的解法

跟我的想法差不多嘛

image-20210216231352461

19 最大连续1的个数 III

image-20210219230908647

别人家思路

问题可以转化为 找出一个最长字串，其中最多允许有 k 个 0

最大连续子区间问题，可以使用 滑动窗口 解决

  • 两个指针分别指向窗口的两端：left、right

  • right 主动右移，若窗口内 0 的个数大于 k，考虑左移 left

  • 一直左移 left，直到窗口内 0 的个数小于 k

  • 统计每次移动后窗口的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 考虑到之后考研算法题大多需要用c或c++实现，故之后的代码都选择用c++实现
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int res = 0, zeros = 0, left = 0;
        for (int right = 0; right < A.size(); right++) {
            if (A[right] == 0) zeros++;
            while (zeros > K) {
                if(A[left++] == 0) --zeros;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

20 比特位计数

image-20210303212948035

自己家解法

没思路直接看了官方解

别人家解法

以下思路及代码均取自LeetCode官方解

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

  • 暴力法

    从 0 到 num 计算每个数二进制的 【一比特数】

    对于任意整数 x，x = x & (x - 1) 可以将二进制下 x 的最后一位 1 置为 0，重复操作，操作次数既为 x 的【一比特数】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    vector<int> countBits(int num) {
        vector<int> bits(num + 1);
        for (int i = 0; i <= num; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }
};

  • 动态规划——最高有效位

    image-20210303214100186

    我们规定 2 的整数次方为最高有效位，最高有效位之间的数与上一最高有效位之间的数存在一定关系，具体看原回答

    其实就是偷懒

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        int highBit = 0;
        for (int i = 1; i <= num; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
}
  • 动态规划——最低有效位
    • 如果 x 是偶数， 那 countBits(x) == countBits(x / 2)
    • 如果 x 是奇数，那countBits(x) == countBits(x - 1) + 1
1
2
3
4
5
6
7
8
9
class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}