做正规网站有哪些,免费ppt模板下载医学,软件技术可以从事什么工作,东莞营销网站建设服务209. 长度最小的子数组
题目#xff1a;
给定一个包含正整数的数组 nums 和一个正整数 target #xff0c;找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0。
示例#xff1a;
示例 1…209. 长度最小的子数组
题目
给定一个包含正整数的数组 nums 和一个正整数 target 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 并返回其长度。如果不存在符合条件的子数组返回 0。
示例
示例 1
输入: target 7, nums [2,3,1,2,4,3]输出: 2解释: 子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2
输入: target 4, nums [1,4,4]输出: 1
示例 3
输入: target 11, nums [1,1,1,1,1,1,1,1]输出: 0
提示
1 target 10^91 nums.length 10^51 nums[i] 10^5
进阶
如果你已经实现 O(n) 时间复杂度的解法请尝试设计一个 O(n log(n)) 时间复杂度的解法。 暴力解法
class Solution {public int minSubArrayLen(int target, int[] nums) {int result nums.length 1;int sum 0;for (int i 0; i nums.length; i) {sum 0;for (int j i; j nums.length; j) {sum sum nums[j];if (sum target result j - i 1) {result j - i 1;}}}if (result nums.length 1) {return 0;} else {return result;}}
}滑动窗口解法
class Solution {public int minSubArrayLen(int target, int[] nums) {int result nums.length 1;int sum 0;int left 0;for (int i 0; i nums.length; i) {sum sum nums[i];while (sum target) {if (result i - left 1) {result i - left 1;}sum sum - nums[left];left;}}if (result nums.length 1) {return 0;} else {return result;}}
}解题思路
滑动窗口是一种高效解决连续子数组问题的算法特别适用于寻找满足特定条件的最小或最大子数组。该方法的核心思想是在遍历数组时维护一个窗口即子数组当窗口中的元素和满足目标条件时缩小窗口的大小以尝试找到更小的子数组。
步骤
初始化两个指针 left 和 right并使用一个变量 sum 来存储窗口内元素的和。当 right 指针向右扩展时将 nums[right] 加入 sum形成窗口。当窗口内的和大于等于目标 target 时计算当前窗口长度并尝试缩小窗口直到窗口内的和小于 target。在每次窗口满足条件时更新最小子数组长度。
这种方法的时间复杂度为 O(n)因为每个元素在遍历过程中最多只会被访问两次。 59. 螺旋矩阵 II
题目
给你一个正整数 n 生成一个包含 1 到 n^2 的所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵。
示例
输入: n 3输出:
[[1, 2, 3],[8, 9, 4],[7, 6, 5]
]代码
class Solution {public int[][] generateMatrix(int n) {int[][] result new int[n][n];int startx 0;int starty 0;int loop 1;int count 1;int offset 1;int i, j;while (loop n / 2) {for (j starty; j n - offset; j) {result[startx][j] count;count;}for (i startx; i n - offset; i) {result[i][n - offset] count;count;}for (j n - offset; j startx; j--) {result[n - offset][j] count;count;}for (i n - offset; i starty; i--) {result[i][starty] count;count;}startx;starty;offset;loop;}if (n % 2 1) {result[startx][starty] count;}return result;}
}解题思路
螺旋矩阵是一个典型的二维数组遍历问题要求我们按照顺时针的顺序填充一个 n x n 的正方形矩阵。可以通过分层的方式逐步填充矩阵的外圈并不断收缩到内圈。
步骤
通过定义上下左右四个边界即 startx、starty、offset按顺时针方向依次填充每层的矩阵元素。每次循环都减少边界的范围直到边界缩小到中心位置。如果矩阵的阶数 n 为奇数最后剩下中心位置需要单独处理。
这是一种逐步推进的方式按照顺时针方向填充矩阵每次循环都会将一圈元素填满。
区间和问题
题目描述
给定一个长度为 n 的整数数组要求计算多个区间的和。每次查询会给出两个整数 a 和 b表示区间 [a, b]程序需返回该区间内的元素之和。
解题思路
这个问题的核心在于如何高效计算多个区间的和。我们可以通过前缀和技巧来快速处理每次的查询。前缀和数组 p[i] 表示从数组的第一个元素到第 i 个元素的累加和。这样对于任意区间 [a, b]其区间和可以通过前缀和数组快速计算
如果 a 0则区间和为 p[b]即直接得到从第 0 到第 b 元素的累积和。如果 a 0则区间和为 p[b] - p[a-1]即减去 a 之前的累积和部分。
这种方法将每次查询的时间复杂度从 O(n) 降低到了 O(1)大大提高了性能。
代码实现
import java.util.Scanner;public class ArraySum {public static void main(String[] args) {Scanner input new Scanner(System.in);int n input.nextInt(); // 读取数组长度int[] vec new int[n]; // 原始数组int[] p new int[n]; // 前缀和数组int presum 0; // 累积和变量// 构建前缀和数组for(int i 0; i n; i) {vec[i] input.nextInt(); // 读取数组元素presum vec[i];p[i] presum;}// 处理多次区间和查询while(input.hasNextInt()) {int a input.nextInt(); // 起始位置int b input.nextInt(); // 结束位置int sum 0;// 通过前缀和计算区间和if (a 0) {sum p[b];} else {sum p[b] - p[a - 1];}// 输出结果System.out.println(sum);}input.close();}
}开发商购买土地问题
题目描述
开发商计划购买一块矩形土地土地被分为 m * n 的格子每个格子有一个整数表示该格子的价值。开发商希望找到一个方式将该土地划分为两部分并使得这两部分的价值差最小。程序要求输出最小价值差。
解题思路
该问题可以通过逐步累积和的方式进行解决
首先我们需要计算每行和每列的总价值这样我们可以比较在每行或每列切分时的两部分价值差。对于每行累加求和 xp[i]表示第 i 行的价值总和对每列累加求和 yp[j]表示第 j 列的价值总和。然后逐行和逐列累积行、列的总和与整体价值总和的差值进行比较得到最小的差值。
通过这种方法我们可以通过不断尝试在不同位置切分土地找到使得两部分价值差最小的位置。
代码实现
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input new Scanner(System.in);int m input.nextInt(); // 行数int n input.nextInt(); // 列数int[][] vec new int[m][n]; // 土地价值矩阵int[] xp new int[m]; // 每行累积价值int[] yp new int[n]; // 每列累积价值int sum 0; // 总价值int presum 0;// 计算每行的累积价值for(int i 0; i m; i) {presum 0;for (int j 0; j n; j) {vec[i][j] input.nextInt();sum vec[i][j]; // 总价值presum vec[i][j]; // 当前行累积价值}xp[i] presum; // 保存当前行的累积价值}// 计算每列的累积价值for (int j 0; j n; j) {presum 0;for (int i 0; i m; i) {presum vec[i][j]; // 当前列累积价值}yp[j] presum; // 保存当前列的累积价值}int xsum 0;int result Integer.MAX_VALUE;// 找出最小行切割差值for (int i 0; i m; i) {xsum xp[i];result Math.min(result, Math.abs(sum - 2 * xsum));}int ysum 0;// 找出最小列切割差值for (int j 0; j n; j) {ysum yp[j];result Math.min(result, Math.abs(sum - 2 * ysum));}// 输出结果System.out.println(result);input.close();}
}
