chocolate1999 / leetcode-javascript Goto Github PK

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

var solveSudoku = function (board) {
  let check = (x, y, val) => {
    // 一行或者一列有重复元素，剪掉
    for (let i = 0; i < 9; i++) {
      if (board[x][i] == val || board[i][y] == val) return true;
    }
    let xx = Math.floor(x / 3) * 3;
    let yy = Math.floor(y / 3) * 3;
    // 3x3宫格内重复的情况，剪掉
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[xx + i][yy + j] == val) return true;
      }
    }
    return false; // 没有冲突情况
  }
  let dfs = (x, y) => {
    if (y == 9) {
      x++;
      y = 0;
      if (x == 9) return true; // 都填完了，直接返回 true
    }
    if (board[x][y] != '.') return dfs(x, y + 1);
    for (let i = 1; i < 10; i++) {
      if (check(x, y, String(i))) continue;
      board[x][y] = String(i);
      if (dfs(x, y + 1)) return true; // 如果往下走，能够解出数独，直接返回 true
      board[x][y] = '.'; // 回溯，因为往下走得不到一个解
    }
    return false;
  }
  dfs(0, 0);
  return board;
};

学如逆水行舟，不进则退

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

var exist = function(grid, word) {
  let dfs = (x,y,t) => {
    // 最后一次还会 +1 因此，条件是大于
    if(t > word.length-1){
      return true
    }
    // 剪枝条件
    if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y]!= word[t] || grid[x][y] == '#') return false
    let tmp = grid[x][y]
    // 开始走
    grid[x][y] = '#'
    // 从四个方向搜索，只要一个方向搜索有结果，那么直接返回 true即可
    let res = dfs(x+1,y,t+1) || dfs(x,y+1,t+1) || dfs(x-1,y,t+1) || dfs(x,y-1,t+1)
    if(res) return true
    // 回溯（重置）
    grid[x][y] = tmp
    return false
  }
  for(let i=0;i<grid.length;i++){
    for(let j=0;j<grid[0].length;j++){
      if(grid[i][j] == word[0]){
        let res = dfs(i,j,0)
        if(res) return true
      }
    }
  }
  return false
};

学如逆水行舟，不进则退

输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

输入：S = "3z4"
输出：["3z4", "3Z4"]

输入：S = "12345"
输出：["12345"]
 

S 的长度不超过12。
S 仅由数字和字母组成。

/**
 * @param {string} S
 * @return {string[]}
 */
var letterCasePermutation = function(S) {
    let res = []
    let dfs = (t,str) => {
        if(t.length === S.length)
            return res.push(t)
        let ch = str[0]
        let nextStr = str.substr(1)
        // 当前位置为数字，只有一个分支
        if(!isNaN(Number(ch))){
            dfs(t+ch,nextStr)
        }else{
            //当前位置为字母，会产生两个分支
            let tmp = ch.toUpperCase()
            if(tmp === ch) tmp = ch.toLowerCase()
            dfs(t+ch,nextStr)
            dfs(t+tmp,nextStr)
        }
    }
    dfs('',S)
    return res
};

学如逆水行舟，不进则退

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

var combine = function (n, k) {
  let res = [];
  let dfs = (t, start) => {
    if (t.length === k) {
      res.push(t);
      return;
    }
    for (let i = start; i <= n; i++) {
      t.push(i);
      dfs(t.slice(), i + 1);
      t.pop();
    }
  }
  dfs([], 1);
  return res;
};

学如逆水行舟，不进则退

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if(!matrix.length) return []
    let n = matrix.length
    let m = matrix[0].length
    let total = n*m
    let top = 0,bottom = n-1
    let left = 0,right = m-1
    let res = []
    while(res.length < total){
        for(let i=left;i<=right;i++) res.push(matrix[top][i]) // 从左到右
        top++
        for(let i=top;i<=bottom;i++) res.push(matrix[i][right]) // 从上到下
        right--
        /* 因为n 和 m 不相同的时候，最后可能会留一列或一行，避免重复计算，总数够了直接跳出去 */
        if(res.length === total) break
        for(let i=right;i>=left;i--) res.push(matrix[bottom][i]) // 从右到左
        bottom--
        for(let i=bottom;i>=top;i--) res.push(matrix[i][left]) // 从下到上
        left++
    }
    return res
};

学如逆水行舟，不进则退

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
    if (!root) return null;
    // 判断值是否小于root，小于走左子树，大于走右子树
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // 1.如果删除节点没有左右子树，直接删除即可
        if (!root.left && !root.right) {
            root = null;
        // 2.如果删除节点仅有左孩子，直接指向左孩子
        } else if (root.left && !root.right) {
            root = root.left;
        // 3.如果删除节点仅有右孩子，直接指向右孩子
        } else if (!root.left && root.right) {
            root = root.right;
        } else {
            // 4.如果左右孩子都有，本代码采用方式是将前驱的最大值替换root的值
            let last = root.left;
            while (last.right) {
                last = last.right;
            }
            root.val = last.val;
            // 然后删除这个前驱最大值节点即可
            root.left = deleteNode(root.left, last.val);
        }
    }
    return root;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
    if (!root) return null;
    // 判断值是否小于root，小于走左子树，大于走右子树
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // 1.如果删除节点没有左右子树，直接删除即可
        if (!root.left && !root.right) {
            root = null;
        // 2.如果删除节点仅有左孩子，直接指向左孩子
        } else if (root.left && !root.right) {
            root = root.left;
        // 3.如果删除节点仅有右孩子，直接指向右孩子
        } else if (!root.left && root.right) {
            root = root.right;
        } else {
            // 4.如果左右孩子都有，本代码采用方式是将后继的最小值替换root的值
            let last = root.right;
            while (last.left) {
                last = last.left;
            }
            root.val = last.val;
            // 然后删除这个后继最小值节点即可
            root.right = deleteNode(root.right, last.val);
        }
    }
    return root;
};

学如逆水行舟，不进则退

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用  10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。

var StockSpanner = function() {
    // 存储股票跨度
    this.spanner = []
    // 存储股票价格
    this.stockPrice = []
};

/** 
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function(price) {
    // 对于第一天进行特殊判断
    if(!this.spanner.length){
        this.spanner.push(1)
        this.stockPrice.push(price)
        // 直接返回1
        return 1
    }
    let cnt = 0
    let idx = this.stockPrice.length-1
    while(price >= this.stockPrice[idx] && idx>=0){
        cnt += this.spanner[idx]
        idx -= this.spanner[idx]
    }
    // 加上本身
    cnt++
    // 进行更新操作，将当前股票价格和跨度入栈
    this.spanner.push(cnt)
    this.stockPrice.push(price)
    return cnt
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * var obj = new StockSpanner()
 * var param_1 = obj.next(price)
 */

学如逆水行舟，不进则退

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

var permuteUnique = function(nums) {
    let res = [];
    nums.sort((a,b) => a-b);
    let vis = {};
    let dfs = (t) => {
      if(t.length === nums.length){
        res.push(t);
      }
      for(let i=0;i<nums.length;i++){
        if(i-1>=0 && nums[i] == nums[i-1] && !vis[i-1]) continue;
        if(vis[i]) continue;
        vis[i] = true;
        t.push(nums[i]);
        dfs(t.slice(),i+1);
        t.pop();
        vis[i] = false;
      }
    }
    dfs([],0);
    return res;
};

学如逆水行舟，不进则退

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
    if (root == null) return [];
    let res = [];
    let dfs = (cur, root) => {
        // 叶子节点，存起来
        if (root.left == null && root.right == null) {
            cur += root.val;
            res.push(cur);
            return;
        }
        cur += root.val + '->'; // 处理非叶子节点
        // 先遍历左子树，再遍历右子树
        root.left && dfs(cur, root.left);
        root.right && dfs(cur, root.right);
    }
    dfs('', root);
    return res;
};

学如逆水行舟，不进则退

输入: k = 3, n = 7
输出: [[1,2,4]]

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

var combinationSum3 = function (k, n) {
  let res = [];
  let dfs = (t, start, sum) => {
    if (t.length === k && sum === n) {
      res.push(t);
    }
    for (let i = start; i < 10; i++) {
      t.push(i);
      dfs(t.slice(), i + 1, sum + i);
      t.pop();
    }
  }
  dfs([], 1, 0);
  return res;
};

学如逆水行舟，不进则退

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

// 判断是否是回文
function isPal(str) {
  let len = Math.floor(str.length / 2);
  if (len === 0) {
    return true;
  }
  let add = str.length % 2 === 0 ? 0 : 1;
  let subStr = str.slice(0, len);
  for (let i = 0; i < len; i++) {
    if (subStr[len - i - 1] !== str[len + add + i]) {
      return false;
    }
  }
  return true;
}
var partition = function (s) {
  let res = [];
  let dfs = (cur, start) => {
    // 当前已经到达了最后一个元素
    if (start >= s.length) {
      res.push(cur.slice());
      return;
    }
    for (let i = start; i < s.length; i++) {
      // 字符串切割
      let str = s.slice(start, i + 1);
      if (str && isPal(str) ) {
        cur.push(str);
        dfs(cur, i + 1);
        // 回溯
        cur.pop();
      }
    }
  }
  dfs([], 0);
  return res;
};

学如逆水行舟，不进则退

输入：s = "(abcd)"
输出："dcba"

输入：s = "(u(love)i)"
输出："iloveu"

输入：s = "(ed(et(oc))el)"
输出："leetcode"

输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"

0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的

样例：a(bcdefghijkl(mno)p)q

a ['a']
( ['a', '']
b ['a', 'b']
c ['a', 'bc']
d ['a', 'bcd']
e ['a', 'bcde']
f ['a', 'bcdef']
g ['a', 'bcdefg']
h ['a', 'bcdefgh']
i ['a', 'bcdefghi']
j ['a', 'bcdefghij']
k ['a', 'bcdefghijk']
l ['a', 'bcdefghijkl']
( ['a', 'bcdefghijkl', '']
m ['a', 'bcdefghijkl', 'm']
n ['a', 'bcdefghijkl', 'mn']
o ['a', 'bcdefghijkl', 'mno']
) ['a', 'bcdefghijklonm']
p ['a', 'bcdefghijklonmp']
) ['apmnolkjihgfedcb']
q ['apmnolkjihgfedcbq']

/**
 * @param {string} s
 * @return {string}
 */
var reverseParentheses = function(s) {
  let stack = ['']
  for(let i=0;i<s.length;i++){
    let ch = s[i]
    if(ch === '('){
      stack.push('')
    }else if(ch === ')'){
      let str = stack.pop()
      let tmp = str.split('').reverse().join('')
      stack[stack.length-1] += tmp
    }else{
      stack[stack.length-1] += ch
    }
  }
  return stack.pop()
};

学如逆水行舟，不进则退

输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

var findWords = function(grid, words) {
  // 存放最终结果集
  let res = []
  // 字典树节点
  class TrieNode {
    constructor(){
      this.end = false
      this.child = {}
    }
  }
  // 最终形成的字典树根节点
  let root = null
  let Trie = function(){
    root = new TrieNode()
  }
  // 建立字典树
  Trie.prototype.insert = (word) => {
    let cur = root
    for(let i=0;i<word.length;i++){
      if(!cur.child[word[i]]){
        cur.child[word[i]] = new TrieNode()
      }
      cur = cur.child[word[i]]
    }
    cur.end = true
  }
  // 创建根节点
  let trie = new Trie()
  // 进行建树操作
  for(let i=0;i<words.length;i++){
    trie.insert(words[i])
  }
  let dfs = (x,y,t,cur) => {
    if(cur.end){
      res.push(t)
      cur.end = false // 避免重复计算
    }
    // 剪枝条件：1.边界处理 2.下一步是否可走 3.下一步字典树是否可走
    if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == '#' || !cur.child[grid[x][y]]) return
    let tmp = grid[x][y]
    grid[x][y] = '#'  // 走
    cur = cur.child[tmp]
    dfs(x+1,y,t+tmp,cur)  // 上下左右四个方向遍历
    dfs(x,y+1,t+tmp,cur)
    dfs(x-1,y,t+tmp,cur)
    dfs(x,y-1,t+tmp,cur)
    grid[x][y] = tmp // 回溯（还原）
  }
  // 对单词表进行全局搜索
  for(let i=0;i<grid.length;i++){
    for(let j=0;j<grid[0].length;j++){
      dfs(i,j,'',root)
    }
  }
  return res
};

var findWords = function(grid, words) {
  // 存放最终结果集
  let res = []
  // 字典树节点
  class TrieNode {
    constructor(){
      this.end = false
      this.child = {}
    }
  }
  // 最终形成的字典树根节点
  let root = null
  let Trie = function(){
    root = new TrieNode()
  }
  // 建立字典树
  Trie.prototype.insert = (word) => {
    let cur = root
    for(let i=0;i<word.length;i++){
      if(!cur.child[word[i]]){
        cur.child[word[i]] = new TrieNode()
      }
      cur = cur.child[word[i]]
    }
    cur.end = true
  }
  // 在 Trie 树中查找键
  let searchPrefix = (word) => {
    let cur = root
    for(let i=0;i<word.length;i++){
      if(cur.child[word[i]]){
        cur = cur.child[word[i]]
      }else{
        return null
      }
    }
    return cur
  }
  Trie.prototype.search = (word) => {
    let cur = searchPrefix(word)
    return cur !== null && cur.end
  }
  // 查找 Trie 树中的键前缀
  Trie.prototype.startsWith = (pre) => {
    return searchPrefix(pre) != null
  }
  // 创建根节点
  let trie = new Trie()
  // 进行建树操作
  for(let i=0;i<words.length;i++){
    trie.insert(words[i])
  }
  let dfs = (x,y,t,cur) => {
    if(cur.end){
      res.push(t)
      cur.end = false // 避免重复计算
    }
    // 剪枝条件：1.边界处理 2.下一步是否可走 3.下一步字典树是否可走
    if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == '#' || !cur.child[grid[x][y]]) return
    let tmp = grid[x][y]
    grid[x][y] = '#'  // 走
    cur = cur.child[tmp]
    dfs(x+1,y,t+tmp,cur)  // 上下左右四个方向遍历
    dfs(x,y+1,t+tmp,cur)
    dfs(x-1,y,t+tmp,cur)
    dfs(x,y-1,t+tmp,cur)
    grid[x][y] = tmp // 回溯（还原）
  }
  // 对单词表进行全局搜索
  for(let i=0;i<grid.length;i++){
    for(let j=0;j<grid[0].length;j++){
      dfs(i,j,'',root)
    }
  }
  return res
};

学如逆水行舟，不进则退

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

var letterCombinations = function (digits) {
  if(!digits.length) return [];
  // 直接映射
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  let res = [];
  let dfs = (cur, start) => {
    if (start >= digits.length) {
      res.push(cur);
      return;
    }
    // 取当前可选的字母组合
    let str = map[digits[start]];
    for (let i = 0; i < str.length; i++) {
      dfs(cur + str[i], start + 1);
    }
  }
  dfs('', 0);
  return res;
};

var letterCombinations = function(digits) {
  if(!digits.length) return []
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  let queue = []
  queue.push('')
  for(let i=0;i<digits.length;i++){
      let size = queue.length
      while(size--){
          let cur = queue.shift()
          let str = map[digits[i]]
          for(let j=0;j<str.length;j++){
              queue.push(cur+str[j])
          }
      }
  }
  return queue
};

学如逆水行舟，不进则退

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    // 借助一个新的栈
    let stack = []
    for(let cur of pushed){
        // 存放入栈的元素
        stack.push(cur)
        // 和出栈元素进行比对，如果匹配都弹出栈
        while(stack[stack.length-1] === popped[0] && stack.length){
            stack.pop()
            popped.shift()
        }
    }
    return !stack.length
};

学如逆水行舟，不进则退

var subsets = function(nums) {
  let res = [];
  let dfs = (t,start) => {
    res.push(t);
    for(let i=start;i<nums.length;i++){
      t.push(nums[i]);
      dfs(t.slice(),i+1);
      t.pop();
    }
  }
  dfs([],0);
  return res;
};

学如逆水行舟，不进则退

输入：inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3,3]

var RecentCounter = function() {
    this.queue = []
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
  // 将新请求加入队列
  this.queue.push(t)
  // 3000ms 前发出的请求就出队列
  while(this.queue[0] < t-3000){
    this.queue.shift()
  }
  return this.queue.length
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

学如逆水行舟，不进则退

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
    if(!root) return true;
    let res = true;
    let dfs = (root) => {
        // 先遍历左子树，在遍历右子树
        let left = root.left && dfs(root.left) + 1;
        let right = root.right && dfs(root.right) + 1;
        // 判断是否是平衡二叉树，就看高度差是否大于1
        if (Math.abs(left - right) > 1) res = false;
        // 返回左右子树深度的最大值
        return Math.max(left, right);
    }
    dfs(root);
    return res;
};

学如逆水行舟，不进则退

    1
   / \
  2   2
 / \ / \
3  4 4  3

    1
   / \
  2   2
   \   \
   3    3
 

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    if (!root) return true;
    let dfs = (left, right) => {
        // 如果左右节点都为空，可以
        if (left == null && right == null) return true;
        // 如果左右节点一个为空，不可以
        if(left == null || right == null) return false;
        // 如果左右节点值不相等，不可以
        if (left.val !== right.val) return false;
        // 递归左右子树镜像
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }
    return dfs(root.left, root.right);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    if (!root) return true
    let queue = [root.left, root.right]
    while (queue.length) {
        let node1 = queue.shift()
        let node2 = queue.shift()
        if (!node1 && !node2) continue
        if (!node1 || !node2 || node1.val !== node2.val) return false
        queue.push(node1.left)
        queue.push(node2.right)
        queue.push(node1.right)
        queue.push(node2.left)
    }
    return true
};

学如逆水行舟，不进则退

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径： 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

输入：[[0,1],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。

1 <= grid.length * grid[0].length <= 20

/**
 * @param {number[][]} grid
 * @return {number}
 */
var uniquePathsIII = function(grid) {
    let cnt = 1 // 统计地图中可走的方格个数，包括终点，故初始值为1
    let sx,sy // 记录起点坐标
    for(let i=0;i<grid.length;i++){
        for(let j=0;j<grid[0].length;j++){
            if(grid[i][j] === 1){
                sx = i
                sy = j
            }
            else if(grid[i][j] === 0){
                cnt++
            }
        }
    }
    return dfs(sx,sy,cnt,grid)
};
// 剪枝条件
let check = (sx,sy,grid) => {
    if(sx<0 || sx>=grid.length || sy<0 || sy>=grid[0].length || grid[sx][sy] == -1) return false
    return true
}

let dfs = (sx,sy,cnt,grid) => {
    if(!check(sx,sy,grid)) return 0
    if(grid[sx][sy] === 2){ // 走到终点时，也要判断一下当前所有空格是否走完
        return cnt === 0 ? 1:0
    }
    let res = 0
    grid[sx][sy] = -1  //走过的空格进行标记，设置为障碍即可
    res += dfs(sx+1,sy,cnt-1,grid)  // 四个方向进行搜索
    res += dfs(sx,sy+1,cnt-1,grid)
    res += dfs(sx-1,sy,cnt-1,grid)
    res += dfs(sx,sy-1,cnt-1,grid)
    grid[sx][sy] = 0  // 回溯过程，不影响后续dfs
    return res
}

学如逆水行舟，不进则退

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  // 如果是奇数，不可能匹配成功，直接返回false
  if(s.length & 1) return false
  let stack = []
  for(let i=0;i<s.length;i++){
    if(s[i] === '(' || s[i] === '{' || s[i] === '[') stack.push(s[i])
    else if(s[i] === ')' && stack[stack.length-1] === '(') stack.pop()
    else if(s[i] === '}' && stack[stack.length-1] === '{') stack.pop()
    else if(s[i] === ']' && stack[stack.length-1] === '[') stack.pop()
    else return false
  }
  return !stack.length
};

学如逆水行舟，不进则退

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

var generateParenthesis = function (n) {
  let res = [];
  let dfs = (cur, left, right) => {
    if (cur.length === 2 * n) {
      res.push(cur);
      return;
    }
    // 左括号还存在，就可以选左括号
    if (left > 0) dfs(cur + '(', left - 1, right);
    // 右括号数量要大于左括号，才可以选右括号
    if (right > left) dfs(cur + ')', left, right - 1);
  }
  dfs('', n, n);
  return res;
};

学如逆水行舟，不进则退

输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。