LeetCode-17

继续二刷代码随想录，现在刷到贪心，U1S1，贪心还是不会，太难了真的。随机新题的话暂时告一段落，每日随机题目，然后刷剑指offer。

2043 简易银行系统

时间：2022-03-18

var Bank = function (balance) {
    this.balance = balance;
    this.len = balance.length;
};

/**
 * @param {number} account1
 * @param {number} account2
 * @param {number} money
 * @return {boolean}
 */
Bank.prototype.transfer = function (account1, account2, money) {
    if (account1 >= 1 && account1 <= this.len && account2 >= 1 && account2 <= this.len) {
        if (this.withdraw(account1, money)) {
            return this.deposit(account2, money);
        }
    }

    return false;
};

/**
 * @param {number} account
 * @param {number} money
 * @return {boolean}
 */
Bank.prototype.deposit = function (account, money) {
    if (account >= 1 && account <= this.len) {
        this.balance[account - 1] += money;
        return true;
    }
    return false;
};

/**
 * @param {number} account
 * @param {number} money
 * @return {boolean}
 */
Bank.prototype.withdraw = function (account, money) {
    if (account >= 1 && account <= this.len && this.balance[account - 1] >= money) {
        this.balance[account - 1] -= money;
        return true;
    }
    return false;
};

offer 12 矩阵中的路径

时间：2022-03-18

拉稀回溯法

var exist = function (board, word) {
    const m = board.length;
    const n = board[0].length;
    const flag = new Array(m).fill(false).map(() => new Array(n).fill(false));
    const dfs = (i, j, index) => {
        if (index == word.length) return true;
        if (i < 0 || i >= m || j < 0 || j >= n || flag[i][j]) return false;
        if (word[index] == board[i][j]) {
            flag[i][j] = true;
            if (dfs(i + 1, j, index + 1)) return true;
            if (dfs(i, j + 1, index + 1)) return true;
            if (dfs(i - 1, j, index + 1)) return true;
            if (dfs(i, j - 1, index + 1)) return true;
            flag[i][j] = false;
        }
        return false;
    };
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] == word[0]) {
                if (dfs(i, j, 0)) return true;
            }
        }
    }
    return false;
};

offer 13 机器人的运动范围

我的回溯还是一如既往的垃圾啊，拉稀的很

var movingCount = function (m, n, k) {
    const flag = Array.from(new Array(m), () => {
        return new Array(n).fill(false);
    });
    const dfs = (i, j) => {
        if (i >= m || j >= n || flag[i][j]) return 0;
        let tmp = (i % 10) + Math.floor(i / 10) + (j % 10) + Math.floor(j / 10);
        if (tmp <= k) {
            flag[i][j] = true;
            return 1 + dfs(i + 1, j) + dfs(i, j + 1);
        }
        return 0;
    };
    return dfs(0, 0);
};

offer 14 剪绳子

时间：2022-03-18

和343一样，之前能写出来，现在居然写不出来了，拉得很我

dp[i]表示长度为i的绳子剪成m段后的最大乘积

var cuttingRope = function (n) {
    const dp = new Array(n + 1).fill(0);
    dp[2] = 1;
    for (let i = 3; i <= n; i++) {
        for (let j = 2; j < i; j++) {
            dp[i] = Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));
        }
    }
    return dp[n];
};

offer 14 II 剪绳子

时间：2022-03-18

数据量变了很多，直接n变成了1000，把上面的使用BigInt，虽然能通过，但是速度变慢了，差点不能AC

var cuttingRope = function (n) {
    const dp = new Array(n + 1).fill(BigInt(0));
    dp[2] = BigInt(1);
    const MOD = BigInt(1e9 + 7);
    for (let i = 3; i <= n; i++) {
        for (let j = 2; j < i; j++) {
            const max = dp[i - j] * BigInt(j) < (i - j) * j ? (i - j) * j : dp[i - j] * BigInt(j);
            dp[i] = dp[i] < max ? BigInt(max) : dp[i];
        }
    }
    return dp[n] % MOD;
};

一种无厘头贪心，就是绳子长度为3的时候最好，反正就这样子，我也没话说。生而为人，我很抱歉。

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

435 无重叠区间

时间：2022-03-18

之前代码随想录漏了一题，或者可能是新增的，未知。

巨难的贪心，贪nmb，这么难，直接看解析。按照右边进行排序，然后就贪心只要找到比右边界大的，就贪进来，这样子算得上贪的最多？然后再总数量减去这个贪的最多，就是删的最少的。

var eraseOverlapIntervals = function (intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    console.log(intervals);
    let res = 1;
    let min = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= min) {
            min = intervals[i][1];
            res++;
        }
    }
    return intervals.length - res;
};

offer 41 数据流中的中位数

时间：2022-03-18

class MedianFinder {
   public:
    priority_queue<int> small;                            // 大根堆放小的
    priority_queue<int, vector<int>, greater<int> > big;  // 小根堆
    MedianFinder() {}

    void addNum(int num) {
        if (small.empty() || num < small.top()) {
            small.push(num);
        } else {
            big.push(num);
        }
        if (small.size() - big.size() == 2) {
            big.push(small.top());
            small.pop();
        } else if (big.size() - small.size() == 2) {
            small.push(big.top());
            big.pop();
        }
    }

    double findMedian() {
        if (small.size() > big.size()) {
            return small.top();
        } else if (small.size() < big.size()) {
            return big.top();
        } else {
            return double(big.top() + small.top()) / 2 ;
        }
    }
};

606 根据二叉树创建字符串

时间：2022-03-19

轻松秒杀

var tree2str = function (root) {
    const res = [];
    const dfs = (root) => {
        if (!root) return;
        res.push(root.val);
        if (!root.left && root.right) {
            res.push('()');
        }
        if (root.left) {
            res.push('(');
            dfs(root.left);
            res.push(')');
        }
        if (root.right) {
            res.push('(');
            dfs(root.right);
            res.push(')');
        }
    };
    dfs(root);
    return res.join('');
};

offer 15 二进制中1的个数

时间：2022-03-19

191相同的题目，我都写出来了 n&=n-1，但我不知道下一步怎么办，主要还是没理解，这就是翻转最低位的1

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

offer 16 数值的整数次方

时间：2022-03-19

非常操蛋的递归，递归就完事了。

var myPow = function (x, n) {
    const dfs = (x, n) => {
        if (n == 0) return 1;
        const num = dfs(x, Math.floor(n / 2));
        if (n & 1) {
            return num * num * x;
        } else {
            return num * num;
        }
    };
    return n >= 0 ? dfs(x, n) : 1 / dfs(x, -n);
};

什么神仙快速幂，但是和上面的差不多吧，一个递归，一个迭代？

var myPow = function (x, n) {
    function quickMul(x, n) {
        let res = 1;
        while (n > 0) {
            if (n & 1) res *= x;
            x *= x;
            n = Math.floor(n / 2);
        }
        return res;
    }
    return n >= 0 ? quickMul(x, n) : 1 / quickMul(x, -n);
};

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

时间：2022-03-19

var printNumbers = function (n) {
    const res = [];
    for (let i = 1; i < 10 ** n; i++) res.push(i);
    return res;
};

谢邀，api

var printNumbers = function (n) {
    return new Array(10 ** n - 1).fill(1).map((_, i) => i + 1);
};

这题原来考虑的是大数情况，那可难多了啊，这就不是简单题了啊。直接抄袭，就是dfs了，这是求组合？反正就很tm妙，妙妙屋的秒

var printNumbers = function (n) {
    const res = [];
    const dfs = (str, len) => {
        // 到达指定长度，返回
        if (str.length === len) {
            return res.push(str * 1);
        }

        for (let i = 0; i <= 9; i++) {
            dfs(str + i, len);
        }
    };
    // 外层 i 控制长度，即 11 是两位，111 是三位     内层 j 控制该字符串第一位是什么，即首位
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= 9; j++) {
            dfs(j.toString(), i);
        }
    }
    return res;
};

offer 18 删除链表的节点

时间：2022-03-19

这个没话说

var deleteNode = function (head, val) {
    const prev = new ListNode(-1);
    prev.next = head;
    let node = prev;
    while (node.next) {
        if (node.next.val === val) {
            node.next = node.next.next;
            break;
        }
        node = node.next;
    }
    return prev.next;
};

763 划分字母区间

时间：2022-03-19

这题又是代码随想录没有刷到的，应该是漏了，这个方法有点怪怪的，确实说不清，但好像又能够想清楚，先统计每个字符最后出现的位置，然后遍历，取每个字符最后出现位置的最大值，如果遍历下标和这个最大值相同，说明前面的已经变成一组了，可以添加到res了。

var partitionLabels = function (s) {
    const arr = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        arr[s.charCodeAt(i) - 97] = i;
    }
    let left = 0,
        right = 0;
    const res = [];
    for (let i = 0; i < s.length; i++) {
        right = Math.max(right, arr[s.charCodeAt(i) - 97]);
        if (right == i) {
            res.push(right - left + 1);
            left = right + 1;
        }
    }
    return res;
};

6027 统计数组中峰和谷的数量

时间：2022-03-20

贪心，和摆动序列那道题差不多，但是需要多考虑前面为平坡的情况。

var countHillValley = function (nums) {
    let res = 0;
    let preDiff = nums[1] - nums[0];
    for (let i = 2; i < nums.length; i++) {
        const diff = nums[i] - nums[i - 1];
        if ((preDiff < 0 && diff > 0) || (preDiff > 0 && diff < 0)) {
            res++;
            preDiff = diff;
        }
        if (preDiff == 0) {
            preDiff = diff;
        }
    }
    return res;
};

6028 统计道路上的碰撞次数

时间：2022-03-20

什么神仙写法，反正我不会，哈哈

 var countCollisions = function (directions) {
    let l = 0,
        r = directions.length - 1;
    while (l <= r && directions[l] == 'L') ++l;
    while (l <= r && directions[r] == 'R') --r;
    let res = 0;
    for (let i = l; i <= r; ++i) if (directions[i] == 'L' || directions[i] == 'R') ++res;
    return res;
};

6029 射箭比赛中的最大得分

时间：2022-03-20

这个是动态规划+路径回溯，不推荐，这个下标非常的混乱我写的，所以不知道怎么解。

var maximumBobPoints = function (numArrows, aliceArrows) {
    // dp[i][j]表示前i个靶子，使用j支箭的最优解
    const dp = new Array(13).fill(0).map(() => new Array(numArrows + 1).fill(0));
    const res = new Array(12).fill(0);
    for (let i = 1; i <= 12; i++) {
        for (let j = numArrows; j >= 1; j--) {
            const num = aliceArrows[i] + 1;
            if (j - num >= 0) {
                dp[i][j] = Math.max(dp[i - 1][j - num] + i, dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    let j = numArrows;
    for (let i = 12; i >= 1; i--) {
        // console.log(dp[i][numArrows]);
        if (dp[i][j] == dp[i - 1][j]) continue;
        if (dp[i][j] == dp[i - 1][j - aliceArrows[i] - 1] + i) {
            res[i] = aliceArrows[i] + 1;
            j -= aliceArrows[i] + 1;
        }
    }
    res[0] += j;
    return res;
};

回溯法，非常推荐，又快又好，我可以打出来。

var maximumBobPoints = function (numArrows, aliceArrows) {
    let res;
    let max = 0;
    const dfs = (path, index, left, score, alicescore) => {
        if (score >= alicescore) {
            if (score > max) {
                max = score;
                path[0] += left;
                res = Array.from(path);
                path[0] -= left;
            }
        }
        for (let i = index; i < 12; i++) {
            if (left < aliceArrows[i] + 1) continue;
            path[i] = aliceArrows[i] + 1;
            dfs(path, i + 1, left - aliceArrows[i] - 1, score + i, alicescore - i);
            path[i] = 0;
        }
    };
    const path = new Array(12).fill(0);
    const alicescore = aliceArrows.reduce((prev, curv, index) => prev + (curv > 0 ? index : 0), 0);
    dfs(path, 0, numArrows, 0, alicescore);
    return res;
};

2039 网络空闲的时刻

时间：2022-03-20

无向图，先求出每个点距离原点最近的距离，然后就公式了。说难也不难，但说简单也不简单

var networkBecomesIdle = function (edges, patience) {
    // 创建graph图
    const n = patience.length,
        graph = new Array(n).fill(0).map(() => []);
    for (let edge of edges) {
        graph[edge[0]].push(edge[1]);
        graph[edge[1]].push(edge[0]);
    }

    // bfs来获得每条路线最短的路径
    let cnt = 0;
    let queue = [0];
    const distance = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    while (queue.length) {
        const next = [];
        cnt++;
        for (let i of queue) {
            for (let j of graph[i]) {
                if (distance[j] === Number.MAX_SAFE_INTEGER) {
                    distance[j] = cnt;
                    next.push(j);
                }
            }
        }
        queue = next;
    }
    let res = 0,
        max = 0;
    for (let i = 1; i < n; i++) {
        const len = distance[i] * 2;
        max = Math.floor((len - 1) / patience[i]) * patience[i] + len;
        res = Math.max(res, max);
    }
    return res + 1;
};

offer 20 表示数值的字符串

时间：2022-03-21

遇到这种题，第一思路先是应该如何用库函数写出来，如果用库函数都写不出来，那人也不行了。

var isNumber = function (s) {
    s = s.trim();
    if (s.length == 0) return false;
    const num = Number(s);
    if (Number.isNaN(num)) return false;
    return typeof num;
};

麻烦死了，就知道不应该写，花了两个小时

var isNumber = function (s) {
    // console.log(s);
    const isFloat = () => {
        let front = false;

        if (isInt()) front = true;

        if (i == n) return true;
        if (s[i] == '.') {
            i++;
            if (!isInt() && !front) return false;
        } else if (!front) return false;
        return true;
    };
    const isInt = () => {
        const tmp = i;
        while (i < n && s[i] >= '0' && s[i] <= '9') {
            i++;
        }
        if (tmp == i) return false;
        return true;
    };
    let n = s.length;
    let i = 0;

    // // 去除前后空格
    while (i < n && s[i] == ' ') i++;
    // 全都是空字符串直接返回false
    if (i == n) false;
    while (i < n && s[n - 1] == ' ') n--;

    // 遇到第一个字符是正负号
    if (s[i] === '+' || s[i] === '-') i++;
    if (i == n) return false;
    if (!isFloat()) return false;
    if (s[i] == 'e' || s[i] == 'E') {
        i++;
        if (i == n) return false;
        if (s[i] === '+' || s[i] === '-') i++;
        if (i == n) return false;
        if (isInt() && i != n) {
            return false;
        }
    }
    if (i != n) return false;
    return true;
};

offer 21 调整数组顺序使奇数位于偶数前面

时间：2022-03-21

秒杀，简简单单

var exchange = function (nums) {
    let i = 0,
        j = nums.length - 1;
    while (i < j) {
        if (nums[j] & 1) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        } else j--;
    }
    return nums;
};

offer 22 链表中倒数第k个节点

时间：2022-03-21

写过，简单

var getKthFromEnd = function (head, k) {
    let last = head;
    while (k-- > 1) last = last.next;
    let cur = head;
    while (last.next != null) {
        cur = cur.next;
        last = last.next;
    }
    return cur;
};

offer 26 树的子结构

时间：2022-03-21

拉胯的写法，时间只能击败5%的人，唉，西八。

var isSubStructure = function (A, B) {
    if (!A || !B) return false;
    const dfs = (A, B, flag) => {
        if (!B) return true;
        if (!A) return false;
        if (A.val == B.val) {
            if(dfs(A.left, B.left, true) && dfs(A.right, B.right, true)) return true;
        } else if (flag) {
            return false;
        }
        return dfs(A.left, B, false) || dfs(A.right, B, false);
    };
    return dfs(A, B);
};

还有一种方法，速度比我快，确实了。

var isSubStructure = function(A, B) {
    if(!A || !B)
        return false;
    
    return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};

function isSame(A, B) {
    // B空了，说明B树遍历完了，是子树
    if(!B)
        return true;
    // 不符合上面情况的前提下A空了，说明B树还没遍历完，不是子树
    if(!A)
        return false;
    // 值不同，不是子树
    if(A.val !== B.val)
        return false;
    return isSame(A.left, B.left) && isSame(A.right, B.right);
}

2038 如果相邻两个颜色均相同则删除当前颜色

时间：2022-03-22

什么简单的中等题

var winnerOfGame = function (colors) {
    let cntA = 0;
    let cntB = 0;
    for (let i = 1; i < colors.length - 1; i++) {
        if (colors[i] == colors[i - 1] && colors[i] == colors[i + 1]) {
            if (colors[i] == 'A') cntA++;
            if (colors[i] == 'B') cntB++;
        }
    }
    return cntA > cntB ? true : false;
};

offer 30 包含min函数的栈

时间：2022-03-22

var MinStack = function () {
    this.stack = [];
    this.minStack = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
    this.stack.push(x);
    if (this.minStack.length == 0 || x <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
    if (this.stack.pop() == this.minStack[this.minStack.length - 1]) {
        this.minStack.pop();
    }
};

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

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

offer 31 栈的压入弹出序列

时间：2022-03-22

很清晰的思路，可惜我写出来一开始，这种思路确实清楚。

var validateStackSequences = function (pushed, popped) {
    const st = [];
    const n = pushed.length;
    let i = 0,
        j = 0;
    for (let i of pushed) {
        st.push(i);
        while (st.length > 0 && popped[j] == st[st.length - 1]) {
            st.pop();
            j++;
        }
    }
    return st.length == 0;
};

offer 32 III 从上到下打印二叉树 III

时间：2022-03-22

要么用unshift，要么就是reverse，就这两种。

var levelOrder = function (root) {
    if (!root) return [];
    const res = [];
    let que = [root];
    let flag = true;
    while (que.length) {
        const tmp = [];
        const tmp_que = [];
        for (let i = 0; i < que.length; i++) {
            tmp.push(que[i].val);
            if (que[i].left) tmp_que.push(que[i].left);
            if (que[i].right) tmp_que.push(que[i].right);
        }
        que = tmp_que;
        if (flag == false) {
            res.push(Array.from(tmp).reverse());
        } else res.push(Array.from(tmp));
        flag ^= 1;
    }
    return res;
};

offer 32 I 从上到下打印二叉树

时间：2022-03-23

var levelOrder = function (root) {
    if (!root) return [];
    const res = [];
    let que = [root];
    while (que.length) {
        const tmp_que = [];
        for (let i = 0; i < que.length; i++) {
            res.push(que[i].val);
            if (que[i].left) tmp_que.push(que[i].left);
            if (que[i].right) tmp_que.push(que[i].right);
        }
        que=tmp_que;
    }
    return res;
};

offer 19 正则表达式匹配

时间：2022-03-23

困难，没话说，直接去看解析就行了，我说了也白搭。

var isMatch = function (s, p) {
    const n = s.length + 1,
        m = p.length + 1,
        //dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。
        dp = new Array(n).fill(0).map(() => new Array(m).fill(0));
    dp[0][0] = true;
    //dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*'： 
    //首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配
    for (let j = 2; j < m; j += 2) {
        dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
    }
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            if (p[j - 1] == '*') {
                // dp[i][j-2]表示前面那个字符出现0次
                // dp[i - 1][j] && s[i - 1] == p[j - 2] 即让字符 p[j - 2] 多出现 1 次时
                // dp[i - 1][j] && p[j - 2] == '.'即让字符 p[j - 2]='.' 多出现 1 次时
                dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        }
    }
    return dp[n - 1][m - 1];
};

offer 33 二叉搜索树的后序遍历序列

时间：2022-03-23

垃圾想法，O(n^2)，利用二叉树，后序就是左右中，左<中，右>左，所以每次循环都判断是不是左边都比中小，右边是不是都比中大，遍历一遍，看看能不能遍历到头，如果能行，就下一轮循环了。

var verifyPostorder = function (postorder) {
    const dfs = (left, right) => {
        if (left >= right) return true;
        const rootVal = postorder[right];
        let index = right;
        while (index >= left && postorder[index] >= rootVal) {
            index--;
        }
        let end = index;
        while (index >= left && postorder[index] <= rootVal) {
            index--;
        }
        return index == left - 1 && dfs(left, end) && dfs(end+1, right - 1);
    };
    return dfs(0, postorder.length - 1);
};

直接抽象单调栈，虽然我是想不出来的，但这波很抽象我只能说。

var verifyPostorder = function (postorder) {
    //我tm直接单调栈
    const st = [];
    let parent = Infinity;
    for (let i = postorder.length - 1; i >= 0; i--) {
        while (st.length && postorder[i] < st[st.length - 1]) {
            parent = st.pop();
        }
        if (parent < postorder[i]) return false;
        st.push(postorder[i]);
    }
    return true;
};

offer 34 二叉树中和为某一值的路径

时间：2022-03-23

113一样，写起来还是有点不顺畅

var pathSum = function (root, target) {
    if (!root) return [];
    const res = [];
    const backtrace = (root, path, target) => {
        path.push(root.val);
        if (!root.left && !root.right && target == root.val) res.push(Array.from(path));
        root.left && backtrace(root.left, path, target - root.val);
        root.right && backtrace(root.right, path, target - root.val);
        path.pop();
    };
    backtrace(root, [], target);
    return res;
};

offer 35 复杂链表的复制

时间：2022-03-23

有没有一种可能，就是一种可能，就是这题是这题。哈希表我没写出来，真的尿了。

var copyRandomList = function (head) {
    if (!head) return head;
    let node = head;
    let map = new Map();
    while (node) {
        map.set(node, new Node(node.val));
        node = node.next;
    }
    node = head;
    while (node) {
        map.get(node).next = map.get(node.next) || null;
        map.get(node).random = map.get(node.random);
        node = node.next;
    }
    return map.get(head);
};

这个牛逼，空间O(1)，每次复制一个新的节点放到后面，然后复制新的random为老节点random 的下一个，然后再重新拆分两条链。

var copyRandomList = function (head) {
    if (!head) return head;
    for (let node = head; node != null; node = node.next.next) {
        const newNode = new Node(node.val, node.next);
        node.next = newNode;
    }
    for (let node = head; node != null; node = node.next.next) {
        const newNode = node.next;
        newNode.random = node.random == null ? null : node.random.next
    }
    let newHead = head.next;
    for (let node = head; node != null; node = node.next) {
        const newNode = node.next;
        if (!newNode.next) { node.next = null; newNode.next = null; break; }
        node.next = node.next.next;
        newNode.next = newNode.next.next;
    }
    return newHead;
};

661 图片平滑器

时间：2022-03-24

简单乱写，但是肯定不是最优的方案

var imageSmoother = function (img) {
    const m = img.length;
    const n = img[0].length;
    const res = new Array(m).fill(0).map(() => new Array(n).fill(0));
    const dirs = [
        [-1, -1],
        [-1, 0],
        [-1, 1],
        [0, -1],
        [0, 1],
        [1, -1],
        [1, 0],
        [1, 1]
    ];
    let tmp = 0;
    let cnt = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            tmp = img[i][j];
            cnt = 1;
            for (let d of dirs) {
                const x = i + d[0];
                const y = j + d[1];
                if (x < 0 || x >= m || y < 0 || y >= n) continue;
                tmp += img[x][y];
                cnt++;
            }
            res[i][j] = Math.floor(tmp / cnt);
        }
    }
    return res;
};

offer 36 二叉搜索树与双向链表

时间：2022-03-24

一把过，没什么难度。

var treeToDoublyList = function (root) {
    if (!root) return null;
    let head = root;
    while (head.left) head = head.left;
    let prev = null;
    const dfs = (root) => {
        if (!root) return;
        dfs(root.left);
        if (prev) {
            prev.right = root;
            root.left = prev;
        }
        prev = root;
        dfs(root.right);
    };
    dfs(root);
    prev.right = head;
    head.left = prev;
    return head;
};

offer 37 序列化二叉树

时间：2022-03-24

层序遍历我的超人，这道题没有困难的难度，只有一般般的难度。

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
    if (!root) return '';
    const res = [];
    let que = [root];
    while (que.length) {
        const tmp_que = [];
        for (let i = 0; i < que.length; i++) {
            if (que[i] != null) {
                res.push(que[i].val);
                tmp_que.push(que[i].left);
                tmp_que.push(que[i].right);
            }else{
                res.push('#')
            }
        }
        que = tmp_que;
    }
    return res.join(',');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
    if (!data) return null;
    const arr = data.split(',');
    const len = arr.length;
    let root = new TreeNode(arr[0]);
    const que = [root];
    let num = 1;
    while (num < len) {
        const node = que.shift();
        let leftVal = arr[num];
        let rightVal = arr[num + 1];
        if (leftVal !== '#') {
            node.left = new TreeNode(leftVal);
            que.push(node.left);
        }
        if (rightVal !== '#') {
            node.right = new TreeNode(rightVal);
            que.push(node.right);
        }
        num += 2;
    }
    return root;
};

offer 38 字符串的排列

时间：2022-03-24

就是全排列，这次得心应手很多，但是从0开始又没有记住

var permutation = function (s) {
    const arr = s.split('');
    const n = arr.length;
    arr.sort();
    const res = [];
    const used = new Array(n).fill(false);
    const backTrace = (path, index) => {
        if (path.length == n) {
            res.push(path.join(''));
            return;
        }
        for (let i = 0; i < n; i++) {
            if (used[i] || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) continue;
            path.push(arr[i]);
            used[i] = true;
            backTrace(path, i);
            used[i] = false;
            path.pop();
        }
    };
    backTrace([], 0);
    return res;
};

offer 39 数组中出现次数超过一半的数字

时间：2022-03-24

以前写过，空间O(n)的方法

var majorityElement = function (nums) {
    const n = Math.floor(nums.length / 2);
    const map = new Map();
    for (let i of nums) {
        map.set(i, (map.get(i) || 0) + 1);
        if (map.get(i) > n) return i;
    }
};

看了一下投票法的想法，直接写出来

var majorityElement = function (nums) {
    let vote = 0;
    let prev = nums[0];
    for (let i of nums) {
        if (i == prev) vote++;
        else {
            vote--;
            if (vote < 0) {
                vote = 0;
                prev = i;
            }
        }
    }
    return prev;
};

offer 40 最小的k个数

时间：2022-03-24

谢邀，秒写，O(nlogn)

var getLeastNumbers = function (arr, k) {
    arr.sort((a, b) => a - b);
    return arr.slice(0,k);
};

手撸快排，虽然我没有撸出来

var getLeastNumbers = function (arr, k) {
    const n = arr.length;
    const quickSort = (arr, left = 0, right = n - 1) => {
        if (left >= right) return;
        let l = left,
            r = right;
        while (l < r) {
            while (l < r && arr[r] >= arr[left]) r--;
            while (l < r && arr[l] <= arr[left]) l++;
            swap(arr, l, r);
        }
        swap(arr, l, left);
        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    };
    quickSort(arr);
    return arr.slice(0,k);
};
var swap = function (arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
};

优化的思维，不用每次都递归调用quickSort()，判断index和k的关系，然后只有计算半边就行了。行中行了。

var getLeastNumbers = function (arr, k) {
    const quickSort = (arr, left = 0, right = n - 1) => {
        if (left >= right) return right;
        const pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    };
    const n = arr.length;
    let start = 0;
    let end = n - 1;
    // 寻找一次标杆元素的位置
    let index = quickSort(arr, start, end);
    while (index !== k - 1) {
        if (index > k - 1) {
            end = index - 1;
        } else {
            start = index + 1;
        }
        index = quickSort(arr, start, end);
    }
    return arr.slice(0, k);
};