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 List<Integer> spiralOrder(int[][] matrix) {int l = 0, m = matrix.length - 1, b = 0, n = matrix[0].length - 1;int r = n, t = m, num = 1;List<Integer> 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;}
}
