论坛 › 数据仓库与分析 › 双指针算法-day17（分组循环）

冬雨财经 发表于 2025-3-24 06:16:02

双指针算法-day17（分组循环）

1.使绳子酿成彩色的最短时间

题目

https://i-blog.csdnimg.cn/direct/ad67259815ac4c34a1ec7f4a4bdc1ffa.png
剖析



[*]计算每组消耗时间总和，减去此中最大时间，得到所需时间；
代码

class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
      // 时间复杂度：O(n)
      // 空间复杂度：O(1)

      int n = colors.size();
      int ans = 0;

      int i = 0;
      while(i < n){
            int start = i ++;
            int sum = neededTime;
            int mx = neededTime;

            while(i < n && colors == colors){
                sum += neededTime;
                mx = max(mx,neededTime);
                i ++;
            }

            ans += sum - mx;
      }

      return ans;
    }
}; 2.所有元音按顺序排布的最宗子字符串

题目

https://i-blog.csdnimg.cn/direct/ee1762ea5bfa47a5b5242660067e78fb.png
剖析



[*]用 trans 记录字符转换次数，如果 trans == 4 说明凑齐了 5 个元音；
代码

class Solution {
    bool check(char a,char b){
      if(a == 'a' && b == 'e') return true;
      else if(a == 'e' && b == 'i') return true;
      else if(a == 'i' && b == 'o') return true;
      else if(a == 'o' && b == 'u') return true;
      else return false;
    }

public:
    int longestBeautifulSubstring(string word) {
      // 时间复杂度：O(n)
      // 空间复杂度：O(1)

      int n = word.size();
      int ans = 0;

      int i = 0;
      while(i < n){
            if(word != 'a') {
                i ++;
                continue;
            }

            int start = i ++, trans = 0;
            while(i < n){
                if(check(word,word)){
                  trans ++;
                  i ++;
                }else if(word == word){
                  i ++;
                }else {
                  break;
                }
            }

            if(trans == 4) ans = max(ans,i - start);
      }

      return ans;
    }
}; 3.最长交替子数组

题目

https://i-blog.csdnimg.cn/direct/52598329ceee4f8a96f6d6024fa8ec33.png
剖析



[*]先找到 后 - 前 == 1 的两个数，再继承遍历探求交替 +-1 的子序列；
代码

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
      // 时间复杂度：O(n)
      // 空间复杂度：O(1)

      int n = nums.size();
      int ans = -1;

      int i = 0;
      while(i < n - 1){
            if(nums - nums != 1){
                i ++;
                continue;
            }

            int start = i ++;
            while(i < n - 1 && (nums - nums) * (nums - nums) == -1){
                i ++;
            }

            ans = max(ans,i - start + 1);
      }

      return ans;
    }
}; 4.长度为 K 的子数组的能量值

题目

https://i-blog.csdnimg.cn/direct/00675cf04f98426da225e1c1f996f05d.png
剖析



[*]焦点思想：双指针，滑动窗口；
[*]移动右指针时进行判定：

[*]不满足递增条件：l 移动到 r，由于 r 左边的数形成的窗口都不会满足递增条件了；
[*]满足递增条件：比及窗口长度为 K，更新答案为 nums，由于右边界为最大值；

代码

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
      // 时间复杂度：O(n)
      // 空间复杂度：O(1)

      int n = nums.size();
      vector<int> ans(n - k + 1,-1);

      int l = 0;
      for(int r = 0;r < n;r ++){
            if(r && nums - nums != 1) {
                l = r;// r 左边元素形成的窗口均不满足条件
            }

            if(r - l + 1 == k) {
                ans = nums;// 右边界元素为最大值
                l ++;
            }
      }

      return ans;
    }
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

查看完整版本: 双指针算法-day17（分组循环）