算法_前缀和

DP34 【模板】前缀和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt(),q = in.nextInt();
        int[] arr = new int[n+1];
        for(int i = 1; i < n+1; i++){
            arr[i] = in.nextInt();
        }
        long[] dp = new long[n+1];
        for(int i = 1; i < n+1; i++){
            dp[i] = dp[i-1] + arr[i];
        }
       while(q > 0){
        int l = in.nextInt(), r = in.nextInt();
        System.out.println(dp[r] - dp[l-1]);
        q--;
       }
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
    }
}

DP35 【模板】二维前缀和

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(), m = in.nextInt(), q = in.nextInt();
        int[][] arr = new int[n+1][m+1];
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < m+1; j++){
                arr[i][j] = in.nextInt(); 
            }
        }
        long[][] dp= new long[n+1][m+1];
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < m+1; j++){
                dp[i][j] = dp[i][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1];
            }
        }
        while(q > 0){
            int x1 = in.nextInt(),y1 = in.nextInt(),
            x2 = in.nextInt(),y2 = in.nextInt();
            System.out.println(dp[x2][y2]-dp[x1-1][y2]
             - dp[x2][y1-1] + dp[x1-1][y1-1]);
            q--;
        }
        // 注意 hasNext 和 hasNextLine 的区别
    }
}

724. 寻找数组的中心下标

class Solution {
    public int pivotIndex(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = dp[i-1] + nums[i];
        }
        if(0 == dp[nums.length-1] -dp[0] ){
            return 0;
        }
        
        for(int i = 1; i < nums.length; i++){
            if(dp[i-1] == dp[nums.length-1] - dp[i]){
                return i;
            }
        }
        return -1;
    }
}

238. 除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int l = nums.length;
        int[] f = new int[l];  
        int[] g = new int[l];  
        f[0] = 1;
        g[l-1] = 1;  
        for(int i = 1; i < l; i++){
            f[i] = f[i-1]*nums[i-1];
        }
        for(int i = l-2; i >= 0; i--){
            g[i] = g[i+1]*nums[i+1];
        }
        int[] answer = new int[l];
        for(int i = 0; i < l; i++){
        answer[i] = f[i]*g[i];
        }
        return answer;
    }
}