主页 / user-625572

v v's questions

Martin Hope
v v
Asked: 2024-09-21 23:39:45 +0000 UTC
  • 4

任务：给定一个数字 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