20. 有效的括号

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

有效字符串需满足：

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

示例 1： 输入：s = ”()” 输出：true

示例 2： 输入：s = ”()[]{}” 输出：true

思路

典中典堆栈判断有效括号，遇到左括号将其入栈，遇到右括号跟栈顶比较，若不匹配或者栈为空则返回 false，全部比较完都没问题且栈为空了则返回 true。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stack = [];
  for (let i = 0; i < s.length; ++i) {
    if (s[i] == '{' || s[i] == '(' || s[i] == '[') {
      stack.push(s[i]);
    } else {
      if (stack.length == 0) return false;
      let top = stack.length - 1;
      if (s[i] == '}' && stack[top] == '{') stack.pop();
      else if (s[i] == ')' && stack[top] == '(') stack.pop();
      else if (s[i] == ']' && stack[top] == '[') stack.pop();
      else return false;
    }
  }
  return stack.length == 0;
};

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1： 输入：

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

输出：1

示例 2： 输入：

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

思路

一眼题，一眼就用 dfs 就行了，标记数组 vis 表示是否访问过，对每个没访问过的 1 进行 dfs 并++ans。也可以用并查集做。

代码

class Solution {
public:
    vector<vector<bool> > vis;
    vector<vector<char> > g;
    int n, m;
    int dx[4] = {-1, 1, 0, 0};// 上下左右
    int dy[4] = {0, 0, -1, 1};// 上下左右
    Solution():vis(305, vector<bool>(305, false)) {}
    void dfs(int i, int j) {
        if(vis[i][j]) return;
        vis[i][j] = true;
        for(int k = 0; k < 4; ++k) {
            int nowx = i+dx[k];
            int nowy = j+dy[k];
            if(nowx >= 0 && nowx < m && nowy >= 0 && nowy < n && g[nowx][nowy] == '1')
                dfs(nowx, nowy);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        m = grid.size();
        n = grid[0].size();
        int ans = 0;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(vis[i][j] || grid[i][j] == '0') continue;
                dfs(i, j);
                ++ans;
            }
        }
        return ans;
    }
};

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1： 输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”

示例 2： 输入：s = “a”, t = “a” 输出：“a”

示例 3: 输入: s = “a”, t = “aa” 输出: "" 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示： 1 <= s.length, t.length <= 105 s 和 t 由英文字母组成

思路

滑动窗口，首先遍历一遍 t（t[i]为该字符的 ASCII 码），将所有出现过的 m[t[i]]—，这样遍历完后，m 中小于 0 的就是需要满足的字符数，然后双指针开始滑动窗口，使用 cnt 作为判断，若 cnt 为 t 中字符数则满足条件，将左指针尽可能往右移动。

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  if (s.length < t.length) return '';
  let m = new Array(130);
  m.fill(0);
  for (let i = 0; i < t.length; ++i) --m[t.charCodeAt(i)];
  let ans = '';
  let cnt = 0; // 满足字符个数
  for (let l = 0, r = 0; r < s.length; ++r) {
    let k = s.charCodeAt(r);
    if (m[k] < 0) ++cnt;
    ++m[k];
    while (cnt == t.length && m[s.charCodeAt(l)] > 0) m[s.charCodeAt(l++)]--;
    if (cnt == t.length && (ans == '' || r - l + 1 <= ans.length)) {
      ans = s.substring(l, r + 1);
    }
  }
  return ans;
};

冲刺春招-精选笔面试66题大通关day8

20. 有效的括号

思路

代码

200. 岛屿数量

思路

代码

76. 最小覆盖子串

思路

代码