Cloud_Player's Notes
0%

LeetCode Day3

发表于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

LeetCode Day3

数组

移除元素

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 复习一下双指针法 */
/* 添加一个 cnt 计数，最后再补上 cnt 个 0 */
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int val = 0;
        int slowIndex = 0, fastIndex = 0;
        int cnt = 0;
        int len = nums.size();
        for (; fastIndex < len; fastIndex++) {
            if (val != nums[fastIndex]) {
                if(fastIndex != slowIndex) nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
            else cnt++;
        }
        for (int i = slowIndex; i < slowIndex + cnt; i++) nums[i] = val;
    }
};

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* 用双指针法 */
/* 时间复杂度 O(n)，空间复杂度 O(1) */
class Solution {
public:
    string dealwithString(string Str) {
        char back = '#';
        int slowIndex = 0, fastIndex = 0;
        for(; fastIndex < Str.length(); fastIndex++){
            if(Str[fastIndex] != back){
                if(fastIndex != slowIndex) Str[slowIndex] = Str[fastIndex];
                slowIndex++;
            }
            else if(slowIndex > 0) slowIndex--;
        }
        return Str.substr(0, slowIndex);
    }
    bool backspaceCompare(string s, string t) {
        return dealwithString(s) == dealwithString(t);
    }
};

/* 也可以用栈来实现 */
class Solution {
public:
    string dealwithString(string Str) {
        char back = '#';
        string result;
        stack<char> StrS;
        for(int i = 0; i < Str.length(); i++) {
            if(Str[i] == back) { if(!StrS.empty()) StrS.pop(); }
            else StrS.push(Str[i]); 
        }
        while(!StrS.empty()) { result += StrS.top(); StrS.pop(); }
        return result;
    }
    bool backspaceCompare(string s, string t) {
        return dealwithString(s) == dealwithString(t);
    }
};

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 双指针法 */
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        int border = len;
        for (int i = 0; i < len; i++) if (nums[i] >= 0) { border = i; break; }
        vector<int> ans;
        int negIndex = border - 1, posIndex = border;
        int negpower, pospower;
        while (negIndex >= 0 || posIndex < len) {
            if (negIndex >= 0) negpower = nums[negIndex] * nums[negIndex];
            if (posIndex < len) pospower = nums[posIndex] * nums[posIndex];
            if (negIndex < 0) { ans.push_back(pospower); posIndex++; }
            else if (posIndex == len) { ans.push_back(negpower); negIndex--; }
            else if (negpower < pospower) { ans.push_back(negpower); negIndex--; }
            else { ans.push_back(pospower); posIndex++; }
        }
        return ans;
    }
};

/*
找到正负数交界的数组索引，将数组分为两段
用双指针法，将两个数组中指针指向的值较小的那一个放入结果数组中去
（类似并归排序）
*/