阿里二面算法题

番茄西红柿发布于2021-11-18 10:07 / 2917人阅读

摘要：分析问题分析问题对于括号匹配问题，最直观的想法就是采用栈来求解。如果是左括号，将其对应的下标加入栈中如果是右括号，栈顶元素出去该算法的时间复杂度和空间复杂度都是。下面我们来看一下代码的实现。

最长的括号子串

问题描述

给出一个长度为 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有趣算法题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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