算法面試真題：完美走位

題目

在第一人稱射擊游戲中，玩家通過鍵盤的A、S、D、W四個按鍵控制游戲人物分別向左、向后、向右、向前進行移動，從而完成走位。

假設玩家每按動一次鍵盤，游戲人物會向某個方向移動一步，如果玩家在操作一定次數(shù)的鍵盤并且各個方向的步數(shù)相同時，此時游戲人物必定會回到原點，則稱此次走位為完美走位。

現(xiàn)給定玩家的走位（例如：ASDA）,請通過更換其中一段連續(xù)走位的方式使得原走位能夠變成一個完美走位。其中待更換的連續(xù)走位可以是相同長度的任何走位。

請返回待更換的連續(xù)走位的最小可能長度。若果原走位本身是一個完美走位，則返回0。

輸入

輸入為由鍵盤字母表示的走位s，例如：ASDA

輸出

輸出為待更換的連續(xù)走位的最小可能長度

備注

走位長度1 ≤ s.length ≤ 10^5

s.length是4的倍數(shù)

s中只含有A,S,D,W四種字符

示例一

輸入

ASDW

輸出

0

說明

已經(jīng)是完美走位了。

示例二

輸入

AASW

輸出

1

說明

需要把一個A更換成D，這樣可以得到ADSW或者DASW。

示例三

輸入

AAAA

輸出

3

說明

可以替換后3個A，得到ASDW。

示例四

輸入

AAAAADDD

輸出

4

解題思路

“

注意，本題和LC76. 最小覆蓋子串幾乎完全一致。重點在于如何將原問題轉化為覆蓋子串的問題。

”

題目有兩個重要條件：

完美走位字符串是指字符串中A、S、D、W四種字符出現(xiàn)次數(shù)相等的字符串

s.length是4的倍數(shù)

對于長度為len(s)的原字符串s來說，為了使其轉變?yōu)橐粋€完美走位字符串，其中A、S、D、W四種字符出現(xiàn)次數(shù)應該均為num = len(s) // 4。

原字符串s中各個字符出現(xiàn)的次數(shù)可以用哈希表cnt_s = Counter(s)進行統(tǒng)計，對于出現(xiàn)次數(shù)多于num = len(s) // 4的字符ch，應該修改cnt_s[ch] - len(s) // 4個字符為其他出現(xiàn)次數(shù)少于num = len(s) // 4的字符，才能夠使得s變?yōu)橐粋€完美走位字符串。

以示例四為例，s = "AAAAADDD"，字符"A"出現(xiàn)的次數(shù)為5，字符"D"應該修改3，而num = len(s) // 4 = 2，需要修改3個"A"和1個"D"為剩余兩種字符，才能使得s變?yōu)橥昝雷呶蛔址?。故我們需要找到包?個"A"和1個"D"的最小子串。

因此這個問題就轉變?yōu)榱?，找到覆蓋cnt_s[ch] - len(s) // 4個的字符ch（ch滿足條件cnt_s[ch] > len(s) // 4）的最短子串。需要覆蓋的子串中所出現(xiàn)的字符以及次數(shù)，可以用另一個哈希表cnt_sub儲存。

那么這個問題就和LC76. 最小覆蓋子串完全一致了。上述邏輯整理為代碼即

num=len(s)//4
cnt_s=Counter(s)
cnt_sub={k:v-numfork,vincnt_s.items()ifv>num}

代碼

#題目：2023Q1A-完美走位
#分值：100
#作者：許老師&&吳師兄學算法
#算法：不定滑窗
#代碼看不懂的地方，請直接在群上提問


fromcollectionsimportCounter
frommathimportinf


#定義輔助函數(shù)check()
#用于檢查cnt_sub中的各個字符是否出現(xiàn)在cnt_win中，
#且cnt_win中的個數(shù)大于等于cnt_sub
defcheck(cnt_win,cnt_sub):
returnall(cnt_win[k]>=cnt_sub[k]forkincnt_sub)


s=input()
num=len(s)//4
#獲得原字符串中所有字符的出現(xiàn)次數(shù)
cnt_s=Counter(s)
#獲得需要覆蓋的子串的字符以及出現(xiàn)次數(shù)
cnt_sub={k:v-numfork,vincnt_s.items()ifv>num}

#如果cnt_sub長度為0，說明每一種字符出現(xiàn)次數(shù)相等
#s已經(jīng)是一個完美走位字符串，輸出0
iflen(cnt_sub)==0:
print(0)
#否則要進行類似LC76.最小覆蓋子串的不定滑窗過程
else:
#初始化滑窗對應的哈希表、最小覆蓋的窗口長度
cnt_win=Counter()
ans=inf
left=0

forright,chinenumerate(s):
# Q1：對于每一個右指針right所指的元素ch，做什么操作？
# A1：將其加入哈希表cnt_win的計數(shù)中
cnt_win[ch]+=1
# Q2：什么時候要令左指針left右移？在什么條件下left停止右移？【循環(huán)不變量】
# A2：check(cnt_win, cnt_sub)為True，left可以右移以縮小窗口長度
whilecheck(cnt_win,cnt_sub):
# Q3：什么時候進行ans的更新？
# A3：check(cnt_win, cnt_sub)為True
ans=min(ans,right-left+1)
cnt_win[s[left]]-=1
left+=1

print(ans)

時空復雜度

時間復雜度：O(N)。僅需一次遍歷整個字符串s。

空間復雜度：O(1)。只有4種字符，哈希表所占用空間為常數(shù)級別空間。

審核編輯：湯梓紅