Skip to content

Commit a3bd72c

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lc problems: No.0198,0213
1 parent 075480f commit a3bd72c

File tree

14 files changed

+190
-297
lines changed

14 files changed

+190
-297
lines changed

‎README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -162,14 +162,14 @@
162162
- [第 N 个泰波那契数](./solution/1100-1199/1137.N-th%20Tribonacci%20Number/README.md)
163163
- [爬楼梯](./solution/0000-0099/0070.Climbing%20Stairs/README.md)
164164
- [使用最小花费爬楼梯](./solution/0700-0799/0746.Min%20Cost%20Climbing%20Stairs/README.md)
165+
- [打家劫舍](./solution/0100-0199/0198.House%20Robber/README.md)
166+
- [打家劫舍 II](./solution/0200-0299/0213.House%20Robber%20II/README.md)
165167
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
166168
- [最大子序和](./solution/0000-0099/0053.Maximum%20Subarray/README.md)
167169
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
168170
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
169171
- [解码方法](./solution/0000-0099/0091.Decode%20Ways/README.md)
170172
- [乘积最大子序列](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README.md)
171-
- [打家劫舍](./solution/0100-0199/0198.House%20Robber/README.md)
172-
- [打家劫舍 II](./solution/0200-0299/0213.House%20Robber%20II/README.md)
173173
- [最长上升子序列](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)
174174
- [俄罗斯套娃信封问题](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README.md)
175175
- [最长公共子序列](./solution/1100-1199/1143.Longest%20Common%20Subsequence/README.md)

‎README_EN.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -156,13 +156,13 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
156156
- [N-th Tribonacci Number](./solution/1100-1199/1137.N-th%20Tribonacci%20Number/README_EN.md)
157157
- [Climbing Stairs](./solution/0000-0099/0070.Climbing%20Stairs/README_EN.md)
158158
- [Min Cost Climbing Stairs](./solution/0700-0799/0746.Min%20Cost%20Climbing%20Stairs/README_EN.md)
159+
- [House Robber](./solution/0100-0199/0198.House%20Robber/README_EN.md)
160+
- [House Robber II](./solution/0200-0299/0213.House%20Robber%20II/README_EN.md)
159161
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
160162
- [Maximum Subarray](./solution/0000-0099/0053.Maximum%20Subarray/README_EN.md)
161163
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
162164
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)
163165
- [Maximum Product Subarray](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README_EN.md)
164-
- [House Robber](./solution/0100-0199/0198.House%20Robber/README_EN.md)
165-
- [House Robber II](./solution/0200-0299/0213.House%20Robber%20II/README_EN.md)
166166
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)
167167
- [Russian Doll Envelopes](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md)
168168
- [Longest Common Subsequence](./solution/1100-1199/1143.Longest%20Common%20Subsequence/README_EN.md)

‎solution/0100-0199/0198.House Robber/README.md

Lines changed: 19 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -54,16 +54,10 @@
5454
```python
5555
class Solution:
5656
def rob(self, nums: List[int]) -> int:
57-
def robRange(nums, start, end):
58-
if end - start == 0:
59-
return nums[start]
60-
pre, cur = 0, nums[start]
61-
for i in range(start + 1, end + 1):
62-
pre, cur = cur, max(pre + nums[i], cur)
63-
return cur
64-
if not nums:
65-
return 0
66-
return robRange(nums, 0, len(nums) - 1)
57+
a, b = 0, nums[0]
58+
for num in nums[1:]:
59+
a, b = b, max(num + a, b)
60+
return b
6761
```
6862

6963
### **Java**
@@ -72,24 +66,18 @@ class Solution:
7266

7367
```java
7468
class Solution {
75-
public int rob(int[] nums) {
76-
int n;
77-
if ((n = nums.length) == 0) return 0;
78-
return robRange(nums, 0, n - 1);
79-
}
80-
81-
private int robRange(int[] nums, int start, int end) {
82-
if (end - start == 0) return nums[start];
83-
int pre = 0;
84-
int cur = nums[start];
85-
for (int i = start + 1; i < end + 1; ++i) {
86-
int t = Math.max(pre + nums[i], cur);
87-
pre = cur;
88-
cur = t;
69+
public:
70+
int rob(vector<int>& nums) {
71+
int n = nums.size();
72+
int a = 0, b = nums[0];
73+
for (int i = 1; i < n; ++i) {
74+
int c = max(nums[i] + a, b);
75+
a = b;
76+
b = c;
8977
}
90-
return cur;
78+
return b;
9179
}
92-
}
80+
};
9381
```
9482

9583
### **C++**
@@ -122,26 +110,15 @@ private:
122110
123111
```go
124112
func rob(nums []int) int {
125-
n := len(nums)
126-
if n == 0 {
127-
return 0
113+
a, b, n := 0, nums[0], len(nums)
114+
for i := 1; i < n; i++ {
115+
a, b = b, max(nums[i] + a, b)
128116
}
129-
return robRange(nums, 0, n - 1)
130-
}
131-
132-
func robRange(nums[]int, start int, end int) int {
133-
if end - start == 0 {
134-
return nums[start]
135-
}
136-
pre, cur := 0, nums[start]
137-
for i := start + 1; i < end + 1; i++ {
138-
pre, cur = cur, max(pre + nums[i], cur)
139-
}
140-
return cur
117+
return b
141118
}
142119
143120
func max(a, b int) int {
144-
if (a > b) {
121+
if a > b {
145122
return a
146123
}
147124
return b

‎solution/0100-0199/0198.House Robber/README_EN.md

Lines changed: 22 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -45,38 +45,24 @@ Total amount you can rob = 2 + 9 + 1 = 12.
4545
```python
4646
class Solution:
4747
def rob(self, nums: List[int]) -> int:
48-
def robRange(nums, start, end):
49-
if end - start == 0:
50-
return nums[start]
51-
pre, cur = 0, nums[start]
52-
for i in range(start + 1, end + 1):
53-
pre, cur = cur, max(pre + nums[i], cur)
54-
return cur
55-
if not nums:
56-
return 0
57-
return robRange(nums, 0, len(nums) - 1)
48+
a, b = 0, nums[0]
49+
for num in nums[1:]:
50+
a, b = b, max(num + a, b)
51+
return b
5852
```
5953

6054
### **Java**
6155

6256
```java
6357
class Solution {
6458
public int rob(int[] nums) {
65-
int n;
66-
if ((n = nums.length) == 0) return 0;
67-
return robRange(nums, 0, n - 1);
68-
}
69-
70-
private int robRange(int[] nums, int start, int end) {
71-
if (end - start == 0) return nums[start];
72-
int pre = 0;
73-
int cur = nums[start];
74-
for (int i = start + 1; i < end + 1; ++i) {
75-
int t = Math.max(pre + nums[i], cur);
76-
pre = cur;
77-
cur = t;
59+
int a = 0, b = nums[0];
60+
for (int i = 1; i < nums.length; ++i) {
61+
int c = Math.max(nums[i] + a, b);
62+
a = b;
63+
b = c;
7864
}
79-
return cur;
65+
return b;
8066
}
8167
}
8268
```
@@ -87,22 +73,14 @@ class Solution {
8773
class Solution {
8874
public:
8975
int rob(vector<int>& nums) {
90-
int n;
91-
if ((n = nums.size()) == 0) return 0;
92-
return robRange(nums, 0, n - 1);
93-
}
94-
95-
private:
96-
int robRange(vector<int>& nums, int start, int end) {
97-
if (end - start == 0) return nums[start];
98-
int pre = 0;
99-
int cur = nums[start];
100-
for (int i = start + 1; i < end + 1; ++i) {
101-
int t = max(pre + nums[i], cur);
102-
pre = cur;
103-
cur = t;
76+
int n = nums.size();
77+
int a = 0, b = nums[0];
78+
for (int i = 1; i < n; ++i) {
79+
int c = max(nums[i] + a, b);
80+
a = b;
81+
b = c;
10482
}
105-
return cur;
83+
return b;
10684
}
10785
};
10886
```
@@ -111,26 +89,15 @@ private:
11189
11290
```go
11391
func rob(nums []int) int {
114-
n := len(nums)
115-
if n == 0 {
116-
return 0
92+
a, b, n := 0, nums[0], len(nums)
93+
for i := 1; i < n; i++ {
94+
a, b = b, max(nums[i] + a, b)
11795
}
118-
return robRange(nums, 0, n - 1)
119-
}
120-
121-
func robRange(nums[]int, start int, end int) int {
122-
if end - start == 0 {
123-
return nums[start]
124-
}
125-
pre, cur := 0, nums[start]
126-
for i := start + 1; i < end + 1; i++ {
127-
pre, cur = cur, max(pre + nums[i], cur)
128-
}
129-
return cur
96+
return b
13097
}
13198
13299
func max(a, b int) int {
133-
if (a > b) {
100+
if a > b {
134101
return a
135102
}
136103
return b

‎solution/0100-0199/0198.House Robber/Solution.cpp

Lines changed: 7 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,13 @@
11
class Solution {
22
public:
33
int rob(vector<int>& nums) {
4-
int n;
5-
if ((n = nums.size()) == 0) return 0;
6-
return robRange(nums, 0, n - 1);
7-
}
8-
9-
private:
10-
int robRange(vector<int>& nums, int start, int end) {
11-
if (end - start == 0) return nums[start];
12-
int pre = 0;
13-
int cur = nums[start];
14-
for (int i = start + 1; i < end + 1; ++i) {
15-
int t = max(pre + nums[i], cur);
16-
pre = cur;
17-
cur = t;
4+
int n = nums.size();
5+
int a = 0, b = nums[0];
6+
for (int i = 1; i < n; ++i) {
7+
int c = max(nums[i] + a, b);
8+
a = b;
9+
b = c;
1810
}
19-
return cur;
11+
return b;
2012
}
2113
};

‎solution/0100-0199/0198.House Robber/Solution.go

Lines changed: 5 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,13 @@
11
func rob(nums []int) int {
2-
n := len(nums)
3-
if n == 0 {
4-
return 0
2+
a, b, n := 0, nums[0], len(nums)
3+
for i := 1; i < n; i++ {
4+
a, b = b, max(nums[i] + a, b)
55
}
6-
return robRange(nums, 0, n - 1)
7-
}
8-
9-
func robRange(nums[]int, start int, end int) int {
10-
if end - start == 0 {
11-
return nums[start]
12-
}
13-
pre, cur := 0, nums[start]
14-
for i := start + 1; i < end + 1; i++ {
15-
pre, cur = cur, max(pre + nums[i], cur)
16-
}
17-
return cur
6+
return b
187
}
198

209
func max(a, b int) int {
21-
if (a > b) {
10+
if a > b {
2211
return a
2312
}
2413
return b

‎solution/0100-0199/0198.House Robber/Solution.java

Lines changed: 6 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,11 @@
11
class Solution {
22
public int rob(int[] nums) {
3-
int n;
4-
if ((n = nums.length) == 0) return 0;
5-
return robRange(nums, 0, n - 1);
6-
}
7-
8-
private int robRange(int[] nums, int start, int end) {
9-
if (end - start == 0) return nums[start];
10-
int pre = 0;
11-
int cur = nums[start];
12-
for (int i = start + 1; i < end + 1; ++i) {
13-
int t = Math.max(pre + nums[i], cur);
14-
pre = cur;
15-
cur = t;
3+
int a = 0, b = nums[0];
4+
for (int i = 1; i < nums.length; ++i) {
5+
int c = Math.max(nums[i] + a, b);
6+
a = b;
7+
b = c;
168
}
17-
return cur;
9+
return b;
1810
}
1911
}

‎solution/0100-0199/0198.House Robber/Solution.py

Lines changed: 4 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,6 @@
11
class Solution:
22
def rob(self, nums: List[int]) -> int:
3-
def robRange(nums, start, end):
4-
if end - start == 0:
5-
return nums[start]
6-
pre, cur = 0, nums[start]
7-
for i in range(start + 1, end + 1):
8-
pre, cur = cur, max(pre + nums[i], cur)
9-
return cur
10-
if not nums:
11-
return 0
12-
return robRange(nums, 0, len(nums) - 1)
3+
a, b = 0, nums[0]
4+
for num in nums[1:]:
5+
a, b = b, max(num + a, b)
6+
return b

0 commit comments

Comments
 (0)