LeetCode-14

开始二刷代码随想录，所以新的题目都是比较杂的题目，包含每日一题和往日的每日一题，以及随机的题目。

688 骑士在棋盘上的概率

时间：2022-02-17

没想到这个居然需要用到动态规划，可能路径规划的都需要用到动态规划吧，毕竟用到上一层的状态。

var knightProbability = function (n, k, row, col) {
    const dirs = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2]];
    const dp = new Array(k + 1).fill(0).map(() => new Array(n).fill(0).map(() => new Array(n).fill(0)));
    for (let step = 0; step <= k; step++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (step == 0) dp[0][i][j] = 1;
                else {
                    for (let dir of dirs) {
                        const ni = i - dir[0],
                            nj = j - dir[1];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][col];
};

2047 句子中的有效单词数

时间：2022-02-17

神级正则表达式，根本不会，这居然还是一道简单题，真有他的。

• 完整正则表达式：/^([,.!]|[a-z]+(-[a-z]+)?[,.!]?)$/
• 其中用 () 和 | 把正则中间部分分成两种情况，实际可以当成两个正则：/^[,.!]$/ 与 /^[a-z]+(-[a-z]+)?[,.!]?$/
• 要匹配完整的token：用 ^ 表示匹配到字符串起始位置，用 $ 表示匹配到字符串末尾
• token只有1个标点符号，即第一种情况 /^[,.!]$/，表示整个字符串是3个标点中任意1个
• token有字母的情况下，即第二种情况 /^[a-z]+(-[a-z]+)?[,.!]?$/，一定是1个或多个字母开头即 ^[a-z]+，后面可能有连字符 - 和字母即 (-[a-z]+)?，末尾可能有标点即 [,.!]?$

var countValidWords = function (sentence) {
    return sentence.split(' ').filter((w) => /^([,.!]|[a-z]+(-[a-z]+)?[,.!]?)$/.test(w)).length;
};

自己写一个匹配的，还是在知道了上述的正则表达式的规则后才写出来的，真是又臭又长

var countValidWords = function (sentence) {
    const arr = sentence.split(' ');
    let res = 0;
    for (let a of arr) {
        a = a.trim();
        if (a.length != 0) {
            res += valid(a);;
        }
    }
    return res;
};
const valid = (str) => {
    let code = 0;
    for (let i = 0; i < str.length; i++) {
        const s = str[i];
        if (i == 0) {
            // 情况1：字母打头
            if (s >= 'a' && s <= 'z') code = 1;
            // 情况2:标点符号打头
            else if (s == ',' || s == '!' || s == '.') {
                if (i == str.length - 1) return 1;
                else return 0;
            } else return 0;
        } else {
            if (code == 1) {
                if (s >= 'a' && s <= 'z') continue;
                // 情况3，有个连字符‘-’
                else if (s == '-') {
                    if (i == str.length - 1) return 0;
                    else code = 2;;
                }
                // 已经到了文字的末尾
                else if (s == ',' || s == '!' || s == '.') {
                    if (i == str.length - 1) return 1;
                    else return 0;
                } else return 0;
            } else if (code == 2) {
                if (s >= 'a' && s <= 'z') code = 3;
                else return 0;
            } else if (code == 3) {
                if (s >= 'a' && s <= 'z') continue;
                else if ((s == ',' || s == '!' || s == '.') && i == str.length - 1) {
                    return 1;
                } else return 0;
            }
        }
    }
    return 1;
};

2013 检测正方形

时间：2022-02-17

虽然逻辑很简单，但是比较细节，而且双重哈希表居然还有点麻烦，需要先检测一遍，然后在添加，这个就挺麻烦的，然后就是遍历哈希表，看看有没有符合条件的。

var DetectSquares = function () {
    this.cnt = new Map();
};

/**
 * @param {number[]} point
 * @return {void}
 */
DetectSquares.prototype.add = function (point) {
    const x = point[0],
        y = point[1];
    if (!this.cnt.has(x)) {
        this.cnt.set(x, new Map());
    }
    const xCnt = this.cnt.get(x);
    xCnt.set(y, (xCnt.get(y) || 0) + 1);
};

/**
 * @param {number[]} point
 * @return {number}
 */
DetectSquares.prototype.count = function (point) {
    let res = 0;
    let x = point[0], y = point[1];
    if (!this.cnt.has(x)) {
        return 0;
    }
    const xCnt = this.cnt.get(x);
    const entries = this.cnt.entries();
    for (const [row, rowCnt] of entries) {
        if (row !== x) {
            // 根据对称性，这里可以不用取绝对值
            let d = row - x;
            res += (rowCnt.get(y) || 0) * (xCnt.get(y + d) || 0) * (rowCnt.get(y + d) || 0);
            res += (rowCnt.get(y) || 0) * (xCnt.get(y - d) || 0) * (rowCnt.get(y - d) || 0);
        }
    }
    return res;
};

1791 找出星型图的中心节点

时间：2022-02-18

var findCenter = function (edges) {
    if (edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1]) return edges[0][0];
    else return edges[0][1];
};

1688 比赛中的配对次数

时间：2022-02-18

var numberOfMatches = function (n) {
    let res = 0;
    while (n > 1) {
        const tmp = Math.floor(n / 2);
        if (n & 1) n = 1 + tmp;
        else n = tmp;
        res += tmp;
    }
    return res;
};

219 存在重复元素 II

时间：2022-02-18

正常思路的模拟做法，拉胯时间

var containsNearbyDuplicate = function (nums, k) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < Math.min(i + k + 1, nums.length); j++) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
};

把上面第二个循环改一下，不是一个一个去找了，而是用set去找，事先存入k个元素，然后滑动窗口，这样子时间就会降维到O(n)

var containsNearbyDuplicate = function (nums, k) {
    const set = new Set();
    for (let i = 0; i < nums.length; i++) {
        if (i > k) {
            set.delete(nums[i - k - 1]);
        }
        if (set.has(nums[i])) {
            return true;
        }
        set.add(nums[i]);
    }
    return false;
};

717 1比特与2比特字符

时间：2022-02-20

以前居然错过一次，有点东西。

var isOneBitCharacter = function (bits) {
    let i = 0;
    let last = 1;
    while (i < bits.length) {
        if (bits[i] === 1) {
            i += 2;
            last = 2;
        } else {
            i += 1;
            last = 1;
        }
    }
    return last === 1 ? true : false;
};

969 煎饼排序

时间：2022-02-20

有点像选择排序了，从后往前遍历，找到一个最大值，然后通过两次翻转就能把最大值的数字排序到最后面

var pancakeSort = function (arr) {
    // n 为数组的长度
    const res = [];
    for (let n = arr.length; n > 1; n--) {
        let index = 0;
        for (let i = 1; i < n; i++) if (arr[i] >= arr[index]) index = i;
        if (index === n - 1) continue;
        reverse(arr, index);
        reverse(arr, n - 1);
        res.push(index + 1);
        res.push(n);
    }
    return res;
};

const reverse = (arr, end) => {
    for (let i = 0, j = end; i < j; i++, j--) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
};

143 重排链表

时间：2022-02-20

这道题真的是典中典了，一共需要三步，先用快慢节点寻找到中间的节点，再反转后半段链表，最后合并两个链表，每一个都是简单的难度，但是合在一起就比较有难度了，不亏是这个题目，还是字节的面试题目。

var reorderList = function (head) {
    let mid = middleNode(head);
    let last = reverseList(mid.next);
    mid.next = null;
    return mergeList(head, last);
};

const middleNode = function (head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

const reverseList = function (head) {
    let prev = null;
    let cur = head;
    while (cur != null) {
        const next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
};
const mergeList = function (head1, head2) {
    const head = head1;
    while (head2) {
        const next2 = head2.next;
        head2.next = head1.next;
        head1.next = head2;
        head1 = head2.next;
        head2 = next2;
    }
    return head;
};

917 仅仅反转字母

时间：2022-02-23

var reverseOnlyLetters = function (s) {
    const arr = s.split('');
    let i = 0,
        j = s.length - 1;
    let tmp;
    while (i < j) {
        if (!isZimu(arr[i])) {
            i++;
            continue;
        }
        if (!isZimu(arr[j])) {
            j--;
            continue;
        }
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++;
        j--;
    }
    return arr.join('');
};

const isZimu = (ch) => {
    if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) return true;
    else return false;
};

838 推多米诺

时间：2022-02-23

抄的，还有一种是队列的写法，但是因为js没有队列的完整实现，所以就没有考虑， 这种就是双指针模拟的方法了，分为LL、RR、LR和RL这四种情况，前两种都是一样的，LR这种就不用懂了，只用RL这种变化一下。

var pushDominoes = function (dominoes) {
    const arr = dominoes.split('');
    let l = -1,
        r = 0,
        n = dominoes.length ,
        left = 'L';
    while (r < n) {
        while (r < n && arr[r] == '.') {
            r++;
        }
        const right = r < n ? arr[r] : 'R';
        // LL和RR的情况
        if (left == right) {
            for (let i = l + 1; i < r; i++) {
                arr[i] = left;
            }
        }
        // LR的情况
        else if (left == 'R' && right == 'L') {
            let i = l + 1,
                j = r - 1;
            while (i < j) {
                arr[i++] = 'R';
                arr[j--] = 'L';
            }
        } //还有个else的情况，RL的情况，但这种情况就不用动了
        l = r;
        left = right;
        r = l + 1;
    }
    return arr.join('');
};

1985 找出数组中的第 K 大整数

时间：2022-02-23

按照一般的排序，最后一个还会超时，有点拉胯，所以要么写成这种形式

var kthLargestNumber = function (nums, k) {
    return nums.sort((a, b) => b.length - a.length || (b > a ? 1 : -1))[k - 1];
};

或者这种形式，转换成BigInt

var kthLargestNumber = function(nums, k) {
    nums = nums.map(item => BigInt(item));
    nums.sort((a,b) => Number(b - a));
    return String(nums[k - 1]);
};

1706 球会落何处

时间：2022-02-24

直接抄袭，模拟题，简简单单

var findBall = function (grid) {
    const n = grid[0].length;
    const res = new Array(n).fill(-1);
    for (let j = 0; j < n; j++) {
        let col = j;
        for (const row of grid) {
            const dir = row[col];
            col += dir;
            if (col < 0 || col == n || row[col] != dir) {
                col = -1;
                break;
            }
        }
        if (col >= 0) res[j] = col;
    }
    return res;
};

1910 删除一个字符串中所有出现的给定子字符串

时间：2022-02-24

直接使用自带的库完成

var removeOccurrences = function (s, part) {
    while (true) {
        const i = s.indexOf(part);
        if (i == -1) return s;
        s = s.slice(0, i) + s.slice(i + part.length);
    }
};

或者使用KMP，但是我依旧还是不会，拉胯的我。

1394 找出数组中的幸运数

时间：2022-02-24

var findLucky = function (arr) {
    const map = new Map();
    for (let a of arr) {
        map.set(a,(map.get(a) || 0) + 1);
    }
    let res=-1;
    for (let m of map) {
        if (m[0] == m[1]) res = Math.max(res,m[0])
    }
    return res;
};

537 复数乘法

时间：2022-02-25

中等题，但却是是简单题的简单题类型。

var complexNumberMultiply = function (num1, num2) {
    const a = num1.indexOf('+');
    const b = num1.indexOf('i');
    const shi1 = Number(num1.substring(0, a));
    const xu1 = Number(num1.substring(a + 1, b));
    const c = num2.indexOf('+');
    const d = num2.indexOf('i');
    const shi2 = Number(num2.substring(0, c));
    const xu2 = Number(num2.substring(c + 1, d));
    const res_shi = shi1 * shi2 - xu1 * xu2;
    const res_xu = shi1 * xu2 + shi2 * xu1;
    return res_shi + '+' + res_xu + 'i';
};

1979 找出数组的最大公约数

时间：2022-02-25

var findGCD = function (nums) {
    const max = Math.max(...nums);
    const min = Math.min(...nums);
    return gcd(max, min);
};

const gcd = (a, b) => {
    if (b === 0) return a;
    return gcd(b, a % b);
};

1013 将数组分成和相等的三个部分

时间：2022-02-25

var canThreePartsEqualSum = function (arr) {
    let sum = arr.reduce((a, b) => a + b, 0);
    if (sum % 3 != 0) return false;
    sum = Math.floor(sum / 3);
    let tmp = 0;
    let group = 0;
    for (let a of arr) {
        tmp += a;
         if (tmp == sum) {
            tmp = 0;
            group++;
            if(group==3) return true
        }
    }
    return false;
};

2075 解码斜向换位密码

时间：2022-02-25

var decodeCiphertext = function (encodedText, rows) {
    const n = encodedText.length;
    const col = Math.floor(n / rows);
    const arr = [];
    for (let i = 0; i < col; i++) {
        let r = 0;
        let c = i;
        while (r < rows && c < col) {
            arr.push(encodedText[r * col + c]);
            ++r;
            ++c;
        }
    }
    while (arr.length && arr[arr.length - 1] == ' ') arr.pop();
    return arr.join('');
};

offer 47 礼物的最大价值

时间：2022-02-25

简单动态规划

var maxValue = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
        }
    }
    return dp[m][n];
};

改成一维数组

var maxValue = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
        }
    }
    return dp[n];
};

2016 增量元素之间的最大差值

时间：2022-02-26

var maximumDifference = function (nums) {
    let min = Number.MAX_SAFE_INTEGER;
    let res = -1;
    for (let i of nums) {
        min = Math.min(i, min);
        res = Math.max(i - min, res);
    }
    if (res == 0) return -1;
    return res;
};

1046 最后一块石头的重量

时间：2022-02-26

这个需要最大堆来实现，所以又用到了C++；

class Solution {
   public:
    int lastStoneWeight(vector<int>& stones) {
        // 优先队列，也就是最大堆
        priority_queue<int> q;
        for (int s : stones) {
            q.push(s);
        }

        while (q.size() > 1) {
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            if (a > b) {
                q.push(a - b);
            }
        }
        return q.empty() ? 0 : q.top();
    }
};

1835 所有数对按位与结果的异或和

时间：2022-02-26

困难题，但是不是是在数学上的困难，所以相当于直接拿证明结果来写了。

var getXORSum = function (arr1, arr2) {
    let sum1 = 0;
    let sum2 = 0;
    for (const i of arr1) sum1 ^= i;
    for (const i of arr2) sum2 ^= i;
    return sum1 & sum2;
};

658 找到 K 个最接近的元素

时间：2022-02-26

O(n)的方法，虽然也是抄过来的，就是比较左边和右边哪个距离远，然后找近一点的。

var findClosestElements = function (arr, k, x) {
    let l = 0,
        r = arr.length - 1;
    while (r - l + 1 > k) {
        const l_dis = x - arr[l];
        const r_dis = arr[r] - x;
        if (r_dis >= l_dis) r--;
        else l++;
    }
    return arr.slice(l, r + 1);
};

RNM退钱，害我写了这么久，二分法+查找，出错了好几次，这个方法真不如上面那个方法，还是上面的简单

var findClosestElements = function (arr, k, x) {
    let index = find(arr, x);
    if(index>0 && x - arr[index-1] <= arr[index] - x)index--;
    if(index<arr.length-1 && x- arr[index] > arr[index+1] - x) index++

    let l = index-1;
    let r = index+1;
    while (r - l -1 < k) {
        if (l < 0) {
            r++;
            continue;
        }
        if (r >= arr.length) {
            l--;
            continue;
        }
        if (x - arr[l] <= arr[r] - x) l--;
        else r++;
    }
    return arr.slice(l+1, r);
};
const find = (arr, x) => {
    let l = 0,
        r = arr.length - 1;
    while (l < r) {
        const mid = Math.floor((r + l) / 2);
        if (arr[mid] > x) r = mid - 1;
        else if (arr[mid] == x) {
            return mid;
        } else l = mid + 1;
    }
    return l;
};

553 最优除法

时间：2022-02-27

var optimalDivision = function (nums) {
    if (nums.length == 1) return nums[0].toString();
    if (nums.length == 2) return nums.join('/');
    nums[1] = '(' + nums[1];
    nums[nums.length - 1] = nums[nums.length - 1] + ')';
    return nums.join('/');
};

1016 子串能表示从 1 到 N 数字的二进制串

时间：2022-02-27

var queryString = function (s, n) {
    for (let i = 1; i <= n; i++) {
        if (!s.includes(i.toString(2))) return false;
    }
    return true;
};

2001 可互换矩形的组数

时间：2022-02-27

哈希表+排列组合了属于是

var interchangeableRectangles = function (rectangles) {
    const map = new Map();
    for (let i = 0; i < rectangles.length; i++) {
        const tmp = rectangles[i][0] / rectangles[i][1];
        map.set(tmp, (map.get(tmp) || 0) + 1);
    }
    let res = 0;
    for (let ele of map) {
        res += (ele[1] * (ele[1] - 1)) / 2;
    }
    return res;
};

Offer 67 把字符串转换成整数

时间：2022-02-27

错了六次之后才成功，真有我的，烦死了就。

var strToInt = function (str) {
    let nege = 0;
    let num = 0;
    let firstEmpty = 0;
    for (let s of str) {
        if (s == ' ') {
            if (firstEmpty == 0) continue;
            else break;
        } else if (s == '-') {
            if (nege == 0 && firstEmpty == 0) {
                nege = -1;
                firstEmpty = 1;
                continue;
            } else break;
        } else if (s == '+' && firstEmpty == 0) {
            if (nege == 0) {
                nege = 1;
                firstEmpty = 1;
                continue;
            } else break;
        } else if (s <= '9' && s >= '0') {
            num *= 10;
            num += parseInt(s);
            firstEmpty = 1;
        } else {
            break;
        }
    }
    if (nege >= 0) return num > 2147483647 ? 2147483647 : num;
    else return -num < -2147483648 ? -2147483648 : -num;
};

1470 重新排列数组

时间：2022-02-27

正常的拉胯想法，空间O(n)的做法，但是要想上一个台阶，就是O(1)的空间法了。

var shuffle = function (nums, n) {
    const arr = Array.from(nums);
    let a = 0;
    let x = 0;
    let y = n;
    while (a < nums.length) {
        nums[a++] = arr[x++];
        nums[a++] = arr[y++];
    }
    return nums;
};

时间O(2n)，空间O(1)，用的方法就是题目给定的数字是1000以内的，所以一个数字的只占10个bit，所以往左10的bit都是空的，所以就往左边去存新的数字，最后再挪回来就行了，神级位运算。

var shuffle = function (nums, n) {
    let a = 0;
    let x = 0;
    let y = n;
    while (a < nums.length) {
        nums[a++] |= (nums[x++] & 0x3ff) << 10;
        nums[a++] |= nums[y++] <<10;
    }
    for (let i = 0; i < nums.length; i++) nums[i] = nums[i] >> 10;
    return nums;
};