算法练习day11、有效的括号思路使用栈数据结构。遍历字符串中的每个字符如果是左括号(、[、{则将其压入栈中。如果是右括号)、]、}则检查栈是否为空以及栈顶元素是否与当前右括号匹配的左括号。如果匹配则弹出栈顶元素否则字符串无效。遍历结束后如果栈为空说明所有括号都正确匹配字符串有效否则无效。function isValid(s) { // 栈 const stack [] const map { ): (, ]: [, }: {, } for (let char of s) { // 匹配右括号 if (map[char]) { // 栈空或者栈顶不匹配 if (stack.length 0 || stack.pop() ! map[char]) { return false } } else { stack.push(char) } } return stack.length 0 } console.log(isValid({()()[]}))2、合并数组区间思路合并重叠区间。首先将所有区间按照起始位置进行排序。初始化结果数组将第一个区间放入结果中。从第二个区间开始遍历如果当前区间的起始位置小于等于结果数组中最后一个区间的结束位置说明两个区间重叠则合并它们更新最后一个区间的结束位置为两者结束位置的较大值。如果不重叠则将当前区间直接加入结果数组。遍历完成后结果数组即为合并后的不重叠区间集合。function merge(arr) { // 数组为空 // if(arr.length 0) return [] arr.sort((a, b) a[0] - b[0]) let res [arr[0]] for (let i 1; i arr.length; i) { const last res[res.length - 1] const curr arr[i] if (curr[0] last[1]) { // 合并重叠 last[1] Math.max(curr[1], last[1]) } else { res.push(curr) } } return res } console.log( merge([ [1, 7], [2, 6], [8, 15], ]), )3、无重复最长字符串长度思路使用滑动窗口双指针和集合。使用两个指针 left 和 right 表示当前窗口的左右边界初始都指向字符串开头。使用一个集合来存储当前窗口中的字符保证无重复。右指针 right 向右移动将字符加入集合如果加入的字符导致集合中出现重复则移动左指针 left并从集合中删除 left 指向的字符直到重复字符被移除。在每次右指针移动后计算当前窗口长度right - left 1并更新最大长度 maxLen。遍历结束后maxLen 即为无重复字符的最长子串长度。function longlength(str) { // 滑动窗口双指针 let left 0 let maxLen 0 const set new Set() for (let right 0; right str.length; right) { while (set.has(str[right])) { set.delete(str[left]) left } set.add(str[right]) maxLen Math.max(maxLen, right - left 1) } return maxLen } console.log(longlength(abcab))
)
