版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434642
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
基本想法:
全部枚举,判断sum == 0,时间复杂度为O(n4)O(n^4),优化,折半枚举。
确定sum意味着给定两个组合,另外一半也将确定,所以可以给出任意两个元素的所有组合,进行折半搜索。sum = a + b,a确定b跟着确定,这是折半的核心思想。这样b的搜索可以采用二分。
总的来说,sum并不关系每个独立的个体具体是什么值,它只关心总和是否等于算,所以sum = a + b + c + d和sum = (a + b) + (c + d),对于sum来说没有区别。既然无区别,干嘛要用独立性如此高的算法O(n4)O(n^4)来实现呢?
当(a + b)看成整体后,它的搜索成本自然就下去了。
代码如下:
void solve() {
int n = ni();
int[] A = new int[n];
int[] B = new int[n];
int[] C = new int[n];
int[] D = new int[n];
for (int i = 0; i < n; ++i){
A[i] = ni();
B[i] = ni();
C[i] = ni();
D[i] = ni();
}
int[] arra = new int[n * n];
for (int i = 0, k = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
arra[k++] = C[i] + D[j];
}
}
Arrays.sort(arra);
long cnt = 0;
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
int key = -(A[i] + B[j]);
int lo = lowBound(arra, key);
int hi = upBound(arra, key);
if (lo == -1 || hi == -1) continue;
cnt += (hi - lo + 1);
}
}
out.println(cnt);
}
private int lowBound(int[] arra, int key){
int lf = 0, rt = arra.length - 1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (arra[mid] < key) lf = mid + 1;
else rt = mid;
}
if (arra[rt] == key) return rt;
return -1;
}
private int upBound(int[] arra, int key){
int lf = 0, rt = arra.length - 1;
while (lf < rt){
int mid = lf + (rt - lf + 1) / 2;
if (arra[mid] > key) rt = mid - 1;
else lf = mid;
}
if (arra[lf] == key) return lf;
return -1;
}
全部枚举需要O(2n)O(2^n)次方,OJ不让过,所以可以采用折半的思路,此题和上题相似,无非由于子集的个数不确定,所以有sum = a + b + c …这种情况,且sum不是固定的值,而是尽可能接近0,天啊噜,改了20多次,依旧WA。
思路:
对数据进行划分,分成n/2和n - n/2的两个子集,分别对子集中的所有可能组合枚举,分别得到两个sum1和sum2,令sum1 + sum2尽可能的接近0,所以只要针对某个sum集合进行排序,二分。
自己代码如下:
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
int n = new Integer(br.readLine());
if (n == 0) break;
long[] arra = new long[n];
String input[] = br.readLine().split("\\s");
for (int i = 0; i < n; i++) {
arra[i] = new Long(input[i]);
}
long[] LL = new long[n];
long[] RR = new long[n];
int LN = 0, RN = 0;
for (int i = 0; i < n; i += 2) {
LL[LN++] = arra[i];
if (i + 1 < n)
RR[RN++] = arra[i + 1];
}
if (RN == 0) {
System.out.println(LL[0] + " " + 1);
continue;
}
Sum[] sums = new Sum[1 << RN];
for (int i = 0; i < 1 << RN; ++i) {
long sum = 0;
int cnt = 0;
for (int j = 0; j < RN; ++j) {
if ((i & (1 << j)) != 0) {
sum += RR[j];
cnt++;
}
}
sums[i] = new Sum(sum, cnt);
}
Arrays.sort(sums);
long ans = 1000000000000001l;
int ansc = 36;
for (int i = 0; i < 1 << LN; ++i) {
long key = 0;
int cnt = 0;
for (int j = 0; j < LN; ++j) {
if ((i & (1 << j)) != 0) {
key += LL[j];
cnt++;
}
}
int l = 0;
int r = sums.length;
while (r - l > 1) {
int m = (l + r) / 2;
if (sums[m].sum + key >= 0) {
r = m;
} else {
l = m;
}
}
int L = l;
l = -1;
r = sums.length - 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (sums[m].sum + key > 0) {
r = m;
} else {
l = m;
}
}
int R = r;
for(int k = L; k <= R; ++k){
long tempsum = Math.abs(sums[k].sum + key);
int tempcount = sums[k].cnt + cnt;
if (tempcount == 0) continue;
if(tempsum < ans){
ans = tempsum;
ansc = tempcount;
}
else if(tempsum == ans & tempcount < ansc){
ansc = tempcount;
}
}
}
System.out.println(ans + " " + ansc);
}
}
WA到心碎,正确代码可以参考http://poj.org/showmessage?message_id=346495
思路:
a + b = d - c,所以把等式两边表示出来用个二分就解决了,一开始二分(a+b),但枚举(d-c)需要的次数较大,所以二分(d-c),枚举(a+b),此时只需要n⋅(n−1)/2n \cdot (n - 1) / 2次的二分查询,勉强过了。前者TLE了。
代码如下:
void solve() {
while (true){
int n = ni();
if (n == 0) break;
long[] arra = new long[n];
Map<Long, Integer> map = new HashMap<Long, Integer>();
for (int i = 0; i < n; ++i){
arra[i] = nl();
if (!map.containsKey(arra[i])){
map.put(arra[i], 0);
}
map.put(arra[i], map.get(arra[i]) + 1);
}
TwoSum[] sums = new TwoSum[n * n];
for (int i = 0; i < sums.length; ++i){
sums[i] = new TwoSum(Long.MAX_VALUE, -1, -1);
}
int N = 0;
for (int i = 0; i < n; ++i){
if (map.get(arra[i]) != 1) continue;
for (int j = 0; j < n; ++j){
if (i == j) continue;
sums[N++] = new TwoSum(arra[i] - arra[j], i, j);
}
}
Arrays.sort(sums);
long max = Long.MIN_VALUE;
for (int i = 0; i < n; ++i){
for (int j = i + 1; j < n; ++j){
long key = arra[i] + arra[j];
int lo = loBound(sums, N, key);
int hi = upBound(sums, N, key);
if (lo == -1 || hi == -1) continue;
for (int l = lo; l <= hi; ++l){
TwoSum sum = sums[l];
if (sum.i == i || sum.j == i || sum.i ==j || sum.j == j) continue;
max = Math.max(arra[sum.i], max);
}
}
}
if (max == Long.MIN_VALUE) out.println("no solution");
else out.println(max);
}
}
public int upBound(TwoSum[] sums, int len, long key){
int lf = 0, rt = len - 1;
while (lf < rt){
int mid = lf + (rt - lf + 1) / 2;
if (sums[mid].sum > key) rt = mid - 1;
else lf = mid;
}
if (sums[lf].sum == key) return lf;
return -1;
}
public int loBound(TwoSum[] sums, int len, long key){
int lf = 0, rt = len - 1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (sums[mid].sum < key) lf = mid + 1;
else rt = mid;
}
if (sums[rt].sum == key) return rt;
return -1;
}
class TwoSum implements Comparable<TwoSum>{
long sum;
int i;
int j;
public TwoSum(long sum, int i, int j) {
this.sum = sum;
this.i = i;
this.j = j;
}
@Override
public String toString() {
return "" + sum;
}
@Override
public int compareTo(TwoSum o) {
return this.sum < o.sum ? -1 : 1;
}
}