金3银4？网友：早就不存在了~
Web前端专栏约 4 分钟最近，我也是闲得蛋疼，在网上瞎逛，突然就看到了一条让人心慌慌的贴子：“金3银4？怎么没人回消息？”金3银4大家都知道，很多人可就指望这个了。
现在连这个黄金时期都废了吗，而评论区也是一片"哀嚎"。
大家态度都很悲观，有网友已经开始摆烂：“直接等下波金九银十看看。”
还有网友给出建议：“能狗就狗，出去找到了也不行”
还有网友也是说：“金三银四，这个是五年前的说法了，早就不存在了”
当然，也有网友提醒，“金三银四是给校招的，社招是金11银12”
评论区的"哀嚎"，让我想说，也许今年的情况真的炸了，连金3银4，以前找工作的黄金时期，大家都这个样。但正如网友说的，金3银4没了，还有金九银十，这只是一个时间段罢了。
专属福利 👉点击领取：最全Python资料合集
而我们不该考虑金3银4去哪了，我们该做的是提升自己，不然时机到了都抓不住，只要自己的能力上去了，每天都是金3银4。
今日算法题，来自LeetCode的第32题：最长有效括号，很多大厂都考过，下面是我的算法思路及实现，让我们来看看吧。
最长有效括号
算法题目
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
引言
算法思路
方法一：栈
初始化栈，栈底元素为最后一个没有被匹配的右括号的下标。
遍历字符串，对于每个字符：
如果栈为空，说明当前右括号没有匹配的左括号，将其下标入栈。
如果栈不为空，当前的有效括号长度为当前字符的下标减去栈顶元素的下标。
如果是 '('，将其下标入栈。
如果是')'，先弹出栈顶元素表示匹配，然后：
在遍历过程中记录并更新最长有效括号的长度。
方法二：动态规划
定义一个 dp 数组，其中 dp[i] 表示以 i 结尾的最长有效括号的长度。
遍历字符串，对于每个字符：
如果是 ')' 且前一个字符是 '('，则 dp[i] = dp[i-2] + 2。
如果是 ')' 且前一个字符也是 ')'，且字符串中位置为 i - dp[i-1] - 1 的字符是 '('，则 dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2。
在遍历过程中记录并更新最长有效括号的长度。
代码实现
JavaScript实现（栈方法）
function longestValidParentheses(s) {let maxLen = 0;const stack = [-1]; // 初始化栈，-1 作为哨兵for (let i = 0; i < s.length; i++) {if (s[i] === '(') {stack.push(i);} else {stack.pop();if (stack.length === 0) {stack.push(i); // 更新最后一个没有被匹配的右括号的下标} else {maxLen = Math.max(maxLen, i - stack[stack.length - 1]);}}}return maxLen;}
public int longestValidParentheses(String s) {int maxLen = 0;int[] dp = new int[s.length()];for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == ')') {if (s.charAt(i - 1) == '(') {dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}maxLen = Math.max(maxLen, dp[i]);}}return maxLen;}
func longestValidParentheses(s string) int {maxLen := 0stack := []int{-1}for i := 0; i < len(s); i++ {if s[i] == '(' {stack = append(stack, i)} else {stack = stack[:len(stack)-1]if len(stack) == 0 {stack = append(stack, i)} else {maxLen = max(maxLen, i-stack[len(stack)-1])}}}return maxLen}func max(a, b int) int {if a > b {return a}return b}
算法解析
栈方法的关键在于利用栈来跟踪可能形成有效括号子串的起始位置。栈的底部始终保持最后一个未匹配的右括号的位置，这样可以方便地计算当前有效子串的长度。
动态规划方法通过一个数组来保存到当前位置为止的最长有效括号子串的长度。它利用子问题的解来构建当前问题的解，这样可以避免重复计算。
示例和测试
对于字符串 s = "(()())"：
使用栈方法或动态规划方法都可以找到最长的有效括号子串为 "(()())"，长度为 6。
对于字符串 s = ")()())"：
最长的有效括号子串为 "()()"，长度为 4。
总结
热门推荐