数组-双指针、滑动窗口、螺旋矩阵

发布于：2023-03-12 ⋅ 阅读:(74) ⋅ 点赞:(0)

双指针算法（其它类型）

leetcode.977

  • 链接https://leetcode.cn/problems/...
  • 解题方法：有序数组的平方最大值一定在数组的两侧
    i指针从前向后遍历，j指针从后向前遍历，k指针用来存储新数组放置在数组前后均可（本题题解放在数组末尾）
    将nums[i]的平方与nums[j]的平方作比较，k指针将较大的数存到答案数组当中，同时移动较大的数的指针和k的指针
    如果将k指针放在数组首位则将k指针将较小的数存到答案数组当中，同时移动较小的数的指针和k的指针

  • leetcode解题代码

    class Solution {
public:
  vector<int> sortedSquares(vector<int>& nums) {
      int n = nums.size();
      vector<int>res(n);
      for (int i = 0, j = n - 1, k = n - 1; i <= j;){
          if (nums[i] * nums[i] > nums[j] * nums[j]){
              res[k] = nums[i] * nums[i];
              i ++, k --;
          }
          else{
              res[k] = nums[j] * nums[j];
              j --, k --;
          }
      }
      return res;
  }
};
  • ACM模式调试

输入
第一行输入n表示数组长度
第二行输入表示原数组

-4 -1 0 3 10

输出

0 1 9 16 100

调试代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    
    vector<int> res(n);
    for (int i = 0, j = n - 1, k = n - 1; i <= j;){
        if (nums[i] * nums[i] > nums[j] * nums[j]){
            res[k] = nums[i] * nums[i];
            i ++, k --;
        }
        else{
            res[k] = nums[j] * nums[j];
            j --, k --;
        }
    }
    
    for (auto c: res){
        cout << c << ' ';
    }
    return 0;
}

滑动窗口算法

leetcode.209

  • 链接https://leetcode.cn/problems/...
  • 解题方法：由于均为正整数，如果找到一段[j, i]满足条件的最小段，当i向右移动时，j同时要向右移动
    将i，j指针同时放在数组首位，i指针向后移动并用sum记录nums[i]的总和
    当sum-nums[j]>=target时说明j指针可以跟随i向右移动
    当满足sum>=target时，用res记录[j, i]长度

  • leetcode解题代码

    class Solution {
public:
  int minSubArrayLen(int target, vector<int>& nums) {
      int sum = 0, res = INT_MAX;
      for (int i = 0, j = 0; i < nums.size(); i ++){
          sum += nums[i];
          while (sum - nums[j] >= target){
              sum -= nums[j];
              j ++;
          }
          if (sum >= target) res = min(res, i - j + 1);
      }
      if (res == INT_MAX) return 0;
      return res;
  }
};
  • ACM模式调试

输入
第一行输入n表示数组长度，target表示目标值
第二行输入表示原数组

6 7
2 3 1 2 4 3

输出

2

调试代码

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main()
{
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    
    int sum = 0, res = INT_MAX;
    for (int i = 0, j = 0; i < n; i ++){
        sum += nums[i];
        while (sum - nums[j] >= target){
            sum -= nums[j];
            j ++;
        }
        if (sum >= target) res = min(res, i - j + 1);
    }
    if (res == INT_MAX) cout << 0 << endl;
    else cout << res << endl;

    return 0;
}

leetcode.3

  • 链接https://leetcode.cn/problems/...
  • 解题方法：与上题类似，需要用一个哈希表存储[j, i]段中字符

  • leetcode解题代码

    class Solution {
public:
  int lengthOfLongestSubstring(string s) {
      int res = 0;
      unordered_map<char, int> cnt;
      for (int i = 0, j = 0; i < s.size(); i ++){
          cnt[s[i]] ++;
          while (cnt[s[i]] > 1){
              cnt[s[j]] --;
              j ++;
          }
          res = max(res, i - j + 1);
      }
      return res;
  }
};
  • ACM模式调试

输入
第一行输入表示字符串s

abcabcbb

输出

3

调试代码

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main()
{
    string s;
    getline(cin, s);
    
    int res = 0;
    unordered_map<char, int> cnt;
    for (int i = 0, j = 0; i < s.size(); i ++){
        cnt[s[i]] ++;
        while (cnt[s[i]] > 1){
            cnt[s[j]] --;
            j ++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    
    return 0;
}

leetcode.904

  • 链接https://leetcode.cn/problems/...
  • 解题方法：本题题意与上题类似，需要用一个哈希表存储[j, i]段中字符出现的次数，同时还要记录水果的种类，题目要求水果种类不超过2

  • leetcode解题代码

    class Solution {
public:
  int totalFruit(vector<int>& fruits) {
      int res = 0, type = 0;// res记录答案，type表示水果的种类
      unordered_map<int, int> cnt;// cnt记录字符出现的次数
      for (int i = 0, j = 0; i < fruits.size(); i ++){
          cnt[fruits[i]] ++;
          if (cnt[fruits[i]] == 1) type ++;// 如果字符第一次出现说明是一种水果
          while (type > 2){
              cnt[fruits[j]] --;
              if (cnt[fruits[j]] == 0) type --;
              j ++;
          }
          res = max(res, i - j + 1);
      }
      return res;
  }
};
  • ACM模式调试

输入
第一行n表示fruits数组长度
第二行表示fruits数组

3
1 2 2

输出

3

调试代码

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> fruits(n);
    for (int i = 0; i < n; i ++) cin >> fruits[i];

    int res = 0, type = 0;
    unordered_map<int, int> cnt;
    for (int i = 0, j = 0; i < n; i ++){
        cnt[fruits[i]] ++;
        if (cnt[fruits[i]] == 1) type ++;
        while (type > 2){
            cnt[fruits[j]] --;
            if (cnt[fruits[j]] == 0) type --;
            j ++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    
    return 0;
}

leetcode.76

  • 链接https://leetcode.cn/problems/...
  • 解题方法：本题题意与上题类似，需要用两个哈希表分别存储两个字符串
    最后输出结果的时候需要特判

  • leetcode解题代码

    class Solution {
public:
  string minWindow(string s, string t) {
      string res;
      int cnt = 0;// 有效字符的数量
      unordered_map<char, int> hs, ht;
      for (auto c: t) ht[c] ++;

      for (int i = 0, j = 0; i < s.size(); i ++){
          hs[s[i]] ++;
          if (hs[s[i]] <= ht[s[i]]) cnt ++;// 是一个有效字符
          while (hs[s[j]] > ht[s[j]]){
              hs[s[j]] --;
              j ++;
          }
          if (cnt == t.size()){
              if (res.empty() || i - j + 1 < res.size())
                  res = s.substr(j, i - j + 1);
          }
      }
      return res;
  }
};
  • ACM模式调试 与leetcode.3类似

螺旋矩阵

leetcode.54

  • 链接https://leetcode.cn/problems/...
  • 解题方法：
    从左上角出发，按照顺时针顺序分别是向右向下向左向上，如果初始坐标为（0，0）
    向右（0，1）向下（1，0）向左（0，-1）向上（-1，0）
    所以x有四个取值{0, 1, 0, -1}，y有四个取值{1, 0, -1, 0}
    按照每一个方向一直走，走到不能走为止
    不能走有两种可能：1.出界 2.走到已经走过的位置

  • leetcode解题代码

    class Solution {
public:
  vector<int> spiralOrder(vector<vector<int>>& matrix) {
      vector<int> res;
      int n = matrix.size();
      int m = matrix[0].size();
      vector<vector<bool>> st(n, vector<bool>(m));

      int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
      for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++){
          res.push_back(matrix[x][y]);
          st[x][y] = true;

          int a = x + dx[d], b = y + dy[d];
          if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
              d = (d + 1) % 4;
              a = x + dx[d], b = y + dy[d];
          }
          x = a, y = b;
      }
      return res;
  }
};
  • ACM模式调试

输入
第一行表示n行m列向量
后面n行m列表示向量的值

3 3
1 2 3
4 5 6
7 8 9

输出

1 2 3 6 9 8 7 4 5

调试代码

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int metrix[n][m];
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < m; j ++){
            cin >> metrix[i][j];
        }
    }
    
    vector<vector<bool>> st(n, vector<bool>(m));
    vector<int> res;
    
    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    
    for (int i = 0, x = 0, y = 0, d = 0; i < n*m; i ++){
        res.push_back(metrix[x][y]);
        st[x][y] = true;
        
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d]; 
        }
        x = a, y = b;
    }
    
    for (auto c: res){
        cout << c << ' ';
    }
    return 0;
}

leetcode.59

  • 链接https://leetcode.cn/problems/...
  • 解题方法：与上一题类似

  • leetcode解题代码

    class Solution {
public:
  vector<vector<int>> generateMatrix(int n) {
      vector<vector<int>> res(n, vector<int>(n));
      int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

      for (int i = 1, x = 0, y = 0, d = 0; i <= n * n; i ++){
          res[x][y] = i;
          int a = x + dx[d], b = y + dy[d];
          if (a < 0 || a >= n || b < 0 || b >= n || res[a][b]){
              d = (d + 1) % 4;
              a = x + dx[d], b = y + dy[d];
          }
          x = a, y = b;
      }
      return res;
  }
};
  • ACM模式调试 与上一题类似

解题参考：https://www.acwing.com/
刷题顺序：https://www.programmercarl.com/

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布