LeetCode-12

贪心还没完事，挺难的，都是看解析，太five了我。

71 简化路径

刷题时间：2022-01-06

直接看的解析，直呼简单，可惜我写不出来的水平

var simplifyPath = function (path) {
    const names = path.split('/');
    console.log(names);
    const stack = [];
    for (const name of names) {
        if (name === '..') {
            if (stack.length) {
                stack.pop();
            }
        } else if (name.length && name !== '.') {
            stack.push(name);
        }
    }
    return '/' + stack.join('/');
};

738 单调递增的数字

刷题时间：2022-01-06

这个贪心从后往前，只要前面的值大于当前的值，就把前面的值-1，当前的值和后面的值都置为9。

这里有个取巧的方法，就是字符串前面带0的，可以使用加号强制转换成数字，并且去掉那个0

var monotoneIncreasingDigits = function (n) {
    n = n.toString();
    n = n.split('').map((item) => {
        return +item;
    });
    let flag = Infinity;
    for (let i = n.length - 1; i > 0; i--) {
        if (n[i - 1] > n[i]) {
            flag = i;
            n[i - 1] = n[i - 1] - 1;
            n[i] = 9;
        }
    }

    for (let i = flag + 1; i < n.length; i++) {
        n[i] = 9;
    }
    n = n.join('');
    return +n;
};

714 买卖股票的最佳时机含手续费

刷题时间：2022-01-06

这个贪心也太难了，搞不定。

var maxProfit = function (prices, fee) {
    let res = 0;
    let minPrice = prices[0];
    for (let i = 1; i < prices.length; i++) {
        // 如果当前价格低于最低的价格，就购买
        if (prices[i] < minPrice) minPrice = prices[i];
        // 如果价格在最低价格和手续费之间，那么就不
        if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
            continue;
        }
        // 如果高于手续费+最低价格，那么就可以卖了
        // 可能有多次利润计算，但是每次最低价格都减去了手续费，这样子最后一次收的时候只有一次手续费
        if (prices[i] > minPrice + fee) {
            res += prices[i] - minPrice - fee;
            minPrice = prices[i] - fee;
        }
    }
    return res;
};

动态规划，非常的拉中拉了

var maxProfit = function (prices, fee) {
    // dp[i][0]表示持有股票拥有的现金，dp[i][1]表示不持有股票拥有的现金
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
    dp[0][0] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    }
    return Math.max(dp[n - 1][0], dp[n - 1][1]);
};

968 监控二叉树

刷题时间：2022-01-06

太牛了，需要看解析才行，毕竟困难题目。

var minCameraCover = function (root) {
    let res = 0;
    // 0  是无覆盖， 1是有摄像头 ， 2是有覆盖
    const traversal = (node) => {
        if (node === null) {
            return 2;
        }
        // 后序遍历，就是为了处理叶子节点
        const left = traversal(node.left);
        const right = traversal(node.right);

        // 如果左右都有覆盖，那本节点就是无覆盖
        if (left == 2 && right == 2) return 0;

        // 如果左右有一个没覆盖，那么本节点就是摄像头
        if (left == 0 || right == 0) {
            res++;
            return 1;
        }

        // 如果左右有一个是摄像头，那么本节点就是有覆盖
        if (left == 1 || right == 1) return 2;

        return -1;
    };
    if (traversal(root) == 0) {
        res++;
    }
    return res;
};

509 斐波那契数

刷题时间：2022-01-11

先用递归爽一下

var fib = function (n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
};

然后动态规划

var fib = function (n) {
    if (n <= 1) return n;
    const dp = new Array(n);
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

再优化一下，使用三个变量表示一下

var fib = function (n) {
    if (n <= 1) return n;
    let dp0 = 0,
        dp1 = 1,
        res = 1;
    for (let i = 2; i <= n; i++) {
        res = dp0 + dp1;
        dp0 = dp1;
        dp1 = res;
    }
    return res;
};

746 使用最小花费爬楼梯

刷题时间：2022-01-11

简单动态规划，直接使用costs作为dp就行了

var minCostClimbingStairs = function (cost) {
    const n = cost.length;
    for (let i = 2; i < n; i++) cost[i] += cost[i - 1] < cost[i - 2] ? cost[i - 1] : cost[i - 2];
    return Math.min(cost[n - 1], cost[n - 2]);
};

63 不同路径 II

刷题时间：2022-01-11

动态规划，和不同路径差不多，就是要处理第一行和第一列的特殊情况，其他的都扎不多。

var uniquePathsWithObstacles = function (obstacleGrid) {
    if (obstacleGrid[0][0] == 1) return 0;
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
    for (let i = 1; i < m; i++) {
        if (dp[i - 1][0] == 0 || obstacleGrid[i][0] == 1) {
            dp[i][0] = 0;
        }
    }
    for (let j = 1; j < n; j++) {
        if (dp[0][j - 1] == 0 || obstacleGrid[0][j] == 1) {
            dp[0][j] = 0;
        }
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
};

334 递增的三元子序列

刷题时间：2022-01-12

日常做不出来每日一题，摸不到头脑一开始，先求出左边的最小值，再右边数列的最大值，然后进行比较。空间是O(n)

var increasingTriplet = function (nums) {
    const length = nums.length;
    if (length < 3) return false;
    const left = new Array(length - 1).fill(0);
    left[0] = nums[0];
    const right = new Array(length - 1).fill(0);
    right[0] = nums[length - 1];
    for (let i = 1; i < length - 1; i++) {
        left[i] = Math.min(nums[i], left[i - 1]);
        right[i] = Math.max(nums[length - i - 1], right[i-1]);
    }
    for (let i = 1; i < length - 1; i++) {
        if (nums[i] > left[i - 1] && nums[i] < right[length-i-1]) return true;
    }
    return false;
};

贪心算法，遍历的是第三个数字，然后给first和second，如果比second大的话，那么就返回true，因为此时first<second<first，else如果比first大，那么就赋值给second，此时必有first<second，要不然，就重新赋值给first，此时first是最小的，当然second和third都不定 ，贪心。尽管我刷完了贪心，但是我还是不会，我就是个five。

var increasingTriplet = function (nums) {
    const length = nums.length;
    if (length < 3) return false;
    let first = nums[0];
    let second = Number.MAX_VALUE;
    for (let i = 1; i < length; i++) {
        if (nums[i] > second) return true;
        else if (nums[i] > first) second = nums[i];
        else first = nums[i];
    }
    return false;
};

96 不同的二叉搜索树

刷题时间：2022-01-12

这个题目真的抽象，需要画图去找出规律，dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。递推公式dp[i] += dp[j – 1] * dp[i – j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量。

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

416 分割等和子集

刷题时间：2022-01-12

非常的简洁啊，虽然是抄的。这就是经典的背包01问题。采用的是一维数组，dp[j] 表示： 容量为j的背包，所背的物品价值可以最大为dp[j]。外循环遍历物品的数量，内循环遍历的是背包的大小，要逆序遍历，从背包总容量遍历到当前物品的大小，再小反正也放不进去了，就是上一个物品的dp了。

var canPartition = function (nums) {
    const sum = nums.reduce((prev, curr) => prev + curr);
    if (sum &1) return false;
    const target = Math.floor(sum / 2);
    const dp = new Array(target + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
        for (let j = target; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[target]==target;
};

747 至少是其他数字两倍的最大数

刷题时间：2022-01-13

时间O(2n)

 var dominantIndex = function(nums) {
    let index = -1;
    let max =  Number.MIN_VALUE
    for(let i =0;i<nums.length;i++){
        if(nums[i]>max){
            max = nums[i];
            index = i;
        }
    }
    for(let i =0;i<nums.length;i++){
        if(max != nums[i] && max<nums[i]*2) return -1;
    }
    return index;
};

1049 最后一块石头的重量 II

刷题时间：2022-01-13

和上面416那题基本上一模一样，思路上，虽然我没想到，其实就是求分隔等和子集，分成两部分重量差最接近的，而不用管真的每一块去比较这样子，整体去思考

var lastStoneWeightII = function (stones) {
    const sum = stones.reduce((prev, curr) => prev + curr);
    const target = Math.floor(sum / 2);
    const dp = new Array(target + 1).fill(0);
    for (let i = 0; i < stones.length; i++) {
        for (let j = target; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }
    return sum - dp[target] * 2;
};

494 目标和

刷题时间：2022-01-13

背包01问题，但这个求的是方法的数量，而不是方法的最优解。这个说实话有点难以理解，比求方法的最优解困难一点点，但总体本质上都差不多。

var findTargetSumWays = function (nums, target) {
    const sum = nums.reduce((p, c) => p + c, 0);
    if ((sum + target) % 2 == 1) return 0;
    if (Math.abs(target) > sum) return 0; // 此时没有方案
    const tar = Math.floor((sum + target) / 2);
    // dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
    const dp = new Array(tar + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < nums.length; i++) {
        for (let j = tar; j >= nums[i]; j--) {
            // 不放就是上一个的dp[j]种方法数，放就是上一个dp[j-nums[i]]方法数，两者相加。
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[tar];
};

474 一和零

刷题时间：2022-01-14

背包01问题还是，只不过变成了两个01背包，所以需要再遍历两遍，分别是m和n两个维度，想dp这个定义应该是比较困难的，需要两个维度。

var findMaxForm = function (strs, m, n) {
    // dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))
    // dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
    // 遍历字符串
    for (let str of strs) {
        let oneNum = 0, zeroNum = 0;
        for (let c of str) {
            if (c == '0') zeroNum++;
            else oneNum++;
        }
        for (let i = m; i >= zeroNum; i--) {
            for (let j = n; j >= oneNum; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
            }
        }
    }
    return dp[m][n]
};

518 零钱兑换 II

刷题时间：2022-01-14

完全背包问题，完全背包的问题，就只用修改内循环的遍历顺序，从前往后遍历就行了，这样子一个东西就可以拿多遍。只不过这个不是完全的完全背包问题，因为求得是组合数量，这样子遍历顺序就会有点区别，求组合数的话，遍历还是原来的样子，外循环是物品的数量，内循环是目标。如果求的是排列数，调换一下这两个遍历顺序了。

var change = function (amount, coins) {
    // dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
};

228 汇总区间

刷题时间：2022-01-14

丢脸，自己找了一道简单题，居然没有写出来，被锤了，因为我没有去记录下标值，就这样子被锤烂了，我这个人啊，唉。

var summaryRanges = function (nums) {
    const result = [];
    let s = 0;
    for (let i = 1; i <= nums.length; i++) {
        if (nums[i - 1] !== nums[i] - 1) {
            let str = s !== i - 1 ? nums[s] + '->' + nums[i - 1] : nums[s] + '';
            result.push(str);
            s = i;
        }
    }
    return result;
};

1716 计算力扣银行的钱

刷题时间：2022-01-15

简单数学问题。

var totalMoney = function (n) {
    const week = Math.floor(n / 7);
    const arr = [0, 1, 3, 6, 10, 15, 21, 28]
    const day = n % 7;
    return (21 + day) * week + Math.floor(week * (week + 1) / 2 * 7) + arr[day];
};

377 组合总和 IV

刷题时间：2022-01-15

排列的问题，就是需要换一下内外循环的顺序，target放外面，n放里面

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

var combinationSum4 = function (nums, target) {
    const n = nums.length;
    const dp = new Array(target + 1).fill(0);
    dp[0] =1;
    for (let i = 0; i <= target; i++) {
        for (let j = 0; j < n; j++) {
            if (i < nums[j]) continue;
            dp[i] += dp[i - nums[j]]
        }
    }
    return dp[target]
};

279 完全平方数

刷题时间：2022-01-15

比之前那题还简单一点。空间可以再优化一下

var numSquares = function (n) {
    const arr = new Array(101).fill(0).map((_, i) => i * i);
    const dp = new Array(n + 1).fill(n + 1);
    dp[0] = 0;
    for (let i = 1; i <= arr.length; i++) {
        if (n < arr[i]) break;
        for (let j = arr[i]; j <= n; j++) {
            dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
        }
    }
    return dp[n];
};

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

382 链表随机节点

刷题时间：2022-01-16

直接抄袭，用数组保存就行了。

/**
 * @param {ListNode} head
 */
var Solution = function(head) {
    this.list = [];
    while (head != null) {
        this.list.push(head.val);
        head = head.next;
    }
};

/**
 * @return {number}
 */
Solution.prototype.getRandom = function() {
    return this.list[Math.floor(Math.random() * this.list.length)];
};

还有个空间O(1)，但是实际用处只是更拉胯的

var Solution = function(head) {
    this.head = head;
};

Solution.prototype.getRandom = function() {
    let i = 1, ans = 0;
    for (let node = this.head; node != null; node = node.next) {
        if (Math.floor(Math.random() * i) === 0) { // 1/i 的概率选中（替换为答案）
            ans = node.val;
        }
        ++i;
    }
    return ans;
};

337 打家劫舍 III

刷题时间：2022-01-16

树的动态规划，难上加难了，这还是入门级别的，慌了嗷

var rob = function (root) {
    // 返回值是长度为2的数组，前面表示不偷的金额，后面表示偷的金额
    const postOrder = node => {
        if (node == null) return [0, 0];
        const left = postOrder(node.left);
        const right = postOrder(node.right);
        const tou = node.val + left[0] + right[0];
        const butou = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [butou, tou]
    }
    const res = postOrder(root);
    return Math.max(res[0], res[1])
};

123 买卖股票的最佳时机 III

时间：2022-01-20

相当的麻烦，需要不同的表示

一天一共就有五个状态：0没有操作，1第一次买入，2第一次卖出，3第二次买入，4第二次卖出

dp[i][j]中 i表示第i天，j为 [0 – 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

var maxProfit = function (prices) {
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => new Array(5).fill(0));
    dp[0][1] = -prices[0];
    dp[0][3] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[i][0] = dp[i][0];
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i])
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i])
        dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i])
    }
    return dp[n - 1][4];
};

188 买卖股票的最佳时机 IV

刷题时间：2022-01-20

上一题的复杂体，注意总数是k*2+1就行

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

263 丑数

刷题时间：2022-01-20

简单题，还是错了两次，尿了。

var isUgly = function (n) {
    if (n <= 0) return false;
    while (n % 2 == 0) n = Math.floor(n / 2);
    while (n % 3 == 0) n = Math.floor(n / 3);
    while (n % 5 == 0) n = Math.floor(n / 5);
    return n == 1;
};

309 最佳买卖股票时机含冷冻期

刷题时间：2022-01-21

这个状态分法实在是有点复杂了，给我整不会了，所以这题就不会吧。

var maxProfit = function (prices) {
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => new Array(4).fill(0));
    dp[0][0] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
        dp[i][2] = dp[i - 1][0] + prices[i];
        dp[i][3] = dp[i - 1][2];
    }
    return Math.max(dp[n - 1][3], Math.max(dp[n - 1][1], dp[n - 1][2]));
};

674 最长连续递增序列

刷题时间：2022-01-21

贪心一波

var findLengthOfLCIS = function (nums) {
    let res = 1;
    let tmp = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) tmp++;
        else {
            res = Math.max(res, tmp);
            tmp = 1;
        }
    }
    return Math.max(res, tmp);
};

动态规划

var findLengthOfLCIS = function (nums) {
    let res=1;
    const dp = new Array(nums.length).fill(1);
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i + 1] > nums[i]) dp[i + 1] = dp[i] + 1;
        if (dp[i + 1] > res) res = dp[i + 1];
    }
    return res;
};

718 最长重复子数组

刷题时间：2022-01-21

正常二维数组

var findLength = function (nums1, nums2) {
    let res = 0;
    const dp = new Array(nums1.length + 1).fill(0).map(() => new Array(nums2.length + 1).fill(0));
    for (let i = 1; i <= nums1.length; i++) {
        for (let j = 1; j <= nums2.length; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            if (dp[i][j] > res) res = dp[i][j];
        }
    }
    return res;
};

滚动数组，注意事项，一定要从后往前滚动，这样子防止重复覆盖。而且不相等的时候要赋值为0

var findLength = function (nums1, nums2) {
    let res = 0;
    const dp = new Array(nums2.length + 1).fill(0);
    for (let i = 1; i <= nums1.length; i++) {
        for (let j = nums2.length; j >=1; j--) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[j] = dp[j - 1] + 1;
            }else dp[j]=0;
            if (dp[j] > res) res = dp[j];
        }
    }
    return res;
};