LeetCode-13

动态这章估计能刷完，之后要干什么就不知道了。

1332 删除回文子序列

刷题时间：2022-01-22

乍眼看是中等难度或者困难难度的题目，没想到居然是简单题，过于生草了。

var removePalindromeSub = function (s) {
    const n = s.length;
    for (let i = 0; i < Math.floor(n / 2); ++i) {
        if (s[i] !== s[n - 1 - i]) {
            return 2;
        }
    }
    return 1;
};

1035 不相交的线

刷题时间：2022-01-22

和1143 最长公共子序列这道题一模一样，甚至解法都是一样，代码都不用改，直接copy过来就行了。s

var maxUncrossedLines = function (nums1, nums2) {
    const m = nums1.length,
        n = nums2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        const num1 = nums1[i - 1];
        for (let j = 1; j <= n; j++) {
            if (num1 == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
};

392 判断子序列

刷题时间：2022-01-22

双指针

var isSubsequence = function (s, t) {
    const n = s.length,
        m = t.length;
    let i = 0,
        j = 0;
    while (i < n && j < m) {
        if (s[i] == t[j]) {
            i++;
        }
        j++;
    }
    return i == n;
};

居然还有动态规划，其实可以从最长公共子序列这道题获取灵感，两者的本质都差不多，这里就可以套用之前写法，只要直接判断最后最长公共子序列的长度是不是等于子序列S的长度就行了。但是可以再简化一下， 因为是判断s是t的子序列，s是必须被包含的，所以当s[i-1]!=t[i-1]的时候，就是取s[0:i-1]和t[0:j-2]的长度，因为s必须被包含嘛，不需要s[0:i-2]和t[0:j-1]了，大概就是这个意思吧，确实有点绕和想不明白，大概就这样

// dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
var isSubsequence = function (s, t) {
    // s、t的长度
    const [m, n] = [s.length, t.length];
    // dp全初始化为0
    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]，两种情况
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i][j - 1];
                // 最长公共子序列，这样子也能通过，dp[i][j] = Math.max(dp[i][j - 1],dp[i-1][j]);
            }
        }
    }
    // 遍历结束，判断dp右下角的数是否等于s的长度
    return dp[m][n] === m ? true : false;
};

115 不同的子序列

刷题时间：2022-01-27

还是抽象的动态规划，太抽象了，尤其是递推公式真的是有、抽象，字符串相同的情况要进行匹配和不匹配两种情况。还有初始化，也有点抽象。

var numDistinct = function (s, t) {
    const [m, n] = [s.length, t.length];
    // dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) dp[i][0] = 1;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 更新dp[i][j]，两种情况
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 遍历结束，判断dp右下角的数是否等于s的长度
    return dp[m][n];
};

647 回文子串

刷题时间：2022-01-27

注意判断条件，一个字符串相同，还有两个字符串相同，都要先判断。

还有注意遍历顺序，要从下到上，从左到右。

var countSubstrings = function (s) {
    const n = s.length;
    // 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
    const dp = new Array(n).fill(false).map(() => new Array(n).fill(false));
    let res = 0;
    for (let i = n-1; i >=0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                res++;
            }
        }
    }
    return res;
};

516 最长回文子序列

时间：2022-01-27

也是需要注意遍历顺序，还有dp递推公式。

var longestPalindromeSubseq = function (s) {
    // dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
    const n = s.length;
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] == s[j]) {
                if (i == j) dp[i][j] = 1;
                else dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
};

739 每日温度

刷题时间：2022-01-28

单调栈的使用，单调栈就是一维数组找到右侧比当前数字大或者小的下标，单调栈存的是下标，而且是单调递增或者单调递减的吧，还是看具体应用场景

var dailyTemperatures = function (temperatures) {
    const n = temperatures.length;
    const res = new Array(n).fill(0);
    const st = [0];
    //单调栈
    for (let i = 1; i < n; i++) {
        let top = st[st.length - 1];
        if (temperatures[i] <= temperatures[top]) {
            st.push(i);
        } else {
            while (st.length && temperatures[i] > temperatures[st[st.length - 1]]) {
                top = st.pop();
                res[top] = i - top;
            }
            st.push(i);
        }
    }
    return res;
};

503 下一个更大元素 II

刷题时间：2022-01-28

单调栈循环两次就行了，只要找到的数字下标超过n就直接返回了。

var nextGreaterElements = function (nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const st = [0];
    //单调栈
    for (let i = 1; i < 2 * n; i++) {
        while (st.length && nums[i%n] > nums[st[st.length - 1]]) {
            const top = st.pop();
            if (top >= n) return res;
            res[top] = nums[i%n];
        }
        st.push(i%n);
    }
    return res;
};

290 单词规律

刷题时间：2022-01-28

简单题的困难吧，用到了双射，需要一一对应才行，即x出现一次，对应y中出现的一次。

var wordPattern = function (pattern, s) {
    const arr = s.split(' ');
    if (arr.length != pattern.length) return false;
    const parr = new Array(26).fill(-1);
    const map = new Map();
    for (let i = 0; i < arr.length; i++) {
        const index = pattern.charCodeAt(i) - 97;
        if (map.get(arr[i]) == undefined && parr[index] == -1) {
            parr[index] = arr[i];
            map.set(arr[i], index);
        } else if (parr[index] !== arr[i] || map.get(arr[i]) !== index) {
            return false;
        }
    }
    return true;
};

884 两句话中的不常见单词

刷题时间：2022-01-30

哈希表

var uncommonFromSentences = function (s1, s2) {
    const map = new Map();
    const arr1 = s1.split(' ');
    const arr2 = s2.split(' ');
    for (let i = 0; i < arr1.length; i++) {
        map.set(arr1[i], (map.get(arr1[i]) || 0) + 1);
    }
    for (let i = 0; i < arr2.length; i++) {
        map.set(arr2[i], (map.get(arr2[i]) || 0) + 1);
    }
    const res = [];
    for (let [key, val] of map.entries()) {
        if (val == 1) res.push(key);
    }
    return res;
};

84 柱状图中最大的矩形

刷题时间：2022-01-30

以为和接雨水差不多，但是更难一点，这个最小值的数组很难想和实现，我肯定不是这么实现的，我应该会遍历查找最小的，他这个操作也有点动态规划的味道了，虽然这个解法就是动态规划。

var largestRectangleArea = function (heights) {
    // 难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
    let res = 0;
    const n = heights.length;
    const minLeftIndex = new Array(n);
    const minRightIndex = new Array(n);
    minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环

    for (let i = 1; i < n; i++) {
        let t = i - 1;
        while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
        minLeftIndex[i] = t;
    }
    minRightIndex[n - 1] = n; // 注意这里初始化，防止下面while死循环
    for (let i = n - 2; i >= 0; i--) {
        let t = i + 1;
        while (t < n && heights[t] >= heights[i]) t = minRightIndex[t];
        minRightIndex[i] = t;
    }
    for (let i = 0; i < n; i++) {
        res = Math.max(res, heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1));
    }
    return res;
};

这个单调栈是真的难啊，还要再前面和后面加上两个0，是不是有点难想到，不亏是困难题目。

var largestRectangleArea = function (heights) {
    // 从栈顶到栈底为单调递减的
    let res = 0;
    const st = [0];
    heights = [0,...heights,0]; // 数组头部加入元素0 数组尾部加入元素0
    for (let i = 1; i < heights.length; i++) {
        while (st.length && heights[i] < heights[st[st.length - 1]]) {
            const mid = st.pop();
            res = Math.max(res, (i - st[st.length - 1] - 1) * heights[mid]);
        }
        st.push(i);
    }
    return res;
};

1725 可以形成最大正方形的矩形数目

刷题时间：2022-02-04

var countGoodRectangles = function (rectangles) {
    let res = 0;
    let max = -1;
    for (let r of rectangles) {
        const min = Math.min(r[0], r[1]);
        if (min > max) {
            max = min;
            res = 1;
        } else if (min == max) {
            res++;
        }
    }
    return res;
};

1984 学生分数的最小差值

刷题时间：2022-02-11

简单题目，我居然第一次还是错误的，真是有我的。

var minimumDifference = function (nums, k) {
    nums.sort((a, b) => a - b);
    let res = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < nums.length - k + 1; i++) {
        res = Math.min(nums[k + i - 1] - nums[i], res);
    }
    return res;
};

1447 最简分数

时间：2022-02-11

暴力法，然后求他的最大公约数

var simplifiedFractions = function (n) {
    const ans = [];
    // 遍历分母
    for (let denominator = 2; denominator <= n; ++denominator) {
        // 遍历分子
        for (let numerator = 1; numerator < denominator; ++numerator) {
            // 求出最大公约数，如果是1，那么就是最简的了
            if (gcd(numerator, denominator) == 1) {
                ans.push(numerator + '/' + denominator);
            }
        }
    }
    return ans;
};
// 辗转相除法
const gcd = (a, b) => {
    if (b === 0) return a;
    return gcd(b, a % b);
};

2006 差的绝对值为 K 的数对数目

时间：2022-02-11

居然就是求两数之和，只不过变成求他的数量罢了。

var countKDifference = function (nums, k) {
    let res = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (Math.abs(nums[j] - nums[i]) == k) res++;
        }
    }
    return res;
};

这个有点绕，我有点想不明白，这个累加操作有点牛的，反正很牛

var countKDifference = function (nums, k) {
    const cnt = new Map();
    let res = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        cnt.set(nums[i], (cnt.get(nums[i]) || 0) + 1);
        res += (cnt.get(nums[i] - k) || 0) + (cnt.get(nums[i] + k) || 0);
    }
    return res;
};

1020 飞地的数量

时间：2022-02-12

就岛屿问题的深度优先

var numEnclaves = function (grid) {
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    const m = grid.length;
    const n = grid[0].length;

    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false));

    const dfs = (row, col) => {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) return;
        visited[row][col] = true;
        for (let dir of dirs) {
            dfs(row + dir[0], col + dir[1]);
        }
    };
    for (let i = 0; i < m; i++) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    for (let j = 0; j < n; j++) {
        dfs(0, j);
        dfs(m- 1, j);
    }
    let res = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                res++;
            }
        }
    }
    return res;
};

1405 最长快乐字符串

时间：2022-02-12

这个官解太抽象了，原理就是很简单的贪心，每次都贪最大的

var longestDiverseString = function (a, b, c) {
    const res = [];
    const arr = [
        [a, 'a'],
        [b, 'b'],
        [c, 'c']
    ];

    while (true) {
        // 降序排序
        arr.sort((a, b) => b[0] - a[0]);
        let has = false;
        for (const [i, [cnt, ch]] of arr.entries()) {
            //如果数量为0，那么就break，因为后面的肯定是小于等于0的
            if (cnt <= 0) break;
            const m = res.length;
            // 如果前两个字符都是相同的，那么就跳过，换下一个字符尝试
            if (m >= 2 && res[m - 1] == ch && res[m - 2] == ch) continue;
            res.push(ch);
            arr[i][0]--;
            has = true;
            break;
        }
        if (!has) {
            break;
        }
    }
    return res.join('');
};

1748 唯一元素的和

时间：2022-02-12

直接哈希表来一波先

var sumOfUnique = function (nums) {
    let res = 0;
    let map = new Map();
    for (let n of nums) map.set(n, (map.get(n) || 0) + 1);
    for (let m of map) if (m[1] == 1) res += m[0];
    return res;
};

1219 黄金矿工

时间：2022-02-12

岛屿类的dfs，基本上大差不多，还需要回溯一下

var getMaximumGold = function (grid) {
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    const m = grid.length;
    const n = grid[0].length;
    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false));
    const dfs = (row, col, num) => {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) return num;
        visited[row][col] = true;
        num += grid[row][col];
        let tmp = num;
        for (let dir of dirs) {
            const res = dfs(row + dir[0], col + dir[1], num);
            tmp = Math.max(res, tmp);
        }
        visited[row][col] = false;
        return tmp;
    };
    let res = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                res = Math.max(dfs(i, j, 0), res);
            }
        }
    }
    return res;
};

1189 气球的最大数量

时间：2022-02-13

简单题，没啥说的。

var maxNumberOfBalloons = function (text) {
    const arr = new Array(26).fill(0);
    for (let i = 0; i < text.length; i++) {
        arr[text.charCodeAt(i) - 97]++;
    }
    let res = 0;
    while (true) {
        arr[0] -= 1;
        arr[1] -= 1;
        arr[11] -= 2;
        arr[13] -= 1;
        arr[14] -= 2;
        if (arr[0] < 0 || arr[1] < 0 || arr[11] < 0 || arr[13] < 0 || arr[14] < 0) break;
        else res++;
    }
    return res;
};

1763 最长的美好子字符串

时间：2022-02-13、

简单题目写不出来，我也是有点菜鸡的，还是要用O(n2)才行，看看滑动窗口能不能写出来，算了，看了一下，题解，代码量一下子翻上来了，太难了。

var longestNiceSubstring = function (s) {
    let left = 0;
    let right = 0;
    for (let i = 0; i < s.length; i++) {
        let lower = 0;
        let upper = 0;
        for (let j = i; j < s.length; j++) {
            if ('a' <= s[j] && 'z' >= s[j]) {
                lower |= 1 << (s.charCodeAt(j) - 97);
            } else {
                upper |= 1 << (s.charCodeAt(j) - 65);
            }
            if (upper == lower && j - i > right - left - 1) {
                right = j + 1;
                left = i;
            }
        }
    }
    return s.slice(left, right);
};

2000 反转单词前缀

时间：2022-02-13

这才是简单题的水平吧

var reversePrefix = function (word, ch) {
    const arr = word.split('');
    const end = word.indexOf(ch);
    for (let i = 0; i <= Math.floor(end / 2); i++) {
        [arr[i], arr[end - i]] = [arr[end - i], arr[i]];
    }
    return arr.join('');
};

1414 和为 K 的最少斐波那契数字数目

时间：2022-02-13

强行证明的题目，虽然不知道为什么，反正就这样子吧。

var findMinFibonacciNumbers = function (k) {
    let res = 0;
    while (k >= 1) {
        k -= fibo(k);
        res++;
    }
    return res;
};
const fibo = (num) => {
    let i1 = 1;
    let i2 = 1;
    let tmp = 1;
    while (true) {
        if (i1 > num) {
            return i2;
        } else {
            tmp = i1;
            i1 = i1 + i2;
            i2 = tmp;
        }
    }
};

540 有序数组中的单一元素

时间：2022-02-14

什么奇偶性巴拉巴拉的，看了好久才看出来，有点尿

var singleNonDuplicate = function (nums) {
    let left = 0,
        right = nums.length - 1;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (mid % 2 == 0) {
            if (nums[mid] == nums[mid + 1]) left = mid + 1;
            else right = mid;
        } else {
            if (nums[mid] == nums[mid - 1]) left = mid + 1;
            else right = mid;
        }
    }
    return nums[left];
};

1342 将数字变成 0 的操作次数

时间：2022-02-14

var numberOfSteps = function (num) {
    let res = 0;
    while (num > 0) {
        if (num & (1 == 1)) num--;
        else num = Math.floor(num / 2);
        res++;
    }
    return res;
};

1765 地图中的最高点

时间：2022-02-14

这题解法是用多源BFS，虽然我不知道是什么意思，但是意思应该就是用队列，虽然添加的顺序不是按照顺序，但是就是源头是多个的嘛，添加一层后，再添加第二层，再添加第三层，大概就是这个意思，堆金字塔一样。注意这道题的js不能使用unshift，会超时，真的是拉胯，需要用一个新的数组时刻替换才行。

var highestPeak = function (isWater) {
    const m = isWater.length;
    const n = isWater[0].length;

    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    const res = new Array(m).fill(0).map(() => new Array(n).fill(-1));
    let queue = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (isWater[i][j]) {
                res[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    while (queue.length) {
        const length = queue.length,
            tmp_q = [];
        for (let i = 0; i < length; i++) {
            const p = queue[i];
            for (let dir of dirs) {
                const row = p[0] + dir[0];
                const col = p[1] + dir[1];
                if (row >= 0 && row < m && col >= 0 && col < n && res[row][col] == -1) {
                    res[row][col] = res[p[0]][p[1]] + 1;
                    tmp_q.push([row, col]);
                }
            }
        }
        queue = tmp_q;
    }

    return res;
};

1380 矩阵中的幸运数

时间：2022-02-16

var luckyNumbers = function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const row = new Array(m).fill(Number.MAX_SAFE_INTEGER);
    const col = new Array(n).fill(0);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            row[i] = Math.min(row[i], matrix[i][j]);
            col[j] = Math.max(col[j], matrix[i][j]);
        }
    }
    let res = [];
    for (let i = 0; i < n; i++) {
        if (row.indexOf(col[i]) != -1) res.push(col[i]);
    }
    return res;
};

1996 游戏中弱角色的数量

时间：2022-02-16

这个题目难啊，应该用单调栈做，经典2个数字的数组比较法，这种方法是排序，第一个从大到小排序，第二个从小到大排序，这样子就遍历一次就行了。

var numberOfWeakCharacters = function (properties) {
    let res = 0;
    const n = properties.length;
    properties.sort((a, b) => {
        return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
    });
    let maxRight;
    for (let p of properties) {
        if (p[1] < maxRight) res++;
        else {
            maxRight = p[1];
        }
    }
    return res;
};

单调栈的做法，说实话，单调栈的做法也挺难想的

var numberOfWeakCharacters = function (properties) {
    let res = 0;
    properties.sort((a, b) => {
        return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
    });
    const st = [];
    for (const p of properties) {
        while (st.length && st[st.length - 1] < p[1]) {
            st.pop();
            res++;
        }
        st.push(p[1]);
    }
    return res;
}

69 x 的平方根

时间：2022-02-16

二分法

var mySqrt = function (x) {
    let left = 0,
        right = x;
    let res = -1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (mid * mid <= x) {
            res = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
};

牛顿迭代法，只需要记住公式就行了

var mySqrt = function (x) {
    if (x == 0) return 0;
    let C = x,
        x0 = x;
    while (true) {
        let xi = 0.5 *(x0 + C / x0);
        if (Math.abs(x0 - xi) < 1e-7) break;
        x0 = xi;
    }
    return Math.floor(x0);
};