主页 / 问题 / 1594462
Accepted
v v
Asked:2024-09-21 23:39:45 +0000 UTC2024-09-21 23:39:45 +0000 UTC

运行时优化

  • 772

任务：给定一个数字 N。N<=1,000,000 分为集合 1...N，检查该集合是否可以表示为两个集合，使得每个集合的总和等于 N/2。例如：N=11，输出：[[1,2,4,5,6,7,8],[3,9,10,11]]。那里和那里 33.

我的代码不适用于大数字。我用爪子写了一些又大又臭的东西：

import java.util.*;
import java.util.ArrayList;
import java.util.List;

public class CreateTwoSetsOfEqualSum {
  
  
    public static List<List<Integer>> createTwoSetsOfEqualSum(int n) {
      
      List<List<Integer>> sets = new ArrayList<>();
      
    int tmp = 0;
    int sum1 = 0;       

List<Integer> list = new ArrayList<>();

List<Integer> res1 = new ArrayList<>(); 

List<Integer> res2 = new ArrayList<>();

        for(int i=1; i<=n; i++){

            tmp += i;

            list.add(i);

        }


        if(tmp % 2 > 0){
sets.add(new ArrayList<>());
sets.add(new ArrayList<>());
            return sets;

        } else {

            tmp /= 2;

            int i = list.size()-1;

            

            while(sum1 < tmp && i>0){

                if(sum1+list.get(i) < tmp){

                   res1.add(list.get(i));

                   sum1 += list.get(i);

                 } else

                 while(sum1 != tmp){

                    if(sum1+list.get(i)==tmp){

                        sum1 += list.get(i);
                        res1.add(list.get(i));

                        break;

                    } else {

                        i--;

                    }

                 }

                 i--;

            }

            for(int a=0; a<res1.size(); a++){

                for(int j=0; j<list.size(); j++){

                    if(res1.get(a)==list.get(j)){

                        list.remove(list.get(j));

                    }

                }

            }

        Collections.reverse(res1);

sets.add(new ArrayList<>());
sets.add(new ArrayList<>());

for(int l : res1){
  sets.get(0).add(l);
  }
for(int l : list){
  sets.get(1).add(l);
  }

return sets;
 }

}
}

int tmp、int sum1 不适合，因为2^31-1 等...长 - 执行时间 16000ms 像这样的：

Test Results:
SolutionTest
randomTests()
STDERR
Execution Timed Out (16000 ms)

测试：

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertTrue;

class SolutionTest {
    @Test
    void fixedTests()  {
        for (int i = 1; i <= 10; i++) {
            final ResultMessage verification =  Preloaded.validateTwoSetsOfEqualSum(i, CreateTwoSetsOfEqualSum.createTwoSetsOfEqualSum(i));
            final boolean result = verification.result;
            final String message = verification.message;
            assertTrue(result,  "i = " + i + " Result: " + message);
        }
    }
}

也许我们不应该受虐，而是直接将数字输入到子列表中。 告诉我一些聪明的事情）

java

2 个回答

  1. 解决方案非常简单。需要更多代码才能输出解决方案。

        public static void main(String[] args) {
        for (int i = 1; i < 100; i++) {
            System.out.println("N = " + i);
            Set<Integer> toMove1;
            Set<Integer> toMove2;
            boolean impossible;
            switch (i % 4) {
                case 0:
                    impossible = false;
                    if (i / 4 % 2 == 0) {
                        toMove1 = Set.of();
                        toMove2 = Set.of(i / 4);
                    } else {
                        toMove1 = Set.of(1);
                        toMove2 = Set.of(i / 4 + 1);
                    }
                    break;
                case 1, 2:
                    impossible = true;
                    System.out.println("impossible");
                    toMove1 = Set.of();
                    toMove2 = Set.of();
                    break;
                case 3:
                    impossible = false;

                    if (i / 4 % 2 == 0) {
                        toMove1 = Set.of(i / 4 + 1);
                        toMove2 = Set.of();
                    } else {
                        toMove1 = Set.of(i / 4, i / 4 + 2);
                        toMove2 = Set.of(i / 4 + 1);

                    }
                    break;
                default:
                    throw new RuntimeException();
            }
            List<Integer> g1 = Stream.concat(
                            toMove2.stream(),
                            odd(i).filter(j -> !toMove1.contains(j)))
                    .toList();
            List<Integer> g2 = Stream.concat(
                    toMove1.stream(),
                    even(i).filter(j -> !toMove2.contains(j))
            ).toList();
            int sumG1 = g1.stream().mapToInt(Integer::intValue).sum();
            System.out.println("sum g1 = " + sumG1 + " g1 = " + g1);
            int sumG2 = g2.stream().mapToInt(Integer::intValue).sum();
            System.out.println("sum g2 = " + sumG2 + " g2 = " + g2);
            if (sumG1 != sumG2 && !impossible) {
                System.out.println("ERROR");
            }
        }
    }

    private static Stream<Integer> even(int i) {
        return IntStream.range(1, i + 1)
                .filter(j -> j % 2 == 0)
                .boxed();
    }

    private static Stream<Integer> odd(int i) {
        return IntStream.range(1, i + 1)
                .filter(j -> j % 2 == 1)
                .boxed();
    }
    • 1
  2. Best Answer

    第一个选项：

    1. 从1到NS的总和=(N^2+N)/2。一定要均匀。让我们将一半和表示为 M=S/2。
    2. 第一个子集的上限为K=INT(0.5+SQRT(0.25+(N^2+N)/2))。也就是说，第一个子集是从 1 到 K，第二个子集是从 K+1 到 N。
    3. 从第一个子集中，您需要将 ((K^2+K)/2-M)/2 代入第二个数字。

    第二个选项：

    // это не Java, если что
int M = N + 1, lim = (N >> 1) + (N & 1);
for (int i = 1; i < lim; i += 2) {
  set1.Add(i); set1.Add(M - i);
  set2.Add(i + 1); set2.Add(N - i);
}
    • 1

相关问题