LeetCode.977.189.283.167(双指针)

977.有序数组的平方

class Solution {
  public:
    vector<int> sortedSquares(vector<int> &nums) {
        /*vector<int> ans;
        int left = 0, right = nums.size() - 1;
        while (right > left) {
            int ansLeft = nums[left] * nums[left], ansRight = nums[right] * nums[right];
            if (ansLeft <= ansRight) {
                ans.insert(ans.begin(), ansRight);
                right--;
            } else {
                ans.insert(ans.begin(), ansLeft);
                left++;
            }
        }
        ans.insert(ans.begin(), nums[left] * nums[left]);
        return ans;*/
        // 137/137 cases passed (844 ms)
        // Your runtime beats 5.66 % of cpp submissions
        // Your memory usage beats 5.11 % of cpp submissions (26.4 MB)
        //!太慢了，不能用insert
        vector<int> ans(nums.size(), 0);
        int pos = nums.size() - 1;
        int left = 0, right = nums.size() - 1;
        while (right > left) {
            int ansLeft = nums[left] * nums[left], ansRight = nums[right] * nums[right];
            if (ansLeft <= ansRight) {
                ans[pos--] = ansRight;
                right--;
            } else {
                ans[pos--] = ansLeft;
                left++;
            }
        }
        ans[pos] = nums[left] * nums[left];
        return ans;
        // 137/137 cases passed (20 ms)
        // Your runtime beats 94.02 % of cpp submissions
        // Your memory usage beats 84.97 % of cpp submissions (25.2 MB)
        //*思路差不多但提前定好大小就很快
    }
};

189.轮转数组

class Solution {
  public:
    void rotate(vector<int> &nums, int k) {
        /*int numsSize = nums.size();
        for (int i = 0; i < k; i++) {
            int temp = nums[numsSize - 1];
            for (int j = numsSize - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = temp;
        }*/
        //!死方法，数据一大就超时
        int numsSize = nums.size();
        k = k % numsSize; //当k>numsSize会出错，反正转了一圈就相当于没转
        /*for (int i = 0; i < numsSize / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[numsSize - 1 - i];
            nums[numsSize - 1 - i] = temp;
        }
        for (int i = 0; i < k / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[k - 1 - i];
            nums[k - 1 - i] = temp;
        }
        for (int i = 0; i < (numsSize - k) / 2; i++) {
            int temp = nums[k + i];
            nums[k + i] = nums[numsSize - 1 - i];
            nums[numsSize - 1 - i] = temp;
        }*/
        // 38/38 cases passed (24 ms)
        // Your runtime beats 75.75 % of cpp submissions
        // Your memory usage beats 79.85 % of cpp submissions (24.3 MB)
        reverse(nums.begin(), nums.begin() + nums.size() - k);
        reverse(nums.begin() + nums.size() - k, nums.end());
        reverse(nums.begin(), nums.end());
        // 38/38 cases passed (20 ms)
        // Your runtime beats 92.47 % of cpp submissions
        // Your memory usage beats 92.28 % of cpp submissions (24.2 MB)
        //*reverse自动翻转(平均效率差不多，这只是最突出的一个成绩)
    }
};

283.移动零

class Solution {
  public:
    void moveZeroes(vector<int> &nums) {
        /*int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0 && i < nums.size() - 1 - count) {
                for (int j = i; j < nums.size() - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                nums[nums.size() - 1] = 0;
                count++;
                i--;
            }
        }*/
        // 74/74 cases passed (596 ms)
        // Your runtime beats 5.03 % of cpp submissions
        // Your memory usage beats 59.76 % of cpp submissions (18.7 MB)
        //!暴力解，为了解决i--造成的无限循环用了count，败笔
        int j = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while (j < nums.size()) {
            nums[j++] = 0;
        }
        // 74/74 cases passed (28 ms)
        // Your runtime beats 20.21 % of cpp submissions
        // Your memory usage beats 89.74 % of cpp submissions (18.6 MB)
        //*反向思考，不处理0，而是处理非0项，速度会快上很多，也不需要双循环，这种操作叫做快慢指针
    }
};

167.两数之和-ii-输入有序数组

class Solution {
  public:
    /*int fun(int left, int right, vector<int> &numbers, int target) {
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (numbers[middle] > target) {
                right = middle - 1;
            } else if (numbers[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }*/
    vector<int> twoSum(vector<int> &numbers, int target) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            if (numbers[i] + numbers[j] > target)
                --j;
            else if (numbers[i] + numbers[j] < target)
                ++i;
            else
                return {i + 1, j + 1};
        }
        return {i, j}; //让编译通过而已，没用
        // 19/19 cases passed (4 ms)
        // Your runtime beats 85.33 % of cpp submissions
        // Your memory usage beats 60.41 % of cpp submissions (9.3 MB)
        //*内心不平衡，沟吧玩意这么简单？二分查找的进化了属于是
        /*vector<int> ans = {0, 0};
        bool judge = 0;
        int start = 0, end = numbers.size() - 1;
        int startB = -1, endB = -1;
        while (end >= start) {
            int median = start + (end - start) / 2;
            if (numbers[median] + numbers[median + 1] > target) {
                end = median - 1;
            } else if (numbers[median] + numbers[numbers.size() - 1] < target) {
                start = median + 1;
            } else {
                if (start == startB && end == endB) {
                    break;
                }
                startB = start;
                endB = end;
            }
        }
        for (int i = start; i <= end; i++) {
            int another = fun(i + 1, numbers.size() - 1, numbers, target - numbers[i]);
            if (another != -1) {
                ans = {i + 1, another + 1};
                break;
            }
        }
        return ans;*/
        // 19/19 cases passed (4 ms)
        // Your runtime beats 85.33 % of cpp submissions
        // Your memory usage beats 41.27 % of cpp submissions (9.4 MB)
        //*完全靠着自己做出来了，最终使用的方法是用双二分查找，先查找出第一个数（小）的区间，再在区间中挨个用二分查找遍历第二个数（大），结果还不错，空间复杂度和时间复杂度都还好
        //!但有个问题：一旦这个“可能区间”过大，那么就可能会变慢
        /*bool judge = 0;
        vector<int> ans(2, 0);
        for (int i = 0; i < numbers.size() - 1 && numbers[i] <= target; i++) {
            int left = i + 1, right = numbers.size() - 1;
            while (left <= right) {
                int middle = left + (right - left) / 2;
                if (numbers[middle] > target - numbers[i]) {
                    right = middle - 1;
                } else if (numbers[middle] < target - numbers[i]) {
                    left = middle + 1;
                } else {
                    ans[0] = i + 1;
                    ans[1] = middle + 1;
                    judge = 1;
                    break;
                }
            }
            if (judge)
                break;
        }
        return ans;*/
        //!还是大数超时
        /*bool judge = 0;
        vector<int> ans(2, 0);
        for (int i = 0; i < numbers.size() - 1 && numbers[i] <= target; i++) {
            for (int j = i + 1; j < numbers.size() && numbers[i] + numbers[j] <= target; j++) {
                if (numbers[i] + numbers[j] == target) {
                    ans[0] = i + 1;
                    ans[1] = j + 1;
                    judge = 1;
                    break;
                }
            }
            if (judge)
                break;
        }
        return ans;*/
        //!大数超时
    }
};