1. 数组之差TapeEquilibrium Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.
2024-09-08 10:26:51
数组之差
package com.code; public class Test03_3 {
public static int solution(int[] A) {
int size = A.length;
if (size<2){
return -1;
}
int [] rightSum = new int[size];
rightSum[size-1] = A[size-1];
for(int i=size-2;i>=0;i--){
rightSum[i] = A[i]+rightSum[i+1];
}
int [] leftSum = new int[size];
leftSum[0] = A[0];
for(int i=1;i<size-1;i++){
leftSum[i] = A[i]+leftSum[i-1];
}
int min = 2147483647;
for(int i=0;i<size-1;i++){
min = Math.min(min, Math.abs(leftSum[i]-rightSum[i+1]));
}
return min;
}
public static void main(String[] args) {
int a [] = {3,1,2,4,3};
System.out.println(solution(a));
int b[] = {1,3};
System.out.println(solution(b));
}
} /** A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1]. The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| In other words, it is the absolute difference between the sum of the first part and the sum of the second part. For example, consider array A such that: A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
We can split this tape in four places: P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7
Write a function: class Solution { public int solution(int[] A); } that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved. For example, given: A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
the function should return 1, as explained above. Assume that: N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
Complexity: expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
*/
最新文章
- nginx负载均衡集群
- Lua 学习笔记(八)错误(error)
- 【学】React的学习之旅1
- 【js】将table的每个td的内容自动赋值给其title属性
- ajax 、ajax的交互模型、如何解决跨域问题
- POJ2449 (k短路)
- C语言 负数取余的原理
- vim操作笔记
- poj1942 Paths on a Grid
- 时隔一年,window.scroll
- git revert all changes
- ImageView 设置OnTouchListener
- C++中的namespace
- mvp框架
- ImageMagick的安装及使用
- 老司机实战Windows Server Docker:4 单节点Windows Docker服务器简单运维(下)
- 【山东省选2008】郁闷的小J 平衡树Treap
- CentOS7使用yum安装配置Redis
- Postgresql-模糊匹配大杀器
- POJ 2676 Sudoku (数独 DFS)