算法: 前缀和题目练习
前缀和题目练习
前缀和
自己写出来了~
坑:
- 数据太大,要用long.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
long[] arr = new long[n];
long[] dp = new long[n+1];
for(int i=0;i<n;i++) {
arr[i] = in.nextLong();
dp[i+1] = arr[i] + dp[i];
}
while(q-- > 0){
int l = in.nextInt();
int r = in.nextInt();
System.out.println(dp[r]-dp[l-1]);
}
}
}
题解代码:
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
long[] arr = new long[n+1];
long[] dp = new long[n+1];
for(int i=1;i<=n;i++) {
arr[i] = in.nextLong();
dp[i] = arr[i] + dp[i-1];
}
while(q-- > 0){
int l = in.nextInt();
int r = in.nextInt();
System.out.println(dp[r]-dp[l-1]);
}
}
}
二维前缀和
自己写出来了~
在往二维数组存数据的时候,内层循环用错了,应该用 m,而不是 n.
在最后计算结果的时候,最开始没有算的太明白.
dp[i][j] 计算的是它左上方所有元素的和(包括自己)~
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
long[][] arr = new long[n+1][m+1];
long[][] dp = new long[n+1][m+1];
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
arr[i][j]=in.nextInt();
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
dp[i][j] = dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+arr[i][j];
// System.out.printf("%d ",dp[i][j]);
}
// System.out.println();
}
while(q-- > 0) {
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
System.out.println(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]);
}
}
}
寻找数组的中心下标
我的第一反应是想用一个sum计算所有元素的和,然后除 2 得到 target,接着再使用滑动窗口寻找这个target , 发现行不通,因为数组中可能有负数和0~
自己写出来了~
坑:
- 题目说: 如果有结果,返回最靠左的那一个~
class Solution {
public int pivotIndex(int[] nums) {
int[] dp = new int[nums.length];
dp[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
dp[i] = dp[i + 1] + nums[i];
}
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == dp[i])
return i;
}
return -1;
}
}
除自身以外数组的乘积
自己写出来了~
优化前(空间复杂度 O(N) ):
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] dp1 = new int[n];
int[] dp2 = new int[n];
int[] ret = new int[n];
dp1[0] = nums[0];
for (int i = 1; i < n; i++) {
dp1[i] = dp1[i - 1] * nums[i];
}
dp2[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
dp2[i] = dp2[i + 1] * nums[i];
}
ret[0] = dp2[1];
ret[n - 1] = dp1[n - 2];
for (int i = 1; i < n - 1; i++) {
ret[i] = dp1[i - 1] * dp2[i + 1];
}
return ret;
}
}
优化后(空间复杂度 O(1) ):
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ret = new int[n];
// 计算前面元素的乘积
ret[0] = nums[0];
for (int i = 1; i < n - 1; i++) {
ret[i] = ret[i - 1] * nums[i];
}
ret[n - 1] = ret[n - 2];
// 用sum表示后面元素的乘积
int sum = nums[n - 1];
for (int i = n - 2; i > 0; i--) {
ret[i] = ret[i - 1] * sum;
sum *= nums[i];
}
ret[0] = sum;
return ret;
}
}
和为 K 的子数组
因为数组中的元素有小于等于0的数,所以不能使用滑动窗口来解题~
没写出来.
- 在 [0 , i - 1] 区间内,有多少个前缀和等于 sum[i] - k
- 使用哈希表<前缀和,出现次数>
- 1,2 都懂, 到 3 的时候有点晕.
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
HashMap<Integer, Integer> hash = new HashMap<>();
int ret = 0;
int sum = 0;
hash.put(0, 1);
for (int i = 0; i < n; i++) {
sum += nums[i];
ret += hash.getOrDefault(sum - k, 0);
hash.put(sum, hash.getOrDefault(sum, 0) + 1);
}
return ret;
}
}
和可被 K 整除的子数组
没写出来,但是写了个大概,就差一点,
就差 sum = (sum % k + k) % k; 这一句话…
遇到取余就满头包~
写这道题需要知道两个前置知识.
-
同余定理
如果(a - b) % n == 0那么我们可以得到一个结论:a % n == b % n. -
修正负数取模的结果
为了防止出现负数的情况,可以使用(a % n + n) % n的形式保证输出结果为正.
public int subarraysDivByK(int[] nums, int k) {
int sum = 0;
int ret = 0;
int n = nums.length;
HashMap<Integer, Integer> hash = new HashMap<>();
hash.put(0, 1);
for (int i = 0; i < n; i++) {
sum += nums[i];
sum = (sum % k + k) % k;
ret += hash.getOrDefault(sum, 0);
hash.put(sum, hash.getOrDefault(sum, 0) + 1);
}
return ret;
}
连续数组
这一次 HashMap 中存的就不是数字出现的次数了,而是数字出现的下标.
class Solution {
public int findMaxLength(int[] nums) {
int ret = 0;
int n = nums.length;
HashMap<Integer,Integer> hash = new HashMap<>();
int sum = 0;
hash.put(0,-1);
for(int i=0;i<n;i++) {
sum += nums[i] == 0?-1:1;
if(hash.containsKey(sum)) {
ret = Math.max(ret,i - hash.get(sum));
}else {
// 当不包含 sum 时,放进hash中
// 当 hash 中已经包含 sum 时,不必再放入
// ret = i - hash.get(sum)
// 我们要求的是最大值,因此hash.get(sum)越小越好,
// 而新 put 进来的下标i 一定没有 之前的下标小
// 也就是说新的hash.get(sum)比旧的hash.get(sum)大
// 用一句话概括:
// 当 hash 中已经包含 sum 时,此时再更新i的话 ret 会变小
// 因此要写 else
hash.put(sum,i);
}
}
return ret;
}
}
矩阵区域和
坑;
-
范围容易找错
-
如果善用 Math 方法更好一点~
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
int[][] ret = new int[m][n];
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = mat[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int a = Math.min(i+k+1,m);
int b = Math.min(j+k+1,n);
int c = Math.max(i-k+1,1);
int d = Math.max(j-k+1,1);
ret[i][j] = dp[c-1][d-1] - dp[c-1][b] - dp[a][d-1] + dp[a][b];
}
}
return ret;
}
}
本文到这里就结束啦~
原文地址：https://blog.csdn.net/qrwitu142857/article/details/142719118
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！