Skip to content

Commit 97e5a4d

Browse files
fishercoder1534fishercoder1534
committed
clean up
1 parent 5c6f815 commit 97e5a4d

File tree

14 files changed

+145
-115
lines changed

14 files changed

+145
-115
lines changed

‎README.md

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -277,13 +277,13 @@ Your ideas/fixes/algorithms are more than welcome!
277277
|187|[Repeated DNA Sequences](https://leetcode.com/problems/repeated-dna-sequences/)|[Solution](../master/src/main/java/com/stevesun/solutions/_187.java)| O(n)|O(n) | Medium
278278
|186|[Reverse Words in a String II](https://leetcode.com/problems/reverse-words-in-a-string-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/_186.java)| O(n)|O(1)| Medium
279279
|179|[Largest Number](https://leetcode.com/problems/largest-number/)|[Queue](../master/src/main/java/com/stevesun/solutions/BSTIterator_using_q.java) [Stack](../../blmaster/MEDIUM/src/medium/LargestNumber.java)| O(?) |O(?) | Medium|
280-
|174|[Dungeon Game](https://leetcode.com/problems/dungeon-game/)|[Queue](../master/src/main/java/com/stevesun/solutions/BSTIterator_using_q.java) [Stack](../../blmaster/MEDIUM/src/medium/DungeonGame.java)| O(?) |O(?) | Hard|
280+
|174|[Dungeon Game](https://leetcode.com/problems/dungeon-game/)|[Queue](../master/src/main/java/com/stevesun/solutions/BSTIterator_using_q.java) [Stack](../../blmaster/MEDIUM/src/medium/_174.java)| O(m*n) |O(m*n) | Hard| DP
281281
|173|[Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)|[Queue](../master/src/main/java/com/stevesun/solutions/BSTIterator_using_q.java) [Stack](../../blmaster/MEDIUM/src/medium/BSTIterator_using_stack.java)| O(1) |O(h) | Medium|
282282
|172|[Factorial Trailing Zeroes](https://leetcode.com/problems/factorial-trailing-zeroes/)|[Solution](../master/src/main/java/com/stevesun/solutions/FactorialTrailingZeroes.java)| O(logn)|O(1)| Easy
283283
|171|[Excel Sheet Column Number](https://leetcode.com/problems/excel-sheet-column-number/)|[Solution](../master/src/main/java/com/stevesun/solutions/_171.java)| O(n)|O(1)| Easy
284284
|170|[Two Sum III - Data structure design](https://leetcode.com/problems/two-sum-iii-data-structure-design/)|[Solution](../master/src/main/java/com/stevesun/solutions/_170.java)| O(n)|O(n)| Easy
285285
|169|[Majority Element](https://leetcode.com/problems/majority-element/)|[Solution](../master/src/main/java/com/stevesun/solutions/MajorityElement.java)| O(n)|O(1) | Easy|
286-
|168|[Excel Sheet Column Title](https://leetcode.com/problems/excel-sheet-column-title/)|[Solution](../master/src/main/java/com/stevesun/solutions/ExcelSheetColumnTitle.java)| O(n)|O(1) | Easy|
286+
|168|[Excel Sheet Column Title](https://leetcode.com/problems/excel-sheet-column-title/)|[Solution](../master/src/main/java/com/stevesun/solutions/_168.java)| O(n)|O(1) | Easy|
287287
|167|[Two Sum II - Input array is sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)|[Solution](../master/src/main/java/com/stevesun/solutions/_167.java)| O(logn)|O(1) | Easy|
288288
|165|[Compare Version Numbers](https://leetcode.com/problems/compare-version-numbers/)|[Solution](../master/src/main/java/com/stevesun/solutions/CompareVersionNumbers.java)| O(n)|O(1) | Easy|
289289
|164|[Maximum Gap](https://leetcode.com/problems/maximum-gap/)|[Solution](../master/src/main/java/com/stevesun/solutions/MaximumGap.java) | O(n) |O(n) | Hard|
@@ -302,7 +302,7 @@ Your ideas/fixes/algorithms are more than welcome!
302302
|150|[Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)|[Solution](../master/src/main/java/com/stevesun/solutions/EvaluateReversePolishNotation.java)| O(?)|O(?) | Medium
303303
|149|[Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)|[Solution](../master/src/main/java/com/stevesun/solutions/MaxPointsonaLine.java)| O(?)|O(?) | Hard|
304304
|147|[Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/)|[Solution](../master/src/main/java/com/stevesun/solutions/InsertionSortList.java) O(n^2)|O(1) | Medium| Linked List
305-
|146|[LRU Cache](https://leetcode.com/problems/lru-cache/)|[Doubly Linked List](../master/src/main/java/com/stevesun/solutions/LRUCache_use_DoublyLinkedList_plus_HashMap.java) |[Linked Hash Map](../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/LRUCache_use_LinkedHashMap.java)| O(?)|O(?) | Hard| Linked List
305+
|146|[LRU Cache](https://leetcode.com/problems/lru-cache/)|[Doubly Linked List](../master/src/main/java/com/stevesun/solutions/_146_use_DoublyLinkedList_plus_HashMap.java) |[Linked Hash Map](../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/_146_use_LinkedHashMap.java)| O(?)|O(?) | Hard| Linked List
306306
|145|[Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/BinaryTreePostOrderTraversal.java)| O(n)|O(h) | Hard| Binary Tree
307307
|144|[Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/BinaryTreePreorderTraversal.java)| O(n)|O(h) | Medium| Binary Tree
308308
|143|[Reorder List](https://leetcode.com/problems/reorder-list/)|[Solution](../master/src/main/java/com/stevesun/solutions/ReorderList.java)| O(n)|O(1) | Medium|
@@ -341,7 +341,7 @@ Your ideas/fixes/algorithms are more than welcome!
341341
|103|[Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/_103.java)| O(n)|O(h) | Medium| BFS,DFS
342342
|102|[Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/BinaryTreeLevelOrderTraversal.java)| O(n)|O(h) | Easy| BFS
343343
|99|[Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/RecoverBinarySearchTree.java) | O(?) | O(?) | Hard |
344-
|98|[Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/ValidateBinarySearchTree.java) | O(n) | O(h) | Medium | DFS/Recursion
344+
|98|[Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/_98.java) | O(n) | O(h) | Medium | DFS/Recursion
345345
|97|[Interleaving String](https://leetcode.com/problems/interleaving-string/)|[Solution](../master/src/main/java/com/stevesun/solutions/InterleavingString.java)| O(?)|O(?) | Hard| DP
346346
|96|[Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)|[Solution](../master/src/main/java/com/stevesun/solutions/UniqueBinarySearchTrees.java) | O(n^2) | O(n) | Medium | Recursion, DP
347347
|95|[Unique Binary Search Trees II](https://leetcode.com/problems/unique-binary-search-trees-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/UniqueBinarySearchTreesII.java) | O(?) | O(?) | Medium | Recursion
@@ -383,7 +383,7 @@ Your ideas/fixes/algorithms are more than welcome!
383383
|53|[Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)|[Solution](../master/src/main/java/com/stevesun/solutions/_53.java)|O(n)|O(1)|Easy|
384384
|50|[Pow(x, n)](https://leetcode.com/problems/powx-n/)|[Solution](../master/src/main/java/com/stevesun/solutions/PowXN.java)|O(logn)|O(logn)|Medium|
385385
|48|[Rotate Image](https://leetcode.com/problems/rotate-image/)|[Solution](../master/src/main/java/com/stevesun/solutions/_48.java)|O(n^2)|O(1)|Medium|Array
386-
|47|[Permutations II](https://leetcode.com/problems/permutations-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/PermutationsII.java)|O(n*n!)|O(n)|Medium|Backtracking
386+
|47|[Permutations II](https://leetcode.com/problems/permutations-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/_47.java)|O(n*n!)|O(n)|Medium|Backtracking
387387
|46|[Permutations](https://leetcode.com/problems/permutations/)|[Solution](../master/src/main/java/com/stevesun/solutions/_46.java)|O(n*n!)|O(n)|Medium|Backtracking
388388
|45|[Jump Game II](https://leetcode.com/problems/jump-game-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/JumpGameII.java)|O(?)|O(?)|Hard|
389389
|42|[Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)|[Solution](../master/src/main/java/com/stevesun/solutions/TrappingRainWater.java)|O(n)|O(1)|Hard|
@@ -407,20 +407,20 @@ Your ideas/fixes/algorithms are more than welcome!
407407
|24|[Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)|[Solution](../master/src/main/java/com/stevesun/solutions/SwapNodesinPairs.java)|O(n)|O(1)|Easy| Recursion, LinkedList
408408
|23|[Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)|[Solution](../master/src/main/java/com/stevesun/solutions/MergeKSortedList.java)|O(n*logk)|O(logk)|Hard|Heap
409409
|22|[Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)|[Solution](../master/src/main/java/com/stevesun/solutions/GenerateParentheses.java)|TBD|O(n)|Medium|Backtracking
410-
|21|[Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)|[Solution](../master/src/main/java/com/stevesun/solutions/_21.java)|O(n)|O(1)|Easy|
411-
|20|[Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)|[Solution](../master/src/main/java/com/stevesun/solutions/ValidParentheses.java)|O(n)|O(n)|Easy|Stack
410+
|21|[Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)|[Solution](../master/src/main/java/com/stevesun/solutions/_21.java)|O(n)|O(h)|Easy| Recursion
411+
|20|[Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)|[Solution](../master/src/main/java/com/stevesun/solutions/_20.java)|O(n)|O(n)|Easy|Stack
412412
|19|[Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)|[Solution](../master/src/main/java/com/stevesun/solutions/_19.java)|O(n)|O(1)|Medium| Linked List
413413
|18|[4 Sum](https://leetcode.com/problems/4sum/)|[Solution](../master/src/main/java/com/stevesun/solutions/_18.java)|O(n^2)|O(1)|Medium|Two Pointers
414414
|17|[Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)|[Solution](../master/src/main/java/com/stevesun/solutions/LetterCombinationsofaPhoneNumber.java)|O(n*4^n)|O(n)|Medium|Backtracking
415415
|16|[3Sum Closest](https://leetcode.com/problems/3sum-closest/)|[Solution](../master/src/main/java/com/stevesun/solutions/_16.java)|O(nlogn)|O(1)|Medium|Two Pointers
416416
|15|[3Sum](https://leetcode.com/problems/3sum/)|[Solution](../master/src/main/java/com/stevesun/solutions/_15.java)|O(n^2)|O(1)|Medium|Two Pointers
417417
|14|[Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)|[Solution](../master/src/main/java/com/stevesun/solutions/LongestCommonPrefix.java)| O(n*min(wordLength in this array)) | O(1) | Easy
418-
|13|[Roman to Integer](https://leetcode.com/problems/roman-to-integer)|[Solution](../master/src/main/java/com/stevesun/solutions/RomantoInteger.java)| O(1) | O(1) | Easy
418+
|13|[Roman to Integer](https://leetcode.com/problems/roman-to-integer)|[Solution](../master/src/main/java/com/stevesun/solutions/_13.java)| O(1) | O(1) | Easy
419419
|12|[Integer to Roman](https://leetcode.com/problems/integer-to-roman/)|[Solution](../master/src/main/java/com/stevesun/solutions/IntegertoRoman.java)|O(1)|O(1)|Medium|
420420
|11|[Container With Most Water](https://leetcode.com/problems/container-with-most-water/)|[Solution](../master/src/main/java/com/stevesun/solutions/ContainerWithMostWater.java)|O(n)|O(1)|Medium|
421421
|10|[Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/)|[Solution](../master/src/main/java/com/stevesun/solutions/RegularExpressionMatching.java)|O(m*n)|O(m*n)|Hard|DP
422422
|9|[Palindrome Number](https://leetcode.com/problems/palindrome-number/)|[Solution](../master/src/main/java/com/stevesun/solutions/PalindromeNumber.java)| O(logn)/(n) | O(1) | Easy
423-
|8|[String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/)|[Solution](../master/src/main/java/com/stevesun/solutions/StringToInteger.java)| O(n) | O(1) | Easy
423+
|8|[String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/)|[Solution](../master/src/main/java/com/stevesun/solutions/_8.java)| O(n) | O(1) | Medium
424424
|7|[Reverse Integer](https://leetcode.com/problems/reverse-integer/)|[Solution](../master/src/main/java/com/stevesun/solutions/ReverseInteger.java) | O(1) | O(1) | Easy |
425425
|6|[ZigZag Conversion](https://leetcode.com/problems/zigzag-conversion/)|[Solution](../master/src/main/java/com/stevesun/solutions/_6.java) | O(n) | O(n) | Easy |
426426
|5|[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)|[Solution](../master/src/main/java/com/stevesun/solutions/LongestPalindromicSubstring.java) | O(n^2) | O(1) | Medium|

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

Lines changed: 0 additions & 32 deletions
This file was deleted.

‎src/main/java/com/stevesun/solutions/RomantoInteger.java renamed to ‎src/main/java/com/stevesun/solutions/_13.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
/**Given a roman numeral, convert it to an integer.
77
88
Input is guaranteed to be within the range from 1 to 3999.*/
9-
public class RomantoInteger {
9+
public class _13 {
1010

1111
public int romanToInt(String s) {
1212
Map<Character, Integer> map = new HashMap();

‎src/main/java/com/stevesun/solutions/LRUCache_use_DoublyLinkedList_plus_HashMap.java renamed to ‎src/main/java/com/stevesun/solutions/_146_use_DoublyLinkedList_plus_HashMap.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@
1313
1 0 0 1 0
1414
Return 4.
1515
*/
16-
public class LRUCache_use_DoublyLinkedList_plus_HashMap {
16+
public class _146_use_DoublyLinkedList_plus_HashMap {
1717
private class Node {
1818
int key, value;
1919
Node prev, next;
@@ -35,7 +35,7 @@ private class Node {
3535
private Map<Integer, Node> map;// ATTN: the value should be Node type! This is the whole point
3636
// of having a class called Node!
3737

38-
public LRUCache_use_DoublyLinkedList_plus_HashMap(int capacity) {
38+
public _146_use_DoublyLinkedList_plus_HashMap(int capacity) {
3939
this.capacity = capacity;
4040
this.count = 0;// we need a count to keep track of the number of elements in the cache so
4141
// that we know when to evict the LRU one from the cache

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

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package com.stevesun.solutions;
2+
3+
import java.util.LinkedHashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
8+
9+
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
10+
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
11+
12+
Follow up:
13+
Could you do both operations in O(1) time complexity?
14+
15+
Example:
16+
17+
LRUCache cache = new LRUCache(2);//capacity
18+
19+
cache.put(1, 1);
20+
cache.put(2, 2);
21+
cache.get(1); // returns 1
22+
cache.put(3, 3); // evicts key 2
23+
cache.get(2); // returns -1 (not found)
24+
cache.put(4, 4); // evicts key 1
25+
cache.get(1); // returns -1 (not found)
26+
cache.get(3); // returns 3
27+
cache.get(4); // returns 4
28+
*/
29+
30+
/**
31+
* The shortest implementation is to use LinkedHashMap:
32+
* specify a size of the linkedHashMap;
33+
* override the removeEldestEntry method when its size exceeds max size: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#removeEldestEntry-java.util.Map.Entry-
34+
* in the constructor, set the last boolean variable to be true: it means the ordering mode, if we set it to be true, it means
35+
* in access order, false, means it's in insertion order: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#LinkedHashMap-int-float-boolean-*/
36+
public class _146_use_LinkedHashMap {
37+
38+
private Map<Integer, Integer> cache;
39+
private final int max;
40+
41+
public _146_use_LinkedHashMap(int capacity) {
42+
max = capacity;
43+
cache = new LinkedHashMap<Integer, Integer>(capacity, 1.0f, true){
44+
public boolean removeEldestEntry(Map.Entry eldest){
45+
return cache.size() > max;
46+
}
47+
};
48+
}
49+
50+
public int get(int key) {
51+
return cache.getOrDefault(key, -1);
52+
}
53+
54+
public void set(int key, int value) {
55+
cache.put(key, value);
56+
}
57+
}

‎src/main/java/com/stevesun/solutions/ExcelSheetColumnTitle.java renamed to ‎src/main/java/com/stevesun/solutions/_168.java

Lines changed: 18 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -12,22 +12,10 @@
1212
26 -> Z
1313
27 -> AA
1414
28 -> AB */
15-
public class ExcelSheetColumnTitle {
16-
public String convertToTitle_accepted(int n) {
17-
/**'Z' is the corner case, so we'll have to special case handling specially, also, we'll have to do (n-1)/26,
18-
* only when this is not equal to 1, we'll continue.*/
19-
StringBuilder sb = new StringBuilder();
20-
while(n != 0){
21-
int temp = n%26;
22-
if(temp == 0) sb.append("Z");
23-
else sb.append((char)(temp+64));
24-
n = (n-1)/26;
25-
}
26-
return sb.reverse().toString();
27-
}
28-
29-
public String convertToTitle_accepted_more_beautiful(int n) {
15+
public class _168 {
3016

17+
public String convertToTitle_accepted_more_beautiful(int n) {
18+
/**Get the right most digit first, move to the left, e.g. when n = 28, we get 'B' first, then we get 'A'.*/
3119
StringBuilder sb = new StringBuilder();
3220
while(n != 0){
3321
int temp = (n-1)%26;
@@ -39,7 +27,7 @@ public String convertToTitle_accepted_more_beautiful(int n) {
3927
}
4028

4129
public static void main(String...strings){
42-
ExcelSheetColumnTitle test = new ExcelSheetColumnTitle();
30+
_168 test = new _168();
4331
// int n = 28899;
4432
// int n = 1;
4533
// int n = 1000000001;
@@ -56,7 +44,20 @@ public static void main(String...strings){
5644
// System.out.println(702%26);
5745
// System.out.println(702/26);
5846
System.out.println(Integer.parseInt(String.valueOf(26), 10));
59-
System.out.println(test.convertToTitle_accepted(n));
47+
System.out.println(test.convertToTitle_accepted_more_beautiful(n));
48+
}
49+
50+
public String convertToTitle_accepted(int n) {
51+
/**'Z' is the corner case, so we'll have to special case handling specially, also, we'll have to do (n-1)/26,
52+
* only when this is not equal to 1, we'll continue.*/
53+
StringBuilder sb = new StringBuilder();
54+
while(n != 0){
55+
int temp = n%26;
56+
if(temp == 0) sb.append("Z");
57+
else sb.append((char)(temp+64));
58+
n = (n-1)/26;
59+
}
60+
return sb.reverse().toString();
6061
}
6162

6263
}

‎src/main/java/com/stevesun/solutions/DungeonGame.java renamed to ‎src/main/java/com/stevesun/solutions/_174.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ The demons had captured the princess (P) and imprisoned her in the bottom-right
2424
The knight's health has no upper bound.
2525
Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
2626
*/
27-
public class DungeonGame {
27+
public class _174 {
2828

2929
/**This problem should fill the dp matrix from bottom right.*/
3030
public int calculateMinimumHP(int[][] dungeon) {
@@ -60,7 +60,7 @@ public int calculateMinimumHP(int[][] dungeon) {
6060

6161

6262
public static void main(String...strings){
63-
DungeonGame test = new DungeonGame();
63+
_174 test = new _174();
6464
// int[][] dungeon = new int[1][1];
6565
// dungeon[0][0] = 0;
6666

0 commit comments

Comments
 (0)