Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8682fc7

Browse files
committed
com sum2
1 parent290e600 commit8682fc7

File tree

3 files changed

+103
-2
lines changed

3 files changed

+103
-2
lines changed

‎combination/CombinationSum2_1203.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
packageAlgorithms.combination;
2+
importjava.util.ArrayList;
3+
importjava.util.Arrays;
4+
importjava.util.List;
5+
6+
publicclassCombinationSum2_1203 {
7+
publicList<List<Integer>>combinationSum2(int[]num,inttarget) {
8+
List<List<Integer>>ret =newArrayList<List<Integer>>();
9+
if (num ==null ||num.length ==0) {
10+
returnret;
11+
}
12+
13+
Arrays.sort(num);
14+
15+
dfs(num,target,newArrayList<Integer>(),ret,0);
16+
returnret;
17+
}
18+
19+
publicvoiddfs1(int[]num,inttarget,ArrayList<Integer>path,List<List<Integer>>ret,intindex) {
20+
if (target ==0) {
21+
ret.add(newArrayList<Integer>(path));
22+
return;
23+
}
24+
25+
if (target <0) {
26+
return;
27+
}
28+
29+
// 注意，这里从 i = index开始
30+
// 每次只取第一个，例如 123334，到了333这里，我们第一次只取第1个3，因为我们选任何一个3是对组合来说是一个解。所以只
31+
// 第一次取就好了。
32+
intpre = -1;
33+
for (inti =index;i <num.length;i++) {
34+
intn =num[i];
35+
if (n ==pre) {
36+
continue;
37+
}
38+
pre =n;
39+
path.add(n);
40+
dfs(num,target -n,path,ret,i +1);
41+
path.remove(path.size() -1);
42+
}
43+
}
44+
45+
publicvoiddfs(int[]num,inttarget,ArrayList<Integer>path,List<List<Integer>>ret,intindex) {
46+
if (target ==0) {
47+
ret.add(newArrayList<Integer>(path));
48+
return;
49+
}
50+
51+
if (target <0) {
52+
return;
53+
}
54+
55+
// 注意，这里从 i = index开始
56+
// 每次只取第一个，例如 123334，到了333这里，我们第一次只取第1个3，因为我们选任何一个3是对组合来说是一个解。所以只
57+
// 第一次取就好了。
58+
for (inti =index;i <num.length;i++) {
59+
intn =num[i];
60+
if (i !=index &&n ==num[i -1]) {
61+
continue;
62+
}
63+
path.add(n);
64+
dfs(num,target -n,path,ret,i +1);
65+
path.remove(path.size() -1);
66+
}
67+
}
68+
}

‎dfs/SolveNQueens.java

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,11 +9,17 @@ public static void main(String[] strs) {
99

1010
for (String[]strss:list) {
1111
for (Strings:strss) {
12-
System.out.println(s);
12+
//System.out.println(s);
1313
}
1414

1515
}
1616

17+
Longret =Long.MAX_VALUE;
18+
inta =Integer.MAX_VALUE;
19+
if (ret ==a) {
20+
System.out.println(true);
21+
}
22+
1723
//System.out.println(solveNQueens(4).toString());
1824
}
1925

‎permutation/PermuteUnique.java

Lines changed: 28 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ public List<List<Integer>> permuteUnique(int[] num) {
1919
returnret;
2020
}
2121

22-
publicvoiddfs(int[]num,ArrayList<Integer>path,List<List<Integer>>ret,boolean[]visit) {
22+
publicvoiddfs1(int[]num,ArrayList<Integer>path,List<List<Integer>>ret,boolean[]visit) {
2323
intlen =num.length;
2424
if (path.size() ==len) {
2525
ret.add(newArrayList<Integer>(path));
@@ -42,4 +42,31 @@ public void dfs(int[] num, ArrayList<Integer> path, List<List<Integer>> ret, boo
4242
visit[i] =false;
4343
}
4444
}
45+
46+
// SOLUTION 2:
47+
// 使用一个pre来记录。只取第一个可以取的位置
48+
publicvoiddfs(int[]num,ArrayList<Integer>path,List<List<Integer>>ret,boolean[]visit) {
49+
intlen =num.length;
50+
if (path.size() ==len) {
51+
ret.add(newArrayList<Integer>(path));
52+
return;
53+
}
54+
55+
longpre =Long.MIN_VALUE;
56+
for (inti =0;i <len;i++) {
57+
intn =num[i];
58+
// 只取第一个可取的位置，因为别的位置取到的也没有区别
59+
if (visit[i] ||pre ==n) {
60+
continue;
61+
}
62+
pre =n;
63+
64+
// 递归以及回溯
65+
visit[i] =true;
66+
path.add(n);
67+
dfs(num,path,ret,visit);
68+
path.remove(path.size() -1);
69+
visit[i] =false;
70+
}
71+
}
4572
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp