【LeetCode】第4天 - 977. 有序数组的平方 | 189. 旋转数组

简介: 【LeetCode】第4天 - 977. 有序数组的平方 | 189. 旋转数组

题目描述

题目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);
    }
}
目录
相关文章
|
2月前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
|
2月前
|
算法
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
|
2月前
|
存储
【合并两个有序数组】LeetCode第88题讲解
【合并两个有序数组】LeetCode第88题讲解
|
19天前
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
|
15天前
【力扣】238. 除自身以外数组的乘积
【力扣】238. 除自身以外数组的乘积
|
15天前
【力扣】80.删除有序数组中的重复项Ⅱ
【力扣】80.删除有序数组中的重复项Ⅱ
|
15天前
|
C++
【力扣】2562. 找出数组的串联值
【力扣】2562. 找出数组的串联值
|
27天前
|
算法 C++ 索引
【力扣经典面试题】238. 除自身以外数组的乘积
【力扣经典面试题】238. 除自身以外数组的乘积
|
27天前
|
存储
【力扣经典面试题】80. 删除有序数组中的重复项 II
【力扣经典面试题】80. 删除有序数组中的重复项 II
|
27天前
|
存储
【力扣经典面试题】合并两个有序数组
【力扣经典面试题】合并两个有序数组

热门文章

最新文章