无码乱伦视频,国产激情无码视频网站在线,肏屄网站在线观看,色婷婷在线视频网站,一本色道久久综合无码人妻四虎,综合亚洲在线,婷婷色在线观看,黄色片在线免费观看91

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(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ù)字有

2 n " role="presentation" style=" display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; "> 2 n 2 n

種，我們無法得知是否這么多數(shù)字都能串聯(lián)起來。假設(shè)可行的話，那么這個(gè)問題其實(shí)就是這

2 n " role="presentation" style=" display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; "> 2 n 2 n

個(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è)思路，雖然也能得到一樣的解法，但是思考的過程會(huì)不太一樣。怎么換思路呢，其實(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è)思考的鏈路會(huì)更短。這也是為什么很多大神建模的時(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è)非常常見的手段，這是比題目本身更加寶貴的東西。

如果你讀過昨天的文章的話，會(huì)發(fā)現(xiàn)昨天的87題，本質(zhì)上也是用的一個(gè)圖論建模的方法。但是從表現(xiàn)形式上來說，這兩題真的可以說是完全不一樣。建議大家能好好做做這兩題，體會(huì)一下其中思維和解法的閃光點(diǎn)。

好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。

上期推文：

LeetCode50-80題匯總，速度收藏！

LeetCode刷題實(shí)戰(zhàn)81：搜索旋轉(zhuǎn)排序數(shù)組 II

LeetCode刷題實(shí)戰(zhàn)82：刪除排序鏈表中的重復(fù)元素 II

LeetCode刷題實(shí)戰(zhàn)83：刪除排序鏈表中的重復(fù)元素

LeetCode刷題實(shí)戰(zhàn)84：?柱狀圖中最大的矩形

LeetCode刷題實(shí)戰(zhàn)85：最大矩形

LeetCode刷題實(shí)戰(zhàn)86：分隔鏈表

LeetCode刷題實(shí)戰(zhàn)87：擾亂字符串

LeetCode刷題實(shí)戰(zhàn)88：合并兩個(gè)有序數(shù)組