📖算法 | 剑指offer

03 数组中重复的数字

解法1

使用数据结构Set，利用其不会储存相同元素的特性来解决，不断往里面添加元素，看看Set大小有没有变，没变说明添加的就是重复的元素

var findRepeatNumber = function(nums) {
    let mySet = new Set();
    let size = mySet.size;
    let result = -1;
    nums.some(e => {
        mySet.add(e);
        if(mySet.size === size) {
            result = e;
            return true;
        }
        size+=1;
    })
    return result;
};

需要注意的是，在遍历数组nums的时候，不能采用forEach里return结果的方式，因为这样并不会跳出循环，break也是一样的；可以使用some和every方法来实现可跳出的循环，前者return true时跳出，后者return false跳出

解法2

可以使用原地交换的方式，因为题目中说长度为n的数组，元素大小在[0,n-1]，有重复元素，那么在建立索引和值的对应关系上，一定会出现某个索引对应了两个值的情况，该值就是重复的元素

var findRepeatNumber = function(nums) {
    let i=0;
    while(true){
        if(nums[i] !== i){
          /*防止出现1，1，1的情况*/
            if(nums[nums[i]] === nums[i]){
                return nums[i];
            }
          /*交换*/
            [nums[nums[i]], nums[i]] =[nums[i], nums[nums[i]]]; 
        }
        else {
            i++;
        }
    }
};

04 二维数组中的查找

因为每行、每列都是递增顺序排列的，所以可以从右上角开始，如果当前数组中的数比target大，那么往左移；小，那么往下移；终止循环的条件是索引越界

var findNumberIn2DArray = function(matrix, target) {
    let i = 0;
    let j = matrix[0].length-1;
    while(true) {
        if(i>matrix.length-1 || j<0) {
            return false;
        }
        if(target === matrix[i][j]) {
            return true;
        }
        if(matrix[i][j] > target) {
            j--;
        }
        else if(matrix[i][j] < target) {
            i++;
        }
    }

};

05 替换空格

使用js的常用API就可以解决

// 法一
var replaceSpace = function(s) {
    return s.split(' ').join('%20');
};

// 法二
var replaceSpace = function(s) {
  // 必须要有g，不然只会替换第一个
    return s.replace(/\s/g, '%20');
};

str.replace(/^\s+|\s+$/g, 'haloha')
\s : 表示 space ，空格
+：一个或多个
^：开始，^\s，以空格开始
$：结束，\s$，以空格结束
|：或者
/g：global，全局

06 从尾到头打印链表

先顺序遍历，把结果放到数组里，再reverse一下；或者使用unshift()

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
// 法一
var reversePrint = function(head) {
    let result = [];
    while(head) {
        result.push(head.val);
        head = head.next;
    }
    result.reverse();
    return result;
};
// 法二
var reversePrint = function(head) {
    let result = [];
    while(head) {
      /*在数组首位置添加元素*/
        result.unshift(head.val);
        head = head.next;
    }
    return result;
};

07 重建二叉树

核心是递归，根据preorder里的第一个元素，可以把inorder划分成左子树和右子树，再根据inoder里子树的大小，将preorder里划分成左子树和右子树，然后对应的进行递归操作即可

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    let result = new TreeNode(preorder[0]);
    // 特殊情况
    // if(preorder.length === 1){
    //     return result;
    // }
    // else if(preorder.length === 0){
    //     return null;
    // }
    let index = inorder.indexOf(preorder[0]);
    result.left = buildTree(preorder.slice(1, 1+index), inorder.slice(0, index));
    result.right = buildTree(preorder.slice(1+index), inorder.slice(index+1));
    return result;
};

10 斐波那契数列

解法1（动态规划）

使用最简单的递归方法，，果然超时了，函数的入栈出栈的时间成本还是太高了，所以用了最简单的迭代，不过空间复杂度是O(N)，比较占用内存

var fib = function(n) {
    if(n === 0 || n === 1) {
        return n;
    }
    let arr = [0, 1];
    for(let i=2; i<=n; i++) {
        arr[i] = (arr[i-1] + arr[i-2])%1000000007;
    }
    return arr[n];
};
// 还可以继续优化，因为n只与n-1，n-2有关，所以可以将空间复杂度降至O（1）

解法2

使用递归的同时，再开辟一个新的数组用来存储已经算过的项，避免重复；例如算n-1和n-2这两项的时候都会用到第n-3项。所以在使用某一项的时候先看看这个数组里面有没有值，没有值再递归计算赋值

不过这样时间复杂度和空间复杂度都好高啊，还是使用动态规划最好

青蛙跳台阶也可以转换成类似的想法，关键是得到f(n)=f(n-1)+f(n-2)这个不变式

11 旋转数组的最小数字

线性遍历数组，发现后一个比前一个小，那么后一个就是答案；如果遍历完都没找到就说明这个数组是升序排列，返回第一个就好；时间复杂度O（N）

var minArray = function(numbers) {
    for(let i=0;i<numbers.length-1;i++){
        if(numbers[i+1] < numbers[i]){
            return numbers[i+1];
        }
    }
    return numbers[0]
};

12 矩阵中的路径🌟

回溯

本题的思路核心是回溯，每次判断完一条路径是否符合条件后，要及时把状态恢复，以便其他条件递归

var exist = function(board, word) {
    for(let i=0;i<board.length;i++){
        for(let j=0;j<board[0].length;j++){
            // 特殊情况，要判断的word只有一个字符
            if(word.length===1 && board[i][j]===word.charAt(0)){
                return true;
            }
            else if(board[i][j]===word.charAt(0)){
                if(help(board,word.substring(1),i,j)){
                    return true;
                }
            }
        }
    }
    return false;
};

// 用来判断某一个字符是否存在符合条件的下一个字符
var help = (board, word, i, j) => {
    // 用来记录i,j位置的元素，用来回溯
    let temp=board[i][j];
    // 确保不会出现重复使用的情况
    board[i][j]='0';
    let target = word.charAt(0);
    let signal1=false;
    let signal2=false;
    let signal3=false;
    let signal4=false;
    let res1=false;
    let res2=false;
    let res3=false;
    let res4=false;

    // 判断四个方向是否可行，并分别进行递归判断
    if(j+1<board[0].length && board[i][j+1]===target){
        signal1=true;
        res1=help(board, word.substring(1),i,j+1);
    }
    if(i+1<board.length && board[i+1][j]===target){
        signal2=true;
        res2=help(board, word.substring(1),i+1,j);
    }
    if(j-1>=0 && board[i][j-1]===target){
        signal3=true;
        res3=help(board, word.substring(1),i,j-1);
    }
    if(i-1>=0 && board[i-1][j]===target){
        signal4=true;
        res4=help(board, word.substring(1),i-1,j);
    }

    // 当前状态的恢复
    board[i][j]=temp;

    // 结果判定
    if(word.length===1 && (signal1||signal2||signal3||signal4)){
        return true;
    }
    else if(signal1||signal2||signal3||signal4){
        return res1||res2||res3||res4;
    }
    else{
        return false;
    }
}

18 有效的回文

解法一

给定的字符串s中会有一些非字母和数字的字符，所以要先做一步过滤

var isPalindrome = function(s) {
    if(!s){
        return true;
    }
    let arr=[];
    let pattern=/[a-z]|[A-Z]|[0-9]/;
    for(let i=0;i<s.length;i++){
        if(pattern.test(s[i])){
            arr.push(s[i]);
        }
    }
    console.log(arr.join(''));
    return arr.join('').toLowerCase()===arr.reverse().join('').toLowerCase();
};

解法二

原地判断，这样空间复杂度就变成了O(1)，时间复杂度还是一遍遍历O(N)

var isPalindrome = function(s) {
    if(!s){
        return true;
    }
    let i=0;
    let j=s.length-1;
    let p=/[a-z]|[A-Z]|[0-9]/;
    while(i<j){
        while(!p.test(s[i])){
            i++;
        }
        while(!p.test(s[j])){
            j--;
        }
        if(!s[i] || !s[j]){
            break;
        }
        if(s[i].toLowerCase()!==s[j].toLowerCase()){
            return false;
        }
        i++;
        j--;
    }
    return true;
};

19 删除链表的倒数第 N 个结点

var removeNthFromEnd = function(head, n) {
    let p=head;
    let target=head;
    for(let i=0;i<n-1;i++){
        p=p.next;
    }
    let pre=head;
    while(p.next){
        pre=target;
        p=p.next;
        target=target.next;
    }
    /** 特殊情况，要删除的节点是头节点
     链表只有一个元素，删除这个元素也可以归为上面👆“要删除的节点是头节点”这一类 **/
    if(head===target){
        return target.next;
    }
    pre.next=target.next;
    return head;
};

29 顺时针打印矩阵

var spiralOrder = function(matrix) {
    let result=[];
    // 判断数组是否为空
    // 不能[]===[] //false
    if(matrix.length===0){
        return result;
    }
    help(matrix,result,0,0,matrix[0].length-1,matrix.length-1);
    return result;
};

let help=(matrix,result,l,t,r,b)=>{
    if(l===r && t===b){
        result.push(matrix[t][l]);
        return;
    }
    if(l>r || t>b){
        return;
    }
    if(l<r && t==b){
        for(let i=l;i<=r;i++){
            result.push(matrix[t][i]);
        }
    }
    else if(t<b && l==r){
        for(let i=t;i<=b;i++){
            result.push(matrix[i][r]);
        }
    }
    else{
        for(let i=l;i<=r;i++){
            result.push(matrix[t][i]);
        }
        for(let i=t+1;i<=b;i++){
            result.push(matrix[i][r]);
        }
        for(let i=r-1;i>=l;i--){
            result.push(matrix[b][i]);
        }
        for(let i=b-1;i>t;i--){
            result.push(matrix[i][l]);
        }
    }
    l++;
    t++;
    r--;
    b--;
    help(matrix,result,l,t,r,b);
}

38 字符串的排列🌟

回溯

考察的是DFS+回溯，回溯体现在数组和字符串上，需要注意的是当字符串只有一个字符时的特殊情况

 // 数组在某个index添加删除元素
var permutation = function(s) {
    if(!s){
        return [];
    }
    let strArr=s.split('');
    let result=new Set();
    let temp='';
    for(let i=0;i<strArr.length;i++){
        temp+=strArr[i];
        let char=strArr[i];
        let charIndex=strArr.indexOf(char);
        strArr.splice(charIndex,1);
        help(strArr,result,temp);
        temp=temp.substring(0,temp.length-1);
        strArr.splice(charIndex,0,char);
    }
    return Array.from(result);
};

let help=(strArr,result,temp)=>{
    // 两种情况
    if(strArr.length===0){
        result.add(temp);
        return ;
    }
    if(strArr.length===1){
        temp+=strArr[0];
        result.add(temp);
        return ;
    }
    else{
        for(let i=0;i<strArr.length;i++){
            temp+=strArr[i];
            let char=strArr[i];
            let charIndex=strArr.indexOf(char);
            strArr.splice(charIndex,1);
            help(strArr,result,temp);
            temp=temp.substring(0,temp.length-1);
            strArr.splice(charIndex,0,char);
        } 
    }
}

44 数字序列中某一位的数字

找规律，计算不同位数占用索引的多少，倒推给定的n属于哪一个数，然后找到对应的某一位即可

var findNthDigit = function(n) {
    if(n<10){
        return n;
    }
    let i=1; // i表示n所在数字的位数
    let cp=n;
    while(cp-(Math.pow(10,i)-Math.pow(10,i-1))*i>0){
        cp=cp-(Math.pow(10,i)-Math.pow(10,i-1))*i;
        i++;
    }
    cp=cp-1;
    let t=Math.floor(cp/i);
    let m=cp%i;
    let tempResult=Math.pow(10,i-1)+t;
    return (tempResult+'').charAt(m);
};

50 第一个只出现一次的字符

解法1

用两个数组来解决这个问题，一个数组用来存储遍历过的字符，一个数组用来存储已经重复过的的字符；遍历时遇到的字符在这两个数组内都没有出现时，进入第一个数组；如果在第一个数组中出现了，那么从第一个数组中剔除，并加入第二个数组；其余情况都不用考虑

不过好像其实也没有降低时间复杂度，因为使用到了indexOf来查找重复字符的索引，如果让自己来实现的话，又是O(N)的复杂度，综合下来还是O(N2)时间复杂度

var firstUniqChar = function(s) {
    if(!s){
        return ' ';
    }
    let temp = [];
    let dupTemp = [];
    for(let i=0;i<s.length;i++){
        if(dupTemp.indexOf(s[i]) === -1 && temp.indexOf(s[i]) === -1){
            temp.push(s[i]);
        }
        else if(temp.indexOf(s[i]) !== -1){
            temp.splice(temp.indexOf(s[i]), 1);
            dupTemp.push(s[i]);
        }
    }
    return temp[0]?temp[0]:' ';
};

解法2

使用map来解决；需要注意到的是，map对象是乱序的；但是按照key,value的形式来遍历时，是按照插入的顺序进行的

var firstUniqChar = function(s) {
    var map = new Map();

    for(let i=0;i<s.length;i++){
        var cur = s.charAt(i);
        if(map.has(cur)){
            // 如果已经出现过这个字符，那么设为false
            map.set(cur,false);
        } else {
            // 第一次遇到设置成true
            map.set(cur,true);
        }
    }

    for([key,value] of map){
        if(value){
            return key;
        }
    }

    return ' '

};

55 平衡二叉树🌟

采用后序遍历的方式来计算每个节点的高度，这样最后遍历的head的高度就很容易计算了

var isBalanced = function(root) {
    return help(root) === -1 ? false : true;
};

let help = function(node) {
    if(!node) {
        return 0;
    }
    let left = help(node.left);
    let right = help(node.right);
  // 出现这种情况直接返回-1
    if(Math.abs(left-right) > 1 || left === -1 || right === -1) {
        return -1;
    }
    return Math.max(left, right) + 1;
}

Tags: 算法

← js常用API 2021总结 →