2021-08-19leetcode刷題

區(qū)間dp降低時(shí)間復(fù)雜度

給你一個(gè)字符串 s 叉讥,找出其中最長(zhǎng)的回文子序列,并返回該序列的長(zhǎng)度饥追。
子序列定義為:不改變剩余字符順序的情況下图仓,刪除某些字符或者不刪除任何字符形成的一個(gè)序列。
示例 1:
輸入:s = "bbbab"
輸出:4
解釋:一個(gè)可能的最長(zhǎng)回文子序列為 "bbbb" 但绕。

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/longest-palindromic-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有救崔。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán),非商業(yè)轉(zhuǎn)載請(qǐng)注明出處捏顺。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n=len(s)
        dp=[[0]*n for _ in range(n)]
        for i in range(n-1,-1,-1):#需要記憶
            dp[i][i]=1
            for j in range(i+1,n):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j])
        return dp[0][n-1]

        '''
        ans=1
        #純暴力解法O(2^N*N^2)
        for i in range(len(s)):
            s1,s2='',''
            for j in s[i:]:
                s1+=j
                s2=j+s2
                if s1==s2:
                    ans=max(ans,len(s1))
        return ans
        '''

順序無所謂帚豪,注意規(guī)劃到最外側(cè)時(shí)的結(jié)果,區(qū)間dp從中心向外擴(kuò)展

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n=len(s)
        dp=[[0]*n for _ in range(n)]
        for i in range(n):#需要記憶
            dp[i][i]=1
            for j in range(i-1,-1,-1):
                if s[i]==s[j]:
                    dp[i][j]=dp[i-1][j+1]+2
                else:
                    dp[i][j]=max(dp[i][j+1],dp[i-1][j])
        return dp[n-1][0]

image.png

關(guān)于另一個(gè)二維DP問題:兩個(gè)序列的最大公共子序列

給定兩個(gè)字符串 text1 和 text2草丧,返回這兩個(gè)字符串的最長(zhǎng) 公共子序列 的長(zhǎng)度狸臣。如果不存在 公共子序列 ,返回 0 昌执。
一個(gè)字符串的 子序列 是指這樣一個(gè)新的字符串:它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符(也可以不刪除任何字符)后組成的新字符串烛亦。
例如,"ace" 是 "abcde" 的子序列懂拾,但 "aec" 不是 "abcde" 的子序列煤禽。
兩個(gè)字符串的 公共子序列 是這兩個(gè)字符串所共同擁有的子序列。

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/longest-common-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有岖赋。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)檬果,非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n=len(text1),len(text2)
        dp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    try:
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                    except:
                        print(i,j)
        return dp[m][n]

修改思路+一次過+極限內(nèi)存消耗以及時(shí)間復(fù)雜度

376. 擺動(dòng)序列

難度中等485 收藏 分享 切換為英文 接收動(dòng)態(tài) 反饋
如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替唐断,則數(shù)字序列稱為** 擺動(dòng)序列 选脊。**第一個(gè)差(如果存在的話)可能是正數(shù)或負(fù)數(shù)。僅有一個(gè)元素或者含兩個(gè)不等元素的序列也視作擺動(dòng)序列脸甘。

  • 例如恳啥, [1, 7, 4, 9, 2, 5] 是一個(gè) 擺動(dòng)序列 ,因?yàn)椴钪?(6, -3, 5, -7, 3) 是正負(fù)交替出現(xiàn)的丹诀。
  • 相反钝的,[1, 4, 7, 2, 5][1, 7, 4, 5, 5] 不是擺動(dòng)序列,第一個(gè)序列是因?yàn)樗那皟蓚€(gè)差值都是正數(shù)铆遭,第二個(gè)序列是因?yàn)樗淖詈笠粋€(gè)差值為零硝桩。
    子序列 可以通過從原始序列中刪除一些(也可以不刪除)元素來獲得,剩下的元素保持其原始順序枚荣。
    給你一個(gè)整數(shù)數(shù)組 nums 碗脊,返回 nums 中作為 擺動(dòng)序列 的 最長(zhǎng)子序列的長(zhǎng)度
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        dp_p,dp_n=1,1
        for i in range(1,len(nums)):
            if nums[i]-nums[i-1]>0:
                dp_p=dp_n+1
            elif nums[i]-nums[i-1]<0:
                dp_n=dp_p+1
        return max(dp_p,dp_n)

image.png

約瑟夫環(huán)問題的遞歸方程解法棍弄,當(dāng)只有一個(gè)字的時(shí)候返回位置0

否則設(shè)f(n,k)即n個(gè)字k個(gè)距離最后一個(gè)的答案
易知:
f(n,k)=(f(n-1,k)+k)%k

  • 即得到轉(zhuǎn)移方程望薄,使用動(dòng)態(tài)規(guī)劃或者遞歸
class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        def transfer_equation(n,k):
            return 0 if n==1 else (transfer_equation(n-1,k)+k)%n
        return transfer_equation(n,k)+1
image.png

設(shè)計(jì)一個(gè)支持 push ,pop 呼畸,top 操作痕支,并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
push(x) —— 將元素 x 推入棧中蛮原。
pop() —— 刪除棧頂?shù)脑亍?br> top() —— 獲取棧頂元素卧须。
getMin() —— 檢索棧中的最小元素。

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/min-stack
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有儒陨。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)花嘶,非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

class MinStack:

   def __init__(self):
       """
       initialize your data structure here.
       """
       self.ds=[]
       #使用輔助棻哪或者多用一個(gè)變量,不可以椭员,為了保持刪除同步
       self.min_=[math.inf]#math.inf


   def push(self, val: int) -> None:
       self.ds.append(val)
       self.min_.append(min(self.min_[-1],val))



   def pop(self) -> None:
       self.ds.pop()
       self.min_.pop()


   def top(self) -> int:
       return self.ds[-1]


   def getMin(self) -> int:
       return self.min_[-1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

棧的用法精妙示意

給你一個(gè)由 '('、')' 和小寫字母組成的字符串 s笛园。
你需要從字符串中刪除最少數(shù)目的 '(' 或者 ')' (可以刪除任意位置的括號(hào))隘击,使得剩下的「括號(hào)字符串」有效。
請(qǐng)返回任意一個(gè)合法字符串研铆。
有效「括號(hào)字符串」應(yīng)當(dāng)符合以下 任意一條 要求:
空字符串或只包含小寫字母的字符串
可以被寫作 AB(A 連接 B)的字符串埋同,其中 A 和 B 都是有效「括號(hào)字符串」
可以被寫作 (A) 的字符串,其中 A 是一個(gè)有效的「括號(hào)字符串」

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有棵红。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)凶赁,非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        set_remove_idx=set()
        stack=[]
        for i in range(len(s)):
            if s[i] not in '()':
                #print('hi')
                continue
            elif s[i]=='(':
                stack.append(i)
            elif not stack:
                set_remove_idx.add(i)
            else:
                stack.pop()
        set_remove_idx=set_remove_idx.union(set(stack))
        #print(set_remove_idx)
        ans=[]
        for i,x in enumerate(s):
            if i not in set_remove_idx:
                ans.append(x)
        return ''.join(ans)

        '''
        ans,left_bracket,right_bracket=[],0,0
        for i in s:
            if i=='(':
                left_bracket+=1
                ans.append(i)
            elif i==')':
                if right_bracket<left_bracket:
                    right_bracket+=1
                    ans.append(i)
            else:
                ans.append(i)
        print(ans)
        if left_bracket>right_bracket:
            flag=[True]*len(ans)
            for i in range(len(ans)):
                if ans[i]=='(':
                    flag[i]=False
                    left_bracket-=1
                    if left_bracket==right_bracket:
                        break
            ans=[ans[i] for i  in range(len(ans)) if flag[i]]
        return ''.join(ans)
        '''

使用棧記錄多余的左括號(hào)逆甜,使用集合記錄多的右括號(hào)虱肄,最后union進(jìn)集合。方便O(1)時(shí)間復(fù)雜度解決交煞。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末浩峡,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子错敢,更是在濱河造成了極大的恐慌翰灾,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,509評(píng)論 6 504
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件稚茅,死亡現(xiàn)場(chǎng)離奇詭異纸淮,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)亚享,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,806評(píng)論 3 394
  • 文/潘曉璐 我一進(jìn)店門咽块,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人欺税,你說我怎么就攤上這事侈沪〗伊В” “怎么了?”我有些...
    開封第一講書人閱讀 163,875評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵亭罪,是天一觀的道長(zhǎng)瘦馍。 經(jīng)常有香客問我,道長(zhǎng)应役,這世上最難降的妖魔是什么情组? 我笑而不...
    開封第一講書人閱讀 58,441評(píng)論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮箩祥,結(jié)果婚禮上院崇,老公的妹妹穿的比我還像新娘。我一直安慰自己袍祖,他們只是感情好底瓣,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,488評(píng)論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著蕉陋,像睡著了一般濒持。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上寺滚,一...
    開封第一講書人閱讀 51,365評(píng)論 1 302
  • 那天柑营,我揣著相機(jī)與錄音,去河邊找鬼村视。 笑死官套,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的蚁孔。 我是一名探鬼主播奶赔,決...
    沈念sama閱讀 40,190評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼杠氢!你這毒婦竟也來了站刑?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,062評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤鼻百,失蹤者是張志新(化名)和其女友劉穎绞旅,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體温艇,經(jīng)...
    沈念sama閱讀 45,500評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡因悲,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,706評(píng)論 3 335
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了勺爱。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片晃琳。...
    茶點(diǎn)故事閱讀 39,834評(píng)論 1 347
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出卫旱,到底是詐尸還是另有隱情人灼,我是刑警寧澤,帶...
    沈念sama閱讀 35,559評(píng)論 5 345
  • 正文 年R本政府宣布顾翼,位于F島的核電站投放,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏暴构。R本人自食惡果不足惜跪呈,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,167評(píng)論 3 328
  • 文/蒙蒙 一段磨、第九天 我趴在偏房一處隱蔽的房頂上張望取逾。 院中可真熱鬧,春花似錦苹支、人聲如沸砾隅。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,779評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽晴埂。三九已至,卻和暖如春寻定,著一層夾襖步出監(jiān)牢的瞬間儒洛,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,912評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工狼速, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留琅锻,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,958評(píng)論 2 370
  • 正文 我出身青樓向胡,卻偏偏與公主長(zhǎng)得像恼蓬,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子僵芹,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,779評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容