10 March 2020
LeetCode(112) -- 228, 229, 236
by Jerry Zhang
P228. Summary Ranges (Medium)
Given a sorted integer array without duplicates, return the summary of its ranges.
My Solution
class Solution {
public List<String> summaryRanges(int[] nums) {
StringBuilder sb = new StringBuilder();
List<String> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
sb.append(nums[i]);
if (i == nums.length - 1) {
list.add(sb.toString());
break;
}
boolean isRange = false;
while (i + 1 < nums.length && nums[i + 1] - nums[i] == 1) {
if (!isRange) {
sb.append("->");
}
isRange = true;
i++;
}
if (isRange) {
sb.append(nums[i]);
}
list.add(sb.toString());
sb.setLength(0);
}
return list;
}
}
100%
The Best Solution
class Solution {
public List<String> summaryRanges(int[] nums) {
int idx = 0;
List<String> summaryRanges = new ArrayList<>();
for( int i = 0; i < nums.length; i++ ){
idx = i;
while( i < nums.length - 1 && ( nums[ i + 1] == nums[i] + 1 ) ){
i++;
}
if( idx == i ){
summaryRanges.add( Integer.toString(nums[idx]) );
}
else{
StringBuilder sb = new StringBuilder();
sb.append(Integer.toString(nums[idx]));
sb.append("->");
sb.append(Integer.toString(nums[i]));
summaryRanges.add( sb.toString() );
}
}
return summaryRanges;
}
}
P229. Majority Element II (Medium)
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
My Solution
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<>();
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
Integer occurrences = map.getOrDefault(num, 0);
map.put(num, occurrences + 1);
}
int times = nums.length / 3;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > times) {
ans.add(entry.getKey());
}
}
return ans;
}
}
33%
The Best Solution
class Solution {
public List<Integer> majorityElement(int[] nums) {
int count1 = 0, count2 = 0;
int num1 = 0, num2 = 1;
for (int num : nums) {
if (num == num1) {
count1++;
} else if (num == num2) {
count2++;
} else if (count1 == 0) {
num1 = num;
count1++;
} else if (count2 == 0) {
num2 = num;
count2++;
} else {
count1--;
count2--;
}
}
int n = nums.length;
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == num1) {
count1++;
}
if (num == num2) {
count2++;
}
}
List<Integer> res = new ArrayList<>();
if (count1 > n / 3) {
res.add(num1);
}
if (count2 > n / 3) {
res.add(num2);
}
return res;
}
}
P236. Lowest Common Ancestor of a Binary Tree (Medium)
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
My Solution
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
ArrayList<TreeNode> ancestor1 = new ArrayList<>();
ArrayList<TreeNode> ancestor2 = new ArrayList<>();
ancestor1.add(p);
ancestor2.add(q);
List<TreeNode> list1 = dfs(root, ancestor1);
List<TreeNode> list2 = dfs(root, ancestor2);
for (TreeNode treeNode : list1) {
if (list2.contains(treeNode)) {
return treeNode;
}
}
return null;
}
private List<TreeNode> dfs(TreeNode root, List<TreeNode> ancestor) {
if (root == null) {
return ancestor;
}
dfs(root.left, ancestor);
dfs(root.right, ancestor);
if (ancestor.contains(root.left) || ancestor.contains(root.right)) {
ancestor.add(root);
return ancestor;
}
return ancestor;
}
}
5% 很慢，勉强用最笨的办法做出来了。
方法一：
Solution
class Solution {
private TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
recurseTree(root, p, q);
return ans;
}
private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
if (currentNode == null) {
return false;
}
int left = recurseTree(currentNode.left, p, q) ? 1 : 0;
int right = recurseTree(currentNode.right, p, q) ? 1 : 0;
int mid = (currentNode == p || currentNode == q) ? 1 : 0;
if (mid + left + right >= 2) {
this.ans = currentNode;
}
return mid + left + right > 0;
}
}
100% 这个方法最好。
方法二：
先用hashmap把所有父子关系记录清楚，然后顺着一条线把所有节点放到一个set中，从另一个节点向上找，第一个交点就是答案。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Deque<TreeNode> stack = new ArrayDeque<>();
Map<TreeNode, TreeNode> parent = new HashMap<>();
parent.put(root, null);
stack.push(root);
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(node.right);
}
}
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
while (!ancestors.contains(q)) {
q = parent.get(q);
}
return q;
}
}
24%
方法三：
class Solution {
private static int BOTH_PENDING = 2;
private static int LEFT_DONE = 1;
private static int BOTH_DONE = 0;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();
stack.push(new Pair<>(root, Solution.BOTH_PENDING));
boolean one_node_found = false;
TreeNode LCA = null;
TreeNode child_node = null;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> top = stack.peek();
TreeNode parent_node = top.getKey();
int parent_state = top.getValue();
if (parent_state != Solution.BOTH_DONE) {
if (parent_state == Solution.BOTH_PENDING) {
if (parent_node == p || parent_node == q) {
if (one_node_found) {
return LCA;
} else {
one_node_found = true;
LCA = stack.peek().getKey();
}
}
child_node = parent_node.left;
} else {
child_node = parent_node.right;
}
stack.pop();
stack.push(new Pair<TreeNode, Integer>(parent_node, parent_state - 1));
if (child_node != null) {
stack.push(new Pair<>(child_node, Solution.BOTH_PENDING));
}
} else {
if (LCA == stack.pop().getKey() && one_node_found) {
LCA = stack.peek().getKey();
}
}
}
return null;
}
}
16%
tags: LeetCode