Two-pointers

雙指針算法（移除元素類型）

leetcode.27

• 鏈接https://leetcode.cn/problems/...
• 解題方法：用len指針指向新數組下標
  i指針從前往後遍歷原數組
  如果nums[i] == val那麼len指針不動，i指針繼續向後遍歷
  如果nums[i] != val那麼len向後移動一位，並將原數組的值賦給新數組
  返回新數組的下標即可

• leetcode解題代碼

  class Solution {
  public:
    int removeElement(vector<int>& nums, int val) {
        int len = 0;
        for (int i = 0; i < nums.size(); i ++){
            if (nums[i] == val) continue;
            else nums[len ++] = nums[i];
        }
        return len;
    }
  };

• ACM模式調試

輸入
第一行輸入兩個數n，val
n表示數組中有n個數，val表示目標值
第二行表示數組

4 3
3 2 2 3

輸出
第一行表示移除目標值之後新數組的長度
第二行表示新數組

2
2 2

調試代碼

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, val;
    vector<int> nums(4);
    cin >> n >> val;
    for (int i = 0; i < n; i ++) cin >> nums[i];
    
    vector<int> res;
    for (int i = 0; i < n; i ++){
        if (nums[i] == val) continue;
        else{
            res.push_back(nums[i]);
        } 
    }
    cout << res.size() << endl;
    for (auto c: res){
        cout << c << ' ';
    }
    return 0;
}

leetcode.26

• 鏈接https://leetcode.cn/problems/...
• 解題方法：與上一題類似，注意特判第一位

• leetcode解題代碼

  class Solution {
  public:
    int removeDuplicates(vector<int>& nums) {
        int len = 0;
        for (int i = 0; i < nums.size(); i ++){
            if (i == 0 || nums[i] != nums[i - 1])
                nums[len ++] = nums[i];
        }
        return len;
    }
  };

• ACM模式調試 和上題類似

leetcode.283

• 鏈接https://leetcode.cn/problems/...
• 解題方法：將題目轉換為
  移除目標值為0的元素（與第一題類似）
  並保證新數組與原數組的元素個數相同（差多少個元素就補多少個0）

• leetcode解題代碼

  class Solution {
  public:
    void moveZeroes(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i ++){
            if (nums[i] != 0)
                nums[k ++] = nums[i];
        }
        while (k < nums.size()) nums[k ++] = 0;
    }
  };

• ACM模式調試

輸入
第一行輸入一個數n
n表示數組中有n個數
第二行表示數組

5
0 1 0 3 12

輸出
新數組

1 3 12 0 0

調試代碼

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    vector<int> nums(5);
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> nums[i];
    
    vector<int> res;
    for (int i = 0; i < n; i ++){
        if (nums[i] != 0)
            res.push_back(nums[i]);
    }
    while (res.size() < n) res.push_back(0);
    
    for (auto c: res){
        cout << c << ' ';
    }
    return 0;
}

leetcode.844

• 鏈接https://leetcode.cn/problems/...
• 解題方法：定義一個函數，函數的功能是返回編輯結束後的字符串
  遍歷字符串
  如果當前字符串不是'#'則將其加入答案
  如果當前字符串是'#'則將上一個字符串刪除
  調用函數，判斷兩個字符串是否相等

• leetcode解題代碼

  class Solution {
  public:
    string edit(string& s){
        string res;
        for (auto c: s){
            if (c != '#') res += c;
            else 
                if (res.size())
                    res.pop_back();
        }
        return res;
    }
  
    bool backspaceCompare(string s, string t) {
        return edit(s) == edit(t);
    }
  };

• ACM模式調試

輸入
第一行輸入字符串s
第二行輸入字符串t

ab#c
ad#c

輸出

true

調試代碼

#include <iostream>
#include <string>

using namespace std;

string edit(string& s){
    string res;
    for (auto c: s){
        if (c != '#') res += c;
        else 
            if (res.size()) 
                res.pop_back();
    }
    return res;
}

bool compare(string& s, string& t){
    if (edit(s) == edit(t)) cout << "true" << endl;
    else cout << "false" << endl;
    return true;
}

int main(){
    string s, t;
    getline(cin, s);
    getline(cin, t);
    compare(s, t);
    return 0;
}

解題參考：https://www.acwing.com/
刷題順序：https://www.programmercarl.com/