2019-06-01
141. Linked List Cycle
Description
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
Solution
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode slow = head;
ListNode fast = head;
//only need check fast cause slow will always follow fast path and will be always not null.
while(fast.next!=null && fast.next.next!=null){
slow =slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
BACKTRACKING
Description
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.
Subsets : https://leetcode.com/problems/subsets/
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}
private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
Permutations : https://leetcode.com/problems/permutations/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // element already exists, skip
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
used[i] = true;
tempList.add(nums[i]);
backtrack(list, tempList, nums, used);
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}
Combination Sum : https://leetcode.com/problems/combination-sum/
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
tempList.remove(tempList.size() - 1);
}
}
}
Combination Sum II (can’t reuse same element) : https://leetcode.com/problems/combination-sum-ii/
public List<List<Integer>> combinationSum2(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/
public List<List<String>> partition(String s) {
List<List<String>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), s, 0);
return list;
}
public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
if(start == s.length())
list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
tempList.add(s.substring(start, i + 1));
backtrack(list, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}
public boolean isPalindrome(String s, int low, int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}
2019-06-12
146. LRU Cache
Description
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. 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.
The cache is initialized with a positive capacity.
Follow up: Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
Solution
import java.util.HashMap;
import java.util.Map;
class LRUCache {
CacheNode head;
CacheNode tail;
int capacity, size;
private Map<Integer,CacheNode> map;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap();
size = 0;
//set head and tail for the double linkedlist
head = new CacheNode();
tail = new CacheNode();
//make it a cycle to prevent null.
head.next = tail;
tail.pre = head;
}
public int get(int key) {
//if not exists, just return -1.
if(!map.containsKey(key)){
return -1;
}else{
CacheNode node = map.get(key);
//update the found node to head.
changeNode(node);
return node.value;
}
}
private void changeNode(CacheNode node){
//remove the current node.
node.pre.next = node.next;
node.next.pre = node.pre;
//add the current node to head.
CacheNode headNext = head.next;
head.next = node;
node.pre = head;
node.next = headNext;
headNext.pre = node;
}
public void put(int key, int value) {
CacheNode node = map.get(key);
//if exists, get it and update the node to head.
if(node != null){
node.value = value;
changeNode(node);
}else{
//if not, increment the size and add to both map and list.
size++;
node = new CacheNode(key,value);
map.put(key,node);
//move to head.
CacheNode headNext = head.next;
head.next = node;
node.next = headNext;
node.pre = head;
headNext.pre = node;
//check the capacity and remove the least used node.
if(size>capacity){
CacheNode last = tail.pre;
tail.pre = tail.pre.pre;
tail.pre.next = tail;
map.remove(last.key);
size--;
}
}
}
//create a class for double linkedlist.
class CacheNode {
int key, value;
CacheNode pre, next;
public CacheNode() {
key = -1;
value = -1;
}
public CacheNode(int key, int value) {
this.key = key;
this.value = value;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such: LRUCache obj = new
* LRUCache(capacity); int param_1 = obj.get(key); obj.put(key,value);
*/
2019-06-17
76. Minimum Window Substring
Description
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
If there is no such window in S that covers all characters in T, return the empty string “”. If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Solution
public String minWindow(String s, String t) {
int [] map = new int[128];
for (char c : t.toCharArray()) {
map[c]++;
}
int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();
while (end < s.length()) {
final char c1 = s.charAt(end);
if (map[c1] > 0) counter--;
map[c1]--;
end++;
while (counter == 0) {
if (minLen > end - start) {
minLen = end - start;
minStart = start;
}
final char c2 = s.charAt(start);
map[c2]++;
if (map[c2] > 0) counter++;
start++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
Longest Substring - at most K distinct characters
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int[] map = new int[256];
int start = 0, end = 0, maxLen = Integer.MIN_VALUE, counter = 0;
while (end < s.length()) {
final char c1 = s.charAt(end);
if (map[c1] == 0) counter++;
map[c1]++;
end++;
while (counter > k) {
final char c2 = s.charAt(start);
if (map[c2] == 1) counter--;
map[c2]--;
start++;
}
maxLen = Math.max(maxLen, end - start);
}
return maxLen;
}
Longest Substring - at most 2 distinct characters
public int lengthOfLongestSubstringTwoDistinct(String s) {
int[] map = new int[128];
int start = 0, end = 0, maxLen = 0, counter = 0;
while (end < s.length()) {
final char c1 = s.charAt(end);
if (map[c1] == 0) counter++;
map[c1]++;
end++;
while (counter > 2) {
final char c2 = s.charAt(start);
if (map[c2] == 1) counter--;
map[c2]--;
start++;
}
maxLen = Math.max(maxLen, end - start);
}
return maxLen;
}
LongestSubstring - without repeating character
public int lengthOfLongestSubstring2(String s) {
int[] map = new int[128];
int start = 0, end = 0, maxLen = 0, counter = 0;
while (end < s.length()) {
final char c1 = s.charAt(end);
if (map[c1] > 0) counter++;
map[c1]++;
end++;
while (counter > 0) {
final char c2 = s.charAt(start);
if (map[c2] > 1) counter--;
map[c2]--;
start++;
}
maxLen = Math.max(maxLen, end - start);
}
return maxLen;
}
41. First Missing Positive
Description
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Solution
class Solution {
public int firstMissingPositive(int[] nums) {
int i = 0;
int len = nums.length;
while(i<len){
if(nums[i]==i+1 || nums[i]<=0 || nums[i]>len) i++;
//set N = nums[i] => nums[N-1]==N. all positive num must follow or
//it's missing.
else if(nums[nums[i]-1] != nums[i]){
swap(nums, i, nums[i]-1);
}
else i++;
}
i = 0;
//find the first missiong one by iterate from start.
while(i<len && nums[i]==i+1) i++;
return i+1;
}
private void swap(int[] A, int i, int j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
2019-06-19
139. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.
xample 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Solution
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
// dp[i] means s.substring(0,i) is/is not breakable.
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}
2019-06-20
224. Basic Calculator
Description
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
Example 1:
Input: "1 + 1"
Output: 2
Example 2:
Input: " 2-1 + 2 "
Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.
Solution
class Solution {
public int calculate(String s) {
int len = s.length(),sign = 1, result = 0;
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<len;i++){
if(Character.isDigit(s.charAt(i))){
int sum = s.charAt(i) - '0';
//get the full number until reach the end or any non-digit.
while(i<len-1 && Character.isDigit(s.charAt(i+1))){
sum = sum *10 + s.charAt(i+1)-'0';
i++;
}
//put it into result.
result += sum * sign;
}else if(s.charAt(i) == '+'){
//set sign as +/- 1.
sign = 1;
}else if(s.charAt(i) == '-'){
sign = -1;
}else if(s.charAt(i) == '('){
//store all the result before the left parentheses.
stack.push(result);
//and also the sign before the left.
stack.push(sign);
//reinit.
result = 0;
sign = 1;
}else if(s.charAt(i)==')'){
//reach the end of the parentheses, add the result in the parentheses with previous sum.
result = result * stack.pop() + stack.pop();
}
}
return result;
}
}
2019-06-24
923. 3Sum With Multiplicity
Description
Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < k and A[i] + A[j] + A[k] == target.
As the answer can be very large, return it modulo 10^9 + 7.
Example 1:
Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation:
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
Example 2:
Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation:
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.
Note:
3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300
Solution
class Solution {
public int threeSumMulti(int[] A, int target) {
//when using int, the multiplication result of c[i] * c[j] * c[k] will be overflow. The max integer value is 2147483647. And 3000 * 3000 * 3000 = 18000000000, it is much more larger than integer maximun value.
long[] count = new long[101];
for(int a : A){
count[a]++;
}
long res = 0;
//set i from 0 to 100.
for(int i = 0;i<=100;i++){
//set j always larger than i.
for(int j = i ;j<=100;j++){
//k will be the rest.
int k = target-i-j;
//if k is invalid.
if(k>100 || k<0) continue;
//situ.1 3 numberis the same.
if(i==j && j==k){
res += count[i] * (count[i] - 1) * (count[i] - 2) / 6;
}else if(i==j && j!=k ){
//situ.2 i==j!=k
res += count[i] * (count[i] - 1) / 2 * count[k];
}else if(j<k){
//situ.3 3 are all diff.
res += count[i] * count[j] * count[k];
}
}
}
return (int) (res% (1e9+7));
}
}
103. Binary Tree Zigzag Level Order Traversal
Description
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).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Solution
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList();
if(root==null){
return res;
}
Queue<TreeNode> queue = new LinkedList();
boolean isRev = false;
queue.offer(root);
while(!queue.isEmpty()){
//the trick is to set two queue:
//deque is for store the value from two directions.
Deque<Integer> temp = new LinkedList();
//queue is for store treenode for next level.
Queue<TreeNode> tempQ = new LinkedList();
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
if(isRev){
temp.addFirst(cur.val);
}else{
temp.addLast(cur.val);
}
if(cur.left != null){
tempQ.offer(cur.left);
}
if(cur.right != null){
tempQ.offer(cur.right);
}
}
res.add(new LinkedList(temp));
queue = tempQ;
isRev = !isRev;
}
return res;
}
}
2019-06-25
482. License Key Formatting
Desc
You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.
Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.
Given a non-empty string S and a number K, format the string according to the rules described above.
Example 1:
Input: S = "5F3Z-2e-9-w", K = 4
Output: "5F3Z-2E9W"
Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.
Example 2:
Input: S = "2-5g-3-J", K = 2
Output: "2-5G-3J"
Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.
Note:
The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.
Solution
class Solution {
public String licenseKeyFormatting(String S, int K) {
String S1 = S.replace("-","").toUpperCase();
//make a string builder.
StringBuilder sb = new StringBuilder();
for(int i = 0;i<S1.length();i++){
//add all char to sb.
sb.append(S1.charAt(i));
}
int len = sb.toString().length();
//insert dash to specific position.
for(int i = K;i<len;i+=K){
sb.insert(len-i,"-");
}
return sb.toString();
}
}
124. Binary Tree Maximum Path Sum
Description
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
Solution
class Solution {
int maxSum;
public int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
maxPathDown(root);
return maxSum;
}
private int maxPathDown(TreeNode root){
if(root==null) return 0;
//max value from current node to the end through left.
int left = Math.max(0, maxPathDown(root.left));
//max value from current node to the end through right.
int right = Math.max(0, maxPathDown(root.right));
//update max, since left/right is larger than 0, l+r+root.val will always be the
//largest value for all paths go through cur node.
maxSum = Math.max(maxSum, left+right+root.val);
//return the max value from cur node to the bottom.
return Math.max(left,right)+root.val;
}
}
2019-06-26
91. Decode Ways
Description
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Solution
class Solution {
public int numDecodings(String s) {
int N = s.length();
int[] dp = new int[N+1];
//one digit itself is always one way to decode.
dp[N] = 1;
//if it's like "06" it's not a valid way.
dp[N-1] = s.charAt(N-1) != '0' ? 1 : 0;
//start from N-2.
for(int i = N-2;i>=0;i--){
//if it's 0 than it's 0 way to decode cause it's invalid to start with 0.
if(s.charAt(i)=='0'){
continue;
}else{
//parse int for i,i+1.
int n = Integer.parseInt(s.substring(i,i+2));
//if it's valid, thanthere's two ways to decode, i+ 1 and i + 2.
dp[i] = n<=26?dp[i+1]+dp[i+2]:dp[i+1];
}
}
return dp[0];
}
}
98. Validate Binary Search Tree
Description
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
=======
# 2019-06-25
## 482. License Key Formatting
### Desc
You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.
Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.
Given a non-empty string S and a number K, format the string according to the rules described above.
Example 1: Input: S = “5F3Z-2e-9-w”, K = 4
Output: “5F3Z-2E9W”
Explanation: The string S has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed. Example 2: Input: S = “2-5g-3-J”, K = 2
Output: “2-5G-3J”
Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above. Note: The length of string S will not exceed 12,000, and K is a positive integer. String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-). String S is non-empty.
### Solution
```java
class Solution {
public String licenseKeyFormatting(String S, int K) {
String S1 = S.replace("-","").toUpperCase();
//make a string builder.
StringBuilder sb = new StringBuilder();
for(int i = 0;i<S1.length();i++){
//add all char to sb.
sb.append(S1.charAt(i));
}
int len = sb.toString().length();
//insert dash to specific position.
for(int i = K;i<len;i+=K){
sb.insert(len-i,"-");
}
return sb.toString();
}
}
124. Binary Tree Maximum Path Sum
Description
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
Solution
//All about INORDER.
class Solution1 {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack();
TreeNode cur = root;
TreeNode pre = null;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(pre != null && cur.val<=pre.val){
return false;
}
pre = cur;
cur = cur.right;
}
return true;
}
}
class Solution2 {
List<Integer> list;
public boolean isValidBST(TreeNode root) {
list = new ArrayList<Integer>();
inorder(root);
for(int i = 0;i<list.size()-1;i++){
if(list.get(i)>=list.get(i+1)){
return false;
}
}
return true;
}
private void inorder(TreeNode root){
if (root == null)
return;
inorder(root.left);
list.add(root.val);
inorder(root.right);
}
}
151. Reverse Words in a String
Description
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: " hello world! "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Note:
A word is defined as a sequence of non-space characters. Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces. You need to reduce multiple spaces between two words to a single space in the reversed string.
###Solution
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
//+ means will appear one or more times, * is 0 or above.
String[] slist = s.split("\\ +");
for(int i = slist.length-1;i>=0;i--){
sb.append(slist[i].trim());
sb.append(" ");
}
return sb.toString().trim();
=======
class Solution {
int maxSum;
public int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
maxPathDown(root);
return maxSum;
}
private int maxPathDown(TreeNode root){
if(root==null) return 0;
//max value from current node to the end through left.
int left = Math.max(0, maxPathDown(root.left));
//max value from current node to the end through right.
int right = Math.max(0, maxPathDown(root.right));
//update max, since left/right is larger than 0, l+r+root.val will always be the
//largest value for all paths go through cur node.
maxSum = Math.max(maxSum, left+right+root.val);
//return the max value from cur node to the bottom.
return Math.max(left,right)+root.val;
}
}
2019-06-27
67. Add Binary
Description
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Solution
class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
String ls,ss;
//find the longer one.
if(a.length()<b.length()){
ls = b;
ss = a;
}else{
ls = a;
ss = b;
}
int len = ls.length();
//new a it array.
int[] add = new int[len];
for(int i = 0; i<len;i++){
add[i] = ls.charAt(i) - '0';
}
int offset = len - ss.length();
for(int i = 0 ;i<ss.length();i++){
//add the short one to add[]. using offset.
add[i + offset] += (ss.charAt(i)-'0');
}
int carry = 0;
//parse the whole
for(int i = len-1;i>=0;i--){
int sum = add[i] + carry;
carry = sum /2;
add[i] = sum % 2;
}
//if there's a carry we should append to head.
if(carry !=0){
sb.append(carry);
}
for(int i = 0 ;i<len;i++){
sb.append(add[i]);
}
return sb.toString();
}
}