算法刷题记录-双指针/滑动窗口(LeetCode)

809. Expressive Words

思路

根据题目描述，我们可以知道，如果要将某个单词定义为可扩张（stretchy），需要满足如下两个条件：

所以，我们在实现的时候，可以通过两个指针p1和p2，分别指向s和word，分别统计连续的相同字符数量c1和c2，然后再通过上述的两个条件进行判断，即：如果

(c1 != c2 && c1 < 3) || (c1 < c2 && c1 >= 3)
1

则表示该单词不是可扩张的。

代码

class Solution {
    public int expressiveWords(String s, String[] words) {
        int result = 0;
        char[] sc = s.toCharArray();
        for (String word: words) result += stretchyWord(sc, word.toCharArray()) ? 1 : 0;
        return result;
    }
    private boolean stretchyWord(char[] sc, char[] wc) {
        if (sc.length < wc.length) return false; // word的字符串长度不允许超过s的字符串长度
        int cp, p1 = 0, p2 = p1;
        while ((cp = p1) < sc.length && p2 < wc.length) {
            int c1 = 0, c2 = 0;
            while (p1 < sc.length && sc[p1] == sc[cp]) {
                c1++; p1++; // 在字符串s中，遍历连续的字符sc[cp]的数量
            }
            while (p2 < wc.length && wc[p2] == sc[cp]) {
                c2++; p2++; // 在字符串word中，遍历连续的的字符sc[cp]的数量
            }
            if ((c1 != c2 && c1 < 3) || (c1 < c2 && c1 >= 3)) return false;
        }
        return p1 == sc.length && p2 == wc.length; // 只有sc和wc都被遍历完毕，才返回true
    }
}

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

823. Binary Trees With Factors

思路

代码

class Solution {
    static final long MOD = (long) 1e9 + 7;
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        long[] ans=new long [arr.length];
        ans[0]=1;
        for (int i=1;i<arr.length;i++){
            ans[i]=1;
            int left=0;
            int right=i-1;
            while (left<=right){
                while (left<=right){
                    long prod= (long) arr[left] *arr[right];
                    if (prod==arr[i]){
                        break;
                    }
                    else if (prod<arr[i]){
                        left++;
                    }
                    else{
                        right--;
                    }
                }
                if (left>right){
                    break;
                }
                if (left==right){
                    ans[i]+=ans[left]*ans[left];
                }
                else{
                    ans[i]+=ans[left]*ans[right]*2;
                }
                left++;
                right--;
            }
            ans[i]%=MOD;
        }
        long final_ans=0;
        for (long val:ans){
            final_ans=final_ans+val;
            final_ans%=MOD;
        }
        return (int)final_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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

*825. Friends Of Appropriate Ages

思路 桶+前缀和+双指针

利用本题数据范围 $1<=ages[i]<=120$，值域较小，我们可以通过「桶排序」的方式进行排序优化。

假设对 ages 进行桶排后得到的数组为 nums，其中 $cnt=nums[i]$ 的含义为在 ages 中年龄为i 的人有 cnt 个。

同时，我们发现在解法一中，我们枚举 $y=ages[k]$，并使用 i 和j 两个指针寻找连续的 x段的过程，x 会始终停留于值与 $y=ages[k]$ 相等的最小下标处，而对于桶排数组而言，当前位置就是最小合法x 值（与y 相等），因此我们只需要找到最大合法 x 值的位置即可（对应解法一的 jjj 位置）。

同样，最大 x 的位置在桶排数组中也是随着 y 的增大（右移）逐渐增大（右移）。

剩下的问题在于，如何统计桶排数组中连续段下标的和为多少（有多少个合法 xxx 值），这可以直接在桶排数组应用前缀和即可。

代码

class Solution {
public:
    int[] prefix_sum=new int[130];
    public int numFriendRequests(int[] ages) {
        int ans=0;
        for (int i:ages) {
            prefix_sum[i]++;
        }
        for (int i = 1; i < 130; i++) {
            prefix_sum[i]+=prefix_sum[i-1];
        }
        for (int x = 1,y=1; y <130 ; y++) {
            int a = prefix_sum[y] - prefix_sum[y - 1]; // 有 a 个 x
            if (a==0){
                continue;
            }
            if (x<y){
                x=y;
            }
            while (x<130&&check(x,y)){
                x++;
            }
            int b=prefix_sum[x-1]-prefix_sum[y-1]-1;
            if (b>0){
                ans+=a*b;
            }
        }
        return ans;
    }

    private boolean check(int x, int y) {
        if (y <= 0.5 * x + 7) return false;
        return 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
28
29
30
31
32
33
34
35

*828. Count Unique Characters of All Substrings of a Given String

思路 贡献法+双指针

请看下图，我们以s=“ABCD”为例，首先，可以将其拆分为10个子串（以“A”为基准的4个子串；以“B”为基准的3个子串；以“C”为基准的2个子串；以“D”为基准的1个子串；），那么由于s字符串中的字符都是彼此不重复的，所以，总结果其实就是“A”、“B”、“C”、“D”这个四个字符在所有10个子串中出现的次数之和，即：A出现4次 + B出现6次 + C出现6次 + D出现4次 = 20。

通过上面的例子，我们将问题转换为某个字符在子串中出现的个数问题了。那么，针对这个问题，其实有3种情况：

情况1：字符是“头元素”，那么出现次数可以通过：数组长度 - 元素下标位置 来计算出来。
情况2：字符是“尾元素”，那么出现次数可以通过：元素下标位置 - (-1) 来计算出来。
情况3：字符是“中间元素”，那么出现次数可以通过：(元素下标位置 - (-1)) * (数组长度 - 元素下标位置) 来计算出来。

那么前面我们是针对于字符串中字符不重复的情况来看的，下面我们再来看一下有重复字符的情况。其实，针对于这种情况，就产生了区间的概念。因为我们上面进行统计的时候，都是针对于某一区间内这个元素是唯一的，所以，如果发生了重复字符，我们就需要将其拆分为多个区间。以下图s="ABCB"为例，当我们要统计元素“B”的时候，由于发生了重复的情况，所以，我们要将其拆分为：
当B的下标=1的时候，它唯一的区间是[0,2] 当B的下标=3的时候，它唯一的区间是[2,3]
那么，由于产生了区间的概念，我们也随之创建两个指针，分别是head和tail，head指向的某区间开始位置的前一个位置；tail指向的是某区间结束为止的后一个位置。那么计算公式最终就是：(某元素下标位置 - head) * (tail - 某元素下标位置)。

我们得出了计算公式之后，就可以针对给出的字符串s中的每个字符进行遍历，在哈希表中记录一下每个元素的所在位置，key=字符，value=该字符出现的位置集合。具体实现，请参照：代码1-哈希表采用哈希表方式实现。如果需要提升执行效率，我们也可以采用数组来记录每个元素的所在位置，26个字母对应数组的坐标，然后一个数组是用来针对某个元素出现多次进行统计

解题思路我们就说完了。下面我们以s=“LEETCODE”为例，看一下具体的计算过程。由于下图中的计算细节已经在图中写出来了，所以这里的文字部分就不去赘述了。具体的计算过程，请参见下图。

代码1-哈希表

    public int uniqueLetterString(String s) {
        HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), new ArrayList<>());
            }
            map.get(s.charAt(i)).add(i);
        }
        int ans = 0;
        for (var pair : map.entrySet()) {
            int head = -1;
            int tail = -1;
            var items = pair.getValue();
            for (int i = 0; i < items.size(); i++) {
                tail = i < (items.size() - 1) ? items.get(i + 1) : s.length();
                ans += (items.get(i) - head) * (tail - items.get(i));
                head = items.get(i);
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

849. Maximize Distance to Closest Person

思路(双指针+贪心)

我们考虑前一个1出现的位置prev,一直向右遍历的位置i每当seats[i]为1时，i与prev相减的值即为距离，求所有可能的距离的最大值即可。注意，在实现代码中，考虑的略复杂了一些 其中while（seat[i]==0）的部分可优化为prev=-1。但是，我们一定需要当遍历结束后强制判断一次，因为可能出现类似$[1,0,0,0]$此类序列。

代码

    int maxDistToClosest(vector<int>& seats) {
        int prev;
        int i=0;
        while (seats[i]==0){
            i++;
        }
        prev=i;
        int max_length=i;
        for (i++; i < seats.size(); ++i) {
            if (seats[i]==0){
                continue;
            }
            int length=i-prev-1;
            max_length=max((int)ceil((double)length/2),max_length) ;
            prev=i;
        }
        int length=seats.size()-prev-1;
        if (length>max_length){
            max_length=length;
        }
        return max_length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

881. Boats to Save People

思路

首先对数组进行排序，设置两个指针left，right。令每次救生艇乘坐的人重量最大。若left+right>limit，则说明位于right位置的人需要一个独立的救生艇。当左右指针相遇时，说明剩下需要一个独立的救生艇，再次＋1。

代码

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int ans=0;
        Arrays.sort(people);
        int left=0;
        int right=people.length-1;
        while (left<=right){
            while (right>left&&people[left]+people[right]>limit){
                right--;
                ans++;
            }
            if (left==right){
                ans++;
                break;
            }
            ans++;
            left++;
            right--;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

904. Fruit Into Baskets

思路 双指针+HashMap

构建一个HashMap,令left指针标注序列开始点，right指针标注序列结束点。
每次将一个新水果fruits[right]加入序列，若map的长度大于2，则右移left指针并对map内的fruits[left]进行-1操作，若map[fruit[left]]为0，则表示已完全移除，map长度减一。从此往复，统计map内key的value和的最大值。

代码

    public int totalFruit(int[] fruits) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        int ans=0;
        while (right < fruits.length) {
            map.merge(fruits[right], 1, Integer::sum);
            while (map.size() > 2) {
                map.merge(fruits[left], -1, Integer::sum);
                if (map.get(fruits[left])==0){
                    map.remove(fruits[left]);
                }
                left++;
            }
            int curr_ans=0;
            for (var key:map.keySet()){
                curr_ans+=map.get(key);
            }
            ans=Math.max(ans,curr_ans);
            right++;
        }
        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

*995. Minimum Number of K Consecutive Bit Flips

思路

位置 i 现在的状态，和它被前面 $K-1$个元素翻转的次数（奇偶性）有关。

我们使用队列模拟滑动窗口，该滑动窗口的含义是前面 $K-1$ 个元素中，以哪些位置起始的 子区间 进行了翻转。该滑动窗口从左向右滑动，如果当前位置 iii 需要翻转，则把该位置存储到队列中。遍历到新位置 $(j<i+K)$ 时，队列中元素的个数代表了 i 被前面$K-1$ 个元素翻转的次数。

• 当 A[i] 为 0，如果 i 位置被翻转了偶数次，那么翻转后仍是 0，当前元素需要翻转；
• 当 A[i] 为 1，如果 i 位置被翻转了奇数次，那么翻转后变成 0，当前元素需要翻转。
  综合上面两点，我们得到一个结论，如果 $len(que)$ 时，当前元素需要翻转。

当 $i+K>N$ 时，说明需要翻转大小为 K 的子区间，但是后面剩余的元素不到 K 个了，所以返回 -1。

代码

    public int minKBitFlips(int[] nums, int k) {
        Deque<Integer> list=new LinkedList<>();
        int res=0;
        for (int i = 0; i < nums.length; i++) {
            if (!list.isEmpty()&&i>list.peekFirst()+k-1){
                list.removeFirst();
            }
            if ((nums[i]+list.size())%2==1){
                continue;
            }
            if (i+k> nums.length){
                return -1;
            }
            list.offerLast(i);
            res++;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

986. Interval List Intersections

思路

记录两个数组的当前遍历坐标first_idx、second_idx。每次判断是否存在重叠以及重叠区域

   int start = max(firstList[first_idx][0], secondList[second_idx][0]);
   int end = min(firstList[first_idx][1], secondList[second_idx][1]);
1
2

直到有任一数组遍历完毕。

代码

    vector<vector<int>> intervalIntersection(vector<vector<int>> &firstList, vector<vector<int>> &secondList) {
        vector<vector<int>> res;
        int length1 = (int) firstList.size();
        int length2 = (int) secondList.size();
        int first_idx = 0;
        int second_idx = 0;
        while (first_idx < length1 && second_idx < length2) {
            while (first_idx < length1&&second_idx<length2 && (secondList[second_idx][0] > firstList[first_idx][1]||firstList[first_idx][0] > secondList[second_idx][1])){
                while (second_idx < length2 && firstList[first_idx][0] > secondList[second_idx][1]) {
                    second_idx++;
                }
                while (first_idx < length1&&second_idx<length2 && secondList[second_idx][0] > firstList[first_idx][1]) {
                    first_idx++;
                }
            }
            if (first_idx >= length1 || second_idx >= length2) {
                return res;
            }
            int start = max(firstList[first_idx][0], secondList[second_idx][0]);
            int end = min(firstList[first_idx][1], secondList[second_idx][1]);
            res.push_back({start, end});
            if (firstList[first_idx][1] > secondList[second_idx][1]) {
                second_idx++;
            } else {
                first_idx++;
            }
        }
        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

1029. Two City Scheduling

思路

求出每个人前往两个城市的cost之差，对其排序，两端分别倾向于两个城市。

代码

    public int twoCitySchedCost(int[][] costs) {
        int[][] diff=new int[costs.length][2];
        for (int i = 0; i < costs.length; i++) {
            diff[i][0]=costs[i][0]-costs[i][1];
            diff[i][1]=i;
        }
        int target=costs.length/2;
        int left_cnt=0;
        int right_cnt=0;
        int ans=0;
        Arrays.sort(diff,(Comparator.comparingInt(o -> o[0])));
        int left_idx=0;
        int right_idx=costs.length-1;
        while (left_cnt<target&&right_cnt<target){
            if(Math.abs(diff[left_idx][0])>Math.abs(diff[right_idx][0])){
                ans+=costs[diff[left_idx][1]][0];
                left_cnt++;
                left_idx++;
            }
            else{
                ans+=costs[diff[right_idx][1]][1];
                right_cnt++;
                right_idx--;
            }
        }
        if (left_cnt<target){
            for (int i = left_cnt; i < target; i++) {
                ans+=costs[diff[left_idx][1]][0];
                left_cnt++;
                left_idx++;
            }
        }
        if (right_cnt<target){
            for (int i = right_cnt; i < target; i++) {
                ans+=costs[diff[right_idx][1]][1];
                right_cnt++;
                right_idx--;
            }
        }
        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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2841. Maximum Sum of Almost Unique Subarray

思路 滑动窗口

用滑动窗口枚举长为 k 的子数组，用哈希表记录子数组中各元素出现的次数，以维护当前子数组中不同元素的个数

代码

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        HashMap<Integer,Integer>map=new HashMap<>();
        int left=0;
        int right=k;
        long ans=0;
        long curr_sum=0;
        for (int i=0;i<k;i++){
            curr_sum+=nums.get(i);
            map.merge(nums.get(i),1,Integer::sum);
        }
        if (map.size()>=m){
            ans=Math.max(curr_sum,ans);
        }
        while (right<nums.size()){
            curr_sum+= nums.get(right);
            curr_sum-= nums.get(left);
            map.merge(nums.get(right),1,Integer::sum);
            map.merge(nums.get(left),-1,Integer::sum);
            if(map.get(nums.get(left))==0){
                map.remove(nums.get(left));
            }
            if (map.size()>=m){
                ans=Math.max(curr_sum,ans);
            }
            left++;
            right++;

        }
        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
27
28
29
30
31
32
33

2844. Minimum Operations to Make a Special Number

思路 滑动窗口

要想被25整除，末尾数字只能是00、25、50、75 。只要从最后一个数字遍历即可，若最后一位数字为5，则向前寻找2或者7、否则向前寻找0或者5。

代码

class Solution {
    public int minimumOperations(String _num) {
        char[] num=_num.toCharArray();
        int ans=120;
        boolean containsZero=false;
        int end=num.length-1;
        while (end>0){
            if (num[end]=='0'||num[end]=='5'){
                int prev=end-1;
                if (num[end]=='0'){
                    containsZero=true;
                    while (prev>=0&&(num[prev]!='5'&&num[prev]!='0')){
                        prev--;
                    }
                }
                else {
                    while (prev>=0&&(num[prev]!='2'&&num[prev]!='7')){
                        prev--;
                    }
                }
                if (prev>=0){
                    ans=Math.min(ans,end-prev-2+num.length-end);
                }
            }
            end--;
        }
        if (ans==120){
            return containsZero? num.length-1 :num.length ;
        }
        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
27
28
29
30
31
32