有效的括号&&Pow(x, n)&&合并两个有序链表

有效的括号

这是力扣 20 题

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。

解题思路

这是一道关于字符串的简单题，题目不难，容易理解。题目意思是找出正确的括号形式，换个理解方式就是就单个括号而言他它们是对称的。这样一来，就非常清楚了。关于字符串题目，有专门的解题方法，比如哈希表、栈、队列等。接下来就来介绍几种关于这道题的解题思路。

栈

第一种思路就是以栈的方式将括号入栈，这种思路是最容易想到的。将三种括号形式通过 for 循环传入栈中保存，然后通过比较左右括号来判断是否是有效括号。比如如果遇到左括号就入栈，遇到右括号就出栈，如果不匹配就返回 false。另外，如果是有效括号，长度一定是偶数，不可能为奇数。 整理一下解题思路如下：

• 新建一个栈
• 遇到左括号进入栈，遇到右括号就出栈，类型不匹配直接判断 false

相关代码如下：

let isValid = function(s) {
    let stack = [], length = s.length;
    if(length % 2) return false;
    for(let item of s){
        switch(item){
            case "{":
            case "[":
            case "(":
                stack.push(item);
                break;
            case "}":
                if(stack.pop() !== "{") return false;
                break;
            case "]":
                if(stack.pop() !== "[") return false;
                break;
            case ")":
                if(stack.pop() !== "(") return false;
                break;
        }
    }
    return !stack.length;
};

数组

用数组代替栈也是可以的，我这里通过数组 + 索引来模拟栈，算是一种对代码的优化了。

相关代码如下：

var isValid = function(s) {
    var lib = ['(',')','[',']','{','}'], stack = [], tail = -1;
    for(var c of s){
        if(lib.indexOf(c)%2==0)
            stack[++tail] = c;
        else{
            if(tail<0)
                return false;
            if(c!=lib[lib.indexOf(stack[tail--])+1])
                return false;
        }
    }
    return tail<0;
};

这是一道关于栈的经典题目，大家可以多研究一下，有助于理解栈的知识点。对于判断括号的题目，用栈来解决是最合适的了。

Pow(x, n)

这是力扣第 50 题

实现 Pow(x, n)，即计算  x  的整数  n  次幂函数（即，xn ）。

解题思路

这是一道中等难度的题目，大致题意就是实现一个幂函数。对于 Pow（） 函数，我们平时也会用到，只不过用的是现成的。调用库函数固然很方便，但是我们也需要对它的实现要有一些理解。因此如果我们要去实现一个 Pow（） 函数，首先得明白它的作用以及它是如何实现功能的。对于这题，简单的思路会特别简单，难的思路也会特别难。因此，我分享一种我认为比较简单且容易理解的解题思路。

无名法

之所以称为无名法，是因为它确实没有一个明确的名称。对于库函数 Pow（），它实现的功能是 —— 返回  x  的  y  次幂，即 x^y。这里 x 代表基数的值，y 代表指数的值。通过这个库函数我们能很方便地返回所需要的幂值。

首先分为两种情况，n<0 和 n>=0。当 n 小于 0 时，基数的值需要变为倒数，n 值变为 -n 成为正数，这样才能开始进行下一步。然后如果当 n 为奇数时，用上一开始定义好的 res 值开始累乘，同时 x 值也要累乘以及 n 值要除以 2 对半求值，来不断更新当前 x 和 n 的值，最后返回 res 的最终值即可。这种解题思路就是抓住了 Pow（） 函数运行的本质从而找到了实现它的方法。

相关代码如下：

var myPow = function(x, n) {
  let res = 1;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    while (n) {
        if (n % 2 === 1) res *= x;
        x *= x;
        n = Math.floor(n / 2);
    }
    return res;
};

除了这种方法，其实它还有更难的解法思路，但是会更有技巧，大家感兴趣的话可以去看看并研究研究其中的精髓。

合并两个有序链表

这是力扣 21 题

将两个升序链表合并为一个新的  升序  链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路

这题虽然是道简单题，但是我觉得它更像是道难题。这题一眼看过去确实很简单，两个链表，合并，好像看起来没啥难度。但是只有当你去做了之后才会发现里面的一些细节以及解题的难点。这题最重要的一点就是，虽然两个链表是升序的，但是它要求返回的链表也是升序的，这里应该怎么去处理呢？我当时想了很久毫无思路，最终不得以看了看题解才明白了其中的奥妙。

新建链表法

我们需要考虑的是如何将它合并，然后再考虑如何使最终结果升序。首先我们先新建一个链表 p，并将原有的链表指向 p1 和 p2，然后开始最关键的几步了，如果 p1 的值大于 p2，就将 p2 赋给新建链表 p，并且 p2 当前指针移动到下一步指针。若反之，p1 同样操作即可。这一步可以理解为不断移动指针来完成链表的初步遍历，并将结果赋给链表 p。最后，分别将 p1 和 p2 赋给 p，这样就返回最终结果即可。

可能这样一时不太好理解思路，我再简单地说一下吧，其实我们不用考虑最终结果是否升序还是降序，因为我们可以在合并的过程的完成这一步。我当初就是陷入这个思路，一直在想最终的结果，没考虑在中途的完成过程，才导致了我当时对这题毫无头绪，看了题解后才豁然开朗。通过这题也让我明白了不用一开始就在意最终的结果，我们走好到达结果的路就行。

相关代码如下：

var mergeTwoLists = function(list1, list2) {
    const dummy =new ListNode();
    let p = dummy;
    let p1=list1;
    let p2=list2;
    while(p1&&p2){
        if(p1.val>p2.val){
            p.next=p2;
            p2=p2.next;
        }else{
            p.next=p1;
            p1=p1.next;
        }
        p=p.next;
    }
    if(p1) p.next=p1;
    if(p2) p.next=p2;
    return dummy.next;
};