LeetCode 209.长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。
示例
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
题目链接
解题思路
从左往右相加，和超过 target时为符合条件的子数组
- 从当前子数组起点开始减，直到不满足条件为止
- 更新最小长度
// 耗时: 14m14s
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int ans = Integer.MAX_VALUE;
int left = 0, right = 0;
while (right < nums.length) {
sum += nums[right++];
while (sum >= target) {
sum -= nums[left++];
ans = Math.min(right - left + 1, ans);
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
LeetCode 59.螺旋矩阵II
题目描述
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
解题思路
重点弄清流程，什么时候用开区间什么时候用闭区间。以及 n为奇偶，循环次数不一样
// 耗时: 13m32s
class Solution {
public int[][] generateMatrix(int n) {
int[][] ans = new int[n][n];
int count = 1;
int left = 0, top = 0;
int right = n - 1, botton = n - 1;
while (count <= n * n && top < botton && left < right){
// ➡️ [)
for (int j = left; j < right; j++) {
ans[top][j] = count++;
}
// ⬇️ [)
for (int i = top; i < botton; i++) {
ans[i][right] = count++;
}
// ⬅️ [)
for (int j = right; j > left; j--) {
ans[botton][j] = count++;
}
// ⬆️ [)
for (int i = botton; i > top; i--) {
ans[i][left] = count++;
}
top++;
right--;
botton--;
left++;
}
if (n % 2 == 1) {
ans[top][top] = count++;
}
return ans;
}
}
区间和
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
题目链接
https://kamacoder.com/problempage.php?pid=1070
解题思路
前缀和，区间内的元素和为 dp[b] - dp[a]， dp[i]为不包含第 i个元素的前缀和
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
int[] dp = new int[n + 1];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
dp[i + 1] = arr[i] + dp[i];
}
while (in.hasNext()) {
int a = in.nextInt();
int b = in.nextInt();
System.out.println(dp[b + 1] - dp[a]);
}
}
}
44.开发商购买土地（卡码网第五期模拟笔试）
题目描述
在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。
现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分。
输入描述
第一行输入两个正整数，代表 n 和 m。
接下来的 n 行，每行输出 m 个正整数。
输出描述
请输出一个整数，代表两个子区域内土地总价值之间的最小差距。
输入示例
3 3
1 2 3
2 1 3
1 2 3
输出示例
0
题目链接
https://kamacoder.com/problempage.php?pid=1044
解题思路
按照行和列两个维度建立两个数组，分别求对应的前缀和。最后求前缀和一分为二时，差值最小的情况
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] land = new int[n][m];
int[] x = new int[m];
int[] y = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
land[i][j] = in.nextInt();
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
y[i] += land[i][j];
}
if (i > 0) {
y[i] += y[i - 1];
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
x[j] += land[i][j];
}
if (j > 0) {
x[j] += x[j - 1];
}
}
int ans = Integer.MAX_VALUE;
for (int j = 1; j < m; j++) {
ans = Math.min(Math.abs(x[m - 1] - 2 * x[j - 1]), ans);
}
for (int i = 1; i < n; i++) {
ans = Math.min(Math.abs(y[n - 1] - 2 * y[i - 1]), ans);
}
System.out.println(ans);
}
}
评论