剑指offer —— javaScript解（持续更新）

缺乏、安全感 2023-05-28 14:24 11阅读 0赞

###### 1. 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 ######

> 思路：从最后一个一维数组的第一个元素开始向上/向右进行遍历，若整数比数组中该位置的元素小，则向上遍历，否则向右遍历该一维数组。

###### 2. 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 ######

> 思想：直接采用replace方法进行替换

function replaceSpace(str)
    { 
        // write code here
        return str.replace(/ /g,"%20")
    }

###### 3. 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。 ######

> 思想：对链表进行正向遍历，并将每一个结点的值`push`进数组中，最终返回翻转后的该数组。

function printListFromTailToHead(head)
        { 
            // write code here
            let now = head;
            let arr=[];
            while(now){ 
                arr.push(now.val);
                now = now.next;
            }
            return arr.reverse();
        }

###### 4. 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。 ######

> 思想：取出前序遍历序列中的第一个元素，该元素为二叉树的根，在中序遍历序列中查找该元素
> 
>  *  对于中序遍历序列而言，该元素左边的所有元素构成的集合是根元素的左子树所有结点构成的集合，该元素右边的所有元素构成的集合是根元素的右子树所有结点构成的集合。
>  *  对于前序遍历序列而言，该元素后的x个元素为根结点对应的左子树所有结点构成的集合（此处的x为中序遍历序列中该元素对应的索引位置）,剩下元素为根结点对应的右子树的所有结点构成的集合。
>  *  对新找出来的左右子树进行以上重复操作，最终可得到二叉树。

###### 5. 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 ######

> 思想：对于两个栈，其中一个（`outArr`）保存一次`pop`之前`push`的所有元素，一个(`inArr`)用来保存一次`pop`之后`push`的所有元素，当调用队列的`push`操作时将其`push`进`inArr`，当调用队列的`pop`操作时将`outArr`的栈顶元素`pop`出来。

###### 6. 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 ######

> 思路：
> 
>  *  由于初始数组是递增排序的旋转后的数组，故最小值的左边和右边一定是递增的。可以设置两个指针，分别指向当前被限定的数组的头和尾。取被限定的数组的中间位置的元素和第一个元素进行对比，如果中间的元素比第一个元素小，则说明最小值在当前中间元素的左边（包含中间元素），若中间的元素比第一个元素大，则说明最小值在当前中间元素的右边，从而得到新的被限定的数组，即中间元素左边的所有元素构成的数组（包含中间元素）/中间元素右边的所有元素构成的数组。如果中间元素和第一个元素一样大，则需要对中间元素左右两边的限定数组都进行上述操作，最终取得最小值。
>  *  在下面求解代码中，如果当前传入的元素的个数为0，则返回0，如果为1，则返回该数组中的唯一一个元素。否则设置`low`和`high`指针（初始`low`为0,`high`为数组的最后一个元素对应的索引），求得当前两个指针之间的中间位置的索引，将该索引对应的元素与`high`指针指向的元素进行对比，如果大于`high`指针指向的元素，则`low = mid`，如果小于`high`指针指向的元素，则`high = mid`，直至`hight-low<=1`，最终求出`high`和`low`两个元素中的最小值并返回。如果中间索引对应的元素和`mid`元素相同，则需要对中间索引的两边元素组成的新的两个数组进行上述操作，最终可求得最小值。

###### 7. 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 ######

> 斐波那契数列：`f(1)=1,f(2)=1,....f(n)=f(n-1)+f(n-2)`

###### 8. 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 ######

> 思想：青蛙跳上1级台阶有1种跳法，跳上2级台阶有2种跳法，跳上n级台阶有f(n) = f(n-1)+f(n-2)种跳法。  
> ![在这里插入图片描述][20200323162326556.png]  
> 理解：当跳上`n`级台阶时，青蛙第一次可以选择跳`1`个台阶，则还剩下`n-1`个台阶，故问题变成青蛙跳`n-1`级台阶有多少种跳法，而青蛙跳`n-1`级台阶有`f(n-1)`种跳法，故当青蛙第一次跳`1`个台阶时，一共有`f(n-1)`种跳法。当青蛙选择第一次跳`2`个台阶时，此时剩下`n-2`个台阶，故问题变为青蛙跳`n-2`级台阶有多少种跳法，而青蛙跳`n-2`级台阶有`f(n-2)`种跳法，故当青蛙第二次跳`2`个台阶时，一共有`f(n-2)`种跳法。故青蛙跳上一个n级台阶时共有`f(n) = f(n-1)+f(n-2)`种跳法。

###### 9. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 ######

> 思想：青蛙跳上1级台阶有1种跳法，跳上2级台阶有2种跳法，跳上n级台阶有`f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(0)`种跳法。而跳上`n-1`级台阶有`f(n-1) = f(n-2)+...f(0)`，故`f(n)=f(n-1)+f(n-1)=2*f(n-1)`  
> 理解：青蛙跳上n级台阶可以选择第一次跳1级、2级、3级…n级，而第一次跳1级剩下`n-1`级台阶，故问题变为青蛙跳`n-1`级台阶有多少种跳法，而青蛙跳`n-1`级台阶有`f(n-1)`种跳法。故当青蛙第一次跳`1`级台阶时，一共有`f(n-1)`种跳法。以该思想去推理其余的情况，最终可得出`f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(0)`

###### 10. 我们可以用`2*1`的小矩形横着或者竖着去覆盖更大的矩形。请问用n个`2*1`的小矩形无重叠地覆盖一个`2*n`的大矩形，总共有多少种方法？ ######

> 思想：该题与第8题思想类似，实际上可以转换为第一个小矩形横着摆放还是竖着摆放的问题，如果第一个小矩形横着摆放，则横轴会被占据2个单位长度的位置。如果纵轴摆放，则横轴会被占据1个单位长度的位置。类似于第8题，即就是第一次选择1还是2的问题。  
> 如下图所示，当横轴摆放时，实际上可供我们摆放矩形的是橙色区域，而剩余区域必须横轴摆放，这是固定的。当纵轴摆放时，实际上可供我们摆放矩形的是橙色区域，无剩余区域受影响。故就转换成了`f(4)=f(2)+f(3)`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 1]

###### 11. 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 ######

> 思想：在该题中，若传入的参数为正数，则计算其二进制中1的个数，如果是负数，则计算其补码中1的个数（包含符号位）。我们可以采用`&`运算的方式，对负数做与运算实际上是对其补码做与运算。而在计算负数的补码的1的个数时，由于也将负数的符号位包含其中，故可以将负数的补码当做正常的正数的二进制来进行计算，故计算正数和负数的补码中的1的个数实际上是相同的。  
> 实现：将当前数`a`和比当前数小一位的数`a-1`做`&`运算，当`a`的末尾为1时，`a-1`特点为：除了末位，其他位和`a`的对应位取值相同，`a-1`的末位为`0`。当`a`的末尾为`0`时，`a-1`的特点为：在进行减运算时会去前面位进行借位，直到遇到`1`，故`a-1`和`a`除了末位不同，还有从后往前遇到的第一个`1`的位置的取值也不同。上诉两种情况，当`(a-1)&a`后，得到的数都会比`a`少一个`1`。故当当前数字为`0`时说明其中已经没有`1`了，这也是循环终止的条件。

function NumberOf1(n)
    { 
        // write code here
        let count=0;
        while(n){ 
            count++;
            n = n&(n-1);
        }
        return count;
    }

###### 12. 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0 ######

> 思想：采用快速幂算法。快速幂算法的主要思想为(快速幂算法的时间复杂度为`O(logn)`)：
> 
>  *  当指数为正数时：(以下假设底数为x，指数值为n。求指数的方法为pow(x,n))  
>     ① 当指数为奇数时，结果为：`x*pow(x,n-1)`  
>     ② 当指数为偶数时，结果为：`pow(x,n/2)*pow(x,n/2)`
>  *  当指数为负数时  
>     ① 当指数为奇数时，结果为：`1/(x*pow(x,-n-1))`  
>     ② 当指数为偶数时，结果为：`1/(pow(x,-n/2)*pow(x,-n/2))`

###### 13. 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 ######

> 思想：采用插入排序算法的思想（插入排序算法是稳定的）

###### 14. 输入一个链表，输出该链表中倒数第k个结点。 ######

> 思想：设置一个快指针和一个慢指针。当快指针已经走了`k`步后慢指针再从头出发。当快指针指向最后一个结点时，此时慢指针指向倒数第`k`个结点。

###### 15. 输入一个链表，反转链表后，输出新链表的表头。 ######

> 思想：对链表进行一次扫描，设置三个指针：`preNode、nowNode、nextNode`，在扫描到某一节点时，`preNode`指向该节点的前一个结点，`nowNode`指向当前结点，`nextNode`指向当前结点的下一个结点。让该结点的`next`指向`preNode`指针指向的结点。操作完后所有指针集体向后移动，直到对所有结点完成以上操作。

[20200323162326556.png]: /images/20230528/0c8de40cc10b423e9b60ace9657c603e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70]: /images/20230528/131d7b862be84cc6a3a231796e976c90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 1]: /images/20230528/2b3572de41604e678a9cab8e224bfc00.png