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

Commitb8e18ba

Browse files
committed
recover
1 parenta328ac7 commitb8e18ba

File tree

2 files changed

+81
-5
lines changed

2 files changed

+81
-5
lines changed

‎permutation/PermuteUnique.java

Lines changed: 11 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,13 @@
44
importjava.util.List;
55

66
publicclassPermuteUnique {
7-
publicList<List<Integer>>permuteUnique(int[]num) {
7+
publicstaticvoidmain(String[]strs) {
8+
int[]num = {1,1,1,3};
9+
List<List<Integer>>ret =permuteUnique(num);
10+
System.out.println(ret.toString());
11+
}
12+
13+
publicstaticList<List<Integer>>permuteUnique(int[]num) {
814
List<List<Integer>>ret =newArrayList<List<Integer>>();
915
if (num ==null ||num.length ==0) {
1016
returnret;
@@ -14,12 +20,12 @@ public List<List<Integer>> permuteUnique(int[] num) {
1420
Arrays.sort(num);
1521
boolean[]visit =newboolean[num.length];
1622

17-
dfs(num,newArrayList<Integer>(),ret,visit);
23+
dfs1(num,newArrayList<Integer>(),ret,visit);
1824

1925
returnret;
2026
}
2127

22-
publicvoiddfs1(int[]num,ArrayList<Integer>path,List<List<Integer>>ret,boolean[]visit) {
28+
publicstaticvoiddfs1(int[]num,ArrayList<Integer>path,List<List<Integer>>ret,boolean[]visit) {
2329
intlen =num.length;
2430
if (path.size() ==len) {
2531
ret.add(newArrayList<Integer>(path));
@@ -30,14 +36,14 @@ public void dfs1(int[] num, ArrayList<Integer> path, List<List<Integer>> ret, bo
3036
// 只能连续地选，这样就可以避免生成重复的solution.
3137
// 例子：1 2 3 4 4 4 5 6 7 8
3238
// 444这个的选法只能:4, 44, 444连续这三种选法
33-
if (visit[i] || (i !=0 &&visit[i -1] &&num[i] ==num[i -1])) {
39+
if (visit[i] || (i !=0 &&!visit[i -1] &&num[i] ==num[i -1])) {
3440
continue;
3541
}
3642

3743
// 递归以及回溯
3844
visit[i] =true;
3945
path.add(num[i]);
40-
dfs(num,path,ret,visit);
46+
dfs1(num,path,ret,visit);
4147
path.remove(path.size() -1);
4248
visit[i] =false;
4349
}

‎tree/RecoverTree.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
11
packageAlgorithms.tree;
22

3+
importjava.util.ArrayList;
4+
importjava.util.Stack;
5+
36
/**
47
* Definition for binary tree
58
* public class TreeNode {
@@ -14,6 +17,24 @@ public class RecoverTree {
1417
TreeNodefirst =null;
1518
TreeNodesecond =null;
1619

20+
publicstaticclassFunction {
21+
intreference;
22+
23+
Function () {
24+
super();
25+
}
26+
}
27+
28+
publicstaticvoidmain(String[]strs) {
29+
ArrayList<Object>list =newArrayList<Object>();
30+
31+
list.add("string");
32+
list.add(1);
33+
34+
Functionfuc =newFunction();
35+
36+
37+
}
1738

1839
publicvoidrecoverTree(TreeNoderoot) {
1940
inOrder(root);
@@ -67,4 +88,53 @@ public void inOrder(TreeNode root) {
6788
// inorder traverse.
6889
inOrder(root.right);
6990
}
91+
92+
publicvoidrecoverTree1(TreeNoderoot) {
93+
if (root ==null) {
94+
return;
95+
}
96+
97+
TreeNodenode1 =null;
98+
TreeNodenode2 =null;
99+
100+
TreeNodepre =null;
101+
102+
Stack<TreeNode>s =newStack<TreeNode>();
103+
TreeNodecur =root;
104+
105+
while (true) {
106+
while (cur !=null) {
107+
s.push(cur);
108+
cur =cur.left;
109+
}
110+
111+
if (s.isEmpty()) {
112+
break;
113+
}
114+
115+
TreeNodenode =s.pop();
116+
117+
if (pre !=null) {
118+
// invalid order
119+
if (pre.val >node.val) {
120+
if (node1 ==null) {
121+
node1 =pre;
122+
node2 =node;
123+
}else {
124+
node2 =node;
125+
}
126+
}
127+
}
128+
129+
pre =node;
130+
131+
cur =node.right;
132+
}
133+
134+
inttmp =node1.val;
135+
node1.val =node2.val;
136+
node2.val =tmp;
137+
138+
return;
139+
}
70140
}

0 commit comments

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