阿里二面算法題

番茄西紅柿發布于2021-11-18 10:07 / 2933人閱讀

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

最長的括號子串

問題描述

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

示例：

輸入："(())"

輸出：4

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

分析問題

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

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

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

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

下面我們來看一下代碼實現。

class Solution(object):    def longestValidParentheses(self, s):        stack=[]        n=len(s)        stack.append(-1)        maxlen=0        for i in range(0,n):            #如果是左括號，將其對應的下標加入棧中            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

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

動態規劃解法

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

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

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

如果s[i]=‘）’且 s[i-1]=‘（’，也就是字符串是 “....()....()....”的形式，那么我們可以得出狀態轉移方程為dp[i] = dp[i-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] 對應的 ‘）’ 是有效子字符串的一部分，我們假設為sub₁，那么它的的長度為dp[i-1]，如果s[i]對應的‘）’是一個更長子字符串的一部分，那么一定有一個對應的‘（’與子相匹配，且它的位置在sub₁的之前。如果sub₁的前面恰好是‘（’，即“ (sub₁) ”的形式，那么dp[i]=dp[i-1] + 2 + dp[i-dp[i-1] - 2] ，其中dp[i-dp[i-1] - 2] 表示字符串“(sub₁)”前面的有效子串的長度，我們需要加上。

下面我們來看一下代碼的實現。

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

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

GPU云服務器云服務器 javascript算法題字符串算法題最難的算法題 java有趣算法題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123772.html

我的春招求職經驗分享（已拿阿里京東網易等 5 個 offer）

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

Winer 2019-08-15 15:48 評論0 收藏1
記錄一下自己的春招，唯品會、360、京東offer已收、騰訊offer_call已達！！！

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

freewolf 2019-08-22 16:57 評論0 收藏1
[面試專題]一線互聯網大廠面試總結

摘要：道阻且長啊前端面試總結前端面試筆試面試騰訊一面瀏覽器工作原理瀏覽器的主要組件包括用戶界面包括地址欄后退前進按鈕書簽目錄瀏覽器引擎用來查詢及操作渲染引擎的接口渲染引擎渲染界面和是基于兩種渲染引擎構建的，使用自主研發的渲染引擎，和都使用網絡用來道阻且長啊TAT(前端面試總結) 前端面試筆試面試騰訊一面 1.瀏覽器工作原理瀏覽器的主要組件包括：用戶界面－包括地址欄、后退/前...

lemanli 2019-08-02 15:57 評論0 收藏0
[面試專題]一線互聯網大廠面試總結

摘要：道阻且長啊前端面試總結前端面試筆試面試騰訊一面瀏覽器工作原理瀏覽器的主要組件包括用戶界面包括地址欄后退前進按鈕書簽目錄瀏覽器引擎用來查詢及操作渲染引擎的接口渲染引擎渲染界面和是基于兩種渲染引擎構建的，使用自主研發的渲染引擎，和都使用網絡用來道阻且長啊TAT(前端面試總結) 前端面試筆試面試騰訊一面 1.瀏覽器工作原理瀏覽器的主要組件包括：用戶界面－包括地址欄、后退/前...

xfee 2019-08-21 11:53 評論0 收藏0