成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

阿里二面算法題

番茄西紅柿 / 2965人閱讀

摘要：分析問題分析問題對于括號匹配問題，最直觀的想法就是采用棧來求解。如果是左括號，將其對應(yīng)的下標(biāo)加入棧中如果是右括號，棧頂元素出去該算法的時間復(fù)雜度和空間復(fù)雜度都是。下面我們來看一下代碼的實現(xiàn)。

最長的括號子串

問題描述

給出一個長度為 n 的，僅包含字符 ( 和 ) 的字符串，計算最長的格式正確的括號子串的長度。

示例：

輸入："(())"

輸出：4

解析：對于"(())"來說，最長格式正確的子串是"(())"，所以為4。

分析問題

對于括號匹配問題，最直觀的想法就是采用棧來求解。所以，我們也可以采用棧來求解這道題。具體來說，我們在遍歷給定字符串的過程中，需要始終保證棧底元素為當(dāng)前已經(jīng)遍歷過的元素中，最后一個沒有被匹配的右括號的下標(biāo)，棧中的其它元素維護(hù)左括號的下標(biāo)。

  1. 如果遇到的是左括號‘（’，我們就把它的下標(biāo)放入棧中；
  2. 如果遇到的是右括號‘）’，此時有兩種情況；
    • 如果此時棧為空，說明當(dāng)前的右括號是沒有被匹配的右括號，
    • 如果此時棧不為空，右括號的下標(biāo)減去棧頂元素即為「以該右括號為結(jié)尾的最長有效括號的長度」，然后用它來更新最大值即可。

這里需要注意一點，因為一開始棧為空，如果此時第一個字符為左括號時，我們會將其對應(yīng)的下標(biāo)放入棧中，這樣就不滿足棧底始終保存的是最后一個沒有被匹配的右括號的下標(biāo)這個條件，為了保證該條件成立，我們在開始時需要往棧中放入一個元素-1。

我們以“())(())”為例，來看一下執(zhí)行過程。

image-20211029222525672

image-20211029222544254

image-20211029222628761

image-20211029222646218

下面我們來看一下代碼實現(xiàn)。

class Solution(object):    def longestValidParentheses(self, s):        stack=[]        n=len(s)        stack.append(-1)        maxlen=0        for i in range(0,n):            #如果是左括號，將其對應(yīng)的下標(biāo)加入棧中            if s[i]==(:                stack.append(i)            else:                #如果是右括號，棧頂元素pop出去                stack.pop()                if not stack:                    stack.append(i)                else:                    maxlen = max(maxlen, i - stack[-1])        return maxlen

該算法的時間復(fù)雜度和空間復(fù)雜度都是O(n)。

動態(tài)規(guī)劃解法

對于求最優(yōu)解問題，我們一般首先需要考慮的就是動態(tài)規(guī)劃的解法。顯然，求最長的括號子串是最優(yōu)解問題，所有我們也可以采用動態(tài)規(guī)劃的思想來求解。

首先我們定義dp[i]表示以下標(biāo)i字符結(jié)尾的最長有效括號的長度，初始時數(shù)組dp全為0。對于有效的括號子串來說，顯然是以字符‘）’結(jié)尾的，因此我們可以知道以‘（’結(jié)尾的子串對應(yīng)的dp值必然為0，所以我們只需要求解字符‘）’在dp數(shù)組中對應(yīng)位置的值即可。

我們從前往后遍歷字符串s。

  1. 如果s[i]=‘）’且 s[i-1]=‘（’，也就是字符串是 “....()....()....”的形式，那么我們可以得出狀態(tài)轉(zhuǎn)移方程為dp[i] = dp[i-2] + 2。

  2. 如果s[i]=‘）’且 s[i-1]=‘）’，也就是字符串是“.........))...”的形式，此時如果s[i-dp[i-1]-1] = ‘（’，那么

    dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]

    解釋：如果 s[i-1] 對應(yīng)的 ‘）’ 是有效子字符串的一部分，我們假設(shè)為sub1，那么它的的長度為dp[i-1]，如果s[i]對應(yīng)的‘）’是一個更長子字符串的一部分，那么一定有一個對應(yīng)的‘（’與子相匹配，且它的位置在sub1的之前。如果sub1的前面恰好是‘（’，即“ (sub1) ”的形式，那么dp[i]=dp[i-1] + 2 + dp[i-dp[i-1] - 2] ，其中dp[i-dp[i-1] - 2] 表示字符串“(sub1)”前面的有效子串的長度，我們需要加上。

image-20211029222732045

image-20211029222748680

image-20211029222807374

image-20211029222823818

下面我們來看一下代碼的實現(xiàn)。

class Solution(object):    def longestValidParentheses(self, s):        maxlen=0        n=len(s)        dp=[0] * n        for i in range(1,n):            #如果s[i]==)并且s[i-1]==(,那么dp[i] = dp[i-2]+2            if s[i]==):                if s[i-1]==(:                    dp[i] = 2 + (dp[i-2] if i>=2 else 0)                elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1]==(:                    dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i-dp[i-1]>=2 else 0)                maxlen=max(maxlen,dp[i])        return maxlen

該算法的時間復(fù)雜度是O(n)，空間復(fù)雜度也是O(n)。

?

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/123772.html

相關(guān)文章

  • 我的春招求職經(jīng)驗分享（已拿阿里京東網(wǎng)易等 5 個 offer）

    摘要：面經(jīng)因為我完全沒有面試經(jīng)驗，從來沒有經(jīng)歷過面試，于是想著在去這類大公司面試之前先找成都的小公司練練手，積累點面試經(jīng)驗。于是三月份開始就有成都的小公司開始約我面試。 前序 從我高考成績出來那一刻開始，從我在高考志愿上填上計算機(jī)科學(xué)與技術(shù)這幾個當(dāng)時在心中堪稱神圣的幾個字開始，我就已經(jīng)把進(jìn)入中國互聯(lián)網(wǎng)最高殿堂BAT作為我整個大學(xué)奮斗的目標(biāo)，哪怕我就讀的是一所位于內(nèi)陸的雙非一本大學(xué)我也認(rèn)為我能...

    Winer 評論0 收藏1

  • 記錄一下自己的春招，唯品會、360、京東offer已收、騰訊offer_call已達(dá)?。?！

    摘要：春招結(jié)果五月份了，春招已經(jīng)接近尾聲，因為到了周五晚上剛好有空，所以簡單地記錄一下自己的春招過程。我的春招從二月初一直持續(xù)到四月底，截止今天，已經(jīng)斬獲唯品會電商前端研發(fā)部大數(shù)據(jù)與威脅分析事業(yè)部京東精銳暑假實習(xí)生的騰訊的是早上打過來的。 春招結(jié)果 五月份了，春招已經(jīng)接近尾聲，因為到了周五晚上剛好有空，所以簡單地記錄一下自己的春招過程。我的春招從二月初一直持續(xù)到四月底，截止今天，已經(jīng)斬獲唯品...

    freewolf 評論0 收藏1

  • [面試專題]一線互聯(lián)網(wǎng)大廠面試總結(jié)

    摘要：道阻且長啊前端面試總結(jié)前端面試筆試面試騰訊一面瀏覽器工作原理瀏覽器的主要組件包括用戶界面包括地址欄后退前進(jìn)按鈕書簽?zāi)夸洖g覽器引擎用來查詢及操作渲染引擎的接口渲染引擎渲染界面和是基于兩種渲染引擎構(gòu)建的，使用自主研發(fā)的渲染引擎，和都使用網(wǎng)絡(luò)用來 道阻且長啊TAT(前端面試總結(jié)) 前端 面試 筆試 面試 騰訊一面 1.瀏覽器工作原理 瀏覽器的主要組件包括： 用戶界面－ 包括地址欄、后退/前...

    lemanli 評論0 收藏0

  • [面試專題]一線互聯(lián)網(wǎng)大廠面試總結(jié)

    摘要：道阻且長啊前端面試總結(jié)前端面試筆試面試騰訊一面瀏覽器工作原理瀏覽器的主要組件包括用戶界面包括地址欄后退前進(jìn)按鈕書簽?zāi)夸洖g覽器引擎用來查詢及操作渲染引擎的接口渲染引擎渲染界面和是基于兩種渲染引擎構(gòu)建的，使用自主研發(fā)的渲染引擎，和都使用網(wǎng)絡(luò)用來 道阻且長啊TAT(前端面試總結(jié)) 前端 面試 筆試 面試 騰訊一面 1.瀏覽器工作原理 瀏覽器的主要組件包括： 用戶界面－ 包括地址欄、后退/前...

    xfee 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<