完整版网站推广方案,金属东莞网站建设技术支持,成品网站分享一下,做淘宝电商比较厉害的网站977. 有序数组的平方
题目链接#xff1a;977. 有序数组的平方
思路#xff1a;双指针思想#xff0c;数组是有序的且含有负数#xff0c;其中元素的平方一定是两边最大。定义两个指针#xff0c;从两端开始向中间靠近#xff0c;每次比较两个指针的元素平方大小#…977. 有序数组的平方
题目链接977. 有序数组的平方
思路双指针思想数组是有序的且含有负数其中元素的平方一定是两边最大。定义两个指针从两端开始向中间靠近每次比较两个指针的元素平方大小将较大的一个存入结果数组。注意结果数组是从小到大的所以要从后往前开始存入
时间复杂度O(n)空间复杂度O(n)
class Solution {public int[] sortedSquares(int[] nums) {int n nums.length;// 两个指针分别初始化在正负子数组绝对值最大的元素索引int i 0, j n - 1;// 得到的有序结果是降序的int p n - 1;int[] res new int[n];// 执行双指针合并有序数组的逻辑// 注意这里要i j因为最后要处理两个元素while (i j) {if (Math.abs(nums[i]) Math.abs(nums[j])) {res[p] nums[i] * nums[i];i;} else {res[p] nums[j] * nums[j];j--;}p--;}return res;}
}也可以使用for循环写法
public int[] sortedSquares(int[] nums) {int left 0, right nums.length - 1;int[] res new int[nums.length];int p res.length - 1;for (int i 0; i res.length; i) {if (nums[left] * nums[left] nums[right] * nums[right]){res[p] nums[left] * nums[left];left;}else {res[p] nums[right] * nums[right];right--;}p--;}return res;
}209. 长度最小的子数组
题目链接209. 长度最小的子数组
思路滑动窗口两个指针代表窗口的左右边界右边界一直遍历到最后当窗口中元素和大于目标值的时候更新结果并且左边界往前走一步。注意这里一定是窗口右边界遍历一次然后根据条件更新左边界。如果左边界作为遍历条件一次循环是解不出来的。
时间复杂度O(n) 为什么时间复杂度是O(n) ? 不要以为双重while就是O(n^2)啊 主要是看每一个元素被操作的次数每个元素在滑动窗口进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)。 class Solution {public int minSubArrayLen(int target, int[] nums) {int i 0; // i代表窗口左边界int j 0; // j为窗口右边界int res nums.length 1; // 定义结果为最大int total 0; // total存放窗口中元素和while (j nums.length) {total total nums[j];j;// 窗口中元素符合题意更新结果更新左边界和totalwhile (total target) {res Math.min(res, j - i);total total - nums[i];i;}}return res nums.length 1 ? 0 : res;}
}59. 螺旋矩阵II
题目链接59. 螺旋矩阵II
思路本题并不涉及什么算法就是模拟过程但却十分考察对代码的掌控能力。借用代码随想录中的图片容易理解。注意每次只需要改变二维数组行或列的坐标。 时间复杂度O(n)
class Solution {public int[][] generateMatrix(int n) {int[][] matrix new int[n][n];int upper_bound 0, lower_bound n - 1;int left_bound 0, right_bound n - 1;// 需要填入矩阵的数字int num 1;while (num n * n) {if (upper_bound lower_bound) {// 在顶部从左向右遍历for (int j left_bound; j right_bound; j) {matrix[upper_bound][j] num;}// 上边界下移upper_bound;}if (left_bound right_bound) {// 在右侧从上向下遍历for (int i upper_bound; i lower_bound; i) {matrix[i][right_bound] num;}// 右边界左移right_bound--;}if (upper_bound lower_bound) {// 在底部从右向左遍历for (int j right_bound; j left_bound; j--) {matrix[lower_bound][j] num;}// 下边界上移lower_bound--;}if (left_bound right_bound) {// 在左侧从下向上遍历for (int i lower_bound; i upper_bound; i--) {matrix[i][left_bound] num;}// 左边界右移left_bound;}}return matrix;}
}数组题目总结
数组的题目的主要解法有以下几种
二分法
遇到有序数组需要进行查找操作的时候可以考虑二分法。
双指针法
双指针法里面比较重要的是快慢指针法。当一个指针无法解题或者需要使用一次循环完成两次循环里才能解决的问题时需要考虑使用双指针。双指针的种类很多滑动窗口也可以看作双指针法。
滑动窗口
滑动窗口是一种很巧妙的方法可以不断的调节子序列的位置。当我们遇到需要查找符合条件的子序列时可以考虑滑动窗口。
模拟行为
这种题目就是考察代码逻辑能力但是要注意遵守循环不变量原则二分法中也用到了循环不变量原则其实就是保证循环过程中定义的循环范围不要改变例如不要再一个开区间的循环中做闭区间的循环操作这样的代码逻辑十分混乱。
