FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/algorithms/cpp/houseRobber/houseRobber.II.cpp at master · wcoder0/leetcode · GitHub
wcoder0
leetcode
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
houseRobber
/
houseRobber.II.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
57 lines (51 loc) · 1.92 KB
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
houseRobber
/
houseRobber.II.cpp
Copy path
File metadata and controls
57 lines (51 loc) · 1.92 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//
Source : https://leetcode.com/problems/house-robber-ii/
//
Author : Hao Chen
//
Date : 2015-06-10
/*
*********************************************************************************
*
* 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.
*
* Credits:Special thanks to @Freezen for adding this problem and creating all test cases.
*
*********************************************************************************
*/
class
Solution
{
public:
int
orginal_rob
(vector<
int
> &money,
int
start,
int
end) {
int
n2=
0
;
int
n1=
0
;
for
(
int
i=start; i<end; i++){
int
current =
max
(n1, n2 + money[i]);
n2 = n1;
n1 = current;
}
return
n1;
}
int
rob
(vector<
int
>& nums) {
int
n = nums.
size
();
switch
(n) {
case
0
:
return
0
;
case
1
:
return
nums[
0
];
case
2
:
return
max
(nums[
0
], nums[
1
]);
default
:
/*
* the idea is we cannot rob[0] and rob[n-1] at same time
* so, we rob [0 .. n-2] or [1 .. n-1], can return the maxinum one.
*/
int
m1 =
orginal_rob
(nums,
0
, n-
1
);
int
m2 =
orginal_rob
(nums,
1
, n);
return
max
(m1, m2);
}
}
};
Back
|
FazBrowse Home
|
New Git URL