- 浏览: 173258 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 224You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 340Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 449Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 509Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 529Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 859Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 627For a undirected graph with tre ...
相关推荐
HouseRobber-问题-LeetCode- @Faizansayeed28 代码 /** * 问题陈述- 你是一名职业劫匪,计划抢劫街道上的房屋。 每个房子都有一定数量的钱 藏起来,阻止你抢劫他们的唯一限制是相邻的房子有安全系统 连接,如果同一...
House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of 1 Bits Gray Code Single Number Single ...
house_robber_family_problems
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
HouseRobber(#198), ClimbingStairs(#70), CoinChange(#322), EditDistance(#72) 图 : 集合的合并(直接求并、按大小求并和按深度求并)、根搜寻(路径压缩) : 有向图和无向图的邻接表表示方法 : 图的深度优先和广度...