LeetCode(力扣)答案解析（二）

[Checkson]

20. 有效的括号

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

解法一 （栈 + 手动匹配）

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    var len = s.length;
    var st = [], top = -1;
    for (var i = 0; i < len; i++) {
        switch (s[i]) {
            case '(':
            case '[':
            case '{':
                st[++top] = s[i];
                break;
            case ')':
                if (st[top] === '(') {
                    top--;
                } else {
                    st[++top] = s[i];
                }
                break;
            case ']':
                if (st[top] === '[') {
                    top--;
                } else {
                    st[++top] = s[i];
                }
                break;
            case '}':
                if (st[top] === '{') {
                    top--;
                } else {
                    st[++top] = s[i];
                }
                break;
        }
    }
    return top === -1;    
};

这个方法利用栈的特性，如果我们遇到右括号: ),], }，我们都可以去匹配栈顶是否存在相应的:(,[, {与之匹配，若不存在，则匹配失败，若存在，则弹出栈顶元素，继续下轮的匹配，直到最后栈中无元素存在，就视为"有效括号"。当然，上述代码中，判断到括号不匹配的时候，可以直接返回false，我这里继续入栈，是因为想保持程序统一入口和出口的原则。

解法二 （栈 + 优化）

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    // 记录匹配关系
    var pattern = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
    // 栈
    var st = [], top = -1;
    // 遍历字符串
    for (var i = 0, len = s.length; i < len; i++) {
        // 若是右括号 && 栈中有元素
        if (pattern[s[i]] && top !== -1) {
            // 若栈顶元素与之匹配
            if (st[top] === pattern[s[i]]) {
                // 出栈
                top--;
            } else {
                break;
            }
        } else {
            // 入栈
            st[++top] = s[i];
        }
    }
    return top === -1;
};

这个方法将匹配规则存入对象中，扩展性比第一种要好。

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解法一 (迭代法)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head) return head;
    var p = head, q = p.next;
    p.next = null;
    while (q) {
       var t = q.next;
        q.next = p;
        p = q;
        q = t;
    }
    return p;
};

图解

我们可以看到，p是指向链表中第一个元素，q是指向链表中第二个元素，那么，我们要反转链表，原来第一个链表节点就应该变成链表最后一个节点，所以第一步我就将p.next指向null。第二步，我用一个临时变量t指向q.next，用意是用来储存还没反转链表的最开始的节点，然后，让q.next指向p，那么第一个节点，和第二个节点就局部反转了。第三步，我们还需要将p指向q，q再指向t，然后重复上述步骤，我们就可以将链表反转过来了。

解法二 （递归）

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 递归终止条件
    if (!head || !head.next) {
        return head;
    }
    var q = head.next;
    var p = reverseList(q);
    q.next = head;
    head.next = null;
    return p;
};

在这里，我想强调的是：任何的递归程序都可以改写成迭代形式，反之也成立。

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。

示例:

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

    3
   / \
  9  20
    /  \
   15   7

返回最大深度为3。

解法一 （递归）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root) {
        var leftMax = maxDepth(root.left),
              rightMax = maxDepth(root.right);
        return Math.max(leftMax, rightMax) + 1;
    } else {
        return 0;
    }
};

这里使用的是递归方式。要求这个树最大的层数，那么，我们只需要求出左子树和右子树最大层数的一方 + 1即可，这里的1是指当前层级。

解法二 (迭代 + 栈 + 深度优先搜索)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) return 0;
    var st = [], top = -1;
     // 根节点入栈
     st[++top] = root;
     // 记录最大的层数
     var maxLevel = 1;
     root.level = 1;
     while (top != -1) {
         // 获取栈顶节点 && 出栈 （先根遍历）
         var node = st[top--],
             level = node.level;
         if (node.right) {
             st[++top] = node.right;
             st[top].level = level + 1;
             maxLevel < level + 1  && (maxLevel = level + 1);
         }
         if (node.left) {
             st[++top] = node.left;
             st[top].level = level + 1;
             maxLevel < level + 1 && (maxLevel = level + 1);
         }
     }
     return maxLevel;
};

这里会让每一个节点有一个额外的存储属性：level，来记录每一个节点的所在层数，然后与已知最大的层数对比即可得出结果。