Leetcode_14 天算法入门_day2

第二天的主题是 two pointers，一道简单题，一道困难题。

977. Squares of a Sorted Array

Analysis

这个题第一眼看到后，脑子里面浮现出来的解法，就是直接算，然后排序。尝试了一下，也是可以这样做的。不过，既然出现在双指针这里，应该可以用双指针来做。
用双指针处理有 2 种思路：

1. 从中间向两边遍历，这样需要先找到中间值，可以认为中间值是平方后数组的最小值，也可以认为是数组中正负数的分界点（题目已经限定是非降序数组，所以正负数是分别分布在两边的）。
2. 从两边向中间遍历，这样每次选出来的值实际上是数组剩余数字中的最大值，所以需要逆序一下。

Code

method 1

Copy

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int size = nums.size();
        for(int i = 0; i < size; i++) {
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

method 2

这里选择平方后最小值为中间值。

Copy

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int size = nums.size(), min_index = 0, min = nums[0] * nums[0];
        for(int i = 0; i < size; i++) {
            nums[i] = nums[i] * nums[i];
            if(nums[i] < min) {
                min = nums[i];
                min_index = i;
            }
        }
        int left = min_index - 1, right = min_index + 1;
        vector<int> ret;
        ret.push_back(min);
        while(left >= 0 && right <= size - 1) {
            if(nums[left] >= nums[right]) {
                ret.push_back(nums[right]);
                right++;
            } else {
                ret.push_back(nums[left]);
                left--;
            }
        }
        while(left >= 0) {
            ret.push_back(nums[left--]);
        }
        while(right <= size - 1) {
            ret.push_back(nums[right++]);
        }
        return ret;
    }
};

method 3

Copy

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int size = nums.size();
        for(int i = 0; i < size; i++) {
            nums[i] = nums[i] * nums[i];
        }
        vector<int> ret(size);
        int index = size - 1;
        for(int i = 0, j = size - 1; i <= j;) {
            if(nums[i] > nums[j]) ret[index--] = nums[i++];
            else ret[index--] = nums[j--];
        }
        return ret;
    }
};

189. Rotate Array

Analysis

这个题很经典，做法很多，是做过很多次的题目了。
用 reverse 函数是最简单直观、而且消耗低的做法了，如果用直接交换数字的方法，需要计算出遍历的次数，但是实际上可以单独设置一个 count，用来记录交换的次数，一旦等于 n 说明都交换过了，就可以退出循环了，这样也是可以的。

Code

method 1

Copy

/* method 1: use queue, but cost many memory */
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size(), tmp;
        vector<int> ret;
        queue<int> q;
        k %= size;
        for(int i = 0; i < size; i++) {
            q.push(nums[i]);
        }
        for(int i = 0; i < size - k; i++) {
            tmp = q.front();
            q.pop();
            q.push(tmp);
        }
        while(!q.epmty()) {
            ret.push_back(q.front());
            q.pop();
        }
        nums = ret;
    }
};

method 2

Copy

/* method 2: use vector, also cost many memory */
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size(), tmp;
        vector<int> ret;
        k %= size;
        for(int i = size - k; i < size; i++) {
            ret.push_back(nums[i]);
        }
        for(int i = 0; i < size - k; i++) {
            ret.push_back(nums[i]);
        }
        nums = ret;
    }
};

method 3

Copy

/* method 3: use reverse function */
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size(), tmp;
        k %= size;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

method 4

Copy

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size(), tmp;
        k %= size;
        /* version 1 */
        int count = gcd(size, k);
        for(int start = 0; start < count; start++) {
            int cur = start;
            int prev = nums[start];
            do{
                int next = (cur + k) % size;
                swap(nums[next], prev);
                cur = next;
            } while(start != cur);
        }
        /* version 2 
        int count = 0;
        for(int start = 0; count < n; start++) {
            int cur = start;
            int prev = nums[start];
            do{
                int next = (cur + k) % size;
                swap(nums[next], prev);
                cur = next;
                count++;
            } while(start != cur);
        }
        */
    }
};

Summary

有时候用双指针来解决一些问题时，可能会有奇效，整体而言，思路不算难。

---