House Robber II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums
representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3] Output: 3
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
C++ House Robber II LeetCode Solution
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n < 2) return n ? nums[0] : 0;
return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
}
private:
int robber(vector<int>& nums, int l, int r) {
int pre = 0, cur = 0;
for (int i = l; i <= r; i++) {
int temp = max(pre + nums[i], cur);
pre = cur;
cur = temp;
}
return cur;
}
};
Java House Robber II LeetCode Solution
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]);
// 1st option: including the 1st and excluding the last house
int resultWithFirst = solve(nums, 0, nums.length - 2);
// 2nd option: excluding the 1st and including the last house
int resultWithLast = solve(nums, 1, nums.length - 1);
// Return the maximum of the two results
return Math.max(resultWithFirst, resultWithLast);
}
public int solve(int[] nums, int start, int end){
if(start == end) return nums[start];
// Array to store the maximum sum at the current iteration
// while traversing all houses
int money[] = new int[nums.length];
/* Base case */
money[start] = nums[start];
// At the 2nd house, we decide to rob
// either the 1st house or the 2nd
// This is the core idea of the transition function
money[start + 1] = Math.max(nums[start + 1], nums[start]);
for (int i = start + 2; i <= end; ++i)
/* At ith house we have two options:
1. not rob it, keeping the money from the (i-1)th house
2. rob it after the (i-2)th house, skipping the (i-1)th house
We choose the one that gives the max amount */
money[i] = Math.max(money[i - 1], money[i - 2] + nums[i]);
// Return the sum that we have at the last house
return money[end];
}
}
Python 3 House Robber II LeetCode Solution
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def simple_rob(nums, i, j):
rob, not_rob = 0, 0
for idx in range(i, j):
num = nums[idx]
rob, not_rob = not_rob + num, max(rob, not_rob)
return max(rob, not_rob)
if not nums:
return 0
elif len(nums) == 1:
return nums[0]
else:
n = len(nums)
return max(simple_rob(nums, 1, n), simple_rob(nums, 0, n-1))
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below