Skip to content

Commit 06144ad

Browse files
awangdevawangdev
committed
02.10.2016
1 parent 81bdde3 commit 06144ad

4 files changed

Lines changed: 227 additions & 180 deletions

File tree

‎Java/Gray Code.java‎

Lines changed: 103 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,13 @@
1-
李特这特题目有点蛋疼，因为目前只接受一种结果。
2-
我做的恰好和它要的结果不一样，但是我觉得我这种走法走出来也是没错的。
1+
M
2+
3+
题目蛋疼，目前只接受一种结果。
4+
5+
BackTracking + DFS:
6+
Recursive helper里每次flip一个 自己/左边/右边. Flip过后还要恢复原样.遍历所有.
7+
8+
曾用法（未仔细验证）：
39
基本想法就是从一个点开始往一个方向走，每次flip一个bit, 碰壁的时候就回头走。
10+
411
```
512
/*
613
@@ -11,25 +18,80 @@
1118
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
1219
1320
00 - 0
14-
1521
01 - 1
16-
1722
11 - 3
18-
1923
10 - 2
20-
2124
Note:
22-
2325
For a given n, a gray code sequence is not uniquely defined.
2426
2527
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
2628
2729
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
2830
29-
Tags:Backtracking
31+
Hide Company Tags Amazon
32+
Hide Tags Backtracking
3033
3134
*/
3235

36+
37+
//Another solution, 02.10.2016 using DFS
38+
//generate order, output the numerical value of each binary code. Integer.parseInt("10101", 2).
39+
//Start with n-bit char[] of 0's. Flip one bit at a time.
40+
//Recursive helper. char[], index. Flip or not flip. DFS
41+
42+
public class Solution {
43+
public List<Integer> grayCode(int n) {
44+
List<Integer> rst = new ArrayList<Integer>();
45+
if (n < 0) {
46+
return rst;
47+
} else if (n == 0) {
48+
rst.add(0);
49+
return rst;
50+
}
51+
char[] list = new char[n];
52+
for (int i = 0; i < n; i++) {
53+
list[i] = '0';
54+
}
55+
helper(rst, list, n - 1);
56+
57+
return rst;
58+
}
59+
60+
public void helper(List<Integer> rst, char[] list, int index) {
61+
62+
rst.add(Integer.parseInt(new String(list), 2));
63+
64+
//self
65+
list[index] = list[index] == '0' ? '1' : '0';
66+
int num = Integer.parseInt(new String(list), 2);
67+
if (!rst.contains(num)) {
68+
helper(rst, list, index);
69+
}
70+
list[index] = list[index] == '0' ? '1' : '0';
71+
72+
//left
73+
if (index -1 >= 0) {
74+
list[index - 1] = list[index - 1] == '0' ? '1' : '0';
75+
num = Integer.parseInt(new String(list), 2);
76+
if (!rst.contains(num)) {
77+
helper(rst, list, index - 1);
78+
}
79+
list[index - 1] = list[index - 1] == '0' ? '1' : '0';
80+
}
81+
82+
//right
83+
if (index + 1 < list.length) {
84+
list[index + 1] = list[index + 1] == '0' ? '1' : '0';
85+
num = Integer.parseInt(new String(list), 2);
86+
if (!rst.contains(num)) {
87+
helper(rst, list, index + 1);
88+
}
89+
list[index + 1] = list[index + 1] == '0' ? '1' : '0';
90+
}
91+
}
92+
}
93+
94+
3395
/*
3496
3597
Leetcode tags shows backtracking. That should be different approach than what I hvae below:
@@ -73,72 +135,41 @@
73135
2. do for loop on 1 ~ 2^n -2. last step '010' is stepped into, but no further action, so take 2^3 - 1 = 7 steps.
74136
75137
*/
76-
77138
public class Solution {
78-
79-
public List<Integer> grayCode(int n) {
80-
81-
List<Integer> rst = new ArrayList<Integer>();
82-
83-
if (n < 0) {
84-
85-
return rst;
86-
87-
}
88-
89-
char[] bits = new char[n];
90-
91-
for (int i = 0; i < bits.length; i++) {
92-
93-
bits[i] = '0';
94-
95-
}
96-
97-
String str = new String(bits);
98-
99-
if (n == 0) {
100-
101-
str = "0";
102-
139+
public List<Integer> grayCode(int n) {
140+
List<Integer> rst = new ArrayList<Integer>();
141+
if (n < 0) {
142+
return rst;
143+
}
144+
char[] bits = new char[n];
145+
for (int i = 0; i < bits.length; i++) {
146+
bits[i] = '0';
147+
}
148+
String str = new String(bits);
149+
if (n == 0) {
150+
str = "0";
151+
}
152+
rst.add(Integer.parseInt(str, 2));
153+
int step = n - 1;
154+
boolean LR = true;//L: true; R: false
155+
int steps = (int)Math.pow(2, n) - 1;
156+
for (int i = 0; i < steps; i++) {
157+
bits[step] = bits[step] == '0' ? '1' : '0';
158+
str = new String(bits);
159+
rst.add(Integer.parseInt(str, 2));
160+
if (LR) {
161+
step--;
162+
} else {
163+
step++;
164+
}
165+
if (step == (n - 1) || step == 0) {//Turn around
166+
LR = !LR;
167+
}
168+
}
169+
170+
return rst;
171+
}
103172
}
104173

105-
rst.add(Integer.parseInt(str, 2));
106-
107-
int step = n - 1;
108-
109-
boolean LR = true;//L: true; R: false
110-
111-
int steps = (int)Math.pow(2, n) - 1;
112-
113-
for (int i = 0; i < steps; i++) {
114-
115-
bits[step] = bits[step] == '0' ? '1' : '0';
116-
117-
str = new String(bits);
118-
119-
rst.add(Integer.parseInt(str, 2));
120-
121-
if (LR) {
122-
123-
step--;
124-
125-
} else {
126174

127-
step++;
128-
129-
}
130-
131-
if (step == (n - 1) || step == 0) {//Turn around
132-
133-
LR = !LR;
134-
135-
}
136-
137-
}
138-
139-
return rst;
140-
141-
}
142-
143-
}
144175
```

‎Java/Reverse Words in a String II.java‎

Lines changed: 87 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,13 @@
1+
M
2+
3+
In-place reverse.
4+
5+
reverse用两回. 全局reverse。局部:遇到空格reverse。
6+
7+
注意：结尾点即使没有' '也要给reverse一下最后一个词。
8+
9+
10+
```
111
/*
212
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
313
@@ -11,55 +21,92 @@
1121
1222
Related problem: Rotate Array
1323
14-
Tags: String
15-
Similar Problems: (M) Reverse Words in a String, (E) Rotate Array
24+
Hide Company Tags Amazon Microsoft
25+
Hide Tags String
26+
Hide Similar Problems (M) Reverse Words in a String (E) Rotate Array
27+
1628
29+
*/
1730

31+
/*
32+
Recap: 02.10.2016
33+
//1. reverse all. 2. reverse local with 2 pointer.
34+
//build reverse(start,end)
1835
*/
1936

37+
public class Solution {
38+
public void reverseWords(char[] s) {
39+
if (s == null || s.length <= 1) {
40+
return;
41+
}
42+
reverse(s, 0, s.length - 1);
43+
int start = 0;
44+
for (int i = 0; i < s.length; i++) {
45+
if (s[i] == ' ') {
46+
reverse(s, start, i - 1);
47+
start = i + 1;
48+
} else if (i == s.length - 1) {
49+
reverse(s, start, i);
50+
}
51+
}//end for
52+
}
53+
54+
public void reverse(char[] s, int start, int end) {
55+
while (start < end) {
56+
char temp = s[start];
57+
s[start] = s[end];
58+
s[end] = temp;
59+
start++;
60+
end--;
61+
}
62+
}
63+
}
64+
65+
2066
/*
2167
Thoughts: write an example: reverse the whole thing, then reverse each individual word, split by space.
2268
2369
Note: becase we don't have space at end of the char[], so we will ignore last word. Remember to reverse that one.
2470
*/
2571
public class Solution {
2672
public void reverseWords(char[] s) {
27-
if (s == null || s.length == 0) {
28-
return;
29-
}
30-
int len = s.length;
31-
//reverse whole
32-
for (int i = 0; i < len / 2; i++) {
33-
char temp = s[i];
34-
s[i] = s[len - 1 - i];
35-
s[len - 1 - i] = temp;
36-
}
37-
38-
//reverse partial
39-
int start = 0;
40-
int mid = 0;
41-
int end = 0;
42-
for (int i = 0; i < len; i++) {
43-
if (s[i] == ' ') {
44-
mid = start + (end - start) / 2;
45-
for (int j = start; j <= mid; j++) {
46-
char temp = s[j];
47-
s[j] = s[end - (j - start)];
48-
s[end - (j - start)] = temp;
49-
}
50-
start = i + 1;
51-
} else {
52-
end = i;
53-
}
54-
}
55-
56-
//Process last word
57-
mid = start + (end - start) / 2;
58-
for (int j = start; j <= mid; j++) {
59-
char temp = s[j];
60-
s[j] = s[end - (j - start)];
61-
s[end - (j - start)] = temp;
62-
}
63-
73+
if (s == null || s.length == 0) {
74+
return;
75+
}
76+
int len = s.length;
77+
//reverse whole
78+
for (int i = 0; i < len / 2; i++) {
79+
char temp = s[i];
80+
s[i] = s[len - 1 - i];
81+
s[len - 1 - i] = temp;
82+
}
83+
84+
//reverse partial
85+
int start = 0;
86+
int mid = 0;
87+
int end = 0;
88+
for (int i = 0; i < len; i++) {
89+
if (s[i] == ' ') {
90+
mid = start + (end - start) / 2;
91+
for (int j = start; j <= mid; j++) {
92+
char temp = s[j];
93+
s[j] = s[end - (j - start)];
94+
s[end - (j - start)] = temp;
95+
}
96+
start = i + 1;
97+
} else {
98+
end = i;
99+
}
100+
}
101+
102+
//Process last word
103+
mid = start + (end - start) / 2;
104+
for (int j = start; j <= mid; j++) {
105+
char temp = s[j];
106+
s[j] = s[end - (j - start)];
107+
s[end - (j - start)] = temp;
108+
}
109+
64110
}
65-
}
111+
}
112+
```

0 commit comments

Comments
 (0)