博客 / 詳情

返回

數組-雙指針、滑動窗口、螺旋矩陣

雙指針算法（其它類型）

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/

leetcode個人解題總結 , c++ , 數據結構與算法
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.