剑指offer刷题记录-JS

因为要面试前端，因此题解全部使用JS

03.数组中的重复数字

解1:使用Set判断

但是使用Set判断的话空间复杂度为O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    let s = new Set()
    for(let i = 0;i < nums.length;i++) {
        if(s.has(nums[i]))return nums[i]
        s.add(nums[i])
    }
};

解2:根据题意，使用负数标记

访问过某下标，就把某下标变为负数，假如发现在访问之前已经是负的，那么直接返回该数字
对于0而言，0===-0，因此特判

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    let flag = false
    for(let i = 0;i < nums.length;i++) {
        const now = Math.abs(nums[i])
        if(nums[now] < 0) return now;
        nums[now] = -nums[now]
        if(now == 0) {
            if(flag) return 0
            flag = true
        }
    }
};

解3:原地交换 回来补

04. 二维数组中的查找

解1:暴力

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    for(let i = 0;i < matrix.length;i++) {
        for(let j = 0;j < matrix[0].length;j++) {
            if(matrix[i][j]===target) return true
        }
    }
    return false
};

解2:按规律移动

从左下角到右上角可以转化为一颗二叉搜索树，遍历求解即可

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    if(matrix.length === 0) return false
    const [lx,ly] = [matrix[0].length,matrix.length]
    if(lx===0) return false
    let [i,j] = [0,lx-1]
    while(true){
        if(matrix[i][j] < target) i++
        else if(matrix[i][j] > target) j--
        else if(matrix[i][j]===target) return true
        if(i < 0 || i >= ly || j < 0 || j >= lx) break
    }
    return false
};

05. 替换空格

解1.使用replace

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    return s.replaceAll(' ','%20')
};

解2.暴力

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    let ans = ""
    const targetCharCode = " ".charCodeAt(0)
    for(let i = 0;i < s.length;i++) {
        if(s.charCodeAt(i)===targetCharCode) ans+='%20'
        else ans += s.charAt(i)
    }
    return ans
};

解3.正则

等JS正则学完了回来补

06. 从尾到头打印链表

解1.暴力:反转数组

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    const ans = []
    while(head!==null){
        ans.push(head.val)
        head = head.next
    }
    ans.reverse()
    return ans
};

解2：嵌套函数模拟栈

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    const ans = []
    const vis = (h)=>{
        if(h===null) return
        vis(h.next)
        ans.push(h.val)
    }
    vis(head)
    return ans
};

解3:栈

07. 重建二叉树

由一个前序可以确定两个中序

/**
 * 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) {
    if(preorder.length===0) return null
    const len = preorder.length
    let now = 0
    const findPos = (v) => {
        for(let i = 0;i < len;i++) if(v===inorder[i]) return i
        return -1
    }
    const construct = (l,r)=>{
        const root = new TreeNode(preorder[now++])
        const pos = findPos(root.val)
        if(pos > l) root.left = construct(l,pos-1)
        if(pos <= r-1) root.right = construct(pos+1,r)
        return root
    }
    return construct(0,len-1);
};

09. 用两个栈实现队列

当第二个stack用尽后，将第一个stack数全部放入第二个中，因为反转的反转为正序

var CQueue = function() {
    this.a = []
    this.b = []
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.b.push(value)
};


/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if(this.a.length > 0) return this.a.pop()
    else {
        while(this.b.length > 0) {
            this.a.push(this.b.pop())
        }
    }
    if(this.a.length > 0) return this.a.pop()
    return -1
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

10- I. 斐波那契数列

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n===0) return 0
    if(n===1) return 1
    let [a,b] = [0,1]
    while(n>0) {
        let tmp = a 
        a = (a+b)%1000000007
        b = tmp
        n--
    }
    return a
};

矩阵快速幂（待补充）

11. 旋转数组的最小数字

思路：二分，寻找一个左边比他大 右边也是大等于的
但是这里要注意一下，遇见相等的就不能确定最终需要的值在mid左边还是右边，因此可以一个一个缩小窗口

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
        const len = numbers.length
        if(numbers[len-1] > numbers[0]) return numbers[0];
        let [l,r] = [0,len-1]
        while(l < r) {
            const mid = (l+r)>>1
            if(numbers[mid] > numbers[r]) l = mid + 1
            else if(numbers[mid] == numbers[r]) r = r-1
            else r = mid
        }
        console.log(l)
        return numbers[l]
    };

12. 矩阵中的路径

常规深搜

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const init2DArr = (x,y,initFun)=>{ 
        const res = []
        for(let i = 0;i < y;i++) {
            const arr = []
            for(let j = 0;j < x;j++) arr.push(initFun(x,y))
            res.push(arr)
        }
        return res
    }
    const [by,bx] = [board.length,board[0].length]
    const vis = init2DArr(bx,by,()=>false)
    const dirs = [[1,0],[0,1],[-1,0],[0,-1]]
    const lenWord = word.length
    
    let flag = false
    const search = (x,y,pos)=>{
        //console.log(x,y,pos,board[y][x])
        if(board[y][x].charCodeAt(0)!==word.charCodeAt(pos)) return false
        if(pos===lenWord-1) {
            flag = true
            return
        }
        for(let i = 0;i < 4;i++) {
            const [nx,ny] = [x+dirs[i][0],y+dirs[i][1]]
            //console.log([nx,ny],[bx,by],vis)
            if(nx >= 0 && ny >= 0 && nx < bx && ny < by && vis[ny][nx] === false){
                console.log([nx,ny],[bx,by],vis[ny][nx])
                vis[ny][nx] = true
                search(nx,ny,pos+1)
                vis[ny][nx] = false
            }
            if(flag) break
        }
        return false
    }
    //console.log(vis)
    for(let i = 0;i < by;i++) {
            for(let j = 0;j < bx;j++){
                vis[i][j] = true
                search(j,i,0)
                vis[i][j] = false
            }
        }
    return flag
};

13. 机器人的运动范围

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
        // visited 用来记录走过的格子，避免重复
        const visited = Array(m).fill(0).map(_ => Array(n).fill(false));

        // 辅助函数，计算位数和
        function sum(n) {
            let res = 0;
            while (n) {
                res += n % 10;
                n = Math.floor(n / 10)
            }
            return res;
        }
        // dfs
        function dfs(x, y) {
            // 对应开头所说的三个终止条件，超过k值、到达边界、走过的格子
            if (sum(x) + sum(y) > k || x >= m || y >= n || visited[x][y]) return 0;
            else {
                // 记录当前格子已经走过，返回当前计数 1 + 后续其他两个方向的总和
                visited[x][y] = true
                return 1 + dfs(x + 1, y) + dfs(x, y + 1);
            }
        }

        return dfs(0, 0);
    };

##14- I. 剪绳子
动态规划，从小绳子向大绳子转移

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
        const dp = []
        for(let i = 0;i < n+1;i++) dp.push(0)
        dp[2] = 1
        for(let i = 3;i < n+1;i++) {
            for(let j = 1;i-j > 0;j++) {
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]))
            }
        }
        return dp[n]
    };

##14- II. 剪绳子 II

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
        if(n < 3) return 1
        if(n === 3) return 2
        let res = 1
        while(n > 4) {
            res *= 3
            res %= 1000000007
            n -= 3
        }
        return (n * res % 1000000007)
    };

##15. 二进制中1的个数

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
        let cnt = 0
        while(n!==0){
            cnt += (n%2)
            n = Math.floor(n/2)
        }
        return cnt
};

这里注意：有一个位运算优化 n&=n-1可以把最低位变为0，而可以跳过其中几个数位

var hammingWeight = function(n) {
    let ret = 0;
    while (n) {
        n &= n - 1;
        ret++;
    }
    return ret;
};

##17. 打印从1到最大的n位数

/**
 * @param {number} n
 * @return {number[]}
 */
var printNumbers = function(n) {
    const res = []
    for(let i = 1;i < Math.pow(10,n);i++) res.push(i)
    return res
};

这道题在实际使用中是大数，可以模拟以下进位

##18. 删除链表的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    let now = head
    let last = null
    while(now!==null) {
        if(val==now.val) {
            if(last===null) head = now.next
            else last.next = now.next
        } 
        last = now
        now = now.next
    }
    return head
};

##[20]
是个状态机

##22. 链表中倒数第k个节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let ans = null
    const search=(head)=>{ 
        if(head==null) return 0
        const res = search(head.next)+1
        if(res===k) ans = head
        return res
    }
    search(head)
    return ans
};

重要的是双指针

25. 合并两个排序的链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let head = new ListNode(0)
    let now = head
    while(l1!==null&&l2!==null) {
        let tmp = null
        if(l1.val < l2.val) {
            tmp = l1
            l1 = l1.next
        }else{
            tmp = l2
            l2 = l2.next
        }
        now.next = tmp
        now = now.next
    }

    if(l1!==null) {
        now.next = l1
    }

    if(l2!==null) {
        now.next = l2
    }
    

    return head.next
};

29. 顺时针打印矩阵

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    const ans = []
    if (matrix.length === 0) return ans
    let [b,t,l,r] = [0,matrix.length-1,0,matrix[0].length-1]

    while(l <= r && b <= t) {
        for(let i = l;i <= r;i++) {
            ans.push(matrix[b][i])
        }
        b++
        if(l > r || b > t) break
        for(let i = b;i <= t;i++) {
            ans.push(matrix[i][r])
        }
        r--
        if(l > r || b > t) break
        for(let i = r;i >= l;i--) {
            ans.push(matrix[t][i])
        }
        t--
        if(l > r || b > t) break
        for(let i = t;i >= b;i--) {
            ans.push(matrix[i][l])
        }
        l++
    }
    return ans
};

###30. 包含min函数的栈
用双重stack包裹下就行

/**
 * initialize your data structure.jpg here.
 */
var MinStack = function() {
    this.realst = []
    this.minst = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.realst.push(x)
    if(this.minst.length===0) this.minst.push(x)
    else{
        if(x <= this.min()) this.minst.push(x)
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    let x = this.realst.pop()
    if (x===this.min()) {
        this.minst.pop()
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.realst[this.realst.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
    return this.minst[this.minst.length - 1]
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

###[32]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    const ans = []
    let now = 0
    const queue = []
    queue.push([root,1])
    while(queue.length != 0){
        const [top,K] = queue.shift()
        if(!top) continue
        if(K>now) {
            now = K
            ans.push([])
        }
        ans[now-1].push(top.val)
        queue.push([top.left,K+1])
        queue.push([top.right,K+1])
    }
    return ans
};

###[33]

###[34]
注意数组展平

/**
 * 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} target
 * @return {number[][]}
 */
var pathSum = function(root, target) {
    const ans = []
    const search = (root,now,arr)=>{
        if(!root) return
        now += root.val
        arr.push(root.val)
        if(!root.left && !root.right) {
            if(now===target) {
                ans.push([...arr])
            }
        }else{
            search(root.left,now,arr)
            search(root.right,now,arr)
        }
        arr.pop()
    }
    search(root,0,[])
    return ans
};

[38]

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function(s) {
    const ans = []
    const len = s.length
    const vis = []
    const set = new Set()
    for(let i = 0;i < len;i++) vis.push(0)
    const search = (str,l)=>{
        if(l===len-1) {
            set.add(str)
            return
        }
        for(let i = 0;i < len;i++) {
            if(vis[i]===0) {
                vis[i] = 1
                search(str+s.charAt(i),l+1)
                vis[i] = 0
            }
        }
    }
    search("",-1)
    for (let i of set) {
        ans.push(i)
    }
    return ans
};

[39]

摩尔投票法

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let [num,count]=[0,0]
    for(let i of nums) {
        if(count===0) {
            num = i
            count = 1
        }
        else{
            if(num===i) count++
            else count--
        }
    }
    return num
};

[40]

求最小用大根堆 求最大用小根堆

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};