- 浏览: 183417 次
- 性别:
- 来自: 济南
文章分类
最新评论
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
House Robber的变形题目,在这个题目中要求收尾两个元素不可以同时选择。我们可以分为两种情况,第一种情况是选择了第一个元素,那么最后一个元素肯定不能选,我们求出这种情况下的最大值max1;第二种情况是不选择第一个元素,那么最后一个元素可以选择,我们同样求出这种情况的下的最大值max2,然后我们返回max1和max2中较大者即可。代码如下:
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
House Robber的变形题目,在这个题目中要求收尾两个元素不可以同时选择。我们可以分为两种情况,第一种情况是选择了第一个元素,那么最后一个元素肯定不能选,我们求出这种情况下的最大值max1;第二种情况是不选择第一个元素,那么最后一个元素可以选择,我们同样求出这种情况的下的最大值max2,然后我们返回max1和max2中较大者即可。代码如下:
public class Solution { public int rob(int[] nums) { if(nums == null || nums.length == 0) return 0; if(nums.length == 1) return nums[0]; if(nums.length == 2) return Math.max(nums[0], nums[1]); int max = 0; int[] dp = new int[nums.length]; dp[1] = nums[0]; for(int i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]); } max = dp[nums.length - 1]; Arrays.fill(dp, 0); dp[1] = nums[1]; for(int i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return Math.max(max, dp[nums.length - 1]); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 265Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 267You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 384Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 374Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 497Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 563Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 475Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 664Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 469The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 429Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 575Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 580Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 426All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 898Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 929Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 672Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 842Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 782You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 704For a undirected graph with tre ...
相关推荐
HouseRobber-问题-LeetCode- @Faizansayeed28 代码 /** * 问题陈述- 你是一名职业劫匪,计划抢劫街道上的房屋。 每个房子都有一定数量的钱 藏起来,阻止你抢劫他们的唯一限制是相邻的房子有安全系统 连接,如果同一...
python python_leetcode题解之213_House_Robber_II.py
在本题中,我们讨论了两个经典的动态规划问题,分别是“House Robber II”(#213)和“Triangle”(#120)。这两个问题都涉及到寻找最优策略,通过迭代计算求解。 1. **House Robber II**: 这个问题是“House ...
python python_leetcode题解之198_House_Robber.py
c c语言_leetcode题解之0337_house_robber_iii
标题 "house_robber_family_problems" 暗示我们正在处理一个与计算机科学和编程相关的挑战,可能是算法问题或编程竞赛的题目。这个题目可能源自经典的“打家劫舍”(House Robber)系列问题,这是一个在算法设计中...
在这个场景中,"Roberry_house_dynamicprogramming_源码" 提到的是一个关于房屋盗窃问题的动态规划解决方案,通常被称为“House Robber”问题。这个问题源于LeetCode等在线编程挑战平台,旨在锻炼程序员的逻辑思维和...
leetcode 和 oj OJ_Solution Solutions for OJ such as leetcode, poj and so on 版本 修改日期 修改人 1 2015-04-16 skymoney ==== ...java/houserobber https://leetcode.com/problems/house-robber/
lru cache leetcode LeetCode copy and think 加油学习 1. 时间轴 时间 题目 描述 知识点 ...House Robber 动态规划 如何确定子问题 20200525 20200525 20200525 20200525 20200525 20200525 $1 234
198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 (Lintcode)92.Backpack, (Lintcode)125.Backpack II, (Lintcode)564.Backpack VI 不适用 53....
House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. Palindromic Substrings [647]9. Maximum Length of Pair Chain [646]10. Integer Break [343]11. Count Numbers with Unique ...
lru cache leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 ...House Robber 213 打家劫舍Ⅱ
House Robber 学会了数组的创建,以及动态规划最基本的题目 2021.2.2 322 兑换钱币 学会了 Arrays.fill 的使用,以及查看源码,返回 记录在哔哩哔哩 中 2021.2.3 53 最大子数字之和 先更新max,再将负数赋值为0 62 ...
编码实践 编码实践 模式:二进制搜索: 二进制搜索 二进制搜索: : 排序数组的上限: : ... 众议院强盗2: ://leetcode.com/problems/house-robber-ii/discuss/59921/9-lines-0ms-O(1)-Space-C++-sol
本压缩包中的内容是针对LeetCode平台上的第198题“打家劫舍”(House Robber)的Python解决方案。 “打家劫舍”是一道经典的动态规划问题,其核心在于寻找最优策略,即在不触动相邻房屋的情况下,最大化抢劫的财富...
HouseRobber(#198), ClimbingStairs(#70), CoinChange(#322), EditDistance(#72) 图 : 集合的合并(直接求并、按大小求并和按深度求并)、根搜寻(路径压缩) : 有向图和无向图的邻接表表示方法 : 图的深度优先和广度...
本题解将深入探讨第198题“打家劫舍”(House Robber),这是一个典型的动态规划问题,对于理解该算法模式及其应用至关重要。 动态规划是一种解决最优化问题的方法,通过将大问题分解为更小的子问题来求解。在这个...
在LeetCode平台上,第337题“打家劫舍III”(House Robber III)是一道涉及深度优先搜索(DFS)和树结构的经典算法题。这道题目要求我们通过Python编程来解决一个树形结构下的抢劫问题,旨在考察我们对递归、树遍历...
1. LeetCode 198:House Robber(打家劫舍) - 这是一个经典的动态规划问题,目标是确定在一个房子列表中,不相邻的房子可以被抢劫的最大金额。需要提交代码并附上运行结果截图。 2. LeetCode 349:Intersection ...