lc22

发表于

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：”bb”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let n = s.length
    if (n < 2) return s
    let begin = 0, maxLen  = 1

    const arr = new Array(n).fill(false).map(() => new Array(n).fill(false))
    for(let i = 0; i < n; i++) arr[i][i] = true
    // L为枚举长度
    for(let L = 2; L <= n; L++){
        for(let i = 0; i < n; i++){
            // 由于 j - i + 1 = L
            let j = L + i - 1
            // 如果长度超出, 则break
            if(j >= n) break

            if(s[i].charCodeAt() !== s[j].charCodeAt()){
                arr[i][j] = false
            }
            else {
                if(j - i < 3) arr[i][j] = true
                else arr[i][j] = arr[i + 1][j - 1]
            }
            if(arr[i][j] && j - i + 1 > maxLen){
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    return s.substr(begin, maxLen)
};

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    function sum (h, t) {
        return (t - h) * Math.min(height[h], height[t])
    }

    let n = height.length
    if(n < 3) return Math.min(height[0], height[1])
    let head = 0, tail = n - 1
    let maxSize = sum(head, tail)
    while(head < tail){
        if(height[head] < height[tail]) {
          maxSize = Math.max(sum(head + 1, tail), maxSize) 
          ++head
        }
        else  {
          maxSize = Math.max(sum(head, tail - 1), maxSize) 
          --tail
        }
    }
    return maxSize
};

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  let ans = []
  let n = nums.length
  if(n < 3) return ans
  //排序后就能用双指针了
  nums.sort((a, b) => a - b)
  // 固定第一个数
  for(let i = 0; i < n; i++){
    if(nums[i] > 0) return ans

    if(i > 0 && nums[i] === nums[i - 1]) continue
    
    // 双向遍历, 双指针必要条件之一
    let left = i + 1, right = n - 1

    while(left < right){
      // 大了就right--
      if(nums[left] + nums[right] > -nums[i]) --right
      // 小了就left++
      else if(nums[left] + nums[right] < -nums[i]) ++left
      // 正好满足条件, 保存答案, 移动左右指针一格
      else {
        ans.push([nums[left], nums[right], nums[i]])
        
        ++left
        --right

        // 第二 第三个数也不能重复
        while(left < right && nums[left] === nums[left - 1]) left++
        while(left < right && nums[right] === nums[right + 1]) right-- 
      }
    }
  }
  return ans
};

17. 电话号码的字母组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// dfs

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  // 初始化数据
  const board = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  const ans = [], n = digits.length
  // 构建递归函数, 另一种构造函数方法
  const dfs = (letter, i) => {
    if(n === i) 
    {
      ans.push(letter)
      return
    }
      // 展开数组写法
    let s = [...board[parseInt(digits[i])]]

    i++
    for(item of s){
      dfs(letter + item, i)
    }
  }
  // 递归入口
  dfs('', 0)
  // 判断结果长度, 为1则证明是空数组
  return ans.length < 2 ? [] : ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// bfs

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  const board = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

  // 创建队列
  let que = ['']
  
  // 广搜的层数
  for(let i = 0; i < digits.length; i++){
    let curNum = que.length   //当前队列中的元素个数
    let newQue = []
    for(let j = 0; j < curNum; j++){
      let newLetter = que.shift() //取出第一个字符串

      for(idx of board[parseInt(digits[i])]){
        newQue.push(newLetter + idx)    //放入新数组
      }
    }
    // 指向新数组
    que = newQue
  }
  return que.length < 2 ? [] : que
};

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  // 建立映射
  const rules = new Map([['(', ')'], ['{', '}'], ['[', ']']])
  const stk = []  //模拟栈
  for(i of s){
    if(i === '(' || i === '[' || i === '{') stk.push(i)
    else {
      if(stk.length === 0) return false
      else {
        let pop = stk.pop()
        if(i !== rules.get(pop)) return false
      }
    }
  }
  // 如果栈不为空 错误
  if(stk.length !== 0) return false
  return true
};