代码随想录算法训练营day2

数组

 暴力解法 两个for循环 不断的寻找符合条件的子序列，时间复杂度O(n^2)

滑动窗口

循环的索引表示 滑动窗口的终止位置​​​​​​​​​​​​​​

根据当前子序列和大小的情况，不断调节子序列的起始位置 时间复杂度O(n)

class Solution {// 滑动窗口public int minSubArrayLen(int s, int[] nums) {int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= s) {result = Math.min(result, right - left + 1);sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}

209.长度最小的子数组

题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。 拓展题目可以先不做。

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：拿下滑动窗口！ | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili

 59.螺旋矩阵II

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

 二分法一定要坚持循环不变量原则 求解本题依然是要坚持循环不变量原则

 模拟顺时针画矩阵的过程:

上行从左到右

右列从上到下

下行从右到左

左列从下到上

每画一条边都要坚持一致的左闭右开，或者左开右闭的原则

class Solution {public int[][] generateMatrix(int n) {int[][] nums = new int[n][n];int startX = 0, startY = 0;  // 每一圈的起始点int offset = 1;int count = 1;  // 矩阵中需要填写的数字int loop = 1; // 记录当前的圈数int i, j; // j 代表列, i 代表行;while (loop <= n / 2) {// 顶部// 左闭右开，所以判断循环结束时， j 不能等于 n - offsetfor (j = startY; j < n - offset; j++) {nums[startX][j] = count++;}// 右列// 左闭右开，所以判断循环结束时， i 不能等于 n - offsetfor (i = startX; i < n - offset; i++) {nums[i][j] = count++;}// 底部// 左闭右开，所以判断循环结束时， j != startYfor (; j > startY; j--) {nums[i][j] = count++;}// 左列// 左闭右开，所以判断循环结束时， i != startXfor (; i > startX; i--) {nums[i][j] = count++;}startX++;startY++;offset++;loop++;}if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值nums[startX][startY] = count;}return nums;}
}

59.螺旋矩阵II

题目建议： 本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：一入循环深似海 | LeetCode：59.螺旋矩阵II_哔哩哔哩_bilibili

 区间和

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

5
1
2
3
4
5
0 1
1 3

1
2
3
4
5
6
7
8

输出示例

3
9

1
2

数据范围：

0 < n <= 100000

 前缀和的思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数

 统计在vec数组上 下标 2 到下标 5 之间的累加和 用 p[5] - p[1] 就可以了

p[1] = vec[0] + vec[1];

p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];

p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] vec = new int[n];int[] p = new int[n];int presum = 0;for (int i = 0; i < n; i++) {vec[i] = scanner.nextInt();presum += vec[i];p[i] = presum;}while (scanner.hasNextInt()) {int a = scanner.nextInt();int b = scanner.nextInt();int sum;if (a == 0) {sum = p[b];} else {sum = p[b] - p[a - 1];}System.out.println(sum);}scanner.close();}
}

 

区间和

前缀和是一种思维巧妙很实用 而且 很有容易理解的一种算法思想，大家可以体会一下

文章讲解：58. 区间和 | 代码随想录