題目描述:

??

思路：

?? 這道題目乍看之下沒有特別適用的算法，于是嘗試用深度優(yōu)先的方法直接暴力搜索。根據(jù)題干描述，最后生成序列的長度為2n-1。為了滿足第三個(gè)條件，在搜索過程中如果在當(dāng)前位置（假設(shè)對應(yīng)數(shù)字為i）填入除1以外的數(shù)字（假設(shè)為j），則可以在對應(yīng)i+j位置同時(shí)填入j，這樣最后得到的序列是滿足第3個(gè)條件的。而為了滿足字典序最大的條件，搜索數(shù)字時(shí)需要從n向2，從大到小搜索，這樣得到的第一個(gè)序列就是題目所求序列。以上為基本思路。

? 在代碼實(shí)現(xiàn)時(shí)，我踩過的坑主要有2個(gè)：

??? 1.代碼中遞歸調(diào)用到的地方有兩處，其中第一處是當(dāng)前位置部位不為空（即當(dāng)前位置是之前搜索中已經(jīng)填入的兩個(gè)位置中的后面一個(gè)），這種情況可以直接搜索下一個(gè)位置，但是需要注意在當(dāng)前遞歸函數(shù)搜索完成，進(jìn)入下一步時(shí)需要先驗(yàn)證一下當(dāng)前位置是否為空。如果不為空說明該位置仍然是之前已經(jīng)填入過的位置，這種情況說明前面的嘗試失敗，應(yīng)該直接返回，不進(jìn)入之后的搜索過程。如果此處再進(jìn)行修改則會導(dǎo)致不符合第三個(gè)條件。

? 2.在第二個(gè)遞歸調(diào)用的地方，如果當(dāng)前選擇的數(shù)字不是1，則應(yīng)該同時(shí)復(fù)原兩個(gè)位置為空。如果只復(fù)原一個(gè)同樣會造成前后不一的情況

代碼

??

class Solution:def constructDistancedSequence(self, n: int) -> List[int]:if n==1:return [1]vis=[False for i in range(2*n-1)]temp=['' for i in range(2*n-1)]ans=[]flag=Falsedef dfs(cur):nonlocal vis,n,ans,temp,flagif flag:returnif cur==2*n-1:ans=copy.deepcopy(temp)flag=Truereturnif temp[cur]!='':dfs(cur+1)if temp[cur]!='':returnfor i in range(n,0,-1):if not vis[i]:if i==1:temp[cur]=ielse:if cur+i>=2*n-1:continueif temp[cur+i]!='':continuetemp[cur]=itemp[cur+i]=iprint(temp,i)vis[i]=Truedfs(cur+1)vis[i]=Falseif i!=1:temp[cur+i]=''temp[cur]=''vis[i]=0dfs(0)return ans

?

總結(jié)

以上是生活随笔為你收集整理的Leetcode.1718 构建字典序最大的可行序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。