荆门网站建设电话咨询,做网站年薪百万,国内 wordpress主机,代理注册公司服务977.有序数组的平方
● 力扣题目链接 ● 给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
思路
● 暴力排序#xff0c;时间复杂度O(n nlogn) ● 使用双指针#xff0c;时间复杂度O(n)
…977.有序数组的平方
● 力扣题目链接 ● 给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
思路
● 暴力排序时间复杂度O(n nlogn) ● 使用双指针时间复杂度O(n)
代码
class Solution {public int[] sortedSquares(int[] nums) {int[] res new int[nums.length]; // 返回的数组这个题目没法原地修改int l 0; int r nums.length -1;for (int i res.length - 1; i 0; i--) { // 遍历返回的数组每个元素都要放到适合的位置if (nums[l] * nums[l] nums[r] * nums[r]) {res[i] nums[l] * nums[l]; // 左边大l; // 左指针右移} else {res[i] nums[r] * nums[r]; // 右边大r--; // 右指针左移}}return res;}
}
// 思路一样换成while循环
class Solution {public int[] sortedSquares(int[] nums) {int[] res new int[nums.length];int l 0; int r nums.length - 1;int index nums.length - 1;while (l r) {if (nums[l] * nums[l] nums[r] * nums[r]) {res[index--] nums[l] * nums[l];l;} else {res[index--] nums[r] * nums[r];r--;}}return res;}
}209.长度最小的子数组
● 力扣题目链接 ● 给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。 思路 ● 可以暴力解法外层循环遍历数组内层不断往后看更新长度的最小值 ● 也可以使用滑动窗口 ○ 外层循环遍历数组不断移动快指针加到sum ○ 一旦发现超过target就开始移动慢指针更新res减去元素 ○ 最后看res是否更新过
代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int s 0; int sum 0; int res Integer.MAX_VALUE;for (int f 0; f nums.length; f) { // 外层循环遍历数组sum nums[f];while (sum target) { // 一旦超过targetres Math.min(res, f - s 1); // 更新ressum - nums[s]; // 移动慢指针减去元素}}return res Integer.MAX_VALUE ? 0 : res; // 看res是否更新过}
}59.螺旋矩阵II
● 力扣题目链接 ● 给定一个正整数 n生成一个包含 1 到 n^2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。
思路
● 设置四个边界不断循环处理
代码
class Solution {public int[][] generateMatrix(int n) {int l 0, r n - 1, b 0, t n - 1, num 0, tar n * n;int[][] res new int[n][n];while (num tar) {for (int i l; i r; i) {res[b][i] num;}b;for (int i b; i t; i) {res[i][r] num;}r--;for (int i r; i l; i--) {res[t][i] num;}t--;for (int i t; i b; i--) {res[i][l] num;}l;}return res;}
}54.螺旋矩阵
● 给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。
思路
● 和上一题类似但是需要注意给集合中加元素不要重复
代码
class Solution {public ListInteger spiralOrder(int[][] matrix) {int l 0, m matrix.length - 1, b 0, n matrix[0].length - 1;int r n, t m, num 1;ListInteger res new ArrayList();while (num (m 1) * (n 1)) {for (int i l; i r num (m 1) * (n 1); i) { // 这步判断尽量写上res.add(matrix[b][i]);num;}b;for (int i b; i t num (m 1) * (n 1); i) {res.add(matrix[i][r]);num;}r--;for (int i r; i l num (m 1) * (n 1); i--) {res.add(matrix[t][i]);num;}t--;for (int i t; i b num (m 1) * (n 1); i--) {res.add(matrix[i][l]);num;}l;}return res;}
}剑指 Offer 29.顺时针打印矩阵
● 输入一个矩阵按照从外向里以顺时针的顺序依次打印出每一个数字。
思路
● 与之前思路类似
代码
class Solution {public int[] spiralOrder(int[][] matrix) {if (matrix null || matrix.length 0) return new int[0];int m matrix.length;int n matrix[0].length;int[] res new int[m * n];int index 0, l 0, r n - 1, b 0, t m - 1;while (index res.length - 1) {for (int i l; i r index res.length - 1; i) {res[index] matrix[b][i];}b;for (int i b; i t index res.length - 1; i) {res[index] matrix[i][r];}r--;for (int i r; i l index res.length - 1; i--) {res[index] matrix[t][i];}t--;for (int i t; i b index res.length - 1; i--) {res[index] matrix[i][l];}l;}return res;}
}
