未分類

Gray Code

Backtracking, Go, LeetCode

Gray Code

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:

1
2
3
4
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.

提示 解題應用
Backtracking 規律觀查

Default:

1
2
3
func grayCode(n int) []int {
}

解答思路:

碰到這種排類組合的題目通常第一個直覺會是要用遞回的方式處理，雖然沒有問題不過就根本上來說，因為是要列出所有可能，並以十進位的方式呈現，如果給的二進位長度為n就直接將0~2的n次方-1的所有值放入十進位的結果之中就搞定，然而題目註明了結果只能以特定的排序方式呈現，依序塞的方式不適用特定的排序的話，要用遞回的方式實作出特定的排序方式也相當麻煩，所以倒不如就直接觀查特定排序二進位與十進位的規律變化來試著找出規律，如下(二進位/十進位):

二進位長度: 1

1
2
0 0
1 1

二進位長度: 2

1
2
3
4
00 0
01 1
11 3
10 2

二進位長度: 3

1
2
3
4
5
6
7
8
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4

最後可以發現到長度每增加1，就是先將前一個二進位的結果複製一份到後頭並翻轉，最後才再開頭補上0與1各一半，如下(二進位長度: 1→2):

將前一個二進位的結果複製一份到後頭並翻轉

1
2
3
4
0 0
1 1
1 1
0 0

最後再開頭補上0與1各一半

1
2
3
4
00 0
01 1
11 3
10 2

完全理解特定排序二進位與十進位的規律變化之後，僅憑二進位長度來直接輸出最後的十進位結果陣列就不是什麼大問題了。

程式碼解說:

在完全理解特定排序二進位與十進位的規律變化之後，就可以僅憑二進位長度來直接輸出最後的十進位結果陣列，所以在操作上完全只有十進位數，一開始先初始化要放十進位的結果陣列並放入數字0為起始值，接著再初始化暫存值為1以隨著二進位長度n的增加，十進位遞增的值(2的n-1次方)也跟著增加，根據先前的思路所得到的規律，我們每次都將前一份結果倒著取出(翻轉)並加上遞增的暫存值(新的二進位在開頭補上1的意思)再將其放入結果後頭之中，待到達題目所指定的二進位長度，才結束重覆上述動作並回傳整個十進位所呈現的所有結果陣列

1
2
3
4
5
6
7
8
9
10
result := []int{0}
tmp := 1
for n > 0 {
	for i := len(result) - 1; i >= 0; i-- {
		result = append(result, result[i]+tmp)
	}
	tmp *= 2
	n--
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
func grayCode(n int) []int {
	result := []int{0}
	tmp := 1
	for n > 0 {
		for i := len(result) - 1; i >= 0; i-- {
			result = append(result, result[i]+tmp)
		}
		tmp *= 2
		n--
	}
	return result
}

總結:

要找出二進位長度n的所有組合，並以十進位方式來呈現，如果沒有特別規定輸出的排序方式，可以用遞回方式來推出結果或是直接將0~2的n次方-1的所有值放入結果之中，然而如果有要求特定的排序方式，與其要用遞回的方式實作出特定的排序方式，倒不如就直接觀查特定排序二進位與十進位的規律變化，最後就能僅憑二進位長度來直接輸出最後的十進位結果陣列。

分享到