Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit26f7fd6

Browse files
committed
finish house robber problems
1 parentbbc7890 commit26f7fd6

File tree

3 files changed

+95
-0
lines changed

3 files changed

+95
-0
lines changed

‎Medium/213-houseRobberII.js‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* Use the idea of House Robber I, find the maxAmount twice.
3+
* first to find the max amount from 0 to length - 2,
4+
* second to find the max amount from 1 to length - 1,
5+
* doing this because the last house and first house are connected, they can't both
6+
* be robbed. Finally find the max value from first and second.
7+
*
8+
*@param {number[]} nums
9+
*@return {number}
10+
*/
11+
varrob=function(nums){
12+
if(nums.length===0)return0;
13+
if(nums.length===1)returnnums[0];
14+
returnMath.max(robSingle(nums,0,nums.length-2),robSingle(nums,1,nums.length-1));
15+
};
16+
17+
varrobSingle=function(nums,start,end){
18+
vartoRob=0;
19+
varnotRob=0;
20+
21+
for(vari=start;i<=end;i++){
22+
vartmp=toRob;
23+
toRob=notRob+nums[i];
24+
notRob=Math.max(notRob,tmp);
25+
}
26+
27+
returnMath.max(toRob,notRob);
28+
};

‎Medium/337-houseRobberIII.js‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* function TreeNode(val) {
4+
* this.val = val;
5+
* this.left = this.right = null;
6+
* }
7+
*/
8+
/**
9+
* Key: similar to every house in previous hourse rob problems, each node store two values,
10+
* first value is to store the max value if the node will be robbed. The second value is the vaule
11+
* if the node will not be robbed.
12+
* In the first case, the value is straightforward to calculate, that is, current node's val
13+
* plus the second value from it's child nodes' second value (not robbed).
14+
* In the second case, because the node is not going to be robbed, its children can be robbed
15+
* or not robbed. So the value is the max value of the left child's two values plus the right child's
16+
* max value from the two values.
17+
*
18+
*@param {TreeNode} root
19+
*@return {number}
20+
*/
21+
varrob=function(root){
22+
varresult=robDFS(root);
23+
returnMath.max(result[0],result[1]);
24+
};
25+
26+
varrobDFS=function(root){
27+
if(!root)return[0,0];
28+
varresult=[];
29+
varleftResults=robDFS(root.left);
30+
varrightResults=robDFS(root.right);
31+
result[0]=root.val+leftResults[1]+rightResults[1];
32+
result[1]=Math.max(leftResults[0],leftResults[1])+Math.max(rightResults[0],rightResults[1]);
33+
returnresult;
34+
};
35+
36+
37+
// not right, why?
38+
varrob=function(root){
39+
varcachedResult={};
40+
returnrobHelper(root,cachedResult);
41+
};
42+
43+
varrobHelper=function(root,cachedResult){
44+
if(!root)return0;
45+
if(cachedResult.hasOwnProperty(root)){
46+
returncachedResult[root];
47+
}
48+
varval=0;
49+
50+
if(root.left!==null){
51+
val+=robHelper(root.left.left,cachedResult)+robHelper(root.left.right,cachedResult);
52+
console.log(root,val);
53+
}
54+
55+
if(root.right!==null){
56+
val+=robHelper(root.right.left,cachedResult)+robHelper(root.right.right,cachedResult);
57+
console.log(root,val);
58+
59+
}
60+
61+
val=Math.max(val+root.val,robHelper(root.left,cachedResult)+robHelper(root.right,cachedResult));
62+
cachedResult[root]=val;
63+
64+
returnval;
65+
};

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,10 +89,12 @@
8989
*[141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) -[Solution](./Medium/141-linkedListCycle.js)
9090
*[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) -[Solution](./Medium/144-binaryTreePreorder.js)
9191
*[153.Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) -[Solution](./Medium/153-findMinimumInRotatedSortedArray.js)
92+
*[213. House Robber II](https://leetcode.com/problems/house-robber-ii/) -[Solution](./Medium/213-houseRobberII.js)
9293
*[230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) -[Solution](./Medium/230-kthSmallestElementinBST.js)
9394
*[238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) -[Solution](./Medium/238-productExceptSelf.js)
9495
*[260. Single Number III](https://leetcode.com/problems/single-number-iii/) -[Solution](./Medium/260-singleNumberIII.js)
9596
*[268. Missing Number](https://leetcode.com/problems/missing-number/) -[Solution](./Medium/268-missingNumber.js)
9697
*[300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) -[Solution](./Medium/300-longestIncreasingSubsequence.js)
9798
*[318. Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) -[Solution](./Medium/318-maximumProductWordLengths.js)
9899
*[319. Bulb Switcher](https://leetcode.com/problems/bulb-switcher/) -[Solution](./Medium/319-bulbSwitcher.js)
100+
*[337. House Robber III](https://leetcode.com/problems/house-robber-iii/) -[Solution](./Medium/337-houseRobberIII.js)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp