Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/89.html
An n-bit gray code sequence is a sequence of 2n
integers where:
- Every integer is in the inclusive range
[0, 2n - 1]
, - The first integer is
0
, - An integer appears no more than once in the sequence,
- The binary representation of every pair of adjacent integers differs by exactly one bit, and
- The binary representation of the first and last integers differs by exactly one bit.
Given an integer n
, return any valid n-bit gray code sequence.
Example 1:
Input: n = 2 Output: [0,1,3,2] Explanation: The binary representation of [0,1,3,2] is [00,01,11,10]. - 00 and 01 differ by one bit - 01 and 11 differ by one bit - 11 and 10 differ by one bit - 10 and 00 differ by one bit [0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01]. - 00 and 10 differ by one bit - 10 and 11 differ by one bit - 11 and 01 differ by one bit - 01 and 00 differ by one bit
Example 2:
Input: n = 1 Output: [0,1]
Constraints:
1 <= n <= 16
Algorithm
For n=3:
Int Grey Code Binary
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111
My idea is using left shifts, and then operate the lowest bit, followed by 0 or 1.
Another idea is to get the highest position directly, and then add all the previous ones to the highest one
- Note that a for loop starts from
0
, if it isn
, then<<n-1
is enough - The second for loop must be reversed from
list-size-1
to0
.
If it starts from 0, then the list keeps getting new homes, the size keeps increasing, and it loops endlessly.
Code
-
import java.util.ArrayList; import java.util.List; public class Gray_Code { public static void main(String[] args) { Gray_Code out = new Gray_Code(); Solution_optimize_on_highest_digit s = out.new Solution_optimize_on_highest_digit(); System.out.println(s.grayCode(3)); // output: [0, 1, 3, 2, 6, 7, 5, 4] } // 0 => 0,1 => 10,11 public class Solution_optimize_on_highest_digit { public List<Integer> grayCode(int n) { List<Integer> list = new ArrayList<Integer>(); list.add(0); // special case for (int i = 1; i <= n; i++) { int highestBit = 1 << (i - 1); // @note:@memorize: nice cutoff! no need to use an extra tmpList for (int j = list.size() - 1; j >= 0; j--) { list.add(highestBit + list.get(j)); } } return list; } } public class Solution_on_highest_digit { public List<Integer> grayCode(int n) { List<Integer> list = new ArrayList<Integer>(); if (n < 0) { return list; } // init list.add(0); // @note: append 1 at highest digit position for (int i = 1; i <= n; i++) { // int prevLen = list.size(); List<Integer> tmpList = new ArrayList<Integer>(list); for (int each: list) { tmpList.add(each + (1 << (i - 1))); } list = tmpList; } return list; } } public class Solution_on_lowest_digit { public List<Integer> grayCode(int n) { List<Integer> list = new ArrayList<Integer>(); if (n == 0) { list.add(0); return list; } list.add(0); list.add(1); for (int i = 2; i <= n; i++) { List<Integer> allprev = new ArrayList<Integer>(list); for (int each : allprev) { each <<= 1; if (!list.contains(each)) list.add(each); if (!list.contains(each + 1)) list.add(each + 1); } } return list; } } } ############ class Solution { public List<Integer> grayCode(int n) { List<Integer> ans = new ArrayList<>(); for (int i = 0; i < 1 << n; ++i) { ans.add(i ^ (i >> 1)); } return ans; } }
-
// OJ: https://leetcode.com/problems/gray-code/ // Time: O(2^N) // Space: O(2^N) class Solution { private: inline int toggle(int n, int i) { return n ^ (1 << i); } int next(int n, unordered_set<int> s) { int ans = 0; for (int i = 0; i < 32; ++i) { ans = toggle(n, i); if (s.find(ans) == s.end()) break; } return ans; } public: vector<int> grayCode(int n) { unordered_set<int> s{0}; vector<int> ans(pow(2, n), 0); for (int i = 1; i < ans.size(); ++i) { s.insert(ans[i] = next(ans[i - 1], s)); } return ans; } };
-
class Solution: def grayCode(self, n: int) -> List[int]: return [i ^ (i >> 1) for i in range(1 << n)] ############ class Solution(object): def grayCode(self, n): """ :type n: int :rtype: List[int] """ if n < 1: return [0] ans = [0] * (2 ** n) ans[1] = 1 mask = 0x01 i = 1 while i < n: mask <<= 1 for j in range(0, 2 ** i): root = (2 ** i) ans[root + j] = ans[root - j - 1] | mask i += 1 return ans
-
func grayCode(n int) (ans []int) { for i := 0; i < 1<<n; i++ { ans = append(ans, i^(i>>1)) } return }
-
/** * @param {number} n * @return {number[]} */ var grayCode = function (n) { const ans = []; for (let i = 0; i < 1 << n; ++i) { ans.push(i ^ (i >> 1)); } return ans; };