亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

阿里二面算法題

番茄西紅柿 / 2993人閱讀

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

最長(zhǎng)的括號(hào)子串

問(wèn)題描述

給出一個(gè)長(zhǎng)度為 n 的，僅包含字符 ( 和 ) 的字符串，計(jì)算最長(zhǎng)的格式正確的括號(hào)子串的長(zhǎng)度。

示例：

輸入："(())"

輸出：4

解析：對(duì)于"(())"來(lái)說(shuō)，最長(zhǎng)格式正確的子串是"(())"，所以為4。

分析問(wèn)題

對(duì)于括號(hào)匹配問(wèn)題，最直觀的想法就是采用棧來(lái)求解。所以，我們也可以采用棧來(lái)求解這道題。具體來(lái)說(shuō)，我們?cè)诒闅v給定字符串的過(guò)程中，需要始終保證棧底元素為當(dāng)前已經(jīng)遍歷過(guò)的元素中，最后一個(gè)沒(méi)有被匹配的右括號(hào)的下標(biāo)，棧中的其它元素維護(hù)左括號(hào)的下標(biāo)。

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

這里需要注意一點(diǎn)，因?yàn)橐婚_始棧為空，如果此時(shí)第一個(gè)字符為左括號(hào)時(shí)，我們會(huì)將其對(duì)應(yīng)的下標(biāo)放入棧中，這樣就不滿足棧底始終保存的是最后一個(gè)沒(méi)有被匹配的右括號(hào)的下標(biāo)這個(gè)條件，為了保證該條件成立，我們?cè)陂_始時(shí)需要往棧中放入一個(gè)元素-1。

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

image-20211029222525672

image-20211029222544254

image-20211029222628761

image-20211029222646218

下面我們來(lái)看一下代碼實(shí)現(xiàn)。

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

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

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

對(duì)于求最優(yōu)解問(wèn)題，我們一般首先需要考慮的就是動(dòng)態(tài)規(guī)劃的解法。顯然，求最長(zhǎng)的括號(hào)子串是最優(yōu)解問(wèn)題，所有我們也可以采用動(dòng)態(tài)規(guī)劃的思想來(lái)求解。

首先我們定義dp[i]表示以下標(biāo)i字符結(jié)尾的最長(zhǎng)有效括號(hào)的長(zhǎng)度，初始時(shí)數(shù)組dp全為0。對(duì)于有效的括號(hào)子串來(lái)說(shuō)，顯然是以字符‘）’結(jié)尾的，因此我們可以知道以‘（’結(jié)尾的子串對(duì)應(yīng)的dp值必然為0，所以我們只需要求解字符‘）’在dp數(shù)組中對(duì)應(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]=‘）’，也就是字符串是“.........))...”的形式，此時(shí)如果s[i-dp[i-1]-1] = ‘（’，那么

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

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

image-20211029222732045

image-20211029222748680

image-20211029222807374

image-20211029222823818

下面我們來(lái)看一下代碼的實(shí)現(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

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

?

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/123772.html

相關(guān)文章

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

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

    Winer 評(píng)論0 收藏1

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

    摘要：春招結(jié)果五月份了，春招已經(jīng)接近尾聲，因?yàn)榈搅酥芪逋砩蟿偤糜锌?，所以?jiǎn)單地記錄一下自己的春招過(guò)程。我的春招從二月初一直持續(xù)到四月底，截止今天，已經(jīng)斬獲唯品會(huì)電商前端研發(fā)部大數(shù)據(jù)與威脅分析事業(yè)部京東精銳暑假實(shí)習(xí)生的騰訊的是早上打過(guò)來(lái)的。 春招結(jié)果 五月份了，春招已經(jīng)接近尾聲，因?yàn)榈搅酥芪逋砩蟿偤糜锌眨院?jiǎn)單地記錄一下自己的春招過(guò)程。我的春招從二月初一直持續(xù)到四月底，截止今天，已經(jīng)斬獲唯品...

    freewolf 評(píng)論0 收藏1

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

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

    lemanli 評(píng)論0 收藏0

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

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

    xfee 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<