代码随想录day2| 209.长度最小的子数组、 59.螺旋矩阵II、区间和、开发商购买土地
209.长度最小的子数组
知识点
滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
寻找子数组使用滑动窗口可以将O(n^2)的复杂度降到O(n)
步骤
- 定义快慢指针s、f （寻找子数组）
- 由于题目只需要返回最小数组的长度，而不是具体的数组，所以只需要一个min来记录最小长度，用cnt来记录当前窗口中数的和。
- 用for循环遍历f，来操作f，f每次加一都要更新cnt的值；
- 当cnt>=target时，用while循环来操作s指针，s每次加一，更新cnt的值
- 直到cnt<target,移动f（快指针），以此增加cnt的值
总结
（窗口中）数组和大了移动慢指针，数组和小了移动快指针，以此方法来寻找所有满足条件的子数组，并在这个过程中记录每个子数组的长度，更新在最小值min中，最后返回即可。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int s = 0;
int f = 0;
int cnt = 0;
int min = -1;
for( ; f < nums.length ; f++){
cnt+=nums[f];
while(cnt>=target){
if(min == -1){
min = f-s+1;
}
min = f-s+1 < min?(f-s+1):min;
cnt -= nums[s++];
}
}
return min == -1?0:min;
}
}
代码优化
class Solution {
// 滑动窗口
public int minSubArrayLen(int target, int[] nums) {
int s= 0;
int cnt= 0;
int min= Integer.MAX_VALUE;
for (int f= 0; f< nums.length; f++) {
cnt+= nums[f];
while (cnt>= target) {
min= Math.min(min, right - left + 1);
cnt-= nums[s++];
}
}
return min== Integer.MAX_VALUE ? 0 : min;
}
}
59.螺旋矩阵II
步骤
- 首先想清楚一圈循环这么操作，这里我采用循环不变量：左开右闭，定义四个for循环操作 和 i，j，指针。
- 一圈的逻辑串通以后，再在四个for循环外层加入while循环，控制要转几圈。
- 转几圈需要考虑n（新数组的宽高）的大小，奇数和偶数两种情况，找出while循环条件为n>1,每次循环结束n-=2;
- 随着每圈的变化（while循环），每圈的起始位置和终止位置都有所变化，单独抽出两个变量start ，end 来控制
- 最后判断n为奇数时最后会有中心一个空位置，填上即可。
class Solution {
public int[][] generateMatrix(int n) {
int j = 0;
int i = 0;
int num = 0;
int start = 0;
int end = n-1;
int[][] matrix = new int[n][n];
while(n>1){
for(;j<end;j++){
matrix[i][j] = ++num;
}
for(;i<end;i++){
matrix[i][j] = ++num;
}
for(;j>start;j--){
matrix[i][j] = ++num;
}
for(;i>start;i--){
matrix[i][j] = ++num;
if(i == 1 && j == 0){
System.out.print("| " +matrix[i][j] + " | ");
}
}
i++;
j++;
start++;
end--;
//start,end不能和n共用，要分开控制！！
n-=2;
}
if(n == 1){
matrix[i][j] = ++num;
}
return matrix;
}
}
区间和
知识点
- 暴力解法的时间复杂度是 O(n * m) m ，使用前缀和，重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。
- 具体思路
代码实现
import java.util.Scanner;
public class Main{
public static void main(String[] args ){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
int cnt = 0;
for(int i = 0 ; i < n ; i++){
cnt+=scanner.nextInt();
arr[i] = cnt;
}
while(scanner.hasNextInt()){
int i = scanner.nextInt();
int j = scanner.nextInt();
int sum;
if (i == 0) {
sum = arr[j];
} else {
sum = arr[j] - arr[i - 1];
}
System.out.println(sum);
}
}
}
开发商购买土地
这道题也是使用的前缀和：具体思路
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] vec = new int[n][m];
int cnt = 0;
for(int i = 0 ; i <n ; i++){
for(int j = 0 ; j <m ; j++){
vec[i][j] = scanner.nextInt();
cnt += vec[i][j];
}
}
int[] vecx = new int[n];
for(int i = 0 ; i <n ; i++){
int sum = 0;
for(int j = 0 ; j <m ; j++){
sum += vec[i][j];
}
vecx[i] = sum;
}
int[] vecy = new int[m];
for(int j = 0 ; j <m ; j++){
int sum = 0;
for(int i = 0 ; i < n ; i++){
sum += vec[i][j];
}
vecy[j] = sum;
}
int min = Integer.MAX_VALUE;
int sumy = 0;
for(int i = 0 ; i<m-1;i++){
sumy+=vecy[i];
int dif = Math.abs(cnt-2*sumy);
min = dif<min?dif:min;
}
int sumx = 0;
for(int i = 0 ; i<n-1;i++){
sumx+=vecx[i];
int dif = Math.abs(cnt-2*sumx);
min = dif < min ? dif : min;
}
System.out.print(min);
}
}
总结反思
- 模拟题目先想清楚思路，写出伪代码，再慢慢调试代码，看写出的代码是不是之前想的思路
原文地址：https://blog.csdn.net/m0_68516464/article/details/143000782
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！