Skip to content

Commit 206fcad

Browse files
fishercoder1534fishercoder1534
committed
check in all
1 parent b74b275 commit 206fcad

File tree

15 files changed

+222
-47
lines changed

15 files changed

+222
-47
lines changed

‎src/main/java/com/stevesun/solutions/MSOnlineAssessment.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.stevesun.solutions;
2+
3+
import java.util.*;
4+
5+
public class MSOnlineAssessment {
6+
7+
public static void main(String... args) {
8+
int[] nums = new int[]{1,2,3,4,5, -1, -3, -6, 3, 2, -4};
9+
// int[] nums = new int[]{-1, -2, 1,2,3};
10+
// int[] nums = new int[]{-1, -2, 1,2,3,-1, -2};
11+
// List<int[]> result = subarraySum_v2(nums);
12+
13+
}
14+
15+
public static List<int[]> subarraySum_v2(int[] nums) {
16+
int[] preSums = new int[nums.length+1];
17+
for (int i = 1; i <= nums.length; i++) {
18+
preSums[i] = preSums[i-1] + nums[i-1];
19+
}
20+
TreeMap<Integer, List<int[]>> preSum = new TreeMap(Collections.reverseOrder());
21+
for (int i = 1; i <= nums.length; i++) {
22+
for (int j = 0; j < i-1; j++) {
23+
int sum = preSums[i] - preSums[j];
24+
if (!preSum.containsKey(sum)) {
25+
List<int[]> value = new ArrayList<>();
26+
value.add(new int[]{j, i-1});
27+
preSum.put(sum, value);
28+
} else {
29+
List<int[]> value = preSum.get(sum);
30+
value.add(new int[]{j, i-1});
31+
preSum.put(sum, value);
32+
}
33+
}
34+
}
35+
Map.Entry<Integer, List<int[]>> firstEntry = preSum.firstEntry();
36+
return firstEntry.getValue();
37+
}
38+
}

‎src/main/java/com/stevesun/solutions/_103.java

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,8 @@
77
/**
88
* 103. Binary Tree Zigzag Level Order Traversal
99
*
10-
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+
Given a binary tree, return the zigzag level order traversal of its nodes' values.
11+
(ie, from left to right, then right to left for the next level and alternate between).
1112
1213
For example:
1314
Given binary tree [3,9,20,null,null,15,7],
@@ -23,7 +24,7 @@
2324
[15,7]
2425
]
2526
*/
26-
public class BinaryTreeZigzagLevelOrderTraversal {
27+
public class _103 {
2728
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2829
Queue<TreeNode> q = new LinkedList();
2930
List<List<Integer>> levels = new ArrayList();

‎src/main/java/com/stevesun/solutions/_116.java

Lines changed: 15 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -31,44 +31,40 @@ You may assume that it is a perfect binary tree (ie, all leaves are at the same
3131
/ \ / \
3232
4->5->6->7 -> NULL */
3333

34-
public class PopulatingNextRightPointersinEachNode {
35-
//copied this post: https://discuss.leetcode.com/topic/1106/o-1-space-o-n-complexity-iterative-solution
36-
//very clever and concise to make it in O(1) space
37-
34+
public class _116 {
35+
//credit: https://discuss.leetcode.com/topic/1106/o-1-space-o-n-complexity-iterative-solution
3836
//based on level order traversal
3937
public static void connect(TreeLinkNode root) {
4038

4139
TreeLinkNode head = null; //head of the next level
4240
TreeLinkNode prev = null; //the leading node on the next level
43-
TreeLinkNode cur = root; //current node of current level
44-
45-
while (cur != null) {
41+
TreeLinkNode curr = root; //current node of current level
4642

47-
while (cur != null) { //iterate on the current level
43+
while (curr != null) {
44+
while (curr != null) { //iterate on the current level
4845
//left child
49-
if (cur.left != null) {
46+
if (curr.left != null) {
5047
if (prev != null) {
51-
prev.next = cur.left;
48+
prev.next = curr.left;
5249
} else {
53-
head = cur.left;
50+
head = curr.left;
5451
}
55-
prev = cur.left;
52+
prev = curr.left;
5653
}
5754
//right child
58-
if (cur.right != null) {
55+
if (curr.right != null) {
5956
if (prev != null) {
60-
prev.next = cur.right;
57+
prev.next = curr.right;
6158
} else {
62-
head = cur.right;
59+
head = curr.right;
6360
}
64-
prev = cur.right;
61+
prev = curr.right;
6562
}
6663
//move to next node
67-
cur = cur.next;
64+
curr = curr.next;
6865
}
69-
7066
//move to next level
71-
cur = head;
67+
curr = head;
7268
head = null;
7369
prev = null;
7470
}

‎src/main/java/com/stevesun/solutions/_117.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@
2424
/ \ \
2525
4-> 5 -> 7 -> NULL */
2626

27-
public class PopulatingNextRightPointersinEachNodeII {
27+
public class _117 {
2828
//copied this post: https://discuss.leetcode.com/topic/1106/o-1-space-o-n-complexity-iterative-solution
2929
//very clever and concise to make it in O(1) space
3030

‎src/main/java/com/stevesun/solutions/_151.java

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,19 +4,20 @@
44
For example,
55
Given s = "the sky is blue",
66
return "blue is sky the".*/
7-
public class ReverseWordsinaString {
7+
8+
public class _151 {
89
public String reverseWords(String s) {
910
if(!s.contains(" ")) return s;//for cases like this: "a"
1011
if(s.matches(" *")) return "";//for cases like this: " "
1112
String[] words = s.split(" ");
12-
StringBuilder sb = new StringBuilder();
13+
StringBuilder stringBuilder = new StringBuilder();
1314
for(int i = words.length-1; i >= 0; i--){
1415
if(!words[i].equals("") && !words[i].equals(" ")){
15-
sb.append(words[i]);
16-
sb.append(" ");
16+
stringBuilder.append(words[i]);
17+
stringBuilder.append(" ");
1718
}
1819
}
19-
sb.deleteCharAt(sb.length()-1);
20-
return sb.toString();
20+
stringBuilder.deleteCharAt(stringBuilder.length()-1);
21+
return stringBuilder.toString();
2122
}
2223
}

‎src/main/java/com/stevesun/solutions/_153.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
1010
You may assume no duplicate exists in the array.
1111
*/
12-
public class FindMinimuminRotatedSortedArray {
12+
public class _153 {
1313

1414
public int findMin(int[] nums) {
1515
int left = 0;

‎src/main/java/com/stevesun/solutions/_186.java

Lines changed: 1 addition & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -10,18 +10,15 @@
1010
return "blue is sky the".
1111
1212
Could you do it in-place without allocating extra space?
13-
14-
Related problem: Rotate Array
1513
*/
16-
public class ReverseWordsinaStringII {
14+
public class _186 {
1715

1816
public void reverseWords(char[] s) {
1917
// Three steps to reverse
2018
// 1, reverse the whole sentence
2119
reverse(s, 0, s.length - 1);
2220
// 2, reverse each word
2321
int start = 0;
24-
int end = -1;
2522
for (int i = 0; i < s.length; i++) {
2623
if (s[i] == ' ') {
2724
reverse(s, start, i - 1);

‎src/main/java/com/stevesun/solutions/_218.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ Three edge cases (see the graph illustration in the above video at 12’18”):
4141
For the sake of efficiency (better time complexity), we’ll use TreeMap which supports O(logn) for remove() operation, this is the reason we choose TreeMap over a normal PriorityQueue in Java (PriorityQueue supports add() and getMaxVal() in both O(logn) time, however, for remove(), it does NOT.)
4242
But TreeMap in Java supports all the three operations in O(logn) time.*/
4343

44-
public class TheSkylineProblem {
44+
public class _218 {
4545

4646
class BuildingPoint implements Comparable<BuildingPoint>{
4747
int x;

‎src/main/java/com/stevesun/solutions/_393.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.stevesun.solutions;
2+
3+
/**
4+
* 393. UTF-8 Validation
5+
*
6+
* A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
7+
8+
For 1-byte character, the first bit is a 0, followed by its unicode code.
9+
For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
10+
This is how the UTF-8 encoding would work:
11+
12+
Char. number range | UTF-8 octet sequence
13+
(hexadecimal) | (binary)
14+
--------------------+---------------------------------------------
15+
0000 0000-0000 007F | 0xxxxxxx
16+
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
17+
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
18+
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
19+
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
20+
21+
Note:
22+
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
23+
24+
Example 1:
25+
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
26+
Return true.
27+
28+
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
29+
30+
31+
Example 2:
32+
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
33+
Return false.
34+
35+
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
36+
The next byte is a continuation byte which starts with 10 and that's correct.
37+
But the second continuation byte does not start with 10, so it is invalid.
38+
*/
39+
public class _393 {
40+
41+
public boolean validUtf8(int[] data) {
42+
//TODO: not finished yet
43+
if (data == null || data.length == 0 || data.length > 4) return false;
44+
int len = data.length;
45+
String[] last8Bits = new String[len];
46+
for (int i = 0; i < len; i++) {
47+
String bin = Integer.toBinaryString(data[i]);
48+
last8Bits[i] = bin.length() >= 8 ? bin.substring(0, 8) : String.format("%08d", Integer.parseInt(bin));//pad left with zeroes to make sure each number is 8 bits long to make coding easier in the later part
49+
}
50+
if (len == 1) {
51+
if (Integer.valueOf(last8Bits[0].substring(0,1)) != 0) return false;
52+
return true;
53+
} else {
54+
55+
}
56+
return false;
57+
}
58+
59+
}

‎src/main/java/com/stevesun/solutions/_471.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.stevesun.solutions;
2+
3+
/**
4+
* 471. Encode String with Shortest Length
5+
Given a non-empty string, encode the string such that its encoded length is the shortest.
6+
7+
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
8+
9+
Note:
10+
k will be a positive integer and encoded string will not be empty or have extra space.
11+
You may assume that the input string contains only lowercase English letters. The string's length is at most 160.
12+
If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them is fine.
13+
Example 1:
14+
15+
Input: "aaa"
16+
Output: "aaa"
17+
Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.
18+
Example 2:
19+
20+
Input: "aaaaa"
21+
Output: "5[a]"
22+
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.
23+
Example 3:
24+
25+
Input: "aaaaaaaaaa"
26+
Output: "10[a]"
27+
Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".
28+
Example 4:
29+
30+
Input: "aabcaabcd"
31+
Output: "2[aabc]d"
32+
Explanation: "aabc" occurs twice, so one answer can be "2[aabc]d".
33+
Example 5:
34+
35+
Input: "abbbabbbcabbbabbbc"
36+
Output: "2[2[abbb]c]"
37+
Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".
38+
*/
39+
public class _471 {
40+
41+
public String encode(String s) {
42+
return null;
43+
}
44+
45+
}

‎src/main/java/com/stevesun/solutions/_53.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
77
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
88
*/
9-
public class MaximumSubarray {
9+
public class _53 {
1010
public int maxSubArray(int[] nums) {
1111
int maxSum = nums[0], currentSum = nums[0];
1212
for(int i = 1; i < nums.length; i++){

‎src/main/java/com/stevesun/solutions/_73.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,16 +2,14 @@
22

33
/**Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
44
5-
click to show follow up.
6-
75
Follow up:
86
Did you use extra space?
97
A straight forward solution using O(mn) space is probably a bad idea.
108
A simple improvement uses O(m + n) space, but still not the best solution.
119
Could you devise a constant space solution?
1210
1311
*/
14-
public class SetMatrixZeroes {
12+
public class _73 {
1513
//this is the most straightforward solution which uses O(mn) space
1614
public void setZeroes(int[][] matrix) {
1715
if(matrix == null || matrix.length == 0) return;
@@ -31,4 +29,6 @@ public void setZeroes(int[][] matrix) {
3129
}
3230
}
3331
}
32+
33+
//TODO: use better solutions
3434
}

‎src/main/java/com/stevesun/solutions/_75.java

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,20 @@
11
package com.stevesun.solutions;
22

3-
/** Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
3+
/** Given an array with n objects colored red, white or blue,
4+
* sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
45
56
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
67
78
Note:
89
You are not suppose to use the library's sort function for this problem.
910
10-
click to show follow up.
11-
1211
Follow up:
1312
A rather straight forward solution is a two-pass algorithm using counting sort.
14-
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
13+
First, iterate the array counting number of 0's, 1's, and 2's,
14+
then overwrite array with total number of 0's, then 1's and followed by 2's.
1515
1616
Could you come up with an one-pass algorithm using only constant space?*/
17-
public class SortColors {
17+
public class _75 {
1818

1919
public void sortColors(int[] nums) {
2020
int zero = 0, two = nums.length-1;

‎src/test/java/com/stevesun/_153Test.java

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
package com.stevesun;
22

3-
import com.stevesun.solutions.FindMinimuminRotatedSortedArray;
3+
import com.stevesun.solutions._153;
44
import org.junit.Before;
55
import org.junit.BeforeClass;
66
import org.junit.Test;
@@ -10,15 +10,15 @@
1010
/**
1111
* Created by stevesun on 1/10/17.
1212
*/
13-
public class FindMinimuminRotatedSortedArrayTest {
14-
private static FindMinimuminRotatedSortedArray test;
13+
public class _153Test {
14+
private static _153 test;
1515
private static int expected;
1616
private static int actual;
1717
private static int[] nums;
1818

1919
@BeforeClass
2020
public static void setup(){
21-
test = new FindMinimuminRotatedSortedArray();
21+
test = new _153();
2222
}
2323

2424
@Before

0 commit comments

Comments
 (0)