1. Toy模板网首页
  2. > Toy博客

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

7月前 作者：ほしのした 分类：Toy博客 阅读(28) 违法举报

这篇具有很好参考价值的文章主要介绍了算法刷题记录-双指针/滑动窗口(LeetCode)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

809. Expressive Words

思路

根据题目描述，我们可以知道，如果要将某个单词定义为可扩张（stretchy），需要满足如下两个条件：
算法刷题记录-双指针/滑动窗口(LeetCode),算法,leetcode,职场和发展
所以，我们在实现的时候，可以通过两个指针p1和p2，分别指向s和word，分别统计连续的相同字符数量c1和c2，然后再通过上述的两个条件进行判断，即：如果

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

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

代码

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
    }
}

823. Binary Trees With Factors

思路

算法刷题记录-双指针/滑动窗口(LeetCode),算法,leetcode,职场和发展

代码

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;
    }
}

*825. Friends Of Appropriate Ages

思路 桶+前缀和+双指针

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

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

同时，我们发现在解法一中，我们枚举 y = a g e s [ k ] y=ages[k] y=ages[k]，并使用 i 和j 两个指针寻找连续的 x段的过程，x 会始终停留于值与 y = a g e s [ k ] y=ages[k] 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;
    }
};

*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。
算法刷题记录-双指针/滑动窗口(LeetCode),算法,leetcode,职场和发展
通过上面的例子，我们将问题转换为某个字符在子串中出现的个数问题了。那么，针对这个问题，其实有3种情况：

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

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

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

解题思路我们就说完了。下面我们以s=“LEETCODE”为例，看一下具体的计算过程。由于下图中的计算细节已经在图中写出来了，所以这里的文字部分就不去赘述了。具体的计算过程，请参见下图。
算法刷题记录-双指针/滑动窗口(LeetCode),算法,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;
    }

849. Maximize Distance to Closest Person

思路(双指针+贪心)

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

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;
    }
}

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;
    }

*995. Minimum Number of K Consecutive Bit Flips

思路

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

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

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

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

算法刷题记录-双指针/滑动窗口(LeetCode),算法,leetcode,职场和发展

代码

    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;
    }

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]);

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

代码

    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;
    }

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;
    }

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;
    }

}

2844. Minimum Operations to Make a Special Number

思路 滑动窗口

要想被25整除，末尾数字只能是00、25、50、75 。只要从最后一个数字遍历即可，若最后一位数字为5，则向前寻找2或者7、否则向前寻找0或者5。文章来源地址https://www.toymoban.com/news/detail-700717.html

代码

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;
    }
}

到了这里，关于算法刷题记录-双指针/滑动窗口(LeetCode)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 算法刷题营【Day2】:: 双指针算法应用：滑动窗口 ：209. 长度最小的子数组

    算法刷题营【Day2】:: 双指针算法应用：滑动窗口 ：209. 长度最小的子数组

    本内容是笔者结合《代码随想录》总结所得，记录学习过程，分享知识！ 目录： 1. 开篇例题：209. 长度最小的子数组 2. 题解参考 - - 2.1 方法一：暴力法 - - 2.2 方法二：滑动窗口 3. 方法思路点拨：滑动窗口 - - 3.1 直白解释 - - 3.2 本题思路点拨 4. 相关题集 1. 开篇例题：209. 长度

    2024年02月04日
    浏览(30)

  • LeetCode算法小抄--滑动窗口算法

    ⚠申明： 未经许可，禁止以任何形式转载，若要引用，请标注链接地址。 全文共计6244字，阅读大概需要3分钟 🌈更多学习内容， 欢迎👏关注👀文末我的个人微信公众号：不懂开发的程序猿 个人网站：https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(28)
  • 【LeetCode 算法专题突破】滑动窗口（⭐）

    【LeetCode 算法专题突破】滑动窗口（⭐）

    学完了双指针算法，滑动窗口那肯定是逃不掉了，我个人感觉他俩就不分家，不把滑动窗口的题目好好刷上一刷我都难受 先来一道经典的滑动窗口试试水 题目链接：209. 长度最小的子数组 其实滑动窗口题目的解法都大同小异，我们基本上写几道题目，就能很好的掌握这个算

    2024年02月07日
    浏览(37)
  • 【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

    【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

    个人主页：兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助 🍓希望我们一起努力、成长，共同进步。

    2024年02月08日
    浏览(28)

  • python - leetcode - 424. 替换后的最长重复字符【经典题解 - 贪心滑动窗口算法】

    描述： 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后，返回包含相同字母的最长子字符串的长度。 示例 1： 示例 2： 提示： 1 = s.length = 105 s 仅由大写英文字母组成 0 =

    2024年02月16日
    浏览(31)
  • 算法刷题记录-树(LeetCode)

    算法刷题记录-树(LeetCode)

    思路(DFS 中序遍历) 考虑中序遍历的性质即可 代码 思路(DFS) 对于一个节点是否删除，有如下几种情况: 思路（DFS） 首先，需要通过dfs算法找到从原点到目标点的路径。 p a t h = [ 2 , 3 , 5 , 7 ] path=[2,3,5,7] p a t h = [ 2 , 3 , 5 , 7 ] , k = 2 k=2 k = 2 。其中7为目标点然后考虑对路径的每一节

    2024年02月09日
    浏览(32)

  • 刷题（双指针思想/滑动窗口思想/l螺旋矩阵）

    刚开始自己做就是无脑ac的，sort： 但是时间复杂度有问题， 是O(nlogn)的时间复杂度 提升：用双指针的思想：时间复杂度为O(n) 使用 双指针 的思想解决本题的思路： 以数组 为例： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 因为输入的数组是递增的，因此，平方后的最大值，只

    2023年04月08日
    浏览(38)
  • LeetCode高频算法刷题记录4

    LeetCode高频算法刷题记录4

    题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 参考题解：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/ 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“

    2024年02月06日
    浏览(45)

  • Java算法 leetcode简单刷题记录6

    环和杆： https://leetcode.cn/problems/rings-and-rods/ 统计范围内的元音字符串数： https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/ 最长平衡子字符串： https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/ K 个元素的最大和： https://leetcode.cn/problems/maximum-sum-with-exa

    2024年01月24日
    浏览(35)

  • Java算法 leetcode简单刷题记录4

    买卖股票的最佳时机： https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 笨办法： 记录当天的值及之后的最大值，相减得到利润； 所有的天都计算下，比较得到利润最大值； 会超时 记录过程中遇到的最低值，每当有利润大于0及大于上一个利润值的情况，赋值； 最小和分割：

    2024年01月23日
    浏览(29)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包