算法入门（第二天）---双指针977，189

977. 有序数组的平方

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
最简单的思路是直接平方后对数组进行简单排序，但是显然效率很低，所以考虑到影响平方后大小的情况只在于符号的变化，
主要有以下三种情况
1.所有数字都是负数，直接将数组平方后反向即可。
2.所有数字都是正数，直接将数组平方即可
3.有正有负，将找到负数和非负数的分界，对于负数（left）和正数（right）平方后的数比较，优先将小的数据填入辅助数组即可。
代码如下

public class Solution {
    public int[] sortedSquares(int[] nums) {
        int mid=0;
        int flag=0;
        if(nums[0]>0) flag=1;//最小为正数，全正数
        if(nums[nums.length-1]<0) flag=-1;//最大为负数，全负数
        for(int i=0;i<nums.length-1;i++)//进行平方
        {
            if(nums[i]<0&&nums[i+1]>=0)
            {
                mid=i;//找分界点
            }
            nums[i]=nums[i]*nums[i];
        }
        nums[nums.length-1]=nums[nums.length-1]*nums[nums.length-1];
        if(flag==1) return nums;//全正，直接平方后返回
        int [] midnums=new int[nums.length];//辅助数组
        if(flag==-1) {//全负，反转
           int left=0,right=nums.length-1;
           while(right>=0)
           {
               midnums[left]=nums[right];
               left++;
               right--;
           }
           return midnums;
        }
        int left=mid,right=mid+1;
        int index=0;
        while(left>=0&&right!=nums.length)
        {
            if(nums[left]<=nums[right])
            {
                midnums[index]=nums[left];
                left--;
            }
            else
            {
                midnums[index]=nums[right];
                right++;
            }
            index++;
        }//将小的优先填入
        if(index==nums.length) return midnums;//正好填完
        else if(index<nums.length&&left<0)//负数一侧已经填完，按序填充正数一侧
        {
            while(right!=nums.length)
            {
                midnums[index]=nums[right];
                right++;
                index++;
            }
        }
        else if(index<nums.length&&right==nums.length)//正数一侧已经填完，按序填充负数一侧
        {
            while(left>=0)
            {
                midnums[index]=nums[left];
                left--;
                index++;
            }
        }  
        return midnums;
}
}

我的代码最开始未考虑全正和全负的情况，加上后逻辑较为混乱，题解代码分类更加清晰

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        int negative = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }

        vector<int> ans;
        int i = negative, j = negative + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {
                ans.push_back(nums[j] * nums[j]);
                ++j;
            }//全正数
            else if (j == n) {
                ans.push_back(nums[i] * nums[i]);
                --i;
            }//全负数
            else if (nums[i] * nums[i] < nums[j] * nums[j]) {
                ans.push_back(nums[i] * nums[i]);
                --i;
            }
            else {
                ans.push_back(nums[j] * nums[j]);
                ++j;
            }
        }
        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/squares-of-a-sorted-array/solution/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

189. 轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

 输入: nums = [1,2,3,4,5,6,7], k = 3
 输出: [5,6,7,1,2,3,4]
 解释:
 向右轮转 1 步: [7,1,2,3,4,5,6]
 向右轮转 2 步: [6,7,1,2,3,4,5]
 向右轮转 3 步: [5,6,7,1,2,3,4]

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/rotate-array
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一.直接利用一个额外的数组空间对数据进行移位，然后重新赋值给nums即可

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

方法二.利用数组的逆转进行数据的移位，首先对整个数组进行转置，然后对0，k-1这前k个数据进行翻转，后对k,n-1的数组进行翻转即可实现k的移位

eg: nums = [1,2,3,4,5,6,7], k = 3
    7,6,5,4,3,2,1 
    5,6,7,4,3,2,1
    5,6,7,1,2,3,4移位成功
以下是我的代码

class Solution {
    public void reverse(int []nums,int start,int end)
    {
        while(start<end)
        {
            int mid=nums[start];
            nums[start]=nums[end];
            nums[end]=mid;
            start++;
            end--;
        }
    }
    public void rotate(int[] nums, int k) {
        int n=nums.length-1;
        if(k>=nums.length) k=k%nums.length;
        reverse(nums,0,n);
        reverse(nums,0,k-1);
        reverse(nums,k,n);
    }
}

方法三.利用双指针，和数学关系进行移位

从位置0开始，令temp=nums[0],然后对0元素进行k的移位即令nums[(0+k)%n]与temp进行交换，然后对nums[k]进行移位直到最终回到开始位置0,由此我们完成了0的剩余系的移位，然后我们需要取下一个剩余系的起始位置，但是这个位置怎么取呢？

由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为 a 圈；再设该过程总共遍历了 b 个元素。因此，我们有an=bk,即 an 一定为 n,k的公倍数。又因为我们在第一次回到起点时就结束，因此 a 要尽可能小，故 an 就是 n,k的最小公倍数 lcm(n,k)，因此 b=lcm(n,k)/k。
这说明单次遍历会访问到lcm(n,k)/k 个元素。为了访问到所有的元素，我们需要进行遍历的次数为
n/lcm(n,k)/k=gcd(n,k)
所以遍历前 gcd(n,k)个元素即可

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

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。