算法——双指针【练习1】

方法一：旋转数组

思路：

 代码实现：

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums , 0 , n - 1);//整个数组反转
        reverse(nums , 0 , k - 1);//前k个反转
        reverse(nums , k , n - 1);//后n-k个反转
    }
    public void reverse(int[] nums,int head,int rear) {
        int n = rear - head + 1;;
        for(int i = 0;i < n / 2;i++) {
            int temp = nums[head];
            nums[head] = nums[rear];
            nums[rear] = temp;
            head++;
            rear--;
        }
    }
}

方法二：额外数组，类似循环数组

思路： 

使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)mod n 的位置，最后将新数组拷贝至原数组即可。 

代码实现： 

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newarr = new int[n];
        for(int i = 0;i < n;i++) {
            newarr[(i+k)%n] = nums[i];
        }
        System.arraycopy(newarr, 0, nums, 0, n);
    }
}

方法三： 环状替换

class Solution {
   public void rotate(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        for(int i = 0;count != n;i++) {
            int next = (i + k) % n;
            int temp = nums[next];
            int prev = nums[i];
            int current = 0;
            do{
                nums[next] = prev;
                prev = temp;
                current = next;
                next = (next + k) % n;
                temp = nums[next];
                count++;
            }while(current != i);
        }
    }
}

 【题目二】有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
 

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
 

代码实现： 

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for(int i = 0 , j = n - 1,k = n - 1;i <= j;k--) {
            if(nums[i]*nums[i] > nums[j]*nums[j]) {
                ans[k] = nums[i]*nums[i];
                i++;
            }else {
                ans[k] = nums[j]*nums[j];
                j--;
            }
        }
        return ans;
    }
}