打家劫舍系列

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

打家劫舍系列,算法,leetcode,数据结构

class Solution {
public:
    int dp[105];
    //dp[i]表示偷取前i个房间获取的最大值
    int rob(vector<int>& nums) {
    //    // dp[i][0];不偷取第i间房,偷取前i-1间房的最大值
    //     //dp[i][1];偷取第i间房,偷取前i间房的最大值
    //     memset(dp,0,sizeof(dp));
    //     dp[0][0]=0;
    //     dp[0][1]=nums[0];
    //     for(int i=1;i<nums.size();i++){
    //             dp[i][1]=max(dp[i-1][0]+nums[i],dp[i][1]);
    //             dp[i][0]=max(dp[i][0],max(dp[i-1][0],dp[i-1][1]));

    //     }
    //     int n=nums.size()-1;
    //     return max(dp[n][0],dp[n][1]);
     memset(dp,0,sizeof(dp));
    if(nums.size()<=1) return nums[0];
    dp[0]=nums[0];
    dp[1]=max(nums[0],nums[1]);
    for(int i=2;i<nums.size();i++)
    {
        dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
    }
     int n=nums.size()-1;
    return dp[n];
    }
};

打家劫舍系列,算法,leetcode,数据结构

class Solution {
public:
     int dp[105];
    int rob(vector<int>& nums) {
        //考虑0——n-2
         memset(dp,0,sizeof(dp));
          int n=nums.size();
          if(n<=1)
          {
              return nums[0];
          }
         dp[0]=nums[0];
         dp[1]=nums[0];
        
         for(int i=2;i<n;i++)
         {
             if(i!=n-1)
             {
                 dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
             }
             else{
                 dp[i]=max(dp[i-1],dp[i-2]);
             }
         }    
         int res1=dp[n-1];
         memset(dp,0,sizeof(dp));
          //考虑1——n-1
         dp[0]=0;
         dp[1]=nums[1];
        for(int i=2;i<n;i++)
         {
              dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
       
             
         }
         int res=max(res1,dp[n-1]);
         return res;
    }
};

打家劫舍系列,算法,leetcode,数据结构

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> dfs(TreeNode* root)
    {
        vector<int>res;
        vector<int>s1(2,0);
        vector<int>s2(2,0);
        //val表示偷根节点
        int val=root->val;
        //val0表示不偷根节点
        int val0=0;
     
        if(root->left!=NULL)
        {
             s1=dfs(root->left);
             val0+=max(s1[0],s1[1]);
             val+=s1[1];
        }
        if(root->right!=NULL)
        {
            s2=dfs(root->right);
            val0+=max(s2[0],s2[1]);
            val+=s2[1];
        }
        res.push_back(val);
        res.push_back(val0);
        return res;
    }
    int rob(TreeNode* root) {
        vector<int>res;
        res= dfs(root);
        return max(res[0],res[1]);
    }
};

打家劫舍系列,算法,leetcode,数据结构

 文章来源地址https://www.toymoban.com/news/detail-608818.html

class Solution {
public:
    int dp[100005];
    int minCapability(vector<int>& nums, int k) {
        int right=*max_element(nums.begin(),nums.end());
          if(nums.size()==1)
            {
                return nums[0];
            }
        int left=0;
        while(left+1<right)
        {
            int mid=(left+right)/2;
            memset(dp,0,sizeof(dp));
            //dp[i]表示前i个房间窃取最大金额为mid的最大房间数
          
            if(nums[0]>mid)
            {
                dp[0]=0;
            }
            else{
                 dp[0]=1;
            }
            if(nums[1]<=mid && dp[0]==0)
            {
                dp[1]=1;
            }
            else{
                dp[1]=dp[0];
            }
            
            for(int i=2;i<nums.size();i++)
            {
                if(nums[i]>mid)
                {
                    dp[i]=max(dp[i-1],dp[i-2]);
                }
                else{
                    dp[i]=max(dp[i-2]+1,dp[i-1]);
                }
            }
            // int x0=0;//
            // int x1=0;//前i位取得的最大值
            // for(int i=0;i<nums.size();i++)
            // {
            //    if(nums[i]>mid) x0=x1;
            //    else{
            //        int t=x1;
            //        x1=max(x0+1,t);
            //        x0=t;
            //    }
            // }
            int x1=dp[nums.size()-1];
            if(x1>=k)
            {
                right=mid;
            }
            else{
                left=mid;
            }
        }
        return right;
        // = *max_element(nums.begin(), nums.end());
    }
};

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

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

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

相关文章

  • 【LeetCode题目详解】第九章 动态规划part09 198.打家劫舍 213.打家劫舍II 337.打家劫舍III(day48补)

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

    2024年02月09日
    浏览(46)
  • LeetCode - 198 打家劫舍

    目录 题目来源 题目描述 示例 提示 题目解析 算法源码 题目来源 198. 打家劫舍 - 力扣(LeetCode) 题目描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在

    2023年04月08日
    浏览(32)
  • LeetCode198.打家劫舍

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

    2024年03月12日
    浏览(89)
  • 算法训练第四十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

    题目链接:198.打家劫舍 参考:https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入

    2023年04月16日
    浏览(40)
  • leetcode 打家劫舍(dp)

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

    2024年02月08日
    浏览(40)
  • 打家劫舍系列

     

    2024年02月15日
    浏览(39)
  • LeetCode 337. 打家劫舍 III

    原题链接:. - 力扣(LeetCode) 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为  root  。 除了  root  之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 

    2024年04月15日
    浏览(33)
  • leetcode hot100 打家劫舍

    本题中,依旧可以发现,当前位置的金额受到前两个位置金额是否被偷的影响,所以这明显是动态规划的问题。 我们采用动态规划五部曲来进行做 首先我们确定dp数组的含义:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。 注意,这里是考虑!那么就说明我这

    2024年02月19日
    浏览(38)
  • leetcode 213. 打家劫舍 II

             本题是 打家劫舍 的进阶版,房屋之间形成一个环了,也就是第一个房屋和最后一个房屋不能一起偷了。那么能偷的情况分为下列三种: 不考虑偷首房间。 不考虑偷尾房间。 不考虑偷首尾房间。         第三种情况包含于第一和第二种情况了,所以分别为第一种

    2024年02月12日
    浏览(35)
  • leetcode 2560. 打家劫舍 IV

    2560. 打家劫舍 IV 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统,所以小偷  不会窃取相邻的房屋  。 小偷的  窃取能力  定义为他在窃取过程中能从单间房屋中窃取的  最大金

    2024年02月07日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包