GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — leet-code/Java/Gray Code.java at master · awangdev/leet-code

Expand file tree

/

Gray Code.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
executable file
·
180 lines (132 loc) · 4.89 KB
/

Gray Code.java

Copy path

File metadata and controls

executable file
·
180 lines (132 loc) · 4.89 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
M
tags: Backtracking
TODO:
1. backtracking, using set to perform contains()
2. BFS: use queue to keep the mutations
题目蛋疼，目前只接受一种结果。
BackTracking + DFS:
Recursive helper里每次flip一个 自己/左边/右边. Flip过后还要恢复原样.遍历所有.
曾用法（未仔细验证）：
基本想法就是从一个点开始往一个方向走，每次flip一个bit, 碰壁的时候就回头走。
```
/*
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
Hide Company Tags Amazon
Hide Tags Backtracking
*/
//Another solution, 02.10.2016 using DFS
//generate order, output the numerical value of each binary code. Integer.parseInt("10101", 2).
//Start with n-bit char[] of 0's. Flip one bit at a time.
//Recursive helper. char[], index. Flip or not flip. DFS
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> rst = new ArrayList<Integer>();
if (n < 0) {
return rst;
} else if (n == 0) {
rst.add(0);
return rst;
}
char[] list = new char[n];
for (int i = 0; i < n; i++) {
list[i] = '0';
}
helper(rst, list, n - 1);
return rst;
}
public void helper(List<Integer> rst, char[] list, int index) {
rst.add(Integer.parseInt(new String(list), 2));
//self
list[index] = list[index] == '0' ? '1' : '0';
int num = Integer.parseInt(new String(list), 2);
if (!rst.contains(num)) {
helper(rst, list, index);
}
list[index] = list[index] == '0' ? '1' : '0';
//left
if (index -1 >= 0) {
list[index - 1] = list[index - 1] == '0' ? '1' : '0';
num = Integer.parseInt(new String(list), 2);
if (!rst.contains(num)) {
helper(rst, list, index - 1);
}
list[index - 1] = list[index - 1] == '0' ? '1' : '0';
}
//right
if (index + 1 < list.length) {
list[index + 1] = list[index + 1] == '0' ? '1' : '0';
num = Integer.parseInt(new String(list), 2);
if (!rst.contains(num)) {
helper(rst, list, index + 1);
}
list[index + 1] = list[index + 1] == '0' ? '1' : '0';
}
}
}
/*
Leetcode tags shows backtracking. That should be different approach than what I hvae below:
*/
/*
TRY: My code works for this run-through, however does not fit the OJ yet
0 0 0 [start, noting happend, flip index 0]
0 0 <-1 [move to flip left adjacent]
0 <-1 1 [move to flip left adjacent]
1-> 1 1 [move to flip right adjacent]
1 0-> 1 [move to flip right adjacent]
1 0 <-0 [move to flip left adjacent]
1 <-1 0 [move to flip left adjacent]
0 1 0 [done]
Conclusion: hit the wall and flip the other direction.
Every flip, add integer to list
Convert the char[] to string, then Integer.parse(str, 2) to integer
Simulate the steps:
For example, when n = 3, step = n - 1. It takes 2 steps from right side to reach left side, it hits the wall and turn around.
Now:
1. Initialize char[] and add '000'
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.
*/
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> rst = new ArrayList<Integer>();
if (n < 0) {
return rst;
}
char[] bits = new char[n];
for (int i = 0; i < bits.length; i++) {
bits[i] = '0';
}
String str = new String(bits);
if (n == 0) {
str = "0";
}
rst.add(Integer.parseInt(str, 2));
int step = n - 1;
boolean LR = true;//L: true; R: false
int steps = (int)Math.pow(2, n) - 1;
for (int i = 0; i < steps; i++) {
bits[step] = bits[step] == '0' ? '1' : '0';
str = new String(bits);
rst.add(Integer.parseInt(str, 2));
if (LR) {
step--;
} else {
step++;
}
if (step == (n - 1) || step == 0) {//Turn around
LR = !LR;
}
}
return rst;
}
}
```
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.