LeetCode-15

继续二刷代码随想录，以及随机的题目。

1477 找两个和为目标值且不重叠的子数组

时间：2022-02-28

这个题真的有点难度，而且一开始看走眼了，没看到互不重叠的子数组了，我以为是不能重复相同的子数组，我就说这也太难了8，所以这个解法就是滑动窗口，记录符合的长度和开始下标，然后按照长度进行排序，再判断两个有没有重叠，大概就这样子，速度有点慢的。

var minSumOfLengths = function (arr, target) {
    let sum = 0;
    // 存入数组[长度，开始下标]
    const memo = [];
    let j = 0;

    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
        while (sum >= target) {
            if (sum == target) memo.push([i - j + 1, j]);
            sum -= arr[j++];
        }
    }
    let min = Infinity;
    memo.sort((a, b) => a[0] - b[0]);
    console.log(memo);
    for (let i = 0; i < memo.length - 1; i++) {
        for (let j = i + 1; j < memo.length; j++) {
            // 两个互不重叠的
            if (memo[i][1] < memo[j][1] && memo[i][1] + memo[i][0] > memo[j][1]) continue;
            if (memo[j][1] < memo[i][1] && memo[j][1] + memo[j][0] > memo[i][1]) continue;

            min = Math.min(min, memo[i][0] + memo[j][0]);
            break;
        }
    }
    return min === Infinity ? -1 : min;
};

还有一种动态规划的写法，这个就比较的抽象了，非常的抽象，dp记录到编号i 满足target的最短子数组的长度，那么res就是dp[i-len]的最短子数组和加上当前len的长度，反正就说的通，但感觉又有点怪怪的。

var minSumOfLengths = function (arr, target) {
    const n = arr.length;
    // d[i]表示到编号i（不包含i）的情况下满足target目标的最短子数组的长度
    const dp = new Array(n + 1).fill(Infinity);
    let res = Infinity;
    let j = 0,
        sum = 0;
    for (let i = 1; i <= n; i++) {
        sum += arr[i - 1];
        while (sum > target) sum -= arr[j++];
        if (sum === target) {
            const len = i - j;
            dp[i] = Math.min(len, dp[i - 1]);
            res = Math.min(res, dp[j] + len);
        } else {
            dp[i] = dp[i - 1];
        }
    }
    return res === Infinity ? -1 : res;
};

1185 一周中的第几天

时间：2022-02-28

这种题目就很操蛋，怎么能算在简单题里面呢，再怎么说应该算在中等题吧，虽然这道题我直接copy的

var dayOfTheWeek = function (day, month, year) {
    const week = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'];
    const monthDays = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30];
    /* 输入年份之前的年份的天数贡献 */
    let days = 365 * (year - 1971) + Math.floor((year - 1969) / 4);
    /* 输入年份中，输入月份之前的月份的天数贡献 */
    for (let i = 0; i < month - 1; ++i) {
        days += monthDays[i];
    }
    if ((year % 400 === 0 || (year % 4 === 0 && year % 100 !== 0)) && month >= 3) {
        days += 1;
    }
    /* 输入月份中的天数贡献 */
    days += day;
    return week[(days + 3) % 7];
};

offer II 12 左右两边子数组的和相等

时间：2022-02-28

var pivotIndex = function (nums) {
    let sum = nums.reduce((a, b) => a + b, 0);
    let tmp = 0;
    for (let i = 0; i < nums.length; i++) {
        const left = sum - nums[i];
        if ((left & 1) == 0 && tmp == Math.floor(left / 2)) return i;
        tmp += nums[i];
    }
    return -1;
};

1128 等价多米诺骨牌对的数量

时间：2022-02-28

虽然这道题是简单题，但是我居然没有直接想到最优解，我太烂了。我还想两次循环呢，没想到因为这道题目因为限制了数字大小在1-9之间，这个真的绝好吧。

var numEquivDominoPairs = function (dominoes) {
    const arr = new Array(100).fill(0);
    let res = 0;
    for (const d of dominoes) {
        const val = d[0] < d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
        res += arr[val];
        arr[val]++;
    }
    return res;
};

6 Z 字形变换

时间：2022-03-01

我tm直接模拟我tm，说简单也是蛮简单，说难也是有点难的，有点艹的

var convert = function (s, numRows) {
    const len = s.length;
    if (numRows == 1 || numRows >= len) return s;
    const t = numRows * 2 - 2;
    const res = [];
    // 每行开始
    for (let i = 0; i < numRows; i++) {
        // 每行的起始下标
        for (j = i; j < len; j += t) {
            res.push(s[j]);
            if (0 < i && i < numRows - 1) res.push(s[j + t - 2 * i]);
        }
    }
    return res.join('');
};

1848 到目标元素的最小距离

时间：2022-03-01

常规暴力

var getMinDistance = function (nums, target, start) {
    let res = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < nums.length; i++) if (nums[i] == target) res = Math.min(res,Math.abs(i - start));
    return res;
};

1685 有序数组中差绝对值之和

时间：2022-03-01

var getSumAbsoluteDifferences = function (nums) {
    const n = nums.length;
    let right = nums.reduce((a, b) => a + b, 0);
    const res = new Array(n).fill(0);
    let left = 0;
    for (let i = 0; i < n; i++) {
        right -= nums[i];
        res[i] += right - (n - i - 1) * nums[i];
        res[i] += i * nums[i] - left;
        left += nums[i];
    }
    return res;
};

648 单词替换

时间：2022-03-01

朴实无华的set集合

var replaceWords = function (dictionary, sentence) {
    const arr = sentence.split(' ');
    const set = new Set(dictionary);
    for (let i = 0; i < arr.length; i++) {
        for (let j = 1; j <= arr[i].length; j++) {
            if (set.has(arr[i].substring(0, j))) arr[i] = arr[i].substring(0, j);
        }
    }
    return arr.join(' ');
};

这里有个字典树，又好又快，好！。

class Trie {
    constructor() {
        this.dictionary = {};
    }

    insert(word) {
        let node = this.dictionary;

        for (const c of word) {
            if (!node[c]) node[c] = {};
            node = node[c];
        }
        node.isEnd = true;
        node.word = word;
    }

    search(word) {
        let node = this.dictionary;
        for (const c of word) {
            if (!node[c]) return word;
            else if (node[c]?.isEnd) return node[c].word;
            else node = node[c];
        }
        return word;
    }
}

const replaceWords = (dictionary, sentence) => {
    let trie = new Trie();
    for (const root of dictionary) trie.insert(root);
    return sentence
        .split(' ')
        .map((word) => trie.search(word))
        .join(' ');
};

还有个API调用法，这个startWith我还没用过呢，速度也还不错，整挺好的。

const replaceWords = (dictionary, sentence) => {
    const words = sentence.split(" ");
    const search = (word) => {
        for(const root of dictionary){
            if(word.startsWith(root)){
                word = root;
            }
        }
        return word;
    };
    return words.map(word => search(word)).join(" ");
};

415 字符串相加

时间：2022-03-02

为了下一道题题目做铺垫

var addStrings = function (num1, num2) {
    let n1 = num1.length - 1;
    let n2 = num2.length - 1;
    const arr = [];
    let add = 0;
    while (n1 >= 0 || n2 >= 0) {
        const x = n1 >= 0 ? num1[n1] - '0' : 0;
        const y = n2 >= 0 ? num2[n2] - '0' : 0;
        const res = x + y + add;
        arr.push(res % 10);
        add = Math.floor(res / 10);
        n1--;
        n2--;
    }
    if (add == 1) arr.push(1);
    return arr.reverse().join('');
};

43 字符串相乘

时间：2022-03-02

这道题就还行，算中等偏难一点点，问题不是很大。

var multiply = function (num1, num2) {
    if (num1 === '0' || num2 === '0') return '0';
    const m = num1.length;
    const n = num2.length;
    if (n < m) multiply(num2, num1);
    const arr = new Array(m + n).fill(0);
    let mul = 0;
    let x = 0,
        y = 0;
    for (let i = m - 1; i >= 0; i--) {
        mul = 0;
        y = num1[i] - '0';
        for (let j = n - 1; j >= 0; j--) {
            x = num2[j] - '0';
            const tmp = x * y + mul + arr[i + j + 1];
            arr[i + j + 1] = tmp % 10;
            mul = Math.floor(tmp / 10);
        }
        arr[i] = mul;
    }
    arr[0] = mul;
    if (arr[0] == 0) arr.shift();
    return arr.join('');
};

76 最小覆盖子串

时间：2022-03-02

困难题目，我只能说有、东西，滑动窗口，右边先找到能够满足的子串，左边再不断收窄看看能不能找到满足的子串，主要是这里判断会有点问题，他这里只判断数量，而不整个进行判断，节省了时间。

var minWindow = function (s, t) {
    const map = new Map();
    for (let i = 0; i < t.length; i++) map.set(t[i], (map.get(t[i]) || 0) + 1);
    let i = 0,
        j = 0;
    let window = {};
    let num = 0,
        res = '',
        length = Number.MAX_SAFE_INTEGER;
    while (j < s.length) {
        let ch = s[j];
        if (map.has(ch)) {
            window[ch] = (window[ch] || 0) + 1;
            if (map.get(ch) == window[ch]) num++;
        }
        while (num == map.size) {
            let c = s[i];
            if (map.has(c)) {
                if (length > j - i + 1) {
                    res = s.substring(i, j + 1);
                    length = j - i + 1;
                }
                window[c]--;
                if (window[c] < map.get(c)) num--;
            }
            i++;
        }
        j++;
    }
    return res;
};

258 各位相加

时间：2022-03-03

简单题简单写，但是还有个O(1)的数学方法，玩不来。

var addDigits = function (num) {
    while (num >= 10) {
        let sum = 0;
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
        num = sum;
    }
    return num;
};

576 出界的路径数

时间：2022-03-03

动态规划，也可以不降维，因为看似降维了，但其实是没有的，反而还增加了垃圾回收的次数，所以不建议。

var findPaths = function (m, n, maxMove, startRow, startColumn) {
    // dp 表示移动到当前坐标的所有路径数量和
    const dp = new Array(maxMove + 1).fill(0).map(() => new Array(m).fill(0).map(() => new Array(n).fill(0)));
    let res = 0;
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    dp[0][startRow][startColumn] = 1;
    const mod = 10 ** 9 + 7;
    for (let i = 1; i <= maxMove; i++) {
        for (let j = 0; j < m; j++) {
            for (let k = 0; k < n; k++) {
                for (let dir of dirs) {
                    const x = dir[0] + j;
                    const y = dir[1] + k;
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        dp[i][j][k] += dp[i - 1][x][y];
                        dp[i][j][k] %= mod;
                    } else {
                        res += dp[i - 1][j][k];
                        res %= mod;
                    }
                }
            }
        }
    }
    return res;
};

2140 解决智力问题

时间：2022-03-03

动态规划，不过要从右到左这样子规划，所以有点绕

var mostPoints = function (questions) {
    // dp为当前获得最多的分数
    const n = questions.length;
    const dp = new Array(n + 1).fill(0);

    for (let i = n - 1; i >= 0; i--) {
        if (i + questions[i][1] < n) {
            dp[i] = Math.max(dp[i + 1], dp[i + questions[i][1] + 1] + questions[i][0]);
        } else {
            dp[i] = Math.max(dp[i + 1], questions[i][0]);
        }
    }
    return dp[0];
};

2104 子数组范围和

时间：2022-03-04

太废物了，我连O(n2)的方法都写不出来，确实有点拉胯了，这个真的是有点真的是了。

var subArrayRanges = function (nums) {
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        let minVal = Number.MAX_VALUE,
            maxVal = -Number.MAX_VALUE;
        for (let j = i; j < nums.length; j++) {
            minVal = Math.min(minVal, nums[j]);
            maxVal = Math.max(maxVal, nums[j]);
            res += maxVal - minVal;
        }
    }
    return res;
};

1856 子数组最小乘积的最大值

时间：2022-03-04

佛了，这尼玛什么神仙解法，两个单调栈+前缀和。前缀和就是从[0,i-1]的和，然后下个就是[0,i-1]+nums[i]的和，相当于递增的和，这个倒是很好理解。

单调栈就是那个样子，这个题就是求出左边和右边都比这个数字小的位置，然后左开右开(left,right)，这个子数组，这个数字就是最小的，然后右边的前缀和减去左边的前缀和，就是子数组的和了。

思路倒是还挺开阔的，但是代码能力太差了，实属有点难了。

var maxSumMinProduct = function (nums) {
    const len = nums.length;

    // 前缀和
    const sum = new Array(len + 1).fill(0);
    for (let i = 1; i <= len; i++) {
        sum[i] = sum[i - 1] + nums[i - 1];
    }
    console.log(sum);
    // 使用单调栈求解出左侧第个严格小于该数的元素位置，和右侧第一个严格小于该数的元素的位置
    let stack = [];
    const right = new Array(len).fill(len);
    for (let i = 0; i < len; i++) {
        while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
            right[stack[stack.length - 1]] = i;
            stack.pop();
        }
        stack.push(i);
    }
    stack = [];
    const left = new Array(len).fill(-1);
    for (let j = len - 1; j >= 0; j--) {
        while (stack.length && nums[stack[stack.length - 1]] > nums[j]) {
            left[stack[stack.length - 1]] = j;
            stack.pop();
        }
        stack.push(j);
    }
    // 根据前缀和和left， right数组进行枚举求解
    let max = BigInt(0);
    for (let k = 0; k < len; k++) {
        const total = BigInt(sum[right[k]] - sum[left[k] + 1]) * BigInt(nums[k]);
        if (max < total) {
            max = total;
        }
    }
    return max % BigInt(1000000007);
};

2108 找出数组中的第一个回文字符串

时间：2022-03-04

var firstPalindrome = function (words) {
    for (let i of words) {
        if (isPalindrome(i)) return i;
    }
    return ""
};
function isPalindrome(word) {
    let i = 0,
        j = word.length - 1;
    while (i < j) {
        if (word[i++] != word[j--]) return false;
    }
    return true;
}

521 最长特殊序列 I

时间：2022-03-05

略草，我以为我没看出来，结果我已经看出来了。

var findLUSlength = function (a, b) {
    return a !== b ? Math.max(a.length, b.length) : -1;
};

1780 判断一个数字是否可以表示成三的幂的和

时间：2022-03-05

这个题目也略草，虽然我没想到，转换成三进制。

var checkPowersOfThree = function (n) {
    while (n > 0) {
        if (n % 3 == 2) return false;
        n = Math.floor(n / 3);
    }
    return true;
};

1503 所有蚂蚁掉下来前的最后一刻

时间：2022-03-05

又是脑筋急转弯，怎么回事，随机一题都是一样的？

var getLastMoment = function (n, left, right) {
    return Math.max(Math.max(...left),n-Math.min(...right));
};

1436 旅行终点站

时间：2022-03-05

过于简单

var destCity = function (paths) {
    const map = new Map();
    for (let p of paths) {
        map.set(p[0], (map.get(p[0]) || 0) + 2);
        map.set(p[1], (map.get(p[1]) || 0) + 1);
    }
    for (let m of map) {
        if (m[1] == 1) return m[0];
    }
};

1287 有序数组中出现次数超过25%的元素

时间：2022-03-05

var findSpecialInteger = function (arr) {
    const n = Math.floor(arr.length / 4);
    let cnt = 1;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i - 1]) {
            cnt++;
            if (cnt > n) return arr[i];
        } else cnt = 1;
    }
    return arr[0]
};

1401 圆和矩形是否有重叠

时间：2022-03-05

这个题目看起来蛮简单的，但是实现起来还是蛮复杂的，我不一定能够做出来。

var checkOverlap = function (radius, xCenter, yCenter, x1, y1, x2, y2) {
    // 在矩形中间
    if (xCenter >= x1 && xCenter <= x2 && yCenter <= y2 && yCenter >= y1) return true;
    // 在上下左右
    if (xCenter >= x1 && xCenter <= x2 && yCenter > y2) return yCenter - y2 <= radius;
    if (xCenter >= x1 && xCenter <= x2 && yCenter < y1) return y1 - yCenter <= radius;
    if (yCenter <= y2 && yCenter >= y1 && xCenter < x1) return  x1- xCenter <= radius;
    if (yCenter <= y2 && yCenter >= y1 && xCenter > x2) return xCenter - x2 <= radius;
    // 在四个角落
    const x0 = Math.floor((x1 + x2) / 2),
        y0 = Math.floor((y1 + y2) / 2);
    const p = [Math.abs(xCenter - x0), Math.abs(yCenter - y0)];
    const q = [x2 - x0, y2 - y0];
    const u = [p[0] - q[0], p[1] - q[1]];
    return u[0] ** 2 + u[1] ** 2 <= radius ** 2;
};

6016 Excel 表中某个范围内的单元格

时间：2022-03-06

尝试打一下周赛，虽然没有正式参加，但也算一种尝试了。

这道简单题简单，不过也浪费了我一些时间

var cellsInRange = function (s) {
    const res = [];
    let xStart = s[0].charCodeAt() - 65;
    let xEnd = s[3].charCodeAt() - 65;
    let yStart = Number.parseInt(s[1]);
    let yEnd = Number.parseInt(s[4]);
    for (let i = xStart; i <= xEnd; i++) {
        for (let j = yStart; j <= yEnd; j++) {
            res.push(String.fromCharCode(i + 65) + j.toString());
        }
    }
    return res;
};

6017 向数组中追加 K 个整数

时间：2022-03-06

这道题JS过不去，BigInt都不行，有点拉胯

var minimalKSum = function (nums, k) {
    nums.sort((a, b) => a - b);
    nums.unshift(0);
    let res = 0;
    for (let i = 1; i < nums.length; i++) {
        const cnt = nums[i] - nums[i - 1] - 1;
        if (cnt <= 0) continue;
        const min = Math.min(cnt, k);
        res += Math.floor((min * (nums[i] + 1 + nums[i - 1] - 1)) / 2);
        k -= min;
        if (k == 0) return res;
    }
    let j = nums[nums.length - 1] + 1;
    res = BigInt(res) + BigInt(Math.floor((k * (j + j + k - 1)) / 2));
    return res;
};

6018 根据描述创建二叉树

时间：2022-03-06

这道题搞不来，我知道要用哈希表和map表，但是，唉，就是没有搞出来，有点拉了兄弟。

var createBinaryTree = function (descriptions) {
    const map = new Map();
    const set = new Set();
    for (let des of descriptions) {
        let parent;
        if (map.has(des[0])) parent = map.get(des[0]);
        else {
            parent = new TreeNode(des[0]);
            map.set(des[0], parent);
        }
        let child;
        if (map.has(des[1])) child = map.get(des[1]);
        else {
            child = new TreeNode(des[1]);
            map.set(des[1], child);
        }
        set.add(des[1]);
        if (des[2] == 1) parent.left = child;
        else parent.right = child;
    }
    for (let m of map) {
        if (!set.has(m[1].val)) {
            return m[1];
        }
    }
    return null;
};

6019 替换数组中的非互质数

时间：2022-03-06

这道题配不上困难，虽然我还是没有一开始做对，还是看了一下题解，但这道题就是用栈弄一下就行了，算不上多难。

var replaceNonCoprimes = function (nums) {
    let st = [nums[0]];
    for (let i = 1; i < nums.length; i++) {
        st.push(nums[i]);
        while (st.length > 1) {
            const res = gcd(st[st.length - 1], st[st.length - 2]);
            if (res !== 1) {
                st.push(Math.floor((st.pop() * st.pop()) / res));
            } else break;
        }
    }
    return st;
};
function gcd(a, b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

1402 做菜顺序

时间：2022-03-07

相当的难，虽然看起来很简单，但是想法却很难。首先从大到小排序，然后计算它的前缀和，再将前缀和累加，如果前缀和小于0，那么就break，因为再加进去肯定是会使值变小。

var maxSatisfaction = function (satisfaction) {
    satisfaction.sort((a, b) => b - a);
    let res = 0;
    let presum = 0;
    for (let i of satisfaction) {
        if (presum + i >= 0) {
            presum += i;
            res += presum;
        } else break;
    }
    return res;
};

504 七进制数

时间：2022-03-07

和两年前的错误一模一样，就是没有考虑0，真有我的。

var convertToBase7 = function (num) {
    if (num == 0) return '0';
    const arr = [];
    let flag = 1;
    if (num < 0) {
        num = -num;
        flag = -1;
    }

    while (num > 0) {
        arr.push(num % 7);
        num = Math.floor(num / 7);
    }
    if (flag < 0) arr.push('-');
    return arr.reverse().join('');
};

1409 查询带键的排列

时间：2022-03-07

就嗯模拟就行了。

var processQueries = function (queries, m) {
    const arr = new Array(m).fill(0).map((value, index) => (value = index + 1));
    const res = [];
    for (let q of queries) {
        const index = arr.indexOf(q);
        for (let i = index - 1; i >= 0; i--) {
            arr[i + 1] = arr[i];
        }
        arr[0] = q;
        res.push(index);
    }
    return res;
};