Skip to content

Commit f8fc631

Browse files
gouthampradhangouthampradhan
committed
HouseRobberII, CompareVersionNumbers and ZigZagTraversal : Accepted
1 parent 247de1a commit f8fc631

4 files changed

Lines changed: 164 additions & 0 deletions

File tree

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@ My accepted leetcode solutions to some of the common interview problems.
8686
- [Coin Change 2](problems/src/dynamic_programming/CoinChange2.java) (Medium)
8787
- [Decode Ways](problems/src/dynamic_programming/DecodeWays.java) (Medium)
8888
- [House Robber](problems/src/dynamic_programming/HouseRobber.java) (Easy)
89+
- [House Robber II](problems/src/dynamic_programming/HouseRobberII.java) (Medium)
8990
- [Longest Increasing Subsequence](problems/src/dynamic_programming/LongestIncreasingSubsequence.java) (Medium)
9091
- [Longest Paliandromic Substring](problems/src/dynamic_programming/LongestPaliandromicSubstring.java) (Medium)
9192
- [Longest Palindromic Subsequence](problems/src/dynamic_programming/LongestPalindromicSubsequence.java) (Medium)
@@ -156,6 +157,7 @@ My accepted leetcode solutions to some of the common interview problems.
156157
- [ZigZag Conversion](problems/src/string/ZigZagConversion.java) (Medium)
157158
- [Implement StrStr](problems/src/string/ImplementStrStr.java) (Easy)
158159
- [Excel Sheet Column Number](problems/src/string/ExcelSheetColumnNumber.java) (Easy)
160+
- [Compare Version Numbers](problems/src/string/CompareVersionNumbers.java) (Easy)
159161

160162

161163
#### [Tree](problems/src/tree)
@@ -179,6 +181,7 @@ My accepted leetcode solutions to some of the common interview problems.
179181
- [Flatten Binary Tree to Linked List](problems/src/tree/FlattenBinaryTree.java) (Medium)
180182
- [Populating Next Right Pointers in Each Node](problems/src/tree/NextRightPointer.java) (Medium)
181183
- [Subtree of Another Tree](problems/src/tree/SubtreeOfAnotherTree.java) (Easy)
184+
- [Binary Tree Zigzag Level Order Traversal](problems/src/tree/ZigZagTraversal.java) (Medium)
182185

183186
#### [Two Pointers](problems/src/two_pointers)
184187

‎problems/src/dynamic_programming/HouseRobberII.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package dynamic_programming;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* Created by pradhang on 7/11/2017.
7+
* 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.
8+
* 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.
9+
10+
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.
11+
*/
12+
public class HouseRobberII {
13+
public static void main(String[] args) throws Exception{
14+
int[] nums = {6,3,10,8,2,10,3,5,10,5,3};
15+
System.out.println(new HouseRobberII().rob(nums));
16+
}
17+
18+
public int rob(int[] nums) {
19+
if(nums.length == 0) return 0;
20+
if(nums.length == 1)
21+
return nums[0];
22+
else if(nums.length == 2){
23+
if(nums[0] > nums[1])
24+
return nums[0];
25+
return nums[1];
26+
}
27+
else if(nums.length == 3) return Math.max(Math.max(nums[0], nums[1]), nums[2]);
28+
int[] DP = new int[nums.length];
29+
for(int i = nums.length - 1; i > 0; i --){
30+
if(i + 3 < nums.length)
31+
DP[i] = Math.max(nums[i] + DP[i + 2], nums[i] + DP[i + 3]);
32+
else if(i + 2 < nums.length)
33+
DP[i] = nums[i] + DP[i + 2];
34+
else DP[i] = nums[i];
35+
}
36+
int max = Math.max(DP[1], DP[2]);
37+
Arrays.fill(DP, 0); //reset
38+
for(int i = nums.length - 2; i >= 0; i --){
39+
if(i + 3 < nums.length)
40+
DP[i] = Math.max(nums[i] + DP[i + 2], nums[i] + DP[i + 3]);
41+
else if(i + 2 < nums.length)
42+
DP[i] = nums[i] + DP[i + 2];
43+
else DP[i] = nums[i];
44+
}
45+
max = Math.max(max, Math.max(DP[0], DP[1]));
46+
return max;
47+
}
48+
}

‎problems/src/string/CompareVersionNumbers.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package string;
2+
3+
import java.util.StringTokenizer;
4+
5+
/**
6+
* Created by pradhang on 7/11/2017.
7+
* Compare two version numbers version1 and version2.
8+
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
9+
10+
You may assume that the version strings are non-empty and contain only digits and the . character.
11+
The . character does not represent a decimal point and is used to separate number sequences.
12+
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
13+
14+
Here is an example of version numbers ordering:
15+
16+
0.1 < 1.1 < 1.2 < 13.37
17+
*/
18+
public class CompareVersionNumbers {
19+
/**
20+
* Main method
21+
* @param args
22+
* @throws Exception
23+
*/
24+
public static void main(String[] args) throws Exception{
25+
System.out.println(new CompareVersionNumbers().compareVersion("1.11.1", "1.11"));
26+
}
27+
28+
public int compareVersion(String version1, String version2) {
29+
StringTokenizer st1 = new StringTokenizer(version1, ".");
30+
StringTokenizer st2 = new StringTokenizer(version2, ".");
31+
while(st1.hasMoreTokens() & st2.hasMoreTokens()){
32+
int token1 = Integer.parseInt(st1.nextToken());
33+
int token2 = Integer.parseInt(st2.nextToken());
34+
if(token1 > token2)
35+
return 1;
36+
else if(token2 > token1)
37+
return -1;
38+
}
39+
if(st1.countTokens() > st2.countTokens()){
40+
while(st1.hasMoreTokens()){
41+
if(Integer.parseInt(st1.nextToken()) > 0)
42+
return 1;
43+
}
44+
}
45+
else if(st2.countTokens() > st1.countTokens()){
46+
while(st2.hasMoreTokens()){
47+
if(Integer.parseInt(st2.nextToken()) > 0)
48+
return -1;
49+
}
50+
}
51+
return 0;
52+
}
53+
54+
}

‎problems/src/tree/ZigZagTraversal.java‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package tree;
2+
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
7+
/**
8+
* Created by pradhang on 7/11/2017.
9+
* Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
10+
11+
For example:
12+
Given binary tree [3,9,20,null,null,15,7],
13+
3
14+
/ \
15+
9 20
16+
/ \
17+
15 7
18+
return its zigzag level order traversal as:
19+
[
20+
[3],
21+
[20,9],
22+
[15,7]
23+
]
24+
*/
25+
public class ZigZagTraversal {
26+
27+
public class TreeNode {
28+
int val;
29+
TreeNode left;
30+
TreeNode right;
31+
TreeNode(int x) { val = x; }
32+
}
33+
34+
public static void main(String[] args) throws Exception{
35+
36+
}
37+
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
38+
List<List<Integer>> result = new ArrayList<>();
39+
if(root == null) return result;
40+
dfs(root, 0, result);
41+
return result;
42+
}
43+
44+
@SuppressWarnings("unchecked")
45+
private void dfs(TreeNode root, int level, List<List<Integer>> result){
46+
if(root != null){
47+
LinkedList<Integer> subList;
48+
if(level >= result.size()){
49+
subList = new LinkedList<>();
50+
result.add(subList);
51+
}else subList = (LinkedList)result.get(level);
52+
if(level % 2 == 0)
53+
subList.addFirst(root.val); //add to right
54+
else subList.add(root.val); //add to left
55+
dfs(root.right, level + 1, result);
56+
dfs(root.left, level + 1, result);
57+
}
58+
}
59+
}

0 commit comments

Comments
 (0)