Leetcode-24

只能说随心一点刷题了好吧。

1108 IP 地址无效化

时间：2022-06-21

var defangIPaddr = function (address) {
    return address.replace(/\./g, '[.]');
};

508 出现次数最多的子树元素和

时间：2022-06-21

就这？

var findFrequentTreeSum = function (root) {
    const map = new Map();
    const dfs = (root) => {
        if (!root) return 0;
        const left = dfs(root.left);
        const right = dfs(root.right);
        const sum = left + right + root.val;
        map.set(sum, (map.get(sum) || 0) + 1);
        return sum;
    };
    dfs(root)
    let max = 0;
    for (let m of map.values()) max = Math.max(m, max);
    const res = [];
    for (let m of map) if (m[1] === max) res.push(m[0]);
    return res;
};

1089 复写零

时间：2022-06-21

一遍遍历过，先统计这个总长度就行了，

var duplicateZeros = function (arr) {
    const len = arr.length;
    let tmp = 0,
        i = 0;
    for (; i < len; i++) {
        if (arr[i] === 0) tmp++;
        tmp++;
        if (tmp >= len) break;
    }
    if (i == len) return arr;
    let j = len - 1;
    if (tmp > len) {
        arr[j] = 0;
        i--;
        j--;
    }
    while (j >= 0) {
        if (arr[i] == 0) arr[j--] = 0;
        arr[j--] = arr[i--];
    }
    return arr;
};

532 数组中的 k-diff 数对

时间：2022-06-21

写的复杂了点，但是不碍事，还行我只能说。

var findPairs = function (nums, k) {
    let res = 0;
    if (k == 0) {
        nums.sort((a, b) => a - b);
        let flag = true;
        for (let i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                if (flag) {
                    res++;
                    flag = false;
                }
                continue;
            }
            flag = true;
        }
        return res;
    }
    const set = new Set(nums);
    const arr = Array.from(set).sort((a, b) => a - b);
    for (let i of arr) {
        if (set.has(i + k)) res++;
    }
    return res;
};

面试 1712 BiNode

时间：2022-06-22

需要注意，把左指针变没这个操作是在root这层级，因为已经遍历完了root.left了，左子树全部遍历完了，所以在这里root.left变成null是合适的。

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

522 最长特殊序列 II

时间：2022-06-30

抄的，题目没看懂，大家都说题目有问题，那我就放心了。总结一句话就是找到数组中的某个字符串不是其他字符串的子序列，返回最长的长度就行了。

var findLUSlength = function (strs) {
    let res = -1;
    out:
    for (let [i, s] of strs.entries()) {
        if (s.length > res) {
            for (let [j, s_] of strs.entries()) {
                if (j != i && isSubStr(s, s_)) {
                    continue out;
                }
            }
            res = s.length;
        }
    }
    return res;
};
function isSubStr(s1, s2) {
    const m = s1.length,
        n = s2.length;
    if (m > n) return false;
    let i = 0;
    for (let j = 0; (i < m) & (j < n); j++) {
        if (s1[i] == s2[j]) i++;
    }
    return i == m;
}

324 摆动排序 II

时间：2022-06-30

抄的，没做出来，这个奇偶性有点恶心。要倒序插入，这谁能够猜到，还有还几种优化方法，太难了这道题。

var wiggleSort = function(nums) {
    const arr = nums.slice();
    arr.sort((a, b) => a - b);
    const n = nums.length;
    const x = Math.floor((n + 1) / 2);
    for (let i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
        nums[i] = arr[j];
        if (i + 1 < n) {
            nums[i + 1] = arr[k];
        }
    }
};

535 TinyURL 的加密与解密

时间：2022-06-30

抄的，就这？我以为有多难呢

var encode = function(longUrl) {
    this.dataBase = new Map();
    let key;
    while (true) {
        key = Math.floor(Math.random() * (Number.MAX_SAFE_INTEGER));
        if (!dataBase.has(key)) {
            break;
        }
    }
    this.dataBase.set(key, longUrl);
    return "http://tinyurl.com/" + key;
};

var decode = function(shortUrl) {
    const p = shortUrl.lastIndexOf('/') + 1;
    const key = parseInt(shortUrl.substring(p));
    return this.dataBase.get(key);
};

1175 质数排列

时间：2022-06-30

抄的，连抄四题，真有我的，先求出质数的个数，再算出质数的排列数和合数的排列数，两个再相乘。

const MOD = 1000000007;
var numPrimeArrangements = function (n) {
    let numPrimes = 0;
    // 先找出1-n的所有质数
    for (let i = 2; i <= n; i++) if (isPrime(i)) numPrimes++;
    // 然后组合，总的方案数即为「所有质数都放在质数索引上的方案数」×「所有合数都放在合数索引上的方案数」
    let res = 1;
    let m = n - numPrimes;
    while (numPrimes > 0) {
        res = res % MOD;
        res *= numPrimes;
        numPrimes--;
    }
    while (m > 0) {
        res = res % MOD;
        res *= m;
        m--;
    }
    return res;
};

const isPrime = (n) => {
    if (n === 1) return false;
    for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;
    return true;
};

241 为运算表达式设计优先级

时间：2022-07-01

抄的，经典的分治思想？反正我做不太出来，看起来比较简单，也确实还行吧，我只能说。主要有两点，一个是分开left和right，然后根据char，来处理left和right。还有一个就是只有一个值的返回值就是直接存。

这里还学到一个新的知识点，就是switch是比if快很多，如果为了性能，能用switch就用switch，比if快的很多。

const map = new Map(); // 表达式 -> 结果集
var diffWaysToCompute = function (expression) {
    if (map.has(expression)) return map.get(expression); // 直接返回
    const res = []; // 每个表达式对应的 结果集
    for (let i = 0; i < expression.length; i++) {
        const char = expression[i];
        if (char === '-' || char === '+' || char === '*') {
            // 分割 分而治之
            const lefts = diffWaysToCompute(expression.slice(0, i)); // slice包前不包后 返回0~i-1表达式的结果集
            const rights = diffWaysToCompute(expression.slice(i + 1)); // 返回i+1~最后表达式的结果集
            for (const left of lefts)
                for (const right of rights) {
                    switch (char) {
                        case '+':
                            res.push(left + right);
                            break;
                        case '-':
                            res.push(left - right);
                            break;
                        case '*':
                            res.push(left * right);
                            break;
                        default:
                            break;
                    }
                }
        }
    }
    if (!res.length) res.push(parseInt(expression)); // 直接存
    map.set(expression, res);
    return res;
};

31 下一个排列

时间：2022-07-04

为了下一道题做准备，这道题还是蛮难的，虽然解析看起来很简单，但其实还是比较难的，直接抄的，需要三步走。图形化想一想就行了，先找到从后往前的小高峰的左边数字，然后找到小高峰右边数字比左边大的，再交换，然后把右边降序的坡改成升序的坡。反正我是绝对想不到这种方法的。

var nextPermutation = function (nums) {
    //从后往前遍历找到相邻升序的数字
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    //从i到末尾找到比i大的数字交换
    let j = nums.length - 1;
    if (i >= 0) {
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    i++;
    j = nums.length - 1;
    // 然后reserve，i+1到末尾
    while (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
        j--;
    }
    return nums;
};

556 下一个更大元素 III

时间：2022-07-04

就是上面那道题目，不过就是那道题的解法，就是需要把数字变成数组

var nextGreaterElement = function (n) {
    const nums = [];
    while (n >= 1) {
        nums.push(n % 10);
        n = Math.floor(n / 10);
    }
    nums.reverse();
    //从后往前遍历找到相邻升序的数字
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    //从i到末尾找到比i大的数字交换
    let j = nums.length - 1;
    if (i >= 0) {
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
    } else return -1;
    i++;
    j = nums.length - 1;
    // 然后reserve，i+1到末尾
    while (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
        j--;
    }
    const res =Number.parseInt(nums.join(''));
    if(res>2147483647) return -1;
    return res;
};

1200 最小绝对差

时间：2022-07-04

就这？简单题确实重拳出击了朋友

var minimumAbsDifference = function (arr) {
    arr.sort((a, b) => a - b);
    let min = Infinity;
    for (let i = 0; i < arr.length - 1; i++) {
        const tmp = arr[i + 1] - arr[i];
        if (tmp < min) min = tmp;
    }
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i + 1] - arr[i] === min) res.push([arr[i], arr[i + 1]]);
    }
    return res;
};