首页 > 编程语言 >代码随想录算法训练营第45天 | 198.打家劫舍 、213.打家劫舍II 、337.打家劫舍III

代码随想录算法训练营第45天 | 198.打家劫舍 、213.打家劫舍II 、337.打家劫舍III

时间:2024-06-23 23:43:01浏览次数:26  
标签:node 198 nums 随想录 https 打家劫舍 com dp

今天就是打家劫舍的一天,这个系列不算难,大家可以一口气拿下。

198.打家劫舍
视频讲解:https://www.bilibili.com/video/BV1Te411N7SX
https://programmercarl.com/0198.打家劫舍.html

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i=2;i<nums.length;i++) {
        dp[i] = Math.max(dp[i-2]+ nums[i], dp[i-1] );
    }

    return dp[nums.length-1];
};

213.打家劫舍II
视频讲解:https://www.bilibili.com/video/BV1oM411B7xq
https://programmercarl.com/0213.打家劫舍II.html

在一的基础上变了下
var numsDp = function(nums) {
    const dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i=2;i<nums.length;i++) {
        dp[i] = Math.max(dp[i-2]+ nums[i], dp[i-1] );
    }

    return dp[nums.length-1];
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 1) return nums[0]
    const nums1 = numsDp(nums.slice(0, nums.length - 1));
    const nums2 = numsDp(nums.slice(1, nums.length));
    return Math.max(nums1, nums2);
};

337.打家劫舍III
视频讲解:https://www.bilibili.com/video/BV1H24y1Q7sY
https://programmercarl.com/0337.打家劫舍III.html

树形dp
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const backtracing = (node) => {
        if (node === null) {
            return [0, 0];
        }
        let leftDp = backtracing(node.left);
        let rightDp = backtracing(node.right);

        const dp = [];
        dp[0] = Math.max(leftDp[1],leftDp[0]) + Math.max(rightDp[1],rightDp[0]);
        dp[1] = leftDp[0] + rightDp[0] + node.val;
        return dp;
    }

    const dpRoot = backtracing(root);
    return Math.max(dpRoot[0],dpRoot[1]);
};

标签:node,198,nums,随想录,https,打家劫舍,com,dp
From: https://www.cnblogs.com/yuanyf6/p/18264158

相关文章

  • 代码随想录DAY2|有序数组的平方|长度最小的子数组|螺旋矩阵II
    有序数组的平方有序数组的平方解题思路最优的解法是通过双指针,由于该数组是一个非递减数列,我们只需要将数组的首尾两端作为两个指针的起始位置,然后进行比较就行。具体地讲,双指针所指向的值相互比较,把较大的值放入新的数组的开通,然后该指针往前(如果是在首端的指针,则往后)。重复这......
  • 代码随想录算法训练营第18天 | 、98验证二叉树、700. 二叉搜索树中的搜索
    代码随想录算法训练营第20天|654.最大二叉树https://leetcode.cn/problems/maximum-binary-tree/654.最大二叉树代码随想录https://programmercarl.com/0654.最大二叉树.html617.合并二叉树https://leetcode.cn/problems/merge-two-binary-trees/description/617.合并二......
  • 代码随想录63——二叉树4——迭代遍历
    ......
  • 代码随想录第13天 | 二叉树part01 基础和遍历
    二叉树基础知识二叉树种类满二叉树满二叉树:如果一棵二叉树只有度为0和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树(子节点要么为0,要么为2)若满二叉树的深度为k(即k层,从1开始),则其节点个数为:2^k-1完全二叉树完全二叉树:从上到下,从左到右,都是连续的。满二叉树一......
  • 代码随想录算法训练营第十四天 | 226.翻转二叉树 101.对称二叉树 104.二叉树的最大深
    226.翻转二叉树题目:给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。解题:思路:遍历的过程中交换每个节点的左右孩子。选择哪种遍历方式?中序不行,左中右,左边子节点交换完,处理中间交换了左节点和右节点,再处理右节点去交换时这个右节点就是原来的左节点,所以有一边就一......
  • Day57 代码随想录打卡|二叉树篇---修建二叉搜索树
    题目(leecodeT669):给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low,high]中。修剪树 不应该 改变保留在树中的元素的相对结构(即,如果没有被移除,原有的父代子代关系都应当保留)。可以证明,存在 唯一的答......
  • 代码随想录Day1-二分查找法|快慢指针
    二分查找题目链接二分查找是一个较为基础的查找方式,对一个有序没有重复值的数组进行查找时,能够提供一个较好的时间复杂度\(O(log(n))\)算法概要对于有序并且没有重复值的数组来说,我们可以首先选定整个数组的中间下标,它的值则称为中间值,通过它把大数组分成两个小的数组,其中一个......
  • 代码随想录算法训练营第17天 | 二叉树04
    代码随想录算法训练营第17天找树左下角的值https://leetcode.cn/problems/find-bottom-left-tree-value/找树左下角的值代码随想录https://leetcode.cn/problems/find-bottom-left-tree-value/路径总和https://leetcode.cn/problems/path-sum/description/路径总和2https......
  • 代码随想录刷题复习day01
    day01数组-二分查找classSolution{publicintsearch(int[]nums,inttarget){//左闭右闭intleft=0;intright=nums.length-1;intmid=0;while(right>=left){mid=left+(right-le......
  • Day56 代码随想录打卡|二叉树篇---删除二叉搜索树中的节点
    题目(leecodeT450):给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。一般来说,删除节点可分为两个步骤:首先找到需要删除的节点;如果找到了,删除它。方法:二叉搜索......