麻豆国产,www在线,国产三级高清在线,一级欧美一级日韩,日韩欧美操逼,黄色一级日逼片,少妇搡B午夜躁,国内内射在线

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?格雷編碼，我們先來看題面：

https://leetcode-cn.com/problems/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.

題意

格雷編碼是一個(gè)二進(jìn)制數(shù)字系統(tǒng)，在該系統(tǒng)中，兩個(gè)連續(xù)的數(shù)值僅有一個(gè)位數(shù)的差異。給定一個(gè)代表編碼總位數(shù)的非負(fù)整數(shù) n，打印其格雷編碼序列。即使有多個(gè)不同答案，你也只需要返回其中一種。格雷編碼序列必須以 0 開頭。
樣例

輸入:?2
輸出:?[0,1,3,2]
解釋:
00?-?0
01?-?1
11?-?3
10?-?2

對于給定的?n，其格雷編碼序列并不唯一。

例如，[0,2,3,1]?也是一個(gè)有效的格雷編碼序列。

00?-?0
10?-?2
11?-?3
01?-?1

解題

https://www.cnblogs.com/techflow/p/13432414.html

題解

當(dāng)然以上的問題其實(shí)也不是事，我們不確定試一次也就知道了，核心還是怎么想出解法來。干想是沒有結(jié)果的，還是要先分析搜集一些信息。首先，題目給定的n，限制了每個(gè)數(shù)能夠使用的二進(jìn)制位的數(shù)量。n個(gè)二進(jìn)制位一共能表示的數(shù)字有2n2n種，我們無法得知是否這么多數(shù)字都能串聯(lián)起來。假設(shè)可行的話，那么這個(gè)問題其實(shí)就是這2n2n個(gè)數(shù)如何擺放的問題。所以問題的關(guān)鍵就是要尋找這樣一個(gè)序列，根據(jù)我們之前解全排列以及各種排列的方法，可以聯(lián)想得到，這大概率是一個(gè)搜索問題。順著搜索的思路繼續(xù)往下，剩下的事情就容易了，我們的起始搜索點(diǎn)是0。題目中要求了每兩個(gè)相鄰的數(shù)的二進(jìn)制位只相差一個(gè)，那么我們可以遍歷這些二進(jìn)制位，尋找0的后繼節(jié)點(diǎn)。同樣對于每一個(gè)后繼節(jié)點(diǎn)來說，我們都可以用同樣的方法尋找它的后繼們。再加上gray code不能包含重復(fù)的元素，我們可以在搜索的時(shí)候加上剪枝。這一套其實(shí)是一個(gè)經(jīng)典的搜索問題的流程。如果我們換個(gè)思路，雖然也能得到一樣的解法，但是思考的過程會不太一樣。怎么換思路呢，其實(shí)也簡單，我們把它想象成一個(gè)圖論問題。也就是說，每一個(gè)數(shù)字都是圖中的一個(gè)節(jié)點(diǎn)。如果兩個(gè)數(shù)字之間滿足只相差了一個(gè)二進(jìn)制位，那么說明它們之間有一條邊相連。整個(gè)問題就轉(zhuǎn)變成了我們從0這個(gè)點(diǎn)出發(fā)，找出所有連通的節(jié)點(diǎn)。對于圖上的遍歷問題，方法就很固定了就是搜索。也就是說從這個(gè)角度思考的話，更加容易想到搜索上面了，整個(gè)思考的鏈路會更短。這也是為什么很多大神建模的時(shí)候喜歡從往圖上考慮的原因。這些都想明白了再來寫代碼真的就水到渠成了，整個(gè)核心代碼真的不長：

class?Solution:
????def?grayCode(self, n: int)?-> List[int]:
????????ret = [0]
????????elements = {0}
????????
????????def?dfs(cur):
????????????# 遍歷與cur唯一不同的二進(jìn)制位
????????????for?i in?range(n):
????????????????# 針對這一維做亦或，將0變1，1變0
????????????????nxt = cur ^ (1?<< i)
????????????????if?nxt in?elements:
????????????????????continue
????????????????# 記錄答案，繼續(xù)往下遍歷
????????????????elements.add(nxt)
????????????????ret.append(nxt)
????????????????dfs(nxt)
????????dfs(0)
????????return?ret

總結(jié)

單純從思路以及最后的AC代碼來看的話，這道題難度應(yīng)該是很低的，實(shí)際上也的確如此，這題的通過率接近50%，已經(jīng)是Medium難度的下屆了。但是相比于做對這題而言，更加重要的是思路。以圖論的思維來抽象建模是算法題當(dāng)中一個(gè)非常常見的手段，這是比題目本身更加寶貴的東西。如果你讀過昨天的文章的話，會發(fā)現(xiàn)昨天的87題，本質(zhì)上也是用的一個(gè)圖論建模的方法。但是從表現(xiàn)形式上來說，這兩題真的可以說是完全不一樣。建議大家能好好做做這兩題，體會一下其中思維和解法的閃光點(diǎn)。好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。

上期推文：

?LeetCode刷題實(shí)戰(zhàn)89:格雷編碼

題意

解題

題解

總結(jié)