【14天算法入门】-第2天-双指针

刺骨的言语ヽ痛彻心扉 2022-09-12 10:55 157阅读 0赞

**目录**

1、有序数组的平方

2、旋转数组

--------------------

# 1、有序数组的平方 #

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

public class sortedSquares {
    
        public int[] sortedSquares(int[] nums) {
            //用双指针，能充分利用已有的序
            int n=nums.length;
            int i=0;
            int j=n-1;
            int[] res = new int[n];
    
            int k=n-1;
            while((k>=0)&&(i<=j)){
                if(Math.abs(nums[i]) > Math.abs(nums[j])){
                    res[k] = nums[i]*nums[i];
                    k--;
                    i++;
                }else{
                    res[k] = nums[j] * nums[j];
                    k--;
                    j--;
                }
            }
            return res;
        }
    }

# 2、旋转数组 #

/**
     * 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]
     *
     * 进阶：
     * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
     * 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
     * */

**方法一：头插法**

public static void rotate(int[] nums, int k) {
            //头插法
            int n = nums.length;
            k = k % n;
    
            //k次右移
            while(k>0){
                int tmp = nums[n-1];
                for(int i=n-1;i>0;i--){
                    nums[i] = nums[i-1];
                }
                nums[0] = tmp;
                k--;
            }
        }

**方法二：新增tmp数组**

public void rotate(int[] nums, int k) {
            //新增tmp数组
            int n=nums.length;
            k = k%n;
            int[] res = new int[n];
    
            for(int i=0;i<k;i++){
                res[i] = nums[n-k+i];
            }
    
            for(int i=k;i<n;i++){
                res[i] = nums[i-k];
            }
    
            for(int i=0;i<n;i++){
                nums[i] = res[i];
            }
        }

**方法三：双倍数组**

public void rotate(int[] nums, int k){
            //拉长2倍数组
            int n=nums.length;
            k = k%n;
            int[] res = new int[2*n];
    
            for(int i=0;i<res.length;i++){
                res[i] = nums[i%n];
            }
            for(int i=0;i<n;i++){
                nums[i] = res[n-k+i];
            }
        }

**方法四：3次翻转**

public void rotate(int[] nums, int k){
            //数组3次翻转
            int n=nums.length;
            k = k%n;
            swap(nums,0,n-1);
            swap(nums,0,k-1);
            swap(nums,k,n-1);
        }
    
        public void swap(int[] nums, int i, int j){
            while(i<j){
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
                i++;
                j--;
            }
        }