Solution to House Robber II by LeetCode

3 Feb

February 3, 2016 Sheng 2

Question: https://leetcode.com/problems/house-robber-ii/

Question Name: House Robber II

This is a variant of House Robber. We need to apply the previous solution to two sub-arrays and return the maximum of the two results:

1. Do not use the first element, and we can safely consider (may or may not use) the last element (case #1);

2. Oppositely, consider (may or may not use) the first element, and ignore the last element. If the first item was used (case #2a), it is reasonable to ignore the last item. Otherwise (case #2b), case #2b and case #1 share the same leading elements. But case #1 has one more element at the end, therefore case #1 always has an equal-or-larger result.

Totally we need the max(case #1, case #2a, case #2b) = max(case #1, case #2).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution(object):

# @param {integer[]} nums

# @return {integer}

def rob_helper(self, nums):

if len(nums) == 0: return 0

if len(nums) <= 2: return max(nums)

max_money = [0] * len(nums)

max_money[0] = nums[0]

max_money[1] = max(nums[0], nums[1])

for house in xrange(2, len(nums)):

max_money[house] = max(max_money[house-1],

max_money[house-2]+nums[house])

return max_money[-1]

def rob(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums) == 0: return 0

if len(nums) <= 3: return max(nums)

return max(self.rob_helper(nums[1:]), self.rob_helper(nums[:-1]))

2 Replies to “Solution to House Robber II by LeetCode”

Just want to stop by and say hi ^_^

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

#include <vector>

#include <algorithm>

using namespace std;

class SolutionHouseRobber2

{

public:

int rob(const vector<int>& nums)

{

int len = nums.size();

if (0 == len)return 0;

long long last1 = nums[0], last2 = 0LL;

long long maxVal1 = nums[0], maxVal2 = 0LL;

for (int i = 1; i < len - 1; last2 = last1, last1 = maxVal1, ++i)

maxVal1 = std::max(last2 + nums[i], last1);

if (len > 1)

{

last1 = nums[1], last2 = 0LL, maxVal2 = nums[1];

for (int i = 2; i < len; last2 = last1, last1 = maxVal2, ++i)

maxVal2 = std::max(last2 + nums[i], last1);

}

return std::max(maxVal1, maxVal2);

}

};

public:

Sheng says:
May 11, 2016 at 7:20 pm
Hello, welcome back :—-)
Reply

Leave a Reply Cancel reply

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Fabien November 7, 2024 at 4:42 am on Unofficial Solutions to the Training by CodilitySimilar but more compact solution using C++17 or later: #include <stack> #include <vector> using namespace std; using point = pair<int, int>; stack<point> pending; void explore(const...
Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...