每日算法（第十五期）-Toy模板网

这篇具有很好参考价值的文章主要介绍了每日算法（第十五期）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

先来回顾一下上期的问题及答案：

「有效的括号」（Valid Parentheses）。

题目描述：给定一个只包含字符 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

解题思路：

使用栈来匹配括号。
遍历字符串，如果当前字符是左括号（'(', '[', '{'），则将其入栈。
如果当前字符是右括号（')', ']', '}'），则从栈顶取出一个字符，如果它与当前字符匹配，则继续遍历；否则返回 false。
最后，检查栈是否为空，如果为空则表示所有括号都匹配成功，返回 true；否则返回 false。

以下是对应的实现：

function isValid(s) {
  const stack = [];

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      if (stack.length === 0) {
        return false;
      }
      const top = stack.pop();
      if (
        (char === ')' && top !== '(') ||
        (char === ']' && top !== '[') ||
        (char === '}' && top !== '{')
      ) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

时间复杂度分析：

遍历字符串的时间复杂度为 O(n)，其中 n 是字符串的长度。

空间复杂度分析：

最坏情况下，栈的深度与字符串的长度相等，所以空间复杂度为 O(n)。

例如：

console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true

在上述例子中，给定字符串分别为 "()"、"()[]{}"、"(]"、"([)]" 和 "{[]}"。通过调用 isValid 函数判断字符串是否有效。有效的字符串返回 true，无效的字符串返回 false。

2023年6月3日

「最大子序和」（Maximum Subarray）。

题目描述：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。提示：使用动态规划的思想解决问题。

定义两个变量 maxSum 和 currSum，分别表示最大和和当前连续子数组的和，初始化为数组的第一个元素。

遍历数组，对于每个元素，计算当前元素加入之后的连续子数组的和，与当前元素自身进行比较，取较大的值作为新的 currSum。

同时，更新 maxSum，记录最大的和。

最终返回 maxSum。

要求的结果：

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5, 4, -1, 7, 8])); // 23

上面问题的答案会在第二天的公众号推文中公布，大家可以关注公众号：程序员每日三问，第一时间获得推送内容。

学习不打烊，充电加油只为遇到更好的自己,每天早上9点纯手工发布面试题（死磕自己，愉悦大家）希望大家在这浮夸的程序员圈里保持冷静，每天坚持花20分钟来学习与思考，在千变万化，类库层出不穷的今天，不要等到找工作时才狂刷题，提倡每日学习。文章来源地址https://www.toymoban.com/news/detail-469815.html

到了这里，关于每日算法（第十五期）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！