day8 题目：20. 有效的括号、200. 岛屿数量、76. 最小覆盖子串

学习计划链接：冲刺春招 - 精选笔面试 66 题大通关

今日知识点：栈、深搜 / 广搜、滑动窗口，难度为简单、中等、困难

# 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;

};