GrayCode [source code]
public class GrayCode {
static
/******************************************************************************/
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<> ();
int num = 0;
res.add (num);
if (n == 0)
return res;
int[] flip_indices = new int[1 << n];
flip_indices[n - 1] = 0;
dfs (flip_indices, n - 1);
for (int i = 0; i < flip_indices.length - 1; i++) {
int flip_idx = flip_indices[i];
num ^= (1 << flip_idx);
res.add (num);
}
return res;
}
// The last element of INDICES stores the next INDEX in it to be updated
void dfs (int[] indices, int depth) {
if (depth < 0)
return;
dfs (indices, depth - 1);
indices[indices[indices.length - 1]++] = depth;
dfs (indices, depth - 1);
}
}
/******************************************************************************/
public static void main(String[] args) {
GrayCode.Solution tester = new GrayCode.Solution();
Integer[][] inputs = {
{2}, {0,1,3,2},
{3}, {0,1,3,2,6,7,5,4},
{0}, {0},
};
for (int i = 0; i < inputs.length / 2; i++) {
int n = inputs[2 * i][0];
System.out.println (Printer.separator ());
List<Integer> ans = Arrays.asList (inputs[2 * i + 1]), output = tester.grayCode (n);
System.out.printf ("%d -> %s, expected: %s\n",
n, Printer.wrap (output.toString (), output.equals (ans) ? 92 : 91), ans
);
}
}
}
downvote很多的题目, 大概做做;
看了一下例子, 意思就是虽然正确的答案其实很多, 但是目前只能接受一种, 那么我分析了一下他给的这个例子, 看看他这个是怎么走的; 感觉他这个就是从右往左进行flip的一个顺序得到的sequence;
另外, toggle bit这个东西, 应该还是很熟悉的;
另外, 这题因为是一个已知层数的情形, 所以真的有必要用recursion吗? 以前总结过, 实现backtracking不是必须定死了只能recursion, iteration在某些场合下也可以;
不对, 这题是不知道层数的: 这里知道的这个n, 不是层数; 这个n控制的实际上是fanning; 层数则是指数级;
直接用backtracking做, 最后好像重复相当多; 当然你可以用set来去重, 不过这个最后就浪费了很多的时间, 也就是指数级别的时间是没有必要的; 不对, 好像是必要的吧?
感觉2的例子看不出来, 看一下3的例子; 这个如果真正面试的时候, 可以问面试官, 认为需要further clarification about the quesiton;
看这个例子:
这个题目最后实际上真正的难点就是研究给的这个例子代表的一个order; 这个就很烦人了;
可以看到, 确实有一个tree结构, 所以我一开始的一个想法, 就是直接用tree的顺序来做, 最后插入位置的时候注意一点就行了; 但是发现并不好些, 因为比如3这个例子这里, root应该是2和6, 但是你怎么知道2和6呢? 这个并不知道;
又重新想了一个思路:
这个0 1 0 2 0 1 0的序列感觉好像应该是固定的? 能不能直接计算这个?
这个好像可以用recursion来计算?
最后超时还是做出来了; 这个题目被喷的厉害估计其实就是题目的要求讲的很模糊; 不过回头看看我的思考过程, 感觉还是挺有意思的其实; 速度是1ms (30%);
几个小东西, 一个是List.equals这个东西, 要记得java的collection的实现都是很完备的, collection的hash和equals这些, 都是完全考虑所有的element的; 另外一个就是这里的test3, 0的时候居然结果是[0], 完全不合理, 不过这种东西, 面试的时候还是问清楚, 这种很edge的case: 亚麻这样的大厂都会有这种很不intuitive的edge case, 其他的公司就更加难说了, 很任性;
当然, 还是想要能够1pass做出来的, 比如把flip的操作也直接融合到这个DFS里面去做; 但是至少我这个思路是做不到的, 因为我是从中间出发的, 在我真正走到bottom之前, 我是不知道这个swap sequence开头的flip index的, 也就不知道我前面的num是什么状态;
另外, 回过头来想想, 为什么现在这个算法就能完成去重? 因为我们现在这个算法的本质是一个recursion tree, 而合理的recursion tree是肯定不会有重复的; 至少tree的node本身之间是没有重复的;
没有editorial;
https://leetcode.com/problems/gray-code/discuss/29881/An-accepted-three-line-solution-in-JAVA
public List<Integer> grayCode(int n) {
List<Integer> result = new LinkedList<>();
for (int i = 0; i < 1<<n; i++) result.add(i ^ i>>1);
return result;
}
大概画一下, 这个算法确实是对的; 不过这是怎么想到的? 简直就是math解法;
有一个非常好的解释:
I don’t know how to come up with the solution i^(i>>1), but I will try to explain why it works.
Adding one to a number results in flipping all the bits from the rightmost zero bit to the end, e.g. 110011 + 1 = 110100
In the general form, i = ...?01...1, i+1 = ...?10...0, ? represents the left bit of the rightmost zero bit, the length of tailing one bits of i is the same as the length of tailing 0 bits of i+1, and the bits from the beginning to the ? are the same.
Then i^(i>>1) = xxx(?^0)10...0, (i+1)^((i+1)>>1) = xxx(?^1)10...0. Since the bits from the beginning to the ? are the same, xxx part of both results must be same, it’s obvious the tailing parts of 10...0 must be same, and its length is the same as the length of tailing one bits of i, so there is only one bit difference comes from (?^0) and (?^1).
虽然没有解释怎么想出来的, 但是对于这个算法的正确性算是解释的非常到位了; 他这个解释还缺最后一点东西, 就是他只解释了为什么是differ by 1 bit, 但是没有解释给出的这个sequence的顺序; 我自己尝试分析了一下, 感觉最后还是转化为我自己对于0 1 0 2 0 1 0这个sequence的分析;
Just added information for those who are interested (all credited to Wiki gray code
// The purpose of this function is to convert an unsigned
// binary number to reflected binary Gray code.
// The operator >> is shift right. The operator ^ is exclusive or.
unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}
// The purpose of this function is to convert a reflected binary
// Gray code number to a binary number.
unsigned int grayToBinary(unsigned int num)
{
unsigned int mask;
for (mask = num >> 1; mask != 0; mask = mask >> 1)
{
num = num ^ mask;
}
return num;
}
所以这个算法其实就是一个经典算法而已; 当然这个人其实也没有讲具体的原理; 不过这些个经典算法, 真正能说出所以然, 说出怎么想出来的, 又有几个呢;
反正知道binary和gray之间是有一个1对1的对应关系的就行了; binary to gray还是比较好记的; 反过来这个转换可能稍微有点麻烦; 如果非要记忆, 拿就是循环shift then xor into accummulator;
终于有人知道怎么用真正的recursion来做了:
https://leetcode.com/problems/gray-code/discuss/29891/Share-my-solution
My idea is to generate the sequence iteratively. For example, when n=3, we can get the result based on n=2.
00,01,11,10 -> (000,001,011,010 ) (110,111,101,100). The middle two numbers only differ at their highest bit, while the rest numbers of part two are exactly symmetric of part one. It is easy to see its correctness.
Code is simple:
public List<Integer> grayCode(int n) {
List<Integer> rs=new ArrayList<Integer>();
rs.add(0);
for(int i=0;i<n;i++){
int size=rs.size();
for(int k=size-1;k>=0;k--)
rs.add(rs.get(k) | 1<<i);
}
return rs;
}
他这里这个symmetry的说起来很轻松, 但是实现起来还是很看功夫的, 比如他这里先把size cache起来; 然后后面从rs里面取之前的结果的时候, 其实是用一个reversed的顺序来取的; 这个对称性其实不是非常容易看出来;
这个解法虽然没有之前那个解法那么不讲道理, 但是还是有点难以想到; 把n=3的情况利用n=2来解, 这个根本就不在我的套路里面; 什么时候才能想到这种方法?
好像这种参数直接给你一个数字, n这样的, 然后就让你自己expand出来一个sequence之类的东西, 可能可以往sub problem这个方向去考虑?
I have a solution here which takes O(1) on space and no recursion used. Is this the best possible solution? (I combined the base cases in the loop as mike3 does. Thanks mike3!)
vector<int> grayCode(int n)
{
vector<int> result(1, 0);
for (int i = 0; i < n; i++) {
int curCount = result.size();
// push back all element in result in reverse order
while (curCount) {
curCount--;
int curNum = result[curCount];
curNum += (1<<i);
result.push_back(curNum);
}
}
return result;
}
跟前面那个是一样的思路; 这个解法应该就是这题的最优解了; 14年的时候就有人提出了; 上面那个好像也是14年的;
Counting from 0, when we generate v[i] from v[i-1], we just need to change bit where the rightmost bit 1 locates in i. For example, [00, 01, 11, 10], when we generate 11(2nd) from 01(1st), we just xor 01 with 10(rightmost bit 1 of 2); when we generate 10(3th) from 11(2nd), we just xor 11 with 01(rightmost bit 1 of 3). Here I use “i&-i” to get the rightmost bit 1 of i.
vector<int> grayCode(int n) {
vector<int> v(1,0);
for (int i=1;i<(1<<n);i++) v.push_back(v[i-1]^(i&-i));
return v;
}
很有意思的思路; 之前第一个解法里面那个分析的人, 也是用这个rightmost的思路来分析的; 好像跟这个有点区别不过有类似性;
i & -i这个好像见过一次了, 回顾一下;
又重新思考了一下他这个算法, 好像并不是那么trivial; 你仔细看他的代码, 他是用i的rightmost 1来和[i-1]的结果来xor; 这个是什么原理? 感觉根本不好解释, 这个多数也是一个依靠观察规律总结出来的思路; 不过这个规律比我找到的规律要难想很多; 我是不会去想着把当前的index的信息和之前的value进行计算操作的;
A different way of solving this problem. Not smart, but a different idea
//try to generate all possible code by 0 1-> 0+0 0+1 1+1 1+0 ->...
//add 0 at begin forward the array such as 0 1 -> 00 01
//add 1 at begin reverse the array such as 0 1 -> 11 10
public List<Integer> grayCode(int n) {
List<Integer> outlist = new ArrayList<Integer>();
if(n == 0) {
outlist.add(0);
return outlist;
}
List<String> list = new ArrayList<String>();
list.add("0");
list.add("1");
for(int i = 0; i < n - 1; i++) {
List<String> tlist = new ArrayList<String>();
int listLen = list.size();
for(int j = 0; j < listLen; j++) {
tlist.add("0" + list.get(j));
}
for(int j = 0; j < listLen; j++) {
tlist.add("1" + list.get(list.size() - 1 - j));
}
list = tlist;
}
for(String s : list) {
outlist.add(Integer.valueOf(s,2));
}
return outlist;
}
跟之前那个降维的思路是差不多的; 不知道这些人怎么想到往这条路上面去考虑的; 当我考虑recursive思路的时候, 想的完全就是针对比如n=3的时候的8个数字的一个类似traversal的操作, 完全没有去考虑向下降低order这种操作;
对于bit做法, 一个稍微像样点的解释:
In the Grey Code generated by (x>>1)^x, each bit is oscillating between going from off to on, and on to off. Meaning the pattern is 0,1,1,0 instead of 0,1,0,1 which is what you have for counting numbers. 0,1,1,0 should remind you of the XOR boolean table:
AB|A^B 00|0 01|1 10|1 11|0Isolate any two adjacent bits in the counting sequence, and you will get the the table input repeating. We can come up with a formula for each bit b in the output g: g(b) = x(b) XOR x(b+1). Think of every next bit encoding whether the current bit is flipping on or flipping off. You can get all the bits at once with g = x ^ (x >> 1).
一个大概的思路, 也不知道是他真的自己能够这么想出来这个答案, 还是就是依葫芦画瓢儿强行解读;
All you need is a bit of careful thought.
Btw, it’s extremely useful to write down your thought/demo in comments before you actually start to write the code, especially during interview.
Even if you do not solve the problem finally, the interviewer at least get to know what you’re thinking.
And if you don’t get the problem right, he/she will have a chance to correct you.
这个经验, 学习了;
class Solution:
# @return a list of integers
'''
from up to down, then left to right
0 1 11 110
10 111
101
100
start: [0]
i = 0: [0, 1]
i = 1: [0, 1, 3, 2]
i = 2: [0, 1, 3, 2, 6, 7, 5, 4]
'''
def grayCode(self, n):
results = [0]
for i in range(n):
results += [x + pow(2, i) for x in reversed(results)]
return results
还是对称解法; 果然是最优解;
submission基本波动, 领头的几个也就是这个symmetry解法;
Problem Description
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.
Difficulty:Medium
Total Accepted:103.1K
Total Submissions:244.3K
Contributor:LeetCode
Companies
amazon
Related Topics
backtracking
Similar Questions
1-bit and 2-bit Characters