题目描述

题目1（977. 有序数组的平方）

题目2（189. 旋转数组）

解题思路

题目1（977. 有序数组的平方）

• 首先找到数组nums的正负分界点（boundary，最后一个负数），将nums分为正负两个部分；
• 使用游标 i （boundary --> 0），和游标 j (boundary --> nums.length - 1)；
• 比较nums[i]平方和 nums[j]平方的大小，若nums[i]平方 > nums[j]平方，将nums[j]平方加入目标数组res中，并将游标 j向后移一位；反之，将nums[i]平方加入目标数组res中，并将游标 i向前移一位；
• 当游标 i<0 时，将nums[j -->nums.length - 1]的平方依次加入res中；当游标 j>=nums.length时，将nums[i -->0]的平方依次加入res中；

题目2（189. 旋转数组）

• 定义一个翻转数组的方法reserve()，实现：[a1,a2,...,an]到[an,an-1,...,a2,a1]的翻转
• nums经过三次翻转得到结果：
  （1）翻转nums整个数组，下标 0 ~ nums.length-1;
  （2）翻转nums[0 ~ k-1]；
  （3）翻转nums[k ~ nums.length-1]
  例如：nums = [1,2,3,4,5,6,7], k = 3
  第1次翻转得到：[==7,6,5,4,3,2,1==]
  第2次翻转得到：[==5,6,7==,4,3,2,1]
  第3次翻转得到：[5,6,7,==1,2,3,4==]

  【注】对于数组旋转步数k, 需要进行如下处理：k = k % nums.length。因为当数组旋转nums.length次时，数组不发生变化。

代码实现

题目1（977. 有序数组的平方）

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];

        int boundary = -1,i;
        for(i=0;i<nums.length;i++){
            if(nums[i]<0){
                boundary = i;    //找到正负数的分界点
            }else break;
        }
        int j = boundary+1, count = 0;
        i = boundary;
        while(i>=0 || j<nums.length){
            if(i>=0 && j<nums.length){
                if(nums[i] * nums[i] >= nums[j] * nums[j]){
                    res[count] = nums[j] * nums[j];
                    ++count;
                    ++j;
                }else{
                    res[count] = nums[i] * nums[i];
                    ++count;
                    --i;
                }
            }
            if(i<0){
                res[count] = nums[j] * nums[j];
                ++count;
                ++j;
            }else if(j>=nums.length){
                res[count] = nums[i] * nums[i];
                ++count;
                --i;
            } 
        }
        return res;
        // int[] res = new int[nums.length];
        // for(int i=0;i<nums.length;i++){
        //     res[i] = nums[i] * nums[i];
        // }

        // Arrays.sort(res);
        // return res;
    }
}

题目2（189. 旋转数组）

class Solution {
    /**
    * nums:进行翻转的数组
    * start:起始下标
    * end:终点下标
    */
    public void reserve(int[] nums, int start, int end){
        while(start<end){
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
    
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reserve(nums, 0, nums.length - 1);
        reserve(nums, 0, k-1);
        reserve(nums, k, nums.length - 1);
    }
}