leetcode-T977有序数组的平方
解法一：暴力破解法
先将数组中的元素遍历变成平方，再进行冒泡排序。
class Solution { public int[] sortedSquares(int[] nums) { for(int i = 0; i < nums.length; i++) { nums[i] = nums[i] * nums[i]; } for(int i = 0; i < nums.length; i++) { for(int j=i+1; j < nums.length; j++) { if(nums[i] > nums[j]) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } } return nums; } }
上面冒泡排序让算法的时间复杂度变成了O(n+n^2),可以换成快速排序。如果您还不知道什么是快速排序，可以参考博客:快速排序
class Solution { public int[] sortedSquares(int[] nums) { for(int i = 0; i < nums.length; i++) { nums[i] = nums[i] * nums[i]; } quickSort(nums, 0, nums.length-1); return nums; } public void quickSort(int[] nums,int left, int right) { if(left > right) { return; } int i = left, j = right, base = nums[i]; while(i != j) { while(i<j && nums[j] >= base ) { j--; } while(i<j && nums[i] <= base) { i++; } int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } nums[left] = nums[i]; nums[i] = base; quickSort(nums, left, i -1); quickSort(nums, i + 1, right); } }
上面的时间复杂度是O(n + n*logn).
解法2：双指针法
注意到数组本来是有序的，平方和后，大的数在两边，小的数在中间，可以采用两个指针在两边遍历，把大的数移到另一个新的数组。
class Solution { public int[] sortedSquares(int[] nums) { for(int i = 0; i < nums.length; i++) { nums[i] = nums[i] * nums[i]; } int i = 0; int j = nums.length - 1; int[] result = new int[nums.length]; int index = nums.length - 1; while(i <= j) { if(nums[i] >= nums[j]) { result[index--] = nums[i]; i++; } else { result[index--] = nums[j]; j--; } } return result; } }
此时的时间复杂度为O(2*n),空间复杂度为O(n),注意到数据的平方操作和排序可以用一次遍历解决，优化如下。
class Solution { public int[] sortedSquares(int[] nums) { int i = 0; int j = nums.length - 1; int[] result = new int[nums.length]; int index = nums.length - 1; while(i <= j) { if(nums[i] * nums[i] >= nums[j] * nums[j]) { result[index--] = nums[i] * nums[i]; i++; } else { result[index--] = nums[j] * nums[j]; j--; } } return result; } }
总结下：
1.数组的最优解法需要观察数据的特点，比如这道题目的数组元素有两边大，中间小的特点
2.双指针法灵活、高效、好用
leetcode-T209 长度最小的子数组
法1：暴力解决法
从第一个元素开始遍历数组元素累加，当累加值到达target记录为最小长度。再从第二个元素，第三个元素开始做同样操作，并且不断对比最小长度是否需要进行更新。其时间复杂度为O(n^2),空间复杂度为O(1)
class Solution { public int minSubArrayLen(int target, int[] nums) { int minLen = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { int sum = 0; int l = 0; for( int j = i;j < nums.length;j++) { sum += nums[j]; l++; if(sum >= target) { // minLen = l < minLen ? l : minLen; if(l < minLen) { minLen = l; } break; } } } // return minLen == Integer.MAX_VALUE ? 0 : minLen; if(minLen == Integer.MAX_VALUE) { minLen = 0; } return minLen; } }
法2：滑动窗口法
所谓滑动窗口，就是不断的调整子序列的起始位置和终止位置，从而得出我们想要的结果。其实，滑动窗口法还是一种双指针法。
💐使用滑动窗口法需要确定几点
1.窗口(两个指针)内是什么
2.窗口起始位置(起始指针)怎么移动
3.窗口结束位置(结束指针)怎么移动
我们来回答下。
1.窗口内容就是满足其和>=target的最小树组
2.如果当前窗口满足条件，起始位置就需要向前移动(缩小窗口)
3.窗口的结束指针就是数组的遍历索引。
可以看出，解题的关键就在于窗口的起始位置如何移动？
其核心逻辑如下。
while(sum >= target) { subLen = j -i + 1; minLen = minLen < subLen ? minLen : subLen; sum -= nums[i++]; }
来看完整代码。
class Solution { public int minSubArrayLen(int target, int[] nums) { int minLen = Integer.MAX_VALUE; int sum = 0; int i = 0; int subLen = 0; for (int j = 0; j < nums.length; j++) { sum += nums[j]; while(sum >= target) { subLen = j -i + 1; minLen = minLen < subLen ? minLen : subLen; sum -= nums[i++]; } } return minLen == Integer.MAX_VALUE ? 0 : minLen; } }
它的时间复杂度是多少呢？虽然这个方法同样有一个for，一个while，但是每个数组元素只被操作了两次，也就是滑动窗口进来操作了一次，滑动窗口除去操作了一次，时间复杂度是O(n)，妙阿。
Leetcode-T59 螺旋矩阵II
这道题目其实不涉及太多算法，却能很好的考察思维能力和编程能力。题目中做的事情无非就是对数组进行上、下、左、右四个方向的遍历，遍历要想不重复、不遗漏一定需要有合理的规则。
我们先以三阶矩阵为例子来画下四条边，采取的规则是：左闭右开。
发现没有，定了规则以后就不乱了，三阶矩阵画边就是每个边界走两步。
边画好了，中间填下最后一个数就好了。
这个时候思维再进一步，四阶矩阵要怎么画？
第一步，四阶矩阵先画边。
第二步，剩下的就是一个三阶矩阵。
class Solution { public int[][] generateMatrix(int n) { int [][] matrix = new int[n][n]; // 定义存储的二维数组 int start = 0; // 定义起始位置 int round = 0; // 控制循环次数 int i,j; // 指针 int count = 1; // 定义填充数字 while(round++ < n/2) { // 右 for(j = start;j < n - round; j++) { matrix[start][j] = count++; } // 下 for(i = start; i < n - round; i++) { matrix[i][j] = count++; } // 左 for(; j >= round; j--) { matrix[i][j] = count++; } // 上 for(; i >= round; i--) { matrix[i][j] = count++; } // 更新起始位置 start++; } // n为奇数时，要单独填充最后一个元素 if(n % 2 == 1) { matrix[start][start] = count; } return matrix; } }
