代码随想录二刷day48

这篇具有很好参考价值的文章主要介绍了代码随想录二刷day48。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章来源地址https://www.toymoban.com/news/detail-728264.html


前言


一、力扣198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i ++){
            dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[dp.length-1];
    }
}

二、力扣213. 打家劫舍 II

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        int a = fun(nums, 0, nums.length-2);
        int b = fun(nums, 1, nums.length-1);
        return Math.max(a,b);

    }
    public int fun(int[] nums, int start, int end){
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start+1]);
        for(int i = start+2; i <= end; i ++){
            dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[end];
    }
}

三、力扣337. 打家劫舍 III

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = fun(root);
        return Math.max(res[0], res[1]);
    }
    public int[] fun(TreeNode root){
        int[] arr = new int[2];
        if(root == null){
            return arr;
        }
        //0不偷, 1 偷
        int[] left = fun(root.left);
        int[] right = fun(root.right);
        arr[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        arr[1] = root.val + left[0] + right[0];
        return arr;
    }
}

到了这里,关于代码随想录二刷day48的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录二刷day01

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 使用左闭右闭区间的二分查找时, 最后low一定是被查找元素的插入位置,若查找的数带小数,low-1, 便是最终结果 1、左闭右闭 2、左闭右开

    2024年02月12日
    浏览(53)
  • 二刷代码随想录——动态规划day40

    一个本硕双非的小菜鸡,备战24年秋招,计划二刷完卡子哥的刷题计划,加油! 二刷决定精刷了,于是参加了卡子哥的刷题班,训练营为期60天,我一定能坚持下去,迎来两个月后的脱变的,加油! 推荐一手卡子哥的刷题网站,感谢卡子哥。代码随想录 终于来到了守关boss。

    2024年03月11日
    浏览(55)
  • 代码随想录Day_48打卡

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你  不触

    2024年02月11日
    浏览(40)
  • 代码随想录Day20 回溯算法 LeetCode77 组合问题

    以下内容更详细解释来自于:代码随想录 (programmercarl.com) 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实 有递归就有回溯 ,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能解决哪些问题.

    2024年02月08日
    浏览(50)
  • 代码随想录二刷 day06 | 哈希表之 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

    哈希表能解决什么问题呢?一般哈希表都是用来快速判断一个元素是否出现集合里。 242.有效的字母异位词 题目链接 解题思路: 题目的意思就是 判断两个字符串是否由相同字母组成。 字符a到字符z的ASCII是26个连续的数值,所以字符a映射为下标0,相应的字符z映射为下标25。

    2024年02月07日
    浏览(47)
  • 代码随想录二刷 |回溯 |分割回文串

    131.分割回文串 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ] 回溯三部曲 递归函数参数 全局变量数组path存放切割后回文的子串,二维数组result存放结果集 参数

    2024年01月24日
    浏览(72)
  • 代码随想录Day1 | 数组01- leetcode 704、27

    题目链接:二分查找 关键问题:         - 边界(left、right)、当前查找值(middle)                 - target大于当前查找值 -- 当前查找区域的右边,更改区间left                 - target小于当前查找值 -- 当前查找区域的左边,更改区间right                 - middle的计

    2024年02月16日
    浏览(43)
  • 代码随想录刷题第48天|LeetCode198打家劫舍、LeetCode213打家劫舍II、LeetCode337打家劫舍III

    1、LeetCode198打家劫舍 题目链接:198、打家劫舍 1、dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i] 。 2、递推公式: 如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ; 如果不偷第i房间,那么dp[i] = dp[i - 1]; 然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1

    2024年02月08日
    浏览(58)
  • 代码随想录Day3 | 链表01-leetcode203、707、206

    题目链接:移除链表元素 思路: 链表中元素的添加和删除关键是要 保证不断链且指向关系正确 。对于删除操作,链的修改涉及将待删除元素的前一个元素指向待删除元素的后一个元素,因此在判断当前元素是否需要删除时,要记录当前元素的前后指针。 1.删除头结点时另作

    2024年02月16日
    浏览(63)
  • 代码随想录二刷-哈希表-几数之和 (JS)

    题目 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果

    2023年04月18日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包