当前位置 : 主页 > 编程语言 > java >

977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II

来源:互联网 收集:自由互联 发布时间:2023-09-14
977.有序数组的平方 力扣题目链接(opens new window) 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums =


977.有序数组的平方

力扣题目链接(opens new window)

给你一个按 非递减顺序 排序的整数数组 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]

思路:

数组元素有正有负但有序,平方后,大的数据都在数组两端,小的数据在数组中间.

用双指针方法在数组首尾定义指针,指针的数据平方后相互比较,将大的数据存放在事先定义好的数组中。大的数据所在指针可能在数组左右两端,左边的话,指针应该++,右边的话指针应该--.直至左指针比右指针大

代码如下

// 时间复杂度为O(n)
public class squareOrderedArray {
    public static void main(String args[]) {
        int[] nums = new int[]{-3,-2,-1,0,1,4,5};
        int[] result = squareOrderedArray(nums);
        System.out.println(result);
    }
    public static int[] squareOrderedArray(int[] nums){
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length-1;
        int index = nums.length-1;
        while(left <= right){
            if(nums[left] * nums[left] < nums[right]*nums[right]){
                result[index] = nums[right]*nums[right];
                right--;
                index--;
            }else{
                result[index] = nums[left] * nums[left];
                left++;
                index--;
            }
        }
        return result;
    }
}

问题

需要注意边界条件.如果边界条件是left < right,那么left = right的元素就不会在while循环中存放到新数组中.

让left <= right.

因为当left = right时.数组此时只剩下一个元素,肯定是最小的或者等于最小的.

如果此时去走while循环,执行else里的代码,此时index = 0,那么会将该元素放到新数组最开始的位置,也就满足了题目的要求.

209.长度最小的子数组

力扣题目链接(opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

  • 输入:s = 7, nums = [2,3,1,2,4,3]
  • 输出:2
  • 解释:子数组 [4,3] 是该条件下的长度最小的子数组。

提示:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

思路:

双指针法。 暴力算法是通过双重for循环遍历数组所有元素,找出所有区间比对。先找到区间左侧,然后For循环遍历找区间右侧,也就是先找左区间,然后找右区间。 那么双指针算法如果也像暴力算法一样,先找区间左侧然后,再找区间右侧,跟暴力算法区别不大。所以需要先找区间右侧. 用right指针表示区间右侧,left指针表示区间左侧,不断累加区间之间的数组元素,直至区间之和大于等于target 此时移动左区间left指针,进一步缩小区间范围。找到数组长度并记录。然后继续移动区间右指针重复操作

代码如下

//时间复杂度:O(n)
//空间复杂度:O(1)
public class longestSubarrayLength {
    public static void main(String args[]) {
        int[] nums = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1};
        int target = 6;
        System.out.println(longestSubarrayLength(nums, target));
    }

    public static int longestSubarrayLength(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        boolean flag = false;
        while (right < nums.length) {
            sum = sum + nums[right];
            // 和大于target,移动left指针
            while (sum >= target) {
                sum = sum - nums[left];
                left++;
                flag = true;
            }
            if (flag && right - left + 2 < minLength) {
                minLength = right - left + 2;
                flag = false;
            }
            right++;

        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;

    }
}

59.螺旋矩阵II

力扣题目链接(opens new window)

给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路

循环处理二维数组,循环处理次数等于n/2.

比如:边长为3,循环一圈即可,剩下最中间的元素单独处理,边长为4,循环两圈即可,没有最中间的元素需要处理 需要注意:对每一条边遍历时,要坚持循环不变量原则。即遍历二维数组使用同一个规则,不能这一条边左闭右开,下一条边左开右闭。这里使用左闭右开

比如一个长度为3的二维数组。遍历流程如下 1.处理上行 从左至右 1 2 0 0 0 0 0 0 0 2.处理右列 从上至下 1 2 3 0 0 4 0 0 0 3.处理下行 从右至左 1 2 3 0 0 4 0 6 5 4.处理左列 从下至上 1 2 3 8 0 4 7 6 5

5.边长为奇数,单独处理最中间的元素

代码如下

public class spiralMatrixII {
    public static void main(String args[]) {
        int n = 2;
        System.out.println(spiralMatrixII(n));
    }

//    时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
//    空间复杂度 O(1)
    public static int[][] spiralMatrixII(int n) {
        int nums[][] = new int[n][n];
        int loop = n / 2; // 边长为n的二维数组,循环几圈。比如:边长为3,循环一圈
        int startx = 0;
        int starty = 0;// 当前数组元素位置
        int count = 1;// 数组元素赋值
        int curNum = 1; // 当前处于第几次循环

        while (loop > 0) {
            // 处理上行 从左至右
            while (starty < n - curNum) {
                nums[startx][starty++] = count;
                count++;
            }
            // 处理右列 从上至下
            while (startx < n - curNum) {
                nums[startx++][starty] = count;
                count++;
            }
            // 处理下行 从右至左
            while (starty >= curNum) {
                nums[startx][starty--] = count;
                count++;
            }
            // 处理左列 从下至上
            while (startx >= curNum) {
                nums[startx--][starty] = count;
                count++;
            }
            loop--;
            curNum++;
            startx++;
            starty++;
        }
        if (n % 2 != 0) {
            nums[n / 2][n / 2] = count;
        }
        return nums;

    }
}
网友评论