Thursday, April 27, 2017
48. Rotate Image
Version #1 Rotate + Recursion
四刷
Fastest ever -> only 19mins to bug freely pass
主要是非常机智的直接把left,right,top,bottom都写下来了，这样就不会有任何的typo了
98.41 %
class Solution {
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
// rotate by layer
helper(matrix, 0, matrix.length);
}
private void helper(int[][] matrix, int offset, int N) {
int left = offset, right = N - offset - 1;
int top = offset, bottom = N - offset - 1;
if (left >= right) return;
for (int i = 0; left + i < right; i++) {
int temp = matrix[top][left + i];
matrix[top][left + i] = matrix[bottom - i][left];
matrix[bottom - i][left] = matrix[bottom][right - i];
matrix[bottom][right - i] = matrix[top + i][right];
matrix[top + i][right] = temp;
}
helper(matrix, offset + 1, N);
}
}
三刷
100.00 %
class Solution {
public void rotate(int[][] matrix) {
helper(matrix, 0, matrix.length);
}
private void helper(int[][] matrix, int j, int N) {
int width = N - 2 * j;
if (width < 2) {
return;
}
for (int i = 0; i < width - 1; i++) {
int temp = matrix[j][j + i];
matrix[j][j + i] = matrix[j + width - 1- i][j];
matrix[j + width - 1 - i][j] = matrix[j + width - 1][j + width - 1 - i];
matrix[j + width - 1][j + width - 1 - i] = matrix[j + i][j + width - 1];
matrix[j + i][j + width - 1] = temp;
}
helper(matrix, j + 1, N);
}
}
Version #2 Swap for 2 times
59.34 %
class Solution {
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
int rows = matrix.length;
int cols = matrix[0].length;
for (int y = 0; y < cols; y++) {
for (int x = 0; x < rows / 2; x++) {
int temp = matrix[x][y];
matrix[x][y] = matrix[rows - x - 1][y];
matrix[rows - x - 1][y] = temp;
}
}
for (int x = 0; x < rows; x++) {
for (int y = 0; y < x; y++) {
int temp = matrix[x][y];
matrix[x][y] = matrix[y][x];
matrix[y][x] = temp;
}
}
}
}
Version #1 Recursion
72.77 %
烦死了这道题。。。。就是一直倒倒倒
想清楚这个size的定义
public class Solution {
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
rotate(matrix, matrix.length, 0);
}
private void rotate(int[][] matrix, int size, int offset) {
if (size <= 1) return;
for (int i = 0; i < size - 1; i++) {
int temp = matrix[offset][offset + i];
matrix[offset][offset + i] = matrix[offset + size - 1 - i][offset];
matrix[offset + size - 1 - i][offset] = matrix[offset + size - 1][offset + size - 1 - i];
matrix[offset + size - 1][offset + size - 1 - i] = matrix[offset + i][offset + size - 1];
matrix[offset + i][offset + size - 1] = temp;
}
rotate(matrix, size - 2, offset + 1);
}
}
236. Lowest Common Ancestor of a Binary Tree
四刷 05/2022
Version #1 Recursion
Time O(N)
Space O(N)
Runtime: 10 ms, faster than 46.12% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 47.1 MB, less than 52.11% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode[] lca = new TreeNode[1];
countTarget(root, p, q, lca);
return lca[0];
}
// Returns how many target nodes are in the subtree
private int countTarget(TreeNode node, TreeNode p, TreeNode q, TreeNode[] lca) {
if (node == null) { // already found
return 0;
}
int left = countTarget(node.left, p, q, lca);
if (left == 2) {
return 2;
}
int right = countTarget(node.right, p, q, lca);
if (right == 2) {
return 2;
}
int count = left + right;
if (node == p || node == q) {
count++;
}
if (count == 2) {
lca[0] = node;
}
return count;
}
}
Version #2 Iteration with BFS
Time O(N)
Space O(N)
Runtime: 22 ms, faster than 7.16% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 49.1 MB, less than 7.00% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
Map<TreeNode, TreeNode> parent = new HashMap<>();
// Find all the parent nodes of p and q
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root);
while (!que.isEmpty() && (!parent.containsKey(p) || !parent.containsKey(q))) {
TreeNode curr = que.poll();
if (curr.left != null) {
parent.put(curr.left, curr);
que.offer(curr.left);
}
if (curr.right != null) {
parent.put(curr.right, curr);
que.offer(curr.right);
}
}
Set<TreeNode> pAncestors = new HashSet<>();
while (p != null) {
pAncestors.add(p);
p = parent.getOrDefault(p, null);
}
while (q != null) {
if (pAncestors.contains(q)) {
return q;
}
q = parent.getOrDefault(q, null);
}
return null;
}
}
感觉还是之前写的好
40.96 %
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return check(root, p, q);
}
// Given a node
// If p == node, return p, if q == node, return q
// If pq in different subtree, return curr node
private TreeNode check(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) {
return null;
}
if (node == p || node == q) {
return node;
}
TreeNode left = check(node.left, p, q);
TreeNode right = check(node.right, p, q);
if (left != null && right != null) {
return node;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
}
二刷
39.72 %
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
}
一刷
15.04 %
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
}
121. Best Time to Buy and Sell Stock
Version #2 DP / Kadane's Algorithm
99.97 %
class Solution {
public int maxProfit(int[] prices) {
// Accumulate difference of price between days
// Find the maximum subarray of diff array -> Kadane's Algo
// prices = [7,1,5,3,6,4]
// diff = [0,-6,4,-2,3,-2]
// dp[i] -> maximum subarray ending at i
// Standing at current index i, we can choose either use dp[i - 1] or not
// if (dp[i - 1] > 0, dp[i] += dp[i - 1])
if (prices == null || prices.length < 2) {
return 0;
}
int dp = 0;
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
int dpCurr = prices[i] - prices[i - 1];
if (dp > 0) {
dpCurr += dp;
}
dp = dpCurr;
maxProfit = Math.max(maxProfit, dp);
}
return maxProfit;
}
}
Version #1 Simple solution
一刷
87.92 %
Find the global minimum so far
Time O(n)
Space O(1)
二刷
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int max = 0;
int prevMin = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prevMin) {
max = Math.max(max, prices[i] - prevMin);
} else {
prevMin = prices[i];
}
}
return max;
}
}
一刷
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int min = Integer.MAX_VALUE;
int profit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < min) min = prices[i];
int diff = prices[i] - min;
if (diff > 0) {
profit = Math.max(profit, diff);
}
}
return profit;
}
}
二刷
99.97 %
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int min = Integer.MAX_VALUE;
int profit = 0;
for (int price : prices) {
min = Math.min(min, price);
if (price > min) {
profit = Math.max(price - min, profit);
}
}
return profit;
}
}
99.97 %
class Solution {
public int maxProfit(int[] prices) {
// Accumulate difference of price between days
// Find the maximum subarray of diff array -> Kadane's Algo
// prices = [7,1,5,3,6,4]
// diff = [0,-6,4,-2,3,-2]
// dp[i] -> maximum subarray ending at i
// Standing at current index i, we can choose either use dp[i - 1] or not
// if (dp[i - 1] > 0, dp[i] += dp[i - 1])
if (prices == null || prices.length < 2) {
return 0;
}
int dp = 0;
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
int dpCurr = prices[i] - prices[i - 1];
if (dp > 0) {
dpCurr += dp;
}
dp = dpCurr;
maxProfit = Math.max(maxProfit, dp);
}
return maxProfit;
}
}
Version #1 Simple solution
一刷
87.92 %
Find the global minimum so far
Time O(n)
Space O(1)
二刷
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int max = 0;
int prevMin = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prevMin) {
max = Math.max(max, prices[i] - prevMin);
} else {
prevMin = prices[i];
}
}
return max;
}
}
一刷
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int min = Integer.MAX_VALUE;
int profit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < min) min = prices[i];
int diff = prices[i] - min;
if (diff > 0) {
profit = Math.max(profit, diff);
}
}
return profit;
}
}
二刷
99.97 %
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int min = Integer.MAX_VALUE;
int profit = 0;
for (int price : prices) {
min = Math.min(min, price);
if (price > min) {
profit = Math.max(price - min, profit);
}
}
return profit;
}
}
Wednesday, April 26, 2017
17. Letter Combinations of a Phone Number
三刷 06/2022
Version #1 DFS
N - String length
Time O(N * N!) - copy string takes O(N) time * N! permutations
Space O(N) depth of the stack
一个可以改进的地方
private Map<Character, String> letters = Map.of(
'2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
Runtime: 2 ms, faster than 61.89% of Java online submissions for Letter Combinations of a Phone Number.
Memory Usage: 42.1 MB, less than 76.74% of Java online submissions for Letter Combinations of a Phone Number.
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
Map<Character, List<Character>> map = Map.of(
'2', Arrays.asList(new Character[]{'a', 'b', 'c'}),
'3', Arrays.asList(new Character[]{'d', 'e', 'f'}),
'4', Arrays.asList(new Character[]{'g', 'h', 'i'}),
'5', Arrays.asList(new Character[]{'j', 'k', 'l'}),
'6', Arrays.asList(new Character[]{'m', 'n', 'o'}),
'7', Arrays.asList(new Character[]{'p', 'q', 'r', 's'}),
'8', Arrays.asList(new Character[]{'t', 'u', 'v'}),
'9', Arrays.asList(new Character[]{'w', 'x', 'y', 'z'}));
dfs(digits.toCharArray(), 0, map, new StringBuilder(), result);
return result;
}
private void dfs(char[] digits, int index, Map<Character, List<Character>> map, StringBuilder sb, List<String> result) {
if (index == digits.length) {
result.add(sb.toString());
return;
}
List<Character> letters = map.get(digits[index]);
for (Character letter : letters) {
sb.append(letter);
dfs(digits, index + 1,map, sb, result);
sb.deleteCharAt(sb.length() - 1);
}
}
}
一刷
Version #1 DFSTime TreeDFS depth = length of digits => n
each node has about b children => branching factor = 3
Size of tree is b^n
O(b^n) => b = [3,4]
Space O(n) => depth of tree
27.73 %
public class Solution {
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return new ArrayList<String>();
//key->digit value->array of chars
Map<Character, char[]> map = new HashMap<Character, char[]>();
map.put('0', new char[] {});
map.put('1', new char[] {});
map.put('2', new char[] { 'a', 'b', 'c' });
map.put('3', new char[] { 'd', 'e', 'f' });
map.put('4', new char[] { 'g', 'h', 'i' });
map.put('5', new char[] { 'j', 'k', 'l' });
map.put('6', new char[] { 'm', 'n', 'o' });
map.put('7', new char[] { 'p', 'q', 'r', 's' });
map.put('8', new char[] { 't', 'u', 'v'});
map.put('9', new char[] { 'w', 'x', 'y', 'z' });
List<String> result = new ArrayList<>();
dfs(digits, new StringBuilder(), 0, map, result);
return result;
}
private void dfs(String digits, StringBuilder path, int index, Map<Character, char[]> map, List<String> result) {
if (index == digits.length()) {
result.add(path.toString());
return;
}
char[] set = map.get(digits.charAt(index));
for (char c : set) {
path.append(c);
dfs(digits, path, index + 1, map, result);
path.deleteCharAt(path.length() - 1);
}
}
}
二刷
Golang DFS
Runtime: 0 ms, faster than 100.00% of Go online submissions for Letter Combinations of a Phone Number.
Memory Usage: 2 MB, less than 45.52% of Go online submissions for Letter Combinations of a Phone Number.
func letterCombinations(digits string) []string {
if digits == "" {
return []string{}
}
m := map[string][]string{
"2": []string{"a", "b", "c"},
"3": []string{"d", "e", "f"},
"4": []string{"g", "h", "i"},
"5": []string{"j", "k", "l"},
"6": []string{"m", "n", "o"},
"7": []string{"p", "q", "r", "s"},
"8": []string{"t", "u", "v"},
"9": []string{"w", "x", "y", "z"},
}
result := []string{}
dfs(0, digits, "", m, &result)
return result
}
func dfs(index int, digits string, path string, m map[string][]string, res *[]string) error {
// fmt.Printf("path: %s\n", path)
if index == len(digits) {
*res = append(*res, path)
return nil
}
list, ok := m[string(digits[index])]
if !ok {
return fmt.Errorf("invalid char: %s", digits[index])
}
for _, c := range list {
dfs(index + 1, digits, path + c, m, res)
}
return nil
}
235. Lowest Common Ancestor of a Binary Search Tree
四刷 08/2022
Version #2 Search on BST
Time O(H) - general O(logN) - O(N)
Space O(1)
Runtime: 7 ms, faster than 64.36% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 50.8 MB, less than 6.63% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val > q.val) {
return lowestCommonAncestor(root, q, p);
}
// p.val <= q.val
while (root != null) {
if (p.val <= root.val && q.val >= root.val) {
return root;
}
if (p.val < root.val) {
root = root.left;
} else {
root = root.right;
}
}
return null;
}
}
三刷 05/2022
还是没有利用到BST的条件
重写
Version #1 General tree solution
Runtime: 10 ms, faster than 14.64% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 51.5 MB, less than 6.51% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class ResultType {
public int targetCount;
public TreeNode ancestor;
public ResultType() {}
public ResultType(int targetCount, TreeNode ancestor) {
this.targetCount = targetCount;
this.ancestor = ancestor;
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
ResultType result = helper(root, p, q);
return result.ancestor;
}
private ResultType helper(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) {
return new ResultType();
}
ResultType left = helper(node.left, p, q);
if (left.targetCount == 2) {
return left;
}
ResultType right = helper(node.right, p, q);
if (right.targetCount == 2) {
return right;
}
int count = left.targetCount + right.targetCount;
if (node == p || node == q) {
count++;
}
if (count == 2) {
return new ResultType(count, node);
}
return new ResultType(count, null);
}
}
Version #2 Binary Search on BST
Runtime: 9 ms, faster than 26.89% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 50.8 MB, less than 6.51% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
continue;
}
if (root.val < p.val && root.val < q.val) {
root = root.right;
continue;
}
return root;
}
return null;
}
}
竟然没有一刷写的好。。。。。。
还是看一刷的答案好了
60.84 %
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) return null;
if (p.val < q.val) return lowestCommonAncestorHelper(root, p.val, q.val);
else return lowestCommonAncestorHelper(root, q.val, p.val);
}
private TreeNode lowestCommonAncestorHelper(TreeNode root, int small, int large) {
if (root.val >= small && root.val <= large) return root;
else if (root.val < small) return lowestCommonAncestorHelper(root.right, small, large);
else return lowestCommonAncestorHelper(root.left, small, large);
}
}
一刷
这道题在LCA的基础上给了BST的条件
所以判断方法可以是自上而下的
不需要recursion到leaf
When we are traversing from root to its subtrees, the first node ensures that p and q are in the different subtrees is the LCA node.
If both of the targets are larger than our current node, we should look for such LCA in its right subtree. Otherwise we should look for it in its left subtree.
60.84 %
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) return null;
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}
49. Group Anagrams
三刷 08/2022
Version #2 Sort the strings
Time O(N*LlogL)
Space O(NL) - we need to store all strings in the map
Runtime: 9 ms, faster than 89.54% of Java online submissions for Group Anagrams.
Memory Usage: 55.8 MB, less than 60.06% of Java online submissions for Group Anagrams.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(str);
}
return new ArrayList<>(map.values());
}
}
Version #3 Use chararray to count
Time O(NL)
Space O(NL)
Runtime: 6 ms, faster than 99.41% of Java online submissions for Group Anagrams.
Memory Usage: 46.4 MB, less than 87.12% of Java online submissions for Group Anagrams.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] count = new char[26];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
String key = String.valueOf(count);
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(str);
}
return new ArrayList<>(map.values());
}
}
Integer 2,147,483,647
| char | 2 byte | 0 to 65,536 (unsigned) |
char is about 60 thousand
Use List<Integer> as the hashkey
查了一下int[] 在hash的时候必须是exact the same object
但是List<Integer> if two lists have the same elements, they will have the same hashcode
所以要用list<Integer> 作为key
reset的时候可以用Arrays.fill(arr, 0);
int[]转化list的时候可以用 Arrays.asList()
但是自己写的for循环在一次同时做了这两件事，感觉更好一点
6.18 %
效率明显不如version#2
应该是对List<Integer> 的hashing 很慢
进化成version #3
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return null;
// key-List<Integer>, value-List<String>
// key is the count of each character of each string
Map<List<Integer>, List<String>> map = new HashMap<>();
int[] count = new int[26]; // all lower case
for (String str : strs) {
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
List<Integer> key = new ArrayList<>();
for (int j = 0; j < count.length; j++) {
// add to key and reset to zero
key.add(count[j]);
count[j] = 0;
}
if (!map.containsKey(key)) map.put(key, new ArrayList<>());
map.get(key).add(str);
}
List<List<String>> result = new ArrayList<>();
for (List<String> list : map.values()) {
list.sort(null);
result.add(list);
}
return result;
}
}
Version #3
二刷
用char array 作为count 数组
然后直接把char array 变成String
这样我们用一个Object-String取代了一个array
提高了hashing的效率
44.96 %
原code看着简洁但是要两次hashing
//if (!map.containsKey(key)) map.put(key, new ArrayList<>());
//map.get(key).add(str);
把map.get(key) cache住以后只需要一次hashing，用空间换时间
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return null;
// key-List<Integer>, value-List<String>
// key is the count of each character of each string
Map<String, List<String>> map = new HashMap<>();
char[] count = new char[26]; // all lower case
List<String> temp = null;
for (String str : strs) {
Arrays.fill(count, (char)0);
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
String key = String.valueOf(count);
temp = map.get(key);
if (temp == null) {
temp = new ArrayList<>();
temp.add(str);
map.put(key, temp);
} else {
temp.add(str);
}
}
List<List<String>> result = new ArrayList<>();
for (List<String> list : map.values()) {
list.sort(null);
result.add(list);
}
return result;
}
}
一刷（还是version #3）
挺好的这道题 很多值得学习的地方
有空再多做做
Time O(inputSize * aveArrayLength)
44.17 %
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return new ArrayList<>();
Map<String, List<String>> map= new HashMap<>();
char[] array = new char[26];
for (String str : strs) {
Arrays.fill(array, (char)0);
for (int i = 0; i < str.length(); i++) {
array[str.charAt(i) - 'a']++;
}
String hash = new String(array);
if (map.containsKey(hash)) {
map.get(hash).add(str);
} else {
List<String> temp = new ArrayList<>();
temp.add(str);
map.put(hash, temp);
}
}
return new ArrayList<List<String>>(map.values());
}
}
Version #2
对于anagram来说invariant是它们按char顺序sort之后的string
用这个string作为key可以把所有的string归类
avage string length -> len
array size -> n
O(n len log(len) + listSize * averagelistLength)
37.71 %
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return null;
List<List<String>> result = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String curr = String.valueOf(chars);
if (!map.containsKey(curr)) map.put(curr, new ArrayList<>());
map.get(curr).add(str);
}
for (List<String> list : map.values()) {
list.sort(null);
result.add(list);
}
return result;
}
}
5. Longest Palindromic Substring
Version #1 DP
Time O(n^2)
感觉并不是太理解这道题
public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
// Write your code here
if (s == null || s.length() == 0) return "";
int len = s.length();
int maxLength = 0, start = 0, end = 0;
//boolean[i][j] means s.substring(i, j + 1) is palindrome or not
boolean[][] isPalind = new boolean[len][len];
int currLength = 0;
for (int right = 0; right < len; right++) {
for (int left = right; left >= 0; left--) {
if (right == left) {
isPalind[left][right] = true;
} else if (s.charAt(left) == s.charAt(right)) {
//next to each other
if (left + 1 == right) {
isPalind[left][right] = true;
} else {
isPalind[left][right] = isPalind[left + 1][right - 1];
}
}
if (isPalind[left][right]) {
currLength = right - left + 1;
if (currLength > maxLength) {
maxLength = currLength;
start = left;
end = right;
}
}
}
}
if (maxLength == 0) return "";
return s.substring(start, end + 1);
}
}
二刷
13.18 %
// only 1 char [Y]
// 2 chars same[Y]
// start1 s2 e2 end1
// a b c.... s a
public class Solution {
public String longestPalindrome(String s) {
//isPalindrome[i][j] -> the substring [i, j] is Palindrome
// if (i + 1 < j) -> isPalindrome[i][j] = char[i] == char[j] && isPalindrome[i + 1][j - 1]
//increase j from 0 to s.length() - 1
//decrease i from i to 0
if (s == null || s.length() == 0) return "";
int start = -1, end = -1;
int i = 0, j = 0;
int max = 0;
int len = s.length();
boolean[][] isPalindrome = new boolean[len][len];
for (j = 0; j < len; j++) {
for (i = j; i >= 0; i--) {
if (i == j) isPalindrome[i][j] = true;
else if (s.charAt(i) == s.charAt(j)) {
if (i + 1 == j) isPalindrome[i][j] = true;
else isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
} else {
isPalindrome[i][j] = false;
}
if (isPalindrome[i][j] && j - i + 1 > max) {
max = j - i + 1;
start = i;
end = j;
}
}
}
if (max == 0) return "";
return s.substring(start, end + 1);
}
}
三刷 6/3/2018
https://articles.leetcode.com/longest-palindromic-substring-part-i/
Previous DP solutions take time O(n^2) and space O(n^2)
If we expand from center, we don't need to use extra space to keep track of isPalindrome[i - 1][ j - 1]
If we go from left to right, we have all together 2length - 1 centers, (i, i)(i, i + 1) are such centers.
We expand our string iff s[i] == s[j], once they are not equal, we know that the current substring is not a valid palindrome any more.
Each expanding can take at most O(n) time, so overall we have (2n - 1)n -> O(n^2) time complexity and O(1) space complexity
beats 93.63 %
class Solution {
private int maxLeft, maxRight;
private int maxLength;
public String longestPalindrome(String s) {
if (s == null) return s;
int max = 0;
for (int i = 0; i < s.length(); i++) {
longestPalindromeHelper(s, i, i);
longestPalindromeHelper(s, i, i + 1);
}
return s.substring(maxLeft + 1, maxRight);
}
private void longestPalindromeHelper(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if ((right - left - 1) > maxLength) {
maxLength = right - left - 1;
maxLeft = left;
maxRight = right;
}
}
}
Time O(n^2)
感觉并不是太理解这道题
public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
// Write your code here
if (s == null || s.length() == 0) return "";
int len = s.length();
int maxLength = 0, start = 0, end = 0;
//boolean[i][j] means s.substring(i, j + 1) is palindrome or not
boolean[][] isPalind = new boolean[len][len];
int currLength = 0;
for (int right = 0; right < len; right++) {
for (int left = right; left >= 0; left--) {
if (right == left) {
isPalind[left][right] = true;
} else if (s.charAt(left) == s.charAt(right)) {
//next to each other
if (left + 1 == right) {
isPalind[left][right] = true;
} else {
isPalind[left][right] = isPalind[left + 1][right - 1];
}
}
if (isPalind[left][right]) {
currLength = right - left + 1;
if (currLength > maxLength) {
maxLength = currLength;
start = left;
end = right;
}
}
}
}
if (maxLength == 0) return "";
return s.substring(start, end + 1);
}
}
二刷
13.18 %
// only 1 char [Y]
// 2 chars same[Y]
// start1 s2 e2 end1
// a b c.... s a
public class Solution {
public String longestPalindrome(String s) {
//isPalindrome[i][j] -> the substring [i, j] is Palindrome
// if (i + 1 < j) -> isPalindrome[i][j] = char[i] == char[j] && isPalindrome[i + 1][j - 1]
//increase j from 0 to s.length() - 1
//decrease i from i to 0
if (s == null || s.length() == 0) return "";
int start = -1, end = -1;
int i = 0, j = 0;
int max = 0;
int len = s.length();
boolean[][] isPalindrome = new boolean[len][len];
for (j = 0; j < len; j++) {
for (i = j; i >= 0; i--) {
if (i == j) isPalindrome[i][j] = true;
else if (s.charAt(i) == s.charAt(j)) {
if (i + 1 == j) isPalindrome[i][j] = true;
else isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
} else {
isPalindrome[i][j] = false;
}
if (isPalindrome[i][j] && j - i + 1 > max) {
max = j - i + 1;
start = i;
end = j;
}
}
}
if (max == 0) return "";
return s.substring(start, end + 1);
}
}
三刷 6/3/2018
https://articles.leetcode.com/longest-palindromic-substring-part-i/
Previous DP solutions take time O(n^2) and space O(n^2)
If we expand from center, we don't need to use extra space to keep track of isPalindrome[i - 1][ j - 1]
If we go from left to right, we have all together 2length - 1 centers, (i, i)(i, i + 1) are such centers.
We expand our string iff s[i] == s[j], once they are not equal, we know that the current substring is not a valid palindrome any more.
Each expanding can take at most O(n) time, so overall we have (2n - 1)n -> O(n^2) time complexity and O(1) space complexity
beats 93.63 %
class Solution {
private int maxLeft, maxRight;
private int maxLength;
public String longestPalindrome(String s) {
if (s == null) return s;
int max = 0;
for (int i = 0; i < s.length(); i++) {
longestPalindromeHelper(s, i, i);
longestPalindromeHelper(s, i, i + 1);
}
return s.substring(maxLeft + 1, maxRight);
}
private void longestPalindromeHelper(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if ((right - left - 1) > maxLength) {
maxLength = right - left - 1;
maxLeft = left;
maxRight = right;
}
}
}
四刷
非dp intuitive solution
Runtime: 22 ms, faster than 92.94% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 39.1 MB, less than 73.74% of Java online submissions for Longest Palindromic Substring.
class Solution {
private int maxLen, start;
public String longestPalindrome(String s) {
// To check if a substring is palindrome or not
for (int i = 0; i < s.length(); i++) {
expand(s, i, i);
expand(s, i, i + 1);
}
return s.substring(start, start + maxLen);
}
private void expand(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
int len = j - i - 1;
if (len > maxLen) {
start = i + 1;
maxLen = len;
}
}
}
五刷 05/2022
Version #1 Intuitive solution without DP
Runtime: 647 ms, faster than 12.42% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 41.9 MB, less than 98.58% of Java online submissions for Longest Palindromic Substring.
class Solution {
// Space O(1)
// Time O(n^3)
private int left = 0, right = 0;
public String longestPalindrome(String s) {
// Enumerate all substrings of the string s
// Check if they are palindrome
// If yes, compare with the longest palindrome and update
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
if ((j - i > right - left)&& isPalin(s, i, j)) {
left = i;
right = j;
}
}
}
return s.substring(left, right + 1);
}
private boolean isPalin(String s, int i, int j) {
// a
// ab, aa
// aba, aac
while (j > i) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
j--;
i++;
}
return true;
}
}
Version #2 DP native
Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.
Runtime: 508 ms, faster than 17.16% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 86.3 MB, less than 16.42% of Java online submissions for Longest Palindromic Substring.
class Solution {
// Space O(n^2)
// Time O(n^2)
private int left = 0, right = 0;
public String longestPalindrome(String s) {
// aabbaa
// If we've already known that bb is a palindrome, then we can cache and reuse this result in the furhter checks
// For example when checking abba, we can reuse the [bb] is palindrome result and char a == a, so abba is a palindrome too
// The base case is each character itself is a palindrom
// for all i == j, isPalin[i][j] == true
// for all i + 1 == j, is Palin[i][j]: s.charAt(i) == s.charAt(j)
// The recursion formulat is that isPalin[i][j] (i + 1 < j): s.charAt(i) == s.charAt(j) && isPalin[i+1][j-1]
int len = s.length();
boolean[][] cache = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = j; i >= 0; i--) {
if (isPalin(s, cache, i, j) && j - i > right - left) {
left = i;
right = j;
}
}
}
return s.substring(left, right + 1);
}
private boolean isPalin(String s, boolean[][] cache, int i, int j) {
// Invalid case in our scenario
if (i > j) {
return false;
}
if (i == j) {
cache[i][j] = true;
} else if (i + 1 == j) {
cache[i][j] = s.charAt(i) == s.charAt(j);
} else {
cache[i][j] = s.charAt(i) == s.charAt(j) && cache[i + 1][j - 1];
}
return cache[i][j];
}
}
Version #3 Optimized O(n^3) solution
Runtime: 755 ms, faster than 10.06% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 43.5 MB, less than 51.91% of Java online submissions for Longest Palindromic Substring.
class Solution {
public String longestPalindrome(String s) {
// We can start checking from the longest substring length to the shortest length 1
// If a substring with length "len" is a palindrome, then we could return the substring directly
if (s == null) {
return null;
}
// babad
for (int len = s.length(); len >= 1; len--) {
for (int start = 0; start + len - 1 < s.length(); start++) {
if (isPalin(s, start, start + len - 1)) {
return s.substring(start, start + len);
}
}
}
return "";
}
private boolean isPalin(String s, int start, int end) {
// ...a...
// ...aa..., ...ab...
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
Version #4 Expand from the center
Runtime: 38 ms, faster than 74.92% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 42.3 MB, less than 91.44% of Java online submissions for Longest Palindromic Substring.
Time O(n^2)
Space O(1)
class Solution {
// Expand around the center
// cabcbad
// We can see from this example that the longest substring is abcba, there's a common substring between abcba and bcb. We could reuse the result of bcb, and expand it from the bcb center. If we failed to expand then bcb will be the longest substring starting from central "c". However if we can successfully expand, then abcba become the longest substring starting from central "c".
// The palindrome can have even or odd number of characters. Which means the center of the palindrome can be either a single character, or between two same characters. E.g. a, and aa
// So there are altogether n + (n - 1) centers
// And we just need to expand these centers to find the longest substrings expanded from those centers
private int start = 0, maxLen = 0;
public String longestPalindrome(String s) {
if (s == null) {
return null;
}
int left = 0, right = 0;
for (int center = 0; center < s.length(); center++) {
expandFromCenter(s, center, center);
expandFromCenter(s, center, center + 1);
}
return s.substring(start, start + maxLen);
}
private void expandFromCenter(String s, int left, int right) {
// The palindrome is between l + 1 and r - 1
// lr
// 012345
// ccaabc
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if (right - left - 1 > maxLen) {
maxLen = right - left - 1;
start = left + 1;
}
}
}
Version #5 Expand from center without global variable
Runtime: 57 ms, faster than 50.09% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 42.9 MB, less than 70.49% of Java online submissions for Longest Palindromic Substring.
class Solution {
// Expand around the center
// cabcbad
// We can see from this example that the longest substring is abcba, there's a common substring between abcba and bcb. We could reuse the result of bcb, and expand it from the bcb center. If we failed to expand then bcb will be the longest substring starting from central "c". However if we can successfully expand, then abcba become the longest substring starting from central "c".
// The palindrome can have even or odd number of characters. Which means the center of the palindrome can be either a single character, or between two same characters. E.g. a, and aa
// So there are altogether n + (n - 1) centers
// And we just need to expand these centers to find the longest substrings expanded from those centers
public String longestPalindrome(String s) {
if (s == null) {
return null;
}
int maxLen = 0, start = 0;
int len = s.length();
// c = 2
// 012345
// ccaacc
// len1 = 1
// len2 = 6
// left = 0
for (int center = 0; center < len; center++) {
int oddLen = expandFromCenter(s, center, center);
int evenLen = expandFromCenter(s, center, center + 1);
// start...center...end
// oddLen = (center - start + 1) * 2 - 1
// start...center center+1...end
// evenLen = (center - start + 1) * 2
if (oddLen > maxLen) {
maxLen = oddLen;
start = center + 1 - (oddLen + 1 ) / 2;
}
if (evenLen > maxLen) {
maxLen = evenLen;
start = center + 1 - evenLen / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expandFromCenter(String s, int left, int right) {
// lr
// 012345
// ccaabc
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
六刷 06/2022
Version #5 Expand from Center
优化了一下，expand的同时update最后的result，代码会简洁一点
Time O(N^2)
Space O(1)
Runtime: 36 ms, faster than 85.66% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 42.4 MB, less than 90.23% of Java online submissions for Longest Palindromic Substring.
class Solution {
public String longestPalindrome(String s) {
int[] startEnd = new int[2];
// Find the longest palindrome expanding from each index
for (int i = 0; i < s.length(); i++) {
expand(s, i, i, startEnd);
expand(s, i, i + 1, startEnd);
}
return s.substring(startEnd[0] + 1, startEnd[1]);
}
private void expand(String s, int i, int j, int[] startEnd) {
if (i > j || i >= s.length() || j >= s.length()) {
return;
}
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
// (i, j)
if (j - i > startEnd[1] - startEnd[0]) {
startEnd[0] = i;
startEnd[1] = j;
}
}
}
Subscribe to:
Posts (Atom)