Leetcode-23

继续程序员面试金典题

面试 1711 单词距离

时间：2022-05-27

今天这道题略草好吧，怎么这也能算，这样子每次都要计算，搞得效率就很下头，官解居然只能这？

var findClosest = function (words, word1, word2) {
    const length = words.length;
    let ans = length;
    let index1 = -1, index2 = -1;
    for (let i = 0; i < length; i++) {
        const word = words[i];
        if (word === word1) {
            index1 = i;
        } else if (word === word2) {
            index2 = i;
        }
        if (index1 >= 0 && index2 >= 0) {
            ans = Math.min(ans, Math.abs(index1 - index2));
        }
    }
    return ans;
};

面试 1601 交换数字

时间：2022-05-27

我tm直接用解构

var swapNumbers = function (numbers) {
    [numbers[0], numbers[1]] = [numbers[1], numbers[0]];
    return numbers;
};

利用异或的方法。

var swapNumbers = function (numbers) {
    numbers[0] = numbers[0] ^ numbers[1];
    numbers[1] = numbers[0] ^ numbers[1];
    numbers[0] = numbers[0] ^ numbers[1];
    return numbers;
};

面试 1602 单词频率

时间：2022-05-27

这个太简单了吧

/**
 * @param {string[]} book
 */
var WordsFrequency = function (book) {
    const map = new Map();
    for (let b of book) map.set(b, (map.get(b) || 0) + 1);
    this.map = map;
};

/**
 * @param {string} word
 * @return {number}
 */
WordsFrequency.prototype.get = function (word) {
    return this.map.get(word) ?? 0;
};

面试 1603 交点

时间：2022-05-27

这什么傻逼题目，求两个线段的交点，没想到这么难，直接复制一个，不建议写，浪费时间和生命，真的划不来

var intersection = function (start1, end1, start2, end2, k = 0) {
    // 特殊k值前置，保证特殊都在前边，好处理
    if (k === 0) {
        if (start2[0] - end2[0] === 0 || start2[1] - end2[1] === 0) return intersection(start2, end2, start1, end1, (k = 1));
    }
    // 这个是可能的交点
    let x = null,
        y = null;
    // 第一条平行于Y轴
    if (start1[0] - end1[0] === 0) {
        if (start2[0] - end2[0] === 0) {
            // 两条线都平行Y轴
            if (start1[0] === start2[0] && Math.max(start1[1], end1[1]) >= Math.min(start2[1], end2[1]) && Math.min(start1[1], end1[1]) <= Math.max(start2[1], end2[1]))
                return [start1[0], Math.max(Math.min(start2[1], end2[1]), Math.min(start1[1], end1[1]))];
        } else {
            // 第二条线不平行Y(未判断线段可交)
            let k = (end2[1] - start2[1]) / (end2[0] - start2[0]);
            x = start1[0];
            y = (x - end2[0]) * k + end2[1];
        }
    } else if (start1[1] - end1[1] === 0) {
        // 第一条平行于X轴
        if (start2[1] - end2[1] === 0) {
            // 两条线都平行X轴
            if (start1[1] === start2[1] && Math.max(start1[0], end1[0]) >= Math.min(start2[0], end2[0]) && Math.min(start1[0], end1[0]) >= Math.max(start2[0], end2[0]))
                return [Math.max(Math.min(start2[0], end2[0]), Math.min(start1[0], end1[0]), start1[1])];
        } else if (start2[0] - end2[0] === 0) {
            // 第二条线平行Y(未判断线段可交)
            x = start2[0];
            y = start1[1];
        } else {
            // 第二条线存在K
            let k = (end2[1] - start2[1]) / (end2[0] - start2[0]);
            y = start1[1];
            x = (y - (start2[1] - k * start2[0])) / k;
        }
    } else if ((end2[1] - start2[1]) / (end2[0] - start2[0]) === (end1[1] - start1[1]) / (end1[0] - start1[0])) {
        // 斜率不为0存在且相等
        let k = (end2[1] - start2[1]) / (end2[0] - start2[0]);
        if (end2[1] - k * end2[0] === end1[1] - k * end1[0]) {
            // b相等
            x = Math.max(Math.min(start1[0], end1[0]), Math.min(start2[0], end2[0]));
            y = Math.max(Math.min(start1[1], end1[1]), Math.min(start2[1], end2[1]));
        } else {
            // b不相等 没有交点
            return [];
        }
    } else {
        // 两个都是正常的K
        let k2 = (end2[1] - start2[1]) / (end2[0] - start2[0]);
        let k1 = (end1[1] - start1[1]) / (end1[0] - start1[0]);
        let b2 = start2[1] - k2 * start2[0];
        let b1 = start1[1] - k1 * start1[0];
        x = (b2 - b1) / (k1 - k2);
        y = x * k1 + b1;
    }
    // 上下左右边界，确定所求出来的x,y是不是在线段上面
    let l = Math.max(Math.min(start1[0], end1[0]), Math.min(start2[0], end2[0]));
    let r = Math.min(Math.max(start1[0], end1[0]), Math.max(start2[0], end2[0]));
    let b = Math.max(Math.min(start1[1], end1[1]), Math.min(start2[1], end2[1]));
    let t = Math.min(Math.max(start1[1], end1[1]), Math.max(start2[1], end2[1]));

    if (x !== null && x >= l && x <= r && y <= t && y >= b) {
        return [x, y];
    } else {
        return [];
    }
};

473 火柴拼正方形

时间：2022-06-02

懒狗回来重新写的第一题，写不出来，居然还是儿童节的题目，太难了。抄的是回溯+剪枝的方法，先排序，然后剪枝，第一个剪枝我能够想到，就是加入此火柴之后超过了边长的长度，还有一个就是和前一条边相等，那么就不加了，会破坏一致性。其实有点道理。但是我估计是想不出来的，现在还有点想不通。

let makesquare = (nums) => {
    if (nums.length < 4) return false;
    let total = nums.reduce((index, x) => (x += index));
    if (total % 4) return false;
    // 排序，从大到小
    nums.sort((a, b) => b - a);
    // 这样子写也行，因为上面已经确定是4的倍数了
    const SIDE = total / 4;
    if (nums[0] > SIDE) return false;
    let edges = [0, 0, 0, 0];

    // 回溯加上剪枝
    const dfs = (index) => {
        if (index === nums.length) return true;
        for (let i = 0; i < 4; i++) {
            // 因为排过序了，所以放不进去就直接pass就行了
            // 但这里还有个取巧的东西，如果i大于0，并且和前面一条相等，那么也跳过，说是为了保持一致性，这个我真没想到
            if (edges[i] + nums[index] > SIDE || (i && edges[i] === edges[i - 1])) continue;
            edges[i] += nums[index];
            if (dfs(index + 1)) return true;
            edges[i] -= nums[index];
        }
        return false;
    };
    return dfs(0);
};

1022 从根到叶的二进制数之和

时间：2022-06-02

好像很快的样子，还可以这波。

var sumRootToLeaf = function (root) {
    let res = 0;
    const dfs = (root, sum) => {
        if (!root) return;
        sum = sum * 2 + root.val;
        if (!root.left && !root.right) {
            res += sum;
            return;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    };
    dfs(root, 0);
    return res;
};

468 验证IP地址

时间：2022-06-02

正则表达式，这种写法说难其实也不是很难，就是有些小细节需要扣一下，比如IPV4这种写法，就比较麻烦

var validIPAddress = function (queryIP) {
    const ipv4 = /^((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)\.){3}(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)$/;
    const ipv6 = /^([\da-fA-F]{1,4}:){7}[\da-fA-F]{1,4}$/;
    return ipv4.test(queryIP) ? 'IPv4' : ipv6.test(queryIP) ? 'IPv6' : 'Neither';
};

下面这种用上了前瞻导言

(?=exp) 顺序肯定环视，表示所在位置右侧能够匹配exp
(?!exp) 顺序否定环视，表示所在位置右侧不能匹配exp

比如下面这个例子

下面匹配\W*(?=\.gif) 匹配 .gif 前面的字母

所以他这里解析的意思是，表示这段数字后面跟行尾符或者不在末尾的.。这个前言?!\.$其实获得是前面数字，所以后面还得再加个判断.，主要是防范这种情况1.1.1.1.。

var validIPAddress = queryIP =>
    queryIP.match(/^((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)($|(?!\.$)\.)){4}$/) ? "IPv4":
    queryIP.match(/^(([\da-fA-F]{1,4})($|(?!:$):)){8}$/) ? "IPv6" : "Neither";

1021 删除最外层的括号

时间：2022-06-02

计数方法，有点困难的说实话这个东西，主要是里面的三个顺序比较重要

var removeOuterParentheses = function (s) {
    let res = '',
        cnt = 0;
    for (let i of s) {
        if (i === ')') cnt--;
        if (cnt > 0) res += i;
        if (i === '(') cnt++;
    }
    return res;
};

或者用栈，其实也是一样的

var removeOuterParentheses = function (s) {
    let res = ''
    const stk = [];
    for (let i of s) {
        if (i === ')') stk.pop();
        if (stk.length) res += i;
        if (i === '(') stk.push(i);
    }
    return res;
};

829 连续整数求和

时间：2022-06-04

抄的，困难题，其实就是数学证明了但是我就是不会，嘿嘿嘿

var consecutiveNumbersSum = function (n) {
    let ans = 0;
    //条件②
    for (let k = 1; k * k < 2 * n; k++) {
        //条件①和条件③
        if (2 * n % k == 0 && (2 * n / k - k + 1) % 2 == 0) {
            ans++;
        }
    }
    return ans;
};

929 独特的电子邮件地址

时间：2022-06-04

简单倒是简单，不过还是用上了js的特性

var numUniqueEmails = function (emails) {
    const set = new Set();
    for (let email of emails) {
        const arr = email.split('@');
        let res = '';
        for (let i = 0; i < arr[0].length; i++) {
            if (arr[0][i] == '.') continue;
            if (arr[0][i] == '+') break;
            res += arr[0][i];
        }
        set.add(res + '@' + arr[1]);
    }
    return set.size;
};

官解比我更逆天，好吧

var numUniqueEmails = function(emails) {
    const emailSet = new Set();
    for (const email of emails) {
        const i = email.indexOf('@');
        let local = email.slice(0, i).split("+")[0]; // 去掉本地名第一个加号之后的部分
        local = local.replaceAll(".", ""); // 去掉本地名中所有的句点
        emailSet.add(local + email.slice(i));
    }
    return emailSet.size;
};

478 在圆内随机生成点

时间：2022-06-06

抄的，说实话也看不懂，考的是概率论

var Solution = function (radius, x_center, y_center) {
    this.xc = x_center;
    this.yc = y_center;
    this.r = radius;
};

Solution.prototype.randPoint = function () {
    while (true) {
        const x = Math.random() * (2 * this.r) - this.r;
        const y = Math.random() * (2 * this.r) - this.r;
        if (x * x + y * y <= this.r * this.r) {
            return [this.xc + x, this.yc + y];
        }
    }
};

面试 1604 井字游戏

时间：2022-06-06

朴素又非常的长，先判断对角线是否成立，再判断行列，然后再看看是否包括空格。

/**
 * @param {string[]} board
 * @return {string}
 */
var tictactoe = function (board) {
    const n = board.length;
    // 先检验对角线
    let tar = board[0][0];
    let flag = true;
    if (tar !== ' ') {
        for (let i = 0; i < n; i++) {
            if (tar != board[i][i]) {
                flag = false;
                break;
            }
        }
        if (flag) return tar;
    }
    tar = board[n - 1][0];
    flag = true;
    if (tar !== ' ') {
        for (let i = 0; i < n; i++) {
            if (tar != board[n - 1 - i][i]) {
                flag = false;
                break;
            }
        }
        if (flag) return tar;
    }
    // 横向和纵向
    for (let i = 0; i < n; i++) {
        const tar1 = board[i][0],
            tar2 = board[0][i];
        let flag1 = true,
            flag2 = true;
        if (tar1 === ' ') flag1 = false;
        if (tar2 === ' ') flag2 = false;

        for (let j = 0; j < n; j++) {
            if (tar1 != board[i][j]) flag1 = false;
            if (tar2 != board[j][i]) flag2 = false;
        }
        if (flag1) return tar1;
        if (flag2) return tar2;
    }
    // 然后判断是否存在空格
    for (let i = 0; i < n; i++) {
        if (board[i].includes(' ')) return 'Pending';
    }
    return 'Draw';
};

面试 1605 阶乘尾数

时间：2022-06-06

我就感觉应该是写过的，好像是找到五的倍数，但这次我还是没有写出来。感觉有点脑筋急转弯的样子，这种题目不应该是简单题啊。

var trailingZeroes = function(n) {
    let ans = 0;
    while (n !== 0) {
        n = Math.floor(n / 5);
        ans += n;
    }
    return ans;
};

面试 1606 最小差

时间：2022-06-06

虽然是简单题，还是小抄了一下

var smallestDifference = function (a, b) {
    a.sort((a, b) => a - b);
    b.sort((a, b) => a - b);
    let i = 0,
        j = 0;
    let res = Infinity;
    while (i < a.length && j < b.length) {
        res = Math.min(res, Math.abs(a[i] - b[j]));
        if (a[i] < b[j]) i++;
        else j++;
    }
    return res;
};

面试 1607 最大数值

时间：2022-06-06

这题其他方法都不够正宗，用上异或这种方法就比较正宗了，所以抄了这种解法。用到了js的无符号右移

其实就是一个思想，如果a>b，那么取k=1，否则取k=0，那么最终结果就是a*k + b * (k^1)。

那么这个k的取法，就是b-a取那个符号位，如果符号位是1，说明b-a<0即 b<a。

上面就是最基本的思路了，但是还需要考虑一个溢出的情况，这种是最蛋疼的。其他语言可以用long这种来解决，但js没有，我抄的思路是用数字的正负关系来解决，溢出就是最大的减去最小的容易溢出。

如果两个数字异号的话，就把之前的k给无效化，如果a的符号位为0，b符号位为1，那么就要a，所以k=1，反正同理，k=0，所以异号的时候k的值就是b的符号位，这样子就解决了溢出了问题。

var maximum = function (a, b) {
    // 先考虑没有溢出时的情况，计算 b - a 的最高位，依照题目所给提示 k = 1 时 a > b，即 b - a 为负
    let k = (b - a) >>> 31;
    // 再考虑 a b 异号的情况，此时无脑选是正号的数字
    let aSign = a >>> 31,
        bSign = b >>> 31;
    // diff = 0 时同号，diff = 1 时异号
    let diff = aSign ^ bSign;
    // 在异号，即 diff = 1 时，使之前算出的 k 无效，只考虑两个数字的正负关系
    k = (k & (diff ^ 1)) | (bSign & diff);
    return a * k + b * (k ^ 1);
};

875 爱吃香蕉的珂珂

时间：2022-06-07

没想到居然要用最暴力的解法，这我是没想到，居然没有高级的算法，就是不断试错呗，不过是用二分搜索而已。

var minEatingSpeed = function (piles, h) {
    let low = 1, high = Math.max(...piles);
    while (low < high) {
        const speed = Math.floor((high - low) / 2) + low;
        const time = piles.reduce((prev, curr) => prev + Math.ceil(curr / speed), 0);
        if (time <= h) high = speed;
        else low = speed + 1;
    }
    return high;
};

面试 1608 整数的英语表示

时间：2022-06-07

这道题虽然是困难题，但其实是细节题目，不过我依旧还是抄别人的，怎么写了600多道题目，还是依旧抄别人的题目呢，真是有点不行

var numberToWords = function (num) {
    const wordA = [
        '',
        'One',
        'Two',
        'Three',
        'Four',
        'Five',
        'Six',
        'Seven',
        'Eight',
        'Nine',
        'Ten',
        'Eleven',
        'Twelve',
        'Thirteen',
        'Fourteen',
        'Fifteen',
        'Sixteen',
        'Seventeen',
        'Eighteen',
        'Nineteen'
    ];
    const wordB = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety'];
    const threeToWord = (num) => {
        const res = [];
        if (num >= 100) {
            res.push(wordA[Math.floor(num / 100)], 'Hundred');
            num %= 100;
        }
        if (num >= 20) {
            res.push(wordB[Math.floor(num / 10)]);
            num %= 10;
        }
        if (num >= 1) {
            console.log(num, '????????,')
            res.push(wordA[num]);
        }
        return res.join(' ');
    };

    if (num == 0) return 'Zero';
    const res = [];
    if (num >= 1000000000) {
        res.push(threeToWord(Math.floor(num / 1000000000)), 'Billion');
        num %= 1000000000;
    }
    if (num >= 1000000) {
        res.push(threeToWord(Math.floor(num / 1000000)), 'Million');
        num %= 1000000;
    }
    if (num >= 1000) {
        res.push(threeToWord(Math.floor(num / 1000)), 'Thousand');
        num %= 1000;
    }
    if (num > 0) res.push(threeToWord(Math.floor(num)));
    return res.join(' ');
};

面试 1610 生存人数

时间：2022-06-07

很慢，我以为是已经排好序的，可惜不是。

var maxAliveYear = function (birth, death) {
    const map = new Map();
    for (let i of birth) {
        map.set(i, (map.get(i) || 0) + 1);
    }
    for (let i = 0; i < birth.length; i++) {
        for (let m of map) {
            if (birth[i] < m[0] && m[0] <= death[i]) map.set(m[0], m[1] + 1);
        }
    }
    let res = Infinity,
        max = 0;
    for (let m of map) {
        if (m[1] > max) {
            max = m[1];
            res = m[0];
        } else if (m[1] == max && m[0] < res) res = m[0]

    }
    return res;
};

抄的，用上了差分法，也就是这一年的人数是变多还是变少，然后遍历年份，那一年的人数就是curAlive

var maxAliveYear = function (birth, death) {
    const change = new Array(102).fill(0);
    for (let i = 0; i < birth.length; i++) {
        change[birth[i] - 1900]++;
        change[death[i] - 1899]--;
    }
    let maxAlive = 0,
        curAlive = 0,
        res = 1900;
    for (let i = 0; i < 101; i++) {
        curAlive += change[i];
        if (curAlive > maxAlive) {
            maxAlive = curAlive;
            res = 1900 + i;
        }
    }
    return res;
};

1037 有效的回旋镖

时间：2022-06-08

初中数学的水平，不过我并不会

var isBoomerang = function(points) {
    const v1 = [points[1][0] - points[0][0], points[1][1] - points[0][1]];
    const v2 = [points[2][0] - points[0][0], points[2][1] - points[0][1]];
    return v1[0] * v2[1] !== v1[1] * v2[0] ;
};

面试 1611 跳水板

时间：2022-06-08

数学题目，可惜我还是没做出来，不过我写的很漂亮哦

var divingBoard = function (shorter, longer, k) {
    if (k == 0) return [];
    if (shorter === longer) return [shorter * k];
    return new Array(k + 1).fill(0).map((_,i)=> (longer - shorter) * i + shorter * k)
};

面试 1613 平分正方形

恶心的模拟题，但是并不恶心我，因为我直接抄啊，抄完了然后改一下，优化一下，诶，速度又提升上去了

时间：2022-06-08

var cutSquares = function (square1, square2) {
    // 圆心坐标
    const x1 = square1[0] + square1[2] / 2,
        y1 = square1[1] + square1[2] / 2,
        x2 = square2[0] + square2[2] / 2,
        y2 = square2[1] + square2[2] / 2;
    if (x1 == x2) {
        // 垂直x轴，交点在上下边
        return [x1, Math.min(square1[1], square2[1]), x1, Math.max(square1[1] + square1[2], square2[1] + square2[2])];
    }
    // 有斜率的情况下
    const k = (y2 - y1) / (x2 - x1),
        b = y1 - k * x1;
    // 斜率的绝对值小于1，那么交点就在左右两边
    if (Math.abs(k) <= 1) {
        // 交点在左右边
        const xmin = Math.min(square1[0], square2[0]),
            xmax = Math.max(square1[0] + square1[2], square2[0] + square2[2]);
        return [xmin, k * xmin + b, xmax, k * xmax + b];
    }
    // 斜率的绝对值大于1，交点在上下两边
    const ymin = Math.min(square1[1], square2[1]),
        ymax = Math.max(square1[1] + square1[2], square2[1] + square2[2]),
        ans = [(ymin - b) / k, ymin, (ymax - b) / k, ymax];
    // 重排序，保证第一个点在左边，斜率为正和负，左边的点可能是上面和下面两种情况
    if (ans[0] < ans[2]) return ans;
    return [ans[2], ans[3], ans[0], ans[1]];
};

面试 1614 最佳直线

时间：2022-06-08

三重暴力循环，真有他的。

var bestLine = function (points) {
    const len = points.length;
    let max = 0;
    let ans = [];
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            let count = 2;
            for (let k = 0; k < len; k++) {
                if (k === i || k === j) continue;
                if ((points[j][0] - points[i][0]) * (points[k][1] - points[j][1]) === (points[j][1] - points[i][1]) * (points[k][0] - points[j][0])) {
                    count++;
                }
            }
            if (count > max) {
                max = count;
                ans = [i, j];
            }
        }
    }
    return ans;
};

497 非重叠矩形中的随机点

时间：2022-06-09

这波啊，这波是这波。用前缀和，累加面积，然后二分法随机抽选一个幸运值的面积，然后再在抽中的矩形中随机抽选一个幸运点，就ok了。

var Solution = function (rects) {
    this.rects = rects;
    this.sum = [0];
    for (const rect of rects) {
        const [x1, y1, x2, y2] = [...rect];
        this.sum.push(this.sum[this.sum.length - 1] + (x2 - x1 + 1) * (y2 - y1 + 1));
    }
};

/**
 * @return {number[]}
 */
Solution.prototype.pick = function () {
    let k = Math.floor(Math.random() * this.sum[this.sum.length - 1]);

    const rectIndex = binarySearch(this.sum, k + 1) - 1;
    k -= this.sum[rectIndex];
    const rect = this.rects[rectIndex];
    const [x1, y1, x2, y2] = [...rect];
    return [Math.floor(Math.random() * (x2 - x1 + 1) + x1), Math.floor(Math.random() * (y2 - y1 + 1) + y1)];
};

const binarySearch = (arr, target) => {
    let l = 0,
        r = arr.length - 1;
    while (l <= r) {
        const mid = (r + l) >> 1;
        const num = arr[mid];
        if (num === target) return mid;
        else if (num > target) r = mid - 1;
        else l = mid + 1;
    }
    return l;
};

面试 1615 珠玑妙算

时间：2022-06-09

这道题还挺难的，明明就这么简单的需求，但是写起来还是有点费劲的。

var masterMind = function (solution, guess) {
    const cnt = {
        R: 0,
        G: 0,
        B: 0,
        Y: 0
    };
    const res = [0, 0];
    for (let i = 0; i < 4; i++) {
        if (guess[i] == solution[i]) res[0]++;
        else {
            if (cnt[guess[i]]++ < 0) res[1]++;
            if (cnt[solution[i]]-- > 0) res[1]++;
        }
    }
    return res;
};

面试 1616 部分排序

时间：2022-06-09

ok，我先排个序然后再看哪里不符合排序不就行了

var subSort = function (array) {
    const arr = Array.from(array).sort((a, b) => a - b);
    let l = 0,
        r = arr.length - 1;
    while (l <= r) {
        if (arr[l] != array[l]) break;
        l++;
    }
    while (l <= r) {
        if (arr[r] != array[r]) break;
        r--;
    }
    if (l >= r) return [-1, -1];
    return [l, r];
};

抄的，就是去找那个突变点，比如找到未排序的最右边的端点，如果是已经排序好的，那么最大值就是当前值，而中间没有排序好的，当前值不是最大值，那么就把当前点当做右端点，大概就是这样子。

var subSort = function (array) {
    let r = -1, l = -1;
    //正向遍历记录最右区间值
    let max = Number.MIN_SAFE_INTEGER,
        min = Number.MAX_SAFE_INTEGER;
    const n = array.length - 1;
    for (let i = 0; i <=n; i++) {
        if (array[i] >= max) {
            max = array[i];
        } else {
            r = i;
        }
        if (array[n-i] <= min) {
            min = array[n-i]
        } else {
            l = n-i;
        }
    }
    return [l, r]
};

面试 1617 连续数列

时间：2022-06-09

写过，贪心就完事了

var maxSubArray = function (nums) {
    let max = -Infinity,
        cnt = 0;
    for (let num of nums) {
        if (cnt < 0) cnt = num;
        else cnt += num;
        if (cnt > max) max = cnt;
    }
    return max;
};

面试 1619 水域大小

时间：2022-06-10、

经典水面题目，这种题目我已经拿下了

var pondSizes = function (land) {
    const dirs = [
        [-1, -1],
        [-1, 0],
        [-1, 1],
        [0, -1],
        [0, 0],
        [0, 1],
        [1, -1],
        [1, 0],
        [1, 1]
    ],
        m = land.length,
        n = land[0].length,
        used = new Array(m).fill(0).map(() => new Array(n).fill(false));

    const dfs = (r, c) => {
        if (land[r][c] != 0 || used[r][c]) return 0;
        used[r][c] = true;
        let res = 1;
        for (let [row, col] of dirs) {
            const x = row + r,
                y = col + c;
            if (x >= 0 && x < m && y >= 0 && y < n && !used[x][y]) res += dfs(x, y);
        }
        return res;

    };
    const res = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let tmp = dfs(i, j);
            if (tmp > 0) res.push(tmp);
        }
    }
    res.sort((a, b) => a - b);
    return res;
};

面试 1620 T9键盘

时间：2022-06-10

又慢又拉，但是一次过也倒是还不错啦

var getValidT9Words = function (num, words) {
    const res = [];
    const obj = {
        a: 2,
        b: 2,
        c: 2,
        d: 3,
        e: 3,
        f: 3,
        g: 4,
        h: 4,
        i: 4,
        j: 5,
        k: 5,
        l: 5,
        m: 6,
        n: 6,
        o: 6,
        p: 7,
        q: 7,
        r: 7,
        s: 7,
        t: 8,
        u: 8,
        v: 8,
        w: 9,
        x: 9,
        y: 9,
        z: 9
    };
    for (let word of words) {
        let tmp = '';
        for (let w of word) {
            tmp += obj[w];
        }
        if (num === tmp) res.push(word);
    }
    return res;
};

面试 1621 交换和

时间：2022-06-10

朴素O(n2)，拉胯的一批

var findSwapValues = function (array1, array2) {
    const sum1 = array1.reduce((a, b) => a + b);
    const sum2 = array2.reduce((a, b) => a + b);
    let cha = sum1 - sum2;
    if (cha & 1) return [];
    cha = cha / 2;
    for (let i = 0; i < array1.length; i++) {
        const tmp = array1[i] - cha;
        if (array2.includes(tmp)) return [array1[i], tmp];
    }
    return [];
};

排序呗，速度快了很多

var findSwapValues = function (array1, array2) {
    const sum1 = array1.reduce((a, b) => a + b);
    const sum2 = array2.reduce((a, b) => a + b);
    let cha = sum1 - sum2;
    if (cha & 1) return [];
    cha /= 2;
    array1.sort((a, b) => a - b);
    array2.sort((a, b) => a - b);
    const m = array1.length,
        n = array2.length;
    let i = (j = 0);
    while (i < m && j < n) {
        const a = array1[i],
            b = array2[j];
        if (a - b === cha) return [a, b];
        if (a - b > cha) j++;
        else i++;
    }
    if (i === m) {
        const a = array1[m - 1];
        while (j < n) {
            if (a - array2[j] === cha) return [a, array2[j]];
            j++;
        }
    }
    if (j === n) {
        const b = array1[n - 1];
        while (i < m) {
            if (array1[i] - b === cha) return [array1[i], b];
            i++;
        }
    }
    return [];
};

没想到用set是最快的，直接秒杀

var findSwapValues = function (array1, array2) {
    const sum1 = array1.reduce((a, b) => a + b);
    const sum2 = array2.reduce((a, b) => a + b);
    let cha = sum1 - sum2;
    if (cha & 1) return [];
    cha = cha / 2;
    const set = new Set(array2);
    for (let i = 0; i < array1.length; i++) {
        const tmp = array1[i] - cha;
        if (set.has(tmp)) return [array1[i], tmp];
    }
    return [];
};

926 将字符串翻转到单调递增

时间：2022-06-11

用的动态规划，虽然我也不明白到底是不是应该这样子的，大概可能就是这样子吧，反正我也没想明白

var minFlipsMonoIncr = function (s) {
    const n = s.length;
    const dp = new Array(n + 1).fill(0).map(() => new Array(2).fill(0));
    for (let i = 0; i < n; i++) {
        if (s[i] == '0') {
            dp[i + 1][0] = dp[i][0];
            dp[i + 1][1] = Math.min(dp[i][0], dp[i][1]) + 1;
        } else {
            dp[i + 1][0] = dp[i][0] + 1;
            dp[i + 1][1] = Math.min(dp[i][0], dp[i][1]);
        }
    }
    return Math.min(dp[n][0], dp[n][1]);
};

面试 1622 兰顿蚂蚁

时间：2022-06-11

这道题就是非常经典的模拟题，但是我不会模拟，其实看了之后也非常顺畅，就是用一个set来保存黑色方块的位置，然后就是把那个图画出来，虽然思路很简单，但是实现应该有很多细节，所以我还是抄的。

class Position {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}
/**
 * @param {number} K
 * @return {string[]}
 */
var printKMoves = function (K) {
    const direction = ['L', 'U', 'R', 'D'];
    const offset = [
        [-1, 0],
        [0, -1],
        [1, 0],
        [0, 1]
    ];
    const antPos = new Position(0, 0);
    let antDir = 2;
    const blackSet = new Set();
    // 走一遍，记录黑块的位置
    while (K > 0) {
        const t = antPos.x + '&' + antPos.y;
        if (!blackSet.has(t)) {
            blackSet.add(t);
            antDir = (antDir + 1) % 4;
        } else {
            antDir = (antDir + 3) % 4;
            blackSet.delete(t);
        }
        antPos.x += offset[antDir][0];
        antPos.y += offset[antDir][1];
        K--;
    }
    let left = antPos.x;
    let top = antPos.y;
    let right = antPos.x;
    let bottom = antPos.y;
    // 找到边界
    for (const pos of blackSet) {
        const [x, y] = pos.split('&');
        left = Math.min(left, x);
        top = Math.min(top, y);
        right = Math.max(right, x);
        bottom = Math.max(bottom, y);
    }

    // 画图
    const grid = new Array(bottom - top + 1).fill(0).map(() =>  new Array(right - left + 1).fill('_'));
    for (const pos of blackSet) {
        const [x, y] = pos.split('&');
        grid[y - top][x - left] = 'X';
    }
    // 然后画小蚂蚁的位置
    grid[antPos.y - top][antPos.x - left] = direction[antDir];
    return grid.map((row) => row.join(''));
};

面试 1624 数对和

时间：2022-06-11

其实就是两数之和，简单的很

var pairSums = function (nums, target) {
    const map = new Map(),
        res = [];
    for (let num of nums) {
        const tar = target - num;
        if (map.has(tar)) {
            res.push([tar, num]);
            if (map.get(tar) === 1) map.delete(tar);
            else map.set(tar, map.get(tar) - 1);
        } else {
            map.set(num, (map.get(num) || 0) + 1);
        }
    }
    return res;
};

或者排序双指针，也简单

var pairSums = function (nums, target) {
    nums.sort((a, b) => a - b);
    const res = [];
    let l = 0,
        r = nums.length - 1;
    while (l < r) {
        if (nums[l] + nums[r] === target) {
            res.push([nums[l], nums[r]]);
            l++;
            r--;
        } else if (nums[l] + nums[r] < target) l++;
        else r--;
    }
    return res;
};

890 查找和替换模式

时间：2022-06-12

还是抄的，虽然比较简单好吧，现在已经抄习惯了，双射，两次都要一样才行

var findAndReplacePattern = function (words, pattern) {
    const res = [];
    for (let word of words) if (match(word, pattern) && match(pattern, word)) res.push(word);
    return res;
};

const match = (word, pattern) => {
    const map = new Map();
    for (let i = 0; i < word.length; i++) {
        const x = word[i],
            y = pattern[i];
        if (!map.has(x)) map.set(x, y);
        else if (map.get(x) != y) return false;
    }
    return true;
};

面试 1625 LRU 缓存

时间：2022-06-12

什么神仙Map的写法，直接利用map每次添加都是放到最后的特性，然后每次get的时候都删掉原来的部分，再重新添加到map中。然后put的时候如果达到上限，那么就用keys().next().value获得第一个key值，也就是使用率最低的那个key，这一手实在是太妙了，妙蛙种子都没有这么妙。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.cache = new Map();
    this.capacity = capacity;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    const cache = this.cache;
    if (cache.has(key)) {
        const value = cache.get(key);
        cache.delete(key);
        cache.set(key, value);
        return value;
    } else return -1;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    const cache = this.cache;
    if (cache.has(key)) cache.delete(key);
    if (cache.size == this.capacity) cache.delete(cache.keys().next().value);
    cache.set(key, value);
};

面试 1626 计算器

时间：2022-06-12

好，又快又好，抄的。即使是这个，我也没法实现，虽然我知道要用栈。这里用了一个非常巧妙的方法，用sign来记上一个运算符，这样子对应的就是运算符后面那个数字了，然后*/的优先级高，先处理了，+和-不处理，到最后的时候处理，一块累加，这种方法我铁是想不到的。

var calculate = function (s) {
    const stack = [];
    let num = 0,
        sign = '+';
    for (let i of s) {
        if (i === ' ') continue;
        if (i <= '9' && i >= '0') {
            num = num * 10 + parseInt(i);
            continue;
        }
        if (sign === '+') stack.push(num);
        else if (sign === '-') stack.push(-num);
        else if (sign === '*') stack.push(stack.pop() * num);
        else if (sign === '/') stack.push(Math.trunc(stack.pop() / num));
        sign = i;
        num = 0;
    }
    if (sign === '+') stack.push(num);
    else if (sign === '-') stack.push(-num);
    else if (sign === '*') stack.push(stack.pop() * num);
    else if (sign === '/') stack.push(Math.trunc(stack.pop() / num));
    return stack.reduce((a, b) => a + b, 0);
};