LeetCode-8

继续开始正常刷题

322 零钱兑换

刷题时间：2021-11-25

动态规划，说实话，动态规划比较简单吧，比起回溯简单一点

dp[i]为当前金额最小的硬币数。初始化每个都是比amount大的，然后dp[0]为0，dp[i]

const coinChange = function (coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let c of coins) {
            if (i - c >= 0) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};

还有一种是带暴力的剪枝回溯法

var coinChange = function (coins, amount) {
    // 备忘录
    let preComputed = {};
    function getNumber(amount) {
        // BASE CASE
        if (amount === 0) return 0;
        if (amount < 0) return -1;
        // 已经计算过
        if (preComputed[amount]) return preComputed[amount];
        // 求最小值，所以初始化为正无穷
        let res = Number.MAX_SAFE_INTEGER;
        for (let coin of coins) {
            let subProblem = getNumber(amount - coin);
            if (subProblem === -1) continue;
            res = Math.min(res, subProblem + 1);
        }
        // 结果存入备忘录
        if (res === Number.MAX_SAFE_INTEGER) {
            preComputed[amount] = -1;
        } else {
            preComputed[amount] = res;
        }
        return preComputed[amount] ;
    }
    return getNumber(amount);
};

343 整数拆分

刷题时间：2021-11-25

呜呜呜，难得有一道dp[i]自己做出来了，但是实属拉胯的O(n2)

dp[i]表示目前数字最大的值

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

还有一种优化的动态规划，过于扯淡了，这里不给出来了。

72 编辑距离

刷题时间：2021-11-25

直接抄袭，和哪个最长公共子序列有点点关系，但也可以说没啥关系。

dp[i][j]代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数。

如果字符不相同的话，删除word1和增加word2以及替换word1和word2都需要加一，找出最小的就行了。

const minDistance = (word1, word2) => {
    let dp = Array.from(Array(word1.length + 1), () => Array(word2.length+1).fill(0));

    for(let i = 1; i <= word1.length; i++) {
        dp[i][0] = i; 
    }

    for(let j = 1; j <= word2.length; j++) {
        dp[0][j] = j;
    }

    for(let i = 1; i <= word1.length; i++) {
        for(let j = 1; j <= word2.length; j++) {
            if(word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1);
            }
        }
    }
    
    return dp[word1.length][word2.length];
};

201 数字范围按位与

刷题时间：2021-11-26

又是一道找规律的题目，规律两个的公共前缀找到就行了，那么其他的都会变成0，下面就是两个数字都往右移动，直到m==n，那么就是找到相同的公共前缀了，那么就是最后得到的数字。

const rangeBitwiseAnd = function (m, n) {
    let shift = 0;
    // 找到公共前缀
    while (m < n) {
        m >>= 1;
        n >>= 1;
        ++shift;
    }
    return m << shift;
};

或者通过n&(n-1)，这样子会每次消掉最右边的1，如果n比m小了，那么就说明找到公共前缀了。

const rangeBitwiseAnd = function (m, n) {
    while (m < n) {
        // 抹去最右边的 1
        n = n & (n - 1);
    }
    return n;
};

519 随机翻转矩阵

刷题日期：2021-11-27

虽然我不会，直接看的解析，但这题可以参考384打乱数组这道题目，应该是可以参考的。

算了，不一样，想了半天没有想出来，烦死了

var Solution = function (m, n) {
    this.m = m;
    this.n = n;
    this.total = m * n;
    this.map = new Map();
};

/**
 * @return {number[]}
 */
// 总的思想就是，抽取total-1的幸运儿，如果没有翻转过，那么返回的就是这个幸运儿，并且把这个幸运儿映射到total-1，就代表用过了
// 那么[total-1,m*n]的映射其实都是被用过了；如果抽到的幸运儿是翻转过的，那么就是之前的映射过的total-1
Solution.prototype.flip = function () {
    // 就随机生成一个数字，抽选一个幸运儿，x是下标
    const x = Math.floor(Math.random() * this.total);
    this.total--;
    // 查找位置 x 对应的映射，如果为没被翻转过，那么就是下标本身
    // 如果被翻转过，那么就是x对应的之前的total下标
    const idx = this.map.get(x) || x;
    // 将位置 x 对应的映射设置为位置 total 对应的映射
    // 如果没被翻转过，那么把当前x的值映射到
    this.map.set(x, this.map.get(this.total) || this.total);
    // 没被翻转过，返回的就是下标的矩阵值
    return [Math.floor(idx / this.n), idx % this.n];
};

/**
 * @return {void}
 */
Solution.prototype.reset = function () {
    this.total = this.m * this.n;
    this.map.clear();
};

202 快乐数

刷题日期：2021-11-27

使用哈希，注意js的数值除法需要用Math.floor来取整

var isHappy = function (n) {
    const st = new Set();
    while (n != 1) {
        let sum = 0;
        while (n) {
            sum += (n % 10)*(n % 10);
            n = Math.floor(n / 10);
        }
        n = sum;
        if (st.has(n)) break;
        st.add(n);
    }
    return n == 1;
};

还有一个是快慢指针法，只需要常数空间就行了，但为什么内存消耗比哈希表还大啊。用快慢指针就能判断出是不是循环了。

var isHappy = function (n) {
    const getNext = (n) => {
        let sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n = Math.floor(n / 10);
        }
        return sum;
    };

    let slow = n;
    let fast = getNext(n);
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast == 1;
};

149 直线上最多的点数

遇到困难睡大觉

var maxPoints = function (points) {
    const gcd = (a, b) => {
        return b != 0 ? gcd(b, a % b) : a;
    };
    const n = points.length;
    if (n <= 2) {
        return n;
    }
    let ret = 0;
    for (let i = 0; i < n; i++) {
        // 如果找到的点超过一半或者超过剩下点的数量，就跳出循环
        if (ret >= n - i || ret > n / 2) {
            break;
        }
        const map = new Map();
        for (let j = i + 1; j < n; j++) {
            let x = points[i][0] - points[j][0];
            let y = points[i][1] - points[j][1];
            if (x === 0) {
                y = 1;
            } else if (y === 0) {
                x = 1;
            } else {
                if (y < 0) {
                    x = -x;
                    y = -y;
                }
                const gcdXY = gcd(Math.abs(x), Math.abs(y));
                x /= gcdXY;
                y /= gcdXY;
            }
            const key = y + x * 20001;
            map.set(key, (map.get(key) || 0) + 1);
        }
        let maxn = 0;
        for (const num of map.values()) {
            maxn = Math.max(maxn, num + 1);
        }
        ret = Math.max(ret, maxn);
    }
    return ret;
};

1991 找到数组的中间位置

724 寻找数组的中心下标

刷题时间：2021-11-28

简单题简单写，没什么难度。

var pivotIndex = function (nums) {
    let sum = 0;
    for (let i of nums) {
        sum += i;
    }
    let tmp = 0;
    sum -= nums[0];
    if (sum == 0) return 0;
    for (let i = 1; i < nums.length; i++) {
        tmp += nums[i - 1];
        sum -= nums[i];
        if (sum == tmp) return i;
    }
    return -1;
};

56 合并区间

刷题时间：2021-11-28

中等题中等写，没什么难度

var merge = function (intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const res = [intervals[0]];
    tmp = intervals[0];
    for (let nums of intervals) {
        if (nums[0] > tmp[1]) res.push(nums);
        else if (nums[1] > tmp[1]) {
            res[res.length - 1][1] = nums[1];
        }
        tmp = res[res.length - 1];
    }
    return res;
};

786 第 K 个最小的素数分数

刷题时间：2021-11-29

困难题困难写，没什么难度

var kthSmallestPrimeFraction = function (arr, k) {
    const n = arr.length;
    const frac = [];
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            frac.push([arr[i], arr[j]]);
        }
    }
    frac.sort((x, y) => x[0] * y[1] - y[0] * x[1]);
    return frac[k - 1];
};

但是上面O(n2logn)这个有点爆炸，纯粹简单了。但是那些难的方法不想看了，头疼。

48 旋转图像

刷题时间：2021-11-29

时间直接拉满，思想倒是简单，就是实现比较复杂

var rotate = function (matrix) {
    const n = matrix.length;
    if (n == 0 || n == 1) return matrix;
    for (let i = 0; i < n / 2; i++) {
        for (let j = i; j < n - i - 1; j++) {
            // console.table(matrix);
            let tmp = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = matrix[i][j];
            matrix[i][j] = tmp;
        }
    }
    return matrix;
};

还有种是水平翻转加上对角线翻转，直接抄的官解，比我的慢

var rotate = function(matrix) {
    const n = matrix.length;
    // 水平翻转
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < n; j++) {
            [matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]];
        }
    }
    // 主对角线翻转
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
};

498 对角线遍历

刷题时间：2021-11-29

时间非常的拉胯，其实我都知道的，唉

var findDiagonalOrder = function (mat) {
    const m = mat.length,
        n = mat[0].length;
    const res = [];
    for (let i = 0; i < m + n - 1; i++) {
        for (let j = 0; j <= i; j++) {
            if (i % 2 == 0) {
                if (i - j < 0 || i - j >= m || j < 0 || j >= n) continue;
                res.push(mat[i - j][j]);
            } else {
                if (i - j < 0 || i - j >= n || j < 0 || j >= m) continue;
                res.push(mat[j][i - j]);
            }
        }
    }
    return res;
};

诶，优化，就是玩，也不根据什么公式了，直接对着公式进行优化，就是玩儿

var findDiagonalOrder = function (mat) {
    const m = mat.length,
        n = mat[0].length;
    const res = [];
    for (let i = 0; i < m + n - 1; i++) {
        if (i % 2 == 0) {
            for (let j = Math.max(0, i - m + 1); j < Math.min(i + 1, n); j++) {
                res.push(mat[i - j][j]);
            }
        } else {
            for (let j = Math.max(0, i - n + 1); j < Math.min(i + 1, m); j++) {
                res.push(mat[j][i - j]);
            }
        }
    }
    return res;
};

400 第 N 位数字

刷题时间：2021-11-30

找规律，找不出来，麻了

var findNthDigit = function (n) {
    let d = 1,
        count = 9;
    while (n > d * count) {
        n -= d * count;
        d++;
        count *= 10;
    }
    const index = n - 1;
    const start = Math.floor(Math.pow(10, d - 1));
    const num = start + Math.floor(index / d);
    const digitIndex = index % d;
    const digit = Math.floor(num / Math.floor(Math.pow(10, d - digitIndex - 1))) % 10;
    return digit;
};

14 最长公共前缀

刷题时间：2021-11-30

就抄题解，就找出公共前缀，横向扫描法

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    let prefix = strs[0];
    const n = strs.length;
    for (let i = 1; i < n; i++) {
        const length = Math.min(prefix.length, strs[i].length);
        let index = 0;
        while (index < length && prefix[index] == strs[i][index]) {
            index++;
        }
        prefix = prefix.substr(0, index);
        if (!prefix.length) break;
    }
    return prefix;
};

竖向扫描

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    let length = strs[0].length;
    const n = strs.length;
    for (let i = 0; i < length; i++) {
        let c = strs[0][i];
        for (let j = 1; j < n; j++) {
            if (i == strs[j].length || strs[j][i] != c) {
                return strs[0].substr(0, i);
            }
        }
    }
    return strs[0];
};

排序，O(mnlogmn)

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    strs.sort();
    let st = strs[0],
        en = strs[strs.length - 1];
    let i,
        num = Math.min(st.length, en.length);
    for (i = 0; i < num && st[i] == en[i]; i++);
    return st.substr(0, i);
};

151 翻转字符串里的单词

刷题时间：2021-11-30

过于生草，全都是调用API，这我是没想到的。

var reverseWords = function (s) {
    return s.trim().split(/\s+/).reverse().join(' ');
};

但除了调用库函数，如何实现这个方法，反而有点难度，思想就是先做一个去除多余的空格的操作，再将所有的字符串进行翻转，然后再对单独的单词进行翻转。

时间和空间拉稀，也不知道为什么。

const removeExtraSpaces = function (strArr) {
    let slowIndex = 0;
    let fastIndex = 0;

    while (fastIndex < strArr.length) {
        // 移除开始位置和重复的空格
        if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
            fastIndex++;
        } else {
            strArr[slowIndex++] = strArr[fastIndex++];
        }
    }
    // 移除末尾空格
    strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
};
const reverse = function (strArr, l, r) {
    while (l < r) {
        [strArr[l], strArr[r]] = [strArr[r], strArr[l]];
        l++;
        r--;
    }
};
var reverseWords = function (s) {
    const arr = Array.from(s);
    removeExtraSpaces(arr);
    reverse(arr, 0, arr.length - 1);
    let l = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] == ' ') {
            reverse(arr, l, i - 1);
            l = i + 1;
        }
    }
    reverse(arr, l, arr.length - 1);
    return arr.join('');
};

28 实现 strStr()

刷题时间：2021-11-30

暴力法，就还行。

var strStr = function (haystack, needle) {
    const n = needle.length;
    if (n == 0) return 0;

    const m = haystack.length;
    if (m < n) return -1;
    for (let i = 0; i < m - n + 1; i++) {
        let s = haystack.substr(i, n);
        if (s == needle) return i;
    }
    return -1;
};

接下来上猛料，学习KMP算法，就有点牛逼的这个算法，需要实现Next数组

用上KMP还慢了好多，真的拉胯

var strStr = function (haystack, needle) {
    const n = haystack.length,
        m = needle.length;
    if (m === 0) {
        return 0;
    }

    // 创建pi也就是next数组，默认初始化都为0，里面的值表示第n个，下标从1开始
    const pi = new Array(m).fill(0);

    for (let i = 1, k = 0; i < m; i++) {
        // 往前找，找到匹配的。
        while (k > 0 && needle[i] !== needle[k]) {
            k = pi[k - 1];
        }
        if (needle[i] == needle[k]) {
            k++;
        }
        console.log(i,k)
        pi[i] = k;
    }
    console.log(pi);
    for (let i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j === m) {
            return i - m + 1;
        }
    }
    return -1;
};

或者下面这种正宗的kmp

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    let i=0;
    let j=0;
    let next=getNext(needle);
    while(i<haystack.length&&j<needle.length){
        if(j==-1||haystack.charAt(i)==needle.charAt(j)){
            j++;
            i++;
        }
        else{
            j=next[j]
        }
    }
    if(j==needle.length)
    return i-j;
    else
    return -1
};
function getNext(needle){
    let k=-1;
    let j=0;
    let next=[-1]
    while(j<needle.length){
        if(k==-1||needle.charAt(j)==needle.charAt(k))
        {
            j++;
            k++;
            next[j]=k
        }
        else{
            k=next[k]
        }
    }
    return next;
}

1446 连续字符

刷题时间：2021-12-01

简单题，但也每一次过，尿了

var maxPower = function (s) {
    let ch = s[0];
    let res = 1,
        tmp = 1;

    for (let i = 1; i < s.length; i++) {
        if (ch == s[i]) {
            tmp++;
        } else {
            res = Math.max(tmp, res);
            tmp = 1;
            ch = s[i];
        }
    }
    return Math.max(tmp, res);
};

官解更好

var maxPower = function(s) {
    let ans = 1, cnt = 1;
    for (let i = 1; i < s.length; ++i) {
        if (s[i] == s[i - 1]) {
            ++cnt;
            ans = Math.max(ans, cnt);
        } else {
            cnt = 1;
        }
    }
    return ans;
};

561 数组拆分 I

刷题时间：2021-12-01

果然和两年前的思路一模一样，尿了

var arrayPairSum = function (nums) {
    let sum = 0;
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i += 2) {
        sum += nums[i];
    }
    return sum;
};

27 移除元素

刷题时间：2021-12-01

简单双指针

var removeElement = function (nums, val) {
    let slow = 0;
    for (let i = 0; i < nums.length; i++) {
        if (val != nums[i]) {
            nums[slow] = nums[i];
            slow++;
        }
    }
    return slow;
};

这居然都有优化，因为顺序可以变，而省去了重复赋值的操作。但这个优化有点蛋疼。

var removeElement = function(nums, val) {
    let left = 0, right = nums.length;
    while (left < right) {
        if (nums[left] === val) {
            nums[left] = nums[right - 1];
            right--;
        } else {
            left++;
        }
    }
    return left;
};

485 最大连续 1 的个数

刷题时间：2021-12-01

简单题，但我还是写错了，以为和1446差不多，可是有点区别的。

var findMaxConsecutiveOnes = function (nums) {
    let maxCount = 0,
        count = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (nums[i] === 1) {
            count++;
        } else {
            maxCount = Math.max(maxCount, count);
            count = 0;
        }
    }
    return Math.max(maxCount, count);
};

506 相对名次

刷题时间：2021-12-02

简单题，没做出来，过于生草了，就是将value和key对调，map的key为原来的值，value为index排序，草了没想到这么简单。

var findRelativeRanks = function (score) {
    const map = new Map();
    const sortNums = [...score]
        .sort((a, b) => b - a)
        .forEach((num, index) => {
            map.set(num, index);
        });
    return score.map((item, index) => {
        if (map.get(item) == 0) {
            return 'Gold Medal';
        } else if (map.get(item) == 1) {
            return 'Silver Medal';
        } else if (map.get(item) == 2) {
            return 'Bronze Medal';
        }
        return map.get(item) + 1 + '';
    });
};

119 杨辉三角 II

刷题时间：2021-12-02

这种就是O(2n)

var getRow = function (rowIndex) {
    let res = [];
    for (let i = 0; i < rowIndex + 1; i++) {
        let temp = new Array(i + 1).fill(1);
        for (let j = 1; j < i; j++) {
            temp[j] = res[j - 1] + res[j];
        }
        res = temp;
    }
    return res;
};

还有一种倒着来，只用O(n)，但说实话倒着来的这种不仅内存消耗大了，时间延迟还大了

var getRow = function (rowIndex) {
    const row = new Array(rowIndex + 1).fill(0);
    row[0] = 1;
    for (let i = 1; i <= rowIndex; ++i) {
        for (let j = i; j > 0; --j) {
            row[j] += row[j - 1];
        }
    }
    return row;
};

1005 K 次取反后最大化的数组和

刷题时间：2021-12-03

唉，艹，这个简单贪心做了好久，果然不能用直觉，要用点贪心的思路和想法，有点拉

var largestSumAfterKNegations = function (nums, k) {
    nums.sort((a, b) => {
        return Math.abs(b) - Math.abs(a);
    });
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < 0 && k > 0) {
            nums[i] *= -1;
            k--;
        }
    }

    if (k > 0 && k % 2 === 1) {
        nums[nums.length - 1] *= -1;
    }

    return nums.reduce((a, b) => {
        return a + b;
    });
};