芝士算法（前缀和 1.0）

目录一维数组前缀和二维数组前缀和寻找数组的中心下标除了自身以外数组的乘积一维数组前缀和一维数组前缀和public static void main(String[] args) { Scanner in new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int n in.nextInt() , q in.nextInt(); int[] arr new int[n 1]; for(int i 1 ; i n;i){ arr[i] in.nextInt(); } //预处理前缀和数组 long[] dp new long[n 1 ]; for(int i 1 ; i n;i){ dp[i] dp[i - 1] arr[i]; } //使用前缀和数组 while(q 0){ int left in.nextInt() , right in.nextInt(); System.out.println(dp[right] - dp[left - 1]); q--; } }二维数组前缀和二维数组前缀和public static void main(String[] args) { Scanner in new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { //写入数据 int n in.nextInt(), m in.nextInt(), q in.nextInt(); int[][] arr new int[n 1][m 1]; for (int i 1 ; i n ; i) { for (int j 1 ; j m ; j) { arr[i][j] in.nextInt(); } } //预处理 dp 表示 1-1 到 i-j 的所有和 long[][] dp new long[n 1][m 1]; for (int i 1 ; i n ; i) { for (int j 1 ; j m ; j) { dp[i][j] dp[i - 1][j] dp[i][j - 1] - dp[i-1][j-1] arr[i][j]; } } while(q0){ 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--; } } }避免越界 所以数组的创建 都是从11开始寻找数组的中心下标寻找数组的中心下标public int pivotIndex(int[] nums) { int n nums.length; int[] f new int[n]; int[] g new int[n]; //预处理 for(int i 1; in; i) f[i] f[i - 1] nums[i - 1]; for(int i n - 2; i0; i--) g[i] g[i 1] nums[i 1]; // for(int i 0 ;in ; i){ if(f[i] g[i]) return i; } return -1; }除了自身以外数组的乘积除了自身以外数组的乘积public int[] productExceptSelf(int[] nums) { int n nums.length; int []j new int[n]; int []q new int[n]; //预处理 j[0] q[n - 1 ] 1; for(int i 1; in; i ) j[i] j[i - 1] * nums[i - 1]; for(int i n - 2; i0;i--) q[i] q[i 1] * nums[i 1 ]; // int [] ret new int [n]; for(int i 0; in; i) ret[i] q[i] * j[i]; return ret; }