Leetcode_14 天算法入门_day3

Posted on | Edited on | In ,
| 4.5k | 38 mins.

第三天的主题还是 two pointers，一道简单题，一道中等题。

283. Move Zeroes

Analysis

拿到这种题之后，脑子里面反应的第一解法，就是直接用 vector 拷贝...😂试了下，确实是可以解出来的。
不过既然出现在这里还是用双指针的方法做一下。

Code

method 1

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int> ret(nums.size());
        int index = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i]) ret[index++] = nums[i];
        }
        nums = ret;
    }
};

method 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int first = 0, second = 1, size = nums.size();
        while(first < size) {
            if(nums[first] == 0) {
                while(second < size && nums[second] == 0) second++;
                if(second < size) {
                    swap(nums[first], nums[second]);
                    first++, second++;
                } else break;
            } else {
                first++;
                if(second <= first) second++;
            }
        }
    }
};

method 3

按照上面代码的思路，从左边指针来考虑问题，会比较麻烦，实际上，可以直接从右边指针的角度来考虑问题。此时，左边指针就是非零数的尾部，右边指针就是待处理数字序列的头部，这样右边指针每遇到一个非零数，就直接移到左边。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0, right = 0, size = nums.size();
        while(right < size) {
          if(nums[right]) {
            swap(nums[left], nums[right]);
            left++;
          }
          right++;
        }
    }
};

167. Two Sum II - Input Array Is Sorted

Analysis

这个题是 1. Two Sum 的加强版，之前的解法在这里可以用。所以，首先想到的就是暴力求解跟哈希，但这两种方法都没有使用题目给的条件：数组有序。

Code

method 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* method 1: violent solution, will cause time limit exceeded. */
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> ret;
        int size = numbers.size();
        for(int i = 0; i < numbers.size(); i++) {
            for(int j = i + 1; j < numbers.size(); j++) {
                if(numbers[j] + numbers[i] == target) {
                    ret.push_back(i + 1);
                    ret.push_back(j + 1);
                }
            }
        }
        return ret;
    }
};

暴力解法，果然不出所料的会超时啊。

method 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* method 2: use hash map */
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> ret(2);
        map<int, int> hash;
        int size = numbers.size();
        hash[numbers[0]] = 0;
        for(int i = 1; i < size; i++) {
            if(hash.find(target - numbers[i]) != hash.end()) {
                ret[0] = hash[target - numbers[i]] + 1;
                ret[1] = i + 1;
            }
            hash[numbers[i]] = i;
        }
        return ret;
    }
};

哈希虽然不超时，但是额外的消耗了内存空间。

method 3

考虑到数组有序，所以可以使用前两天学习的二分查找，这样时间复杂度就是 $O(nlogn)$ 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* method 3: use binary search */
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i = 0; i < numbers.size(); i++) {
            int left = i + 1, right = numbers.size() - 1;
            while(left <= right) {
                int mid = (right + left) / 2;
                if(numbers[mid] == target - numbers[i]) {
                    return {i + 1, mid + 1};
                } else if(numbers[mid] > target - numbers[i]) right = mid - 1;
                else left = mid + 1;
            }
        }
        return {-1, -1};
    }
};

method 4

由于这个题出现在双指针里面，所以肯定可以使用双指针的解法。如何使用双指针呢？
需要设置两个指针分别从数组的左右两边进行遍历，每次将指针所指的值之和与目标值进行比较。如果大于目标值，那么左移右指针；如果小于，那么右移左指针。可能会有人觉得漏解，实际上并不会。从反证法的角度很容易想明白，如果右指针固定，左指针左边存在满足条件的解，或者左指针固定，右指针右边存在满足条件的解，那么这个数组一定不是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* method 4: use two pointers */
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while(left < right) {
            int sum = numbers[left] + numbers[right];
            if(sum < target) left++;
            else if(sum > target) right++;
            else return {left + 1, right + 1};
        }
        return {-1, -1};
    }
};

Summary

双指针用来解决一些问题真是有奇效啊。大体上来讲，要么是从中间向两边遍历，要么是两边向中间遍历。遇到这种类型的题目的时候，不妨从这两个角度思考一下，说不定问题就能得到解决。

Buy me a coffee ? :)
0%