LeetCode-9

54 螺旋矩阵

刷题时间：2021-12-03

直接抄以前抄过来的想法，一路抄袭，不亏是我。

var spiralOrder = function (matrix) {
    const m = matrix.length,
        n = matrix[0].length;
    const res = [];
    let up = 0,
        down = m - 1,
        left = 0,
        right = n - 1;
    while (true) {
        for (let j = left; j <= right; j++) res.push(matrix[up][j]);
        if (++up > down) break;
        for (let i = up; i <= down; i++) res.push(matrix[i][right]);
        if (--right < left) break;
        for (let j = right; j >= left; j--) res.push(matrix[down][j]);
        if (--down < up) break;
        for (let i = down; i >= up; i--) res.push(matrix[i][left]);
        if (++left > right) break;
    }
    return res;
};

但上面这种方法不是正常的思路，看起来很厉害，但是我想不到，就很尿，需要用自己的思维那种。

不过下面也是抄袭的，嘿嘿，抄的好理解一点，转圈圈就是。

var spiralOrder = function (matrix) {
    const result = [];
    let left = 0;
    let right = matrix[0].length - 1;
    let top = 0;
    let bottom = matrix.length - 1;
    let numEle = matrix.length * matrix[0].length;
    while (numEle >= 1) {
        for (let i = left; i <= right && numEle >= 1; i++) {
            result.push(matrix[top][i]);
            numEle--;
        }
        top++;
        for (let i = top; i <= bottom && numEle >= 1; i++) {
            result.push(matrix[i][right]);
            numEle--;
        }
        right--;
        for (let i = right; i >= left && numEle >= 1; i--) {
            result.push(matrix[bottom][i]);
            numEle--;
        }
        bottom--;
        for (let i = bottom; i >= top && numEle >= 1; i--) {
            result.push(matrix[i][left]);
            numEle--;
        }
        left++;
    }
    return result;
};

59 螺旋矩阵 II

刷题时间：2021-12-03

这个是每个位置都左闭右开，算我我能想出来，但是写起来可能有点麻烦的。

var generateMatrix = function (n) {
    let startX = 0,
        startY = 0; // 起始位置
    let loop = Math.floor(n / 2); // 旋转圈数
    let mid = Math.floor(n / 2); // 中间位置
    let offset = 1; // 控制每一层填充元素个数
    let count = 1; // 更新填充数字
    const res = new Array(n).fill(new Array(n).fill(0));

    while (loop--) {
        let row = startX,
            col = startY;
        // 上行从左到右（左闭右开）
        for (; col < startY + n - offset; col++) {
            res[row][col] = count++;
        }
        // 右列从上到下（左闭右开）
        for (; row < startX + n - offset; row++) {
            res[row][col] = count++;
        }
        // 下行从右到左（左闭右开）
        for (; col > startX; col--) {
            res[row][col] = count++;
        }
        // 左列做下到上（左闭右开）
        for (; row > startY; row--) {
            res[row][col] = count++;
        }

        // 更新起始位置
        startX++;
        startY++;

        // 更新offset
        offset += 2;
    }
    // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
    if (n % 2 === 1) {
        res[mid][mid] = count;
    }
    return res;
};

下面这个优雅了，非常的简单，很喜欢这个方法

var generateMatrix = function (n) {
    const res = new Array(n).fill(0).map(() => new Array(n).fill(0));

    let up = 0,
        down = n - 1,
        left = 0,
        right = n - 1,
        index = 1;
    while (index <= n * n) {
        for (let i = left; i <= right; i++) {
            res[up][i] = index++;
        }
        up++;
        for (let i = up; i <= down; i++) {
            res[i][right] = index++;
        }
        right--;
        for (let i = right; i >= left; i--) {
            res[down][i] = index++;
        }
        down--;
        for (let i = down; i >= up; i--) {
            res[i][left] = index++;
        }
        left++;
    }
    return res;
};

707 设计链表

刷题时间：2021-12-04

非常完美的解决方案啊，纯自己手敲的，就是有点麻烦。老是漏一个_。

class LinkNode {
    constructor(val, next) {
        this.val = val;
        this.next = next === undefined ? null : next;
    }
}

var MyLinkedList = function () {
    this._size = 0;
    this._tail = null;
    this._head = null;
};

/**
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
    if (index < 0 || index >= this._size) {
        return -1;
    }
    if (index == this._size - 1) return this._tail.val;
    let cur = this._head;
    for (let i = 0; i < index; i++) {
        cur = cur.next;
    }
    return cur.val;
};

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
    if (this._size == 0) {
        this._head = new LinkNode(val, null);
        this._tail = this._head;
    } else {
        const prev = new LinkNode(val, this._head);
        this._head = prev;
    }
    this._size++;
};

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
    if (this._size == 0) {
        this._head = new LinkNode(val, null);
        this._tail = this._head;
    } else {
        this._tail.next = new LinkNode(val, null);
        this._tail = this._tail.next;
    }
    this._size++;
};

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
    if (index <= 0) {
        this.addAtHead(val);
    } else if (index == this._size) {
        this.addAtTail(val);
    } else if (index < this._size) {
        let cur = this._head;
        for (let i = 1; i < index; i++) {
            cur = cur.next;
        }
        let tmp = new LinkNode(val, cur.next);
        cur.next = tmp;
        this._size++;
    }
};

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
    if (index < 0 || index >= this._size) {
        return;
    }
    let prev = new LinkNode(-1, this._head);
    for (let i = 0; i < index; i++) {
        prev = prev.next;
    }
    prev.next = prev.next.next;

    if (index == 0) this._head = prev.next;
    if (index == this._size - 1) this._tail = prev;

    this._size--;
};

MyLinkedList.prototype.out = function () {
    let cur = this._head;
    const res = [];
    while (cur) {
        res.push(cur.val);
        cur = cur.next;
    }
};

24 两两交换链表中的节点

刷题时间：2021-12-04

看图写代码

var swapPairs = function (head) {
    let prev = new ListNode(-1, head);
    let curr = prev;
    while (curr.next && curr.next.next) {
        const tmp = curr.next;
        const tmp2 = curr.next.next.next;

        curr.next = curr.next.next;
        curr.next.next = tmp;
        curr = tmp;
        curr.next = tmp2;
    }
    return prev.next;
};

这居然也有递归，时间和空间都快一点。不过这个很难理解，我肯定写不出来，尿了。

var swapPairs = function(head) {
    if (head === null|| head.next === null) {
        return head;
    }
    const newHead = head.next;
    head.next = swapPairs(newHead.next);
    newHead.next = head;
    return newHead;
};

50 Pow(x, n)

刷题时间：2021-12-05

做372的前提知识，需要做这道题。先学一下方法

快速幂+递归，就是每次都/2，然后计算值，时间是O(logn)，空间也是log(n)

var myPow = function (x, n) {
    function quickMul(x, N) {
        if (N == 0) {
            return 1.0;
        }
        const y = quickMul(x, Math.floor(N / 2));
        return N % 2 == 0 ? y * y : y * y * x;
    }
    return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -n);
};

快速幂+递归，方法非常的妙啊，就是找规律，总结来说就是x的指数相乘，而这些指数就对应了二进制位置的1

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

372 超级次方

刷题时间：2021-12-05

抄袭三叶姐的P2做法，没用上快速幂的思想，公式具体看文章，里面pow还有取余的做法，应该是用上这个交换律，( a ⋅ b ) mod m = [( a mod m )⋅( b mod m )] mod m

var superPow = function (a, b) {
    const MOD = 1337;

    const dfs = (a, b, u) => {
        if (u == -1) return 1;
        return (pow(dfs(a, b, u - 1), 10) * pow(a, b[u])) % MOD;
    };
    
    const pow = (a, b) => {
        ans = 1;
        // 这里每次都使用MOD，我猜想是为了降低数字大小，否则会无限膨胀，用上交换律
        a %= MOD;
        while (b-- > 0) ans = (ans * a) % MOD;
        return ans;
    };
    return dfs(a, b, b.length - 1);
};

160 相交链表

刷题时间：2021-12-05

好家伙，我直接抄以前的，这个真的绝了，其实相当于A拼接B和B拼接A，这样子两者的长度肯定相同，所以末尾就会有重合的，直接O(m+n)

var getIntersectionNode = function (headA, headB) {
    if (!headA || !headB) return null;
    let curA = headA,
        curB = headB;
    while (curA != curB) {
        curA = curA ? curA.next : headB;
        curB = curB ? curB.next : headA;
    }
    return curA;
};

但正常的肯定不是这么写的，这才是正常的思路好吧，先求两个长度，然后最长的减去长度差，就是一样的长度，再判断是不是相同就行了

var getIntersectionNode = function (headA, headB) {
    let a = headA,
        b = headB;
    let la = 0,
        lb = 0;
    while (a) {
        la++;
        a = a.next;
    }
    while (b) {
        lb++;
        b = b.next;
    }
    if (lb > la) {
        let tmp = headA;
        headA = headB;
        headB = tmp;
        tmp = la;
        la = lb;
        lb = tmp;
    }
    (a = headA), (b = headB);
    let len = la - lb;
    while (len--) {
        a = a.next;
    }
    while (a != b) {
        a = a.next;
        b = b.next;
    }
    return a;
};

142 环形链表

刷题时间：2021-12-05

靠，这题还挺难的，得看详解，意思就是一旦找到了那个slow和fast相同的点，那么再次碰到相遇的点就是入口的长度。也算是需要公式推导才能行。

var detectCycle = function (head) {
    let fast = head;
    let slow = head;

    while (fast != null && fast.next != null) {
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
        if (slow == fast) {
            let index1 = fast;
            let index2 = head;
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index2; // 返回环的入口
        }
    }
    return null;
};

1816 截断句子

刷题时间：2021-12-06

时间居然非常的拉胯，想不明白了

var truncateSentence = function (s, k) {
    const arr = s.split(' ');
    arr.length = k;
    return arr.join(' ');
};

或者直接一句话，这个快一点，但是内存消耗大了

var truncateSentence = function (s, k) {
    return s.split(' ').slice(0, k).join(' ');
};

18 四数之和

刷题时间：2021-12-06

我tm直接抄袭。

var fourSum = function (nums, target) {
    const res = [];
    const length = nums.length;
    if (length < 4) {
        return res;
    }
    nums.sort((x, y) => x - y);
    // 一重循环，取第一个
    for (let i = 0; i < length - 3; i++) {
        //这里剪枝去重
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        // 终止，如果四个数加起来已经大于target，那么说明后面的数字依旧是大于target，直接停止。
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        // 剪枝，如果第一个数字加上最后三个数字还是小于target，那么后面的数字怎么取都没有意义，直接剪枝
        if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
            continue;
        }
        // 二重循环，取第二个
        for (let j = i + 1; j < length - 2; j++) {
            //这里也需要剪枝去重
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            // 终止，如果四个数加起来已经大于target，那么说明后面的数字依旧是大于target，直接停止这二重循环
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            //同理
            if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            let left = j + 1,
                right = length - 1;
            // 接下来就是两数之和了
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    res.push([nums[i], nums[j], nums[left], nums[right]]);
                    // 相等的情况下，去重
                    while (left < right && nums[left] === nums[left + 1]) {
                        left++;
                    }
                    left++;
                    // 去重
                    while (left < right && nums[right] === nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return res;
};

454 四数相加 II

刷题时间：2021-12-06

直接参考代码随想录的思想，前两个作为一个数，后两个作为一个数，相当于两数之和了。

var fourSumCount = function (nums1, nums2, nums3, nums4) {
    const map = new Map();
    for (let i of nums1) {
        for (let j of nums2) {
            map.set(i + j, (map.get(i + j) || 0) + 1);
        }
    }
    let cnt = 0;
    for (let i of nums3) {
        for (let j of nums4) {
            if (map.has(-i - j)) {
                cnt += map.get(-i - j);
            }
        }
    }
    return cnt;
};

794 有效的井字游戏

刷题时间：2021-12-09

没写，直接抄的题解，细节我肯定把握不住。

var validTicTacToe = function (board) {
    let xCount = 0,
        oCount = 0;
    for (const row of board) {
        for (const c of row) {
            if (c == 'X') xCount++;
            else if (c == 'O') oCount++;
        }
    }
    // 数量判定，不同或者少一个就返回false
    if (oCount != xCount && oCount !== xCount - 1) {
        return false;
    }
    // 如果X赢了但是数量对不上，也返回失败
    if (win(board, 'X') && oCount !== xCount - 1) {
        return false;
    }
    if (win(board, 'O') && oCount !== xCount) {
        return false;
    }
    return true;
};

const win = (board, p) => {
    for (let i = 0; i < 3; ++i) {
        if (p === board[0][i] && p === board[1][i] && p === board[2][i]) {
            return true;
        }
        if (p === board[i][0] && p === board[i][1] && p === board[i][2]) {
            return true;
        }
    }
    if (p === board[0][0] && p === board[1][1] && p === board[2][2]) {
        return true;
    }
    if (p === board[0][2] && p === board[1][1] && p === board[2][0]) {
        return true;
    }
    return false;
};

offer 05 替换空格

刷题时间：2021-12-09

 var replaceSpace = function(s) {
    return s.split(' ').join('%20');
};

双指针

var replaceSpace = function (s) {
    // 字符串转为数组
    const strArr = Array.from(s);
    let count = 0;

    // 计算空格数量
    for (let i = 0; i < strArr.length; i++) {
        if (strArr[i] === ' ') {
            count++;
        }
    }
    let right = strArr.length - 1 + 2 * count;
    let left = strArr.length - 1;
    while (count > 0) {
        if (strArr[left] == ' ') {
            strArr[right--] = '0';
            strArr[right--] = '2';
            strArr[right--] = '%';
            left--;
            count--;
        } else {
            strArr[right--] = strArr[left--];
        }
    }
    // 数组转字符串
    return strArr.join('');
};

offer 58 II 左旋转字符串

刷题时间：2021-12-09

api解法

var reverseLeftWords = function (s, n) {
    return s.slice(n, s.length) + s.slice(0, n);
};

O(n)做法

var reverseLeftWords = function (s, n) {
    const arr = [];
    for (let i = n; i < s.length; i++) {
        arr.push(s[i]);
    }
    for (let i = 0; i < n; i++) {
        arr.push(s[i]);
    }
    return arr.join('');
};

精简O(n)做法

var reverseLeftWords = function (s, n) {
    const arr = [];
    for (let i = n; i < s.length + n; i++) {
        arr.push(s[i % s.length]);
    }
    return arr.join('');
};

还有一种是三次翻转，但肯定过于费时，没办法，毕竟js字符串是不可变，要操作必须要变成数组，这样子必然是O(n)空间，所以不用那么麻烦。

459 重复的子字符串

刷题时间：2021-12-09

我还真是给废物，连个简单题都做不出来，这道简单题是不是有点难了，真的难好吧。

var repeatedSubstringPattern = function (s) {
    const n = s.length;
    for (let i = 1; i * 2 <= n; ++i) {
        if (n % i == 0) {
            let match = true;
            for (let j = i; j < n; ++j) {
                if (s[j] != s[j - i]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
    }
    return false;
};

我草，有个方法巨简单，但是我看不懂，需要数学证明，太难了

var repeatedSubstringPattern = function (s) {
    return (s + s).indexOf(s, 1) != s.length;
};

KMP思想，求出来的next最后一个值不为0，并且减去那个数字的长度的倍数是真实的长度，才是true

var repeatedSubstringPattern = function (s) {
    const next = new Array(s.length).fill(0);
    for (let i = 1, k = 0; i < s.length; i++) {
        while (k > 0 && s[k] != s[i]) {
            k = next[k - 1];
        }
        if (s[k] == s[i]) {
            k++;
        }
        next[i] = k;
    }
    // console.log(next);
    const last = next[next.length - 1];
    if (last !== 0 && s.length % (s.length - last) === 0) return true;
    return false;
};

911 在线选举

刷题时间：2021-12-11

题目一时半会还没看懂，然后看题解理解了一下，这个方法我肯定想不到，二分法这一手确实，我还是非常的生疏。

var TopVotedCandidate = function (persons, times) {
    this.times = times;
    this.tops = [];

    this.map = new Map();
    this.map.set(-1, -1);
    let top = -1;
    for (let p of persons) {
        this.map.set(p, (this.map.get(p) || 0) + 1);
        if (this.map.get(p) >= this.map.get(top)) {
            top = p;
        }
        this.tops.push(top);
    }
};

/**
 * @param {number} t
 * @return {number}
 */
TopVotedCandidate.prototype.q = function (t) {
    let l = 0,
        r = this.times.length;
    while (l < r) {
        let m = l + ((r - l) >> 2);
        if (this.times[m] <= t) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    // console.log(this.tops);
    // console.log(this.times[l]);
    return this.tops[l - 1];
};

225 用队列实现栈

刷题时间：2021-12-11

只用一个栈就行了，不能和栈实现队列的思想来，因为栈其实改变了出入顺序，用两个栈，负负得正就能得到队列的形态。但是两个队列不能得到栈，正正还是正，所以只用一个队列，每次都把老的弹出放到最后，然后最新的就到了顶部，这样子就可以取出来了，可见花费的时间应该非常大。

var MyStack = function () {
    this.queue = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
    this.queue.push(x);
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
    let length = this.queue.length;
    while (length >= 1) {
        length--;
        this.queue.push(this.queue.pop());
    }
    return this.queue.pop();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
    let length = this.queue.length;
    while (length >= 1) {
        length--;
        this.queue.push(this.queue.pop());
    }
    const res = this.queue.pop();
    this.queue.push(res);
    return res;
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    return this.queue.length == 0;
};

1047 删除字符串中的所有相邻重复项

刷题时间：2021-12-11

用上栈思路就非常的清晰，栈对于相邻的重复项非常的有用。

var removeDuplicates = function (s) {
    const st = [];
    for (let ch of s) {
        if (st.length != 0 && st[st.length - 1] == ch) {
            st.pop();
        } else {
            st.push(ch);
        }
    }
    return st.join('');
};

709 转换成小写字母

刷题时间：2021-12-12

啊，这，为什么会有这种题目。

 var toLowerCase = function(s) {
    return s.toLowerCase();
};

自己写的，方法略拉，改了一下，把+好改成或号，就很牛逼

var toLowerCase = function (s) {
    const arr = s.split('');
    for (let i = 0; i < arr.length; i++) {
        const n = arr[i].charCodeAt();
        if (n >= 65 && n <= 90) {
            arr[i] = String.fromCharCode(n |32);
        }
    }
    return arr.join('');
};

150 逆波兰表达式求值

刷题时间：2021-12-12

直接用栈重拳出击。

var evalRPN = function (tokens) {
    const stack = [];
    const r = /^-?\d+$/;
    for (let str of tokens) {
        if (r.test(str)) {
            stack.push(parseInt(str));
        } else if (str == '+') {
            stack.push(stack.pop() + stack.pop());
        } else if (str == '-') {
            stack.push(-stack.pop() + stack.pop());
        } else if (str == '*') {
            stack.push(stack.pop() * stack.pop());
        } else if (str == '/') {
            let tmp = stack.pop();
            stack.push(parseInt(stack.pop() / tmp));
        }
    }
    return stack.pop();
};

239 滑动窗口最大值

刷题时间：2021-12-12

没做出来，这里用的是单调递减的队列，用deque来实现，还好js自带[]就有deque类似的操作，所以底层不用找了。

var maxSlidingWindow = function (nums, k) {
    const n = nums.length;
    const res = [];
    // 这就是deque，双向队列了属于是，既要后面弹出来，也要前面shift
    const q = [];
    for (let i = 0; i < n; i++) {
        // 如果当前的数字比最后一个数字大，那么不断弹出，直至找到比他小的。
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
        // 判断当前最大值（即队首元素）是否在窗口中，若不在便将其出队
        if (q[0] <= i - k) {
            q.shift();
        }
        // 当达到窗口大小时便开始向结果中添加数据
        if (i >= k - 1) res.push(nums[q[0]]);
    }
    return res;
};

347 前 K 个高频元素

刷题时间：2021-12-12

优先队列，以后凡是遇到优先队列，就切换到C++来实现，因为js没有优先队列，所以不建议使用js来写。

class Solution {
   public:
    //小顶堆
    class mycomparison {
       public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for (int i : nums) {
            map[i]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (auto it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
            if (pri_que.size() > k) {
                pri_que.pop();
            }
        }
        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

807 保持城市天际线

刷题时间：2021-12-13

虽说中等题，但是通过率高达87%，比简单题还难了属于是。

var maxIncreaseKeepingSkyline = function (grid) {
    const m = grid.length;
    const arrm = new Array(m).fill(0);
    const arrn = new Array(m).fill(0);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < m; j++) {
            arrm[i] = Math.max(arrm[i], grid[i][j]);
            arrn[i] = Math.max(arrn[i], grid[j][i]);
        }
    }
    let sum = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < m; j++) {
            // console.log(grid[i][j]);
            sum += Math.min(arrm[i], arrn[j]) - grid[i][j];
        }
    }
    return sum;
};