代码随想录算法训练营day2 | 题目977、题目 209、题目 59
题目一描述
给你一个按 非递减顺序 排序的整数数组 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)的算法解决本问题
解题思路
双指针从两边向中间移动即可，注意left可以等于right
代码实现
方法一：
class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int left = 0;
int right = nums.length - 1;
int i = nums.length - 1;
while (left <= right) { // 是有意义的，比如只有一个元素的情况
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
res[i] = nums[left] * nums[left];
i--;
left++;
} else {
res[i] = nums[right] * nums[right];
i--;
right--;
}
}
return res;
}
}
技巧总结
学会Math.abs()取绝对值
题目二描述
给定一个含有 n个正整数的数组和一个正整数 target。
找出该数组中满足其总和大于等于target的长度最小的 连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 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
进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(nlog(n))时间复杂度的解法。
解题思路
每次有“一段连续的区间这样的情形”，就可以考虑滑动窗口。
滑动窗口实现，也是双指针的一个变种，最好还是记住一个模板，自己现场想就太麻烦了。
代码实现
方法一（自己写的）：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 要找连续子数组。所以不能排序打乱顺序
// 连续子数组，并不是要求数组中的数字是+1 -1 这样连续的，只要位置相邻就是连续
int left = 0;
int right = 0;
int sum = nums[0];
int length = 0;
int result = nums.length + 1;
while (left <= right) {
if (sum < target) {
right++;
if(right == nums.length) break;
sum += nums[right];
} else {
length = right - left + 1;
result = Math.min(length, result);
sum -= nums[left];
left++;
}
}
return result > nums.length ? 0 : result;
}
}
方法二：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 要找连续子数组。所以不能排序打乱顺序
// 连续子数组，并不是要求数组中的数字是+1 -1 这样连续的，只要位置相邻就是连续
int left = 0;
int right = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
int length = 0;
while (right < nums.length) {
sum += nums[right];
right++;
while (sum >= target) {
length = right - left;
result = Math.min(length, result);
sum -= nums[left];
left++;
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
技巧总结
学会滑动窗口的通用模板，两个while循环
/* 滑动窗⼝算法框架 */
void slidingWindow(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < s.size()) {
// c 是将移⼊窗⼝的字符
char c = s[right];
// 增⼤窗⼝
right++;
// 进⾏窗⼝内数据的⼀系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗⼝是否要收缩
while (window needs shrink) {
// d 是将移出窗⼝的字符
char d = s[left];
// 缩⼩窗⼝
left++;
// 进⾏窗⼝内数据的⼀系列更新
...
}
}
}
学会Interger.MAX_VALUE的使用
题目三描述
给你一个正整数 n ，生成一个包含 1 到 n 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例:
示例1.png
输入: 3
输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
提示：
1 <= n <= 20
解题思路
注意根据图片和题意，二维数组的原点在左上角，而不是左下角，根据此来每次固定行或列，填充数字并缩小边界。
代码实现
方法一：
class Solution {
public int[][] generateMatrix(int n) {
// 题目的意思，res[0][0]在左上角
int number = 1;
int[][] res = new int[n][n];
int left_bound = 0, up_bound= 0;
int right_bound = n - 1, down_bound = n - 1;
while (number <= n * n) {
for (int j = left_bound; j <= right_bound; j++) {
//[0][0] [0][2] 确定起始点后写出来，才知道不变的是行还是列
res[up_bound][j] = number;
number++;
}
up_bound++;
for (int i = up_bound; i <= down_bound; i++) { //[0][2] [2][2]
res[i][right_bound] = number;
number++;
}
right_bound--;
for (int j = right_bound; j >= left_bound; j--) { //[2][2] [2][0]
res[down_bound][j] = number;
number++;
}
down_bound--;
for (int i = down_bound; i >= up_bound; i--) { //[2][0] [1][0]
res[i][left_bound] = number;
number++;
}
left_bound++;
}
return res;
}
}
技巧总结
一定要打草稿，不要只用脑袋想。
题目3.1描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
示例1
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
示例2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
解题思路
和之前的不同是，这个题不是n*n，要考虑到根据收缩快的那一边来判断移动有无意义
代码实现
方法一：
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int top_bound = 0;
int bottom_bound = m - 1;
int left_bound = 0;
int right_bound = n - 1;
List<Integer> res = new ArrayList<>();
while (res.size() < m * n) {
if (top_bound <= bottom_bound) {
// 由于不是n*n, 有可能左右边界，或者上下边界收缩的比较慢，上下收缩完了之后，左右移动就无意义了，所以要判断是否还有意义
for (int j = left_bound; j <= right_bound; j++) { // 00-02
res.add(matrix[top_bound][j]);
}
top_bound++;
}
if (left_bound <= right_bound) {
for (int i = top_bound; i <= bottom_bound; i++) {// 02-22
res.add(matrix[i][right_bound]);
}
right_bound--;
}
if (top_bound <= bottom_bound) {
for (int j = right_bound; j >= left_bound; j--) { // 22-20
res.add(matrix[bottom_bound][j]);
}
bottom_bound--;
}
if (left_bound <= right_bound) {
for (int i = bottom_bound; i >= top_bound; i--) { // 20-00
res.add(matrix[i][left_bound]);
}
left_bound++;
}
}
return res;
}
}
技巧总结
List.size()可以得到列表大小
