# 2019-03-01

## 34. Find First and Last Position of Element in Sorted Array

### Description

Medium Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1:

``````Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
``````

Example 2:

``````Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
``````

### Solution

``````//using binary search twice and find left/right side each time;
public int[] searchRange(int[] nums, int target) {
int i = 0;
int j = nums.length - 1;
int[] res = new int[]{-1, -1};
if (nums.length == 0) {
return res;
}
int mid = 0;
while (i < j) {
mid = (i + j) / 2;
//has to use >= not > because we are looking at left side,
//so when it's equal should set right j to mid;
if (nums[mid] >= target) {
j = mid;
} else {
i = mid + 1;
}
}
if (nums[i] != target) {
return res;
}
res = i;
//no need to set i to 0;
j = nums.length - 1;
while (i < j) {
mid = (i + j) / 2 + 1;
if (nums[mid] > target) {
j = mid - 1;
} else {
i = mid;
}
}
res = j;
return res;
}
``````

## 35. Search Insert Position

### Description

Easy Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1:

``````Input: [1,3,5,6], 5
Output: 2
``````

Example 2:

``````Input: [1,3,5,6], 2
Output: 1
``````

Example 3:

``````Input: [1,3,5,6], 7
Output: 4
``````

Example 4:

``````Input: [1,3,5,6], 0
Output: 0
``````

### Solution

``````//Using Binary Search, if found then return, if not, just return the lo.
public int searchInsert(int[] nums, int target) {
int lo=0,hi=nums.length-1;
while(lo<=hi){
int mid = (lo+hi)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
lo = mid + 1;
}else{
hi = mid - 1;
}
}
return lo;
}
``````

## 39. Combination Sum

### Description

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1:

``````Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
,
[2,2,3]
]
``````

Example 2:

``````Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
``````

### Solution

``````class Solution {

//Global Variable for convenience
HashSet<Integer> hash;
int N;

public List<List<Integer>> combinationSum(int[] candidates, int target)     {
hash = new HashSet(Arrays.asList(candidates));
N = candidates.length;
List<List<Integer>> res = new ArrayList();
helper(candidates,0,new ArrayList(),target,res);
return res;
}

//using recursion and construct
public void helper(int[] candidates, int index,List<Integer> temp,
int target,List<List<Integer>> res){
//situation that should stop searching.
if(index>=N || target<0){return;}
//if found one, add to the result.
if(target==0){
//must using deep copy! Or result will be all empty list.
List r = new ArrayList();
}
for(int i = index;i<candidates.length;i++){
//adding candidates to temp one at a time
//!!must using index to record position, or it will have duplicate result
//like [2,2,3] & [2,3,2].
helper(candidates,i, temp,target-candidates[i],res);
//remember to remove it afterward.
temp.remove(temp.size()-1);
}
}
}
``````

## 40. Combination Sum II

### Description

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

**All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.** Example 1:

``````Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
``````

Example 2:

``````Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],

]
``````

### Solution

``````class Solution {

int[] A;
int N;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
A = candidates;
N = candidates.length;
List<List<Integer>> res = new ArrayList<>();
helper(res,new ArrayList<Integer>(),target,0);
return res;
}

private void helper(List<List<Integer>> res, List<Integer> path,int remain, int index){
if(remain<=0){
if(remain == 0){
}
return;
}
for(int i = index;i<N;i++){
//tricky part: avoid duplication.
if(i>index && A[i-1]==A[i])continue;
helper(res,path,remain-A[i],i+1);
path.remove(path.size()-1);
}
}
}
``````

## 66. Plus One

### Description

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

``````Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
``````

Example 2:

``````Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
``````

### Solution

``````class Solution {
//the clever version of the solution.
public int[] plusOne(int[] digits) {
int n = digits.length;
for(int i = n-1;i>=0;i--){
//if the current digits will not carry one
//then just add one and return.
if(digits[i]<9){
digits[i]++;
return digits;
}else{
//if current digit is 9, then need to carry one
//since we only add one, then the current digits must be 0.
//set digit to 0 and continue to the next digit.
digits[i] = 0;
}
}
//if finally we still not return, means it's 9 all the way, so just carry One
int[] newNumber = new int [n+1];
newNumber = 1;
return newNumber;
}
}
``````

# 2019-03-03

### 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 {
//using iteration to go through every bit of the string and add them up.
//Recording carry and add to next iteration.
public String addBinary(String a, String b) {
StringBuffer res = new StringBuffer();
//start from the end of the string.
int i = a.length()-1, j = b.length() -1;
//record carry for each step.
int carry = 0;
while(i>=0 || j>=0){
int sum = carry;
if(i>=0){sum += (a.charAt(i--)-'0');}
if(j>=0){sum += (b.charAt(j--)-'0');}
//update carry.
carry = sum / 2;
res.append(sum%2);
}
if(carry == 1){
res.append(1);
}
return res.reverse().toString();
}
}
``````

## 135. Candy

### Description

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?

Example 1:

``````Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
``````

Example 2:

``````Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.The third child gets 1 candy because it satisfies the above two conditions.
``````

### Solution

``````class Solution {
//the idea is to go through the array twice, one from head to end, one from end to head.
public int candy(int[] ratings) {
int N = ratings.length;
if(N==0){return 0;}
int[] height = new int[N];
int res = 0;
height =1;
//first iteration, make sure the current one is more than left one.
for(int i = 1;i<N;i++){
height[i] = 1;
if(ratings[i]>ratings[i-1]){
height[i] = height[i-1]+1;
}
}
//make sure suitable to right one.
for(int i = N-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
height[i] = Math.max(height[i],height[i+1]+1);
}
}
//sum up
for(int i:height){res += i;}
return res;
}
}
``````

## 219. Contains Duplicate II

### Description

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

``````Input: nums = [1,2,3,1], k = 3
Output: true
``````

Example 2:

``````Input: nums = [1,0,1,1], k = 1
Output: true
``````

Example 3:

``````Input: nums = [1,2,3,1,2,3], k = 2
Output: false
``````

### Solution

``````class Solution {
//using map to store location information.
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap();
for(int i = 0;i<nums.length;i++){
if(map.containsKey(nums[i])){
int pre = map.get(nums[i]);
//check if its distance is less than k
if(i-pre<=k){
return true;
}
}
map.put(nums[i],i);
}
return false;
}
}
``````

## 220. Contains Duplicate III

### Description

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

``````Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
``````

Example 2:

``````Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
``````

Example 3:

``````Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
``````

### Solution

``````public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(k<1 || t<0 || nums==null || nums.length<2) return false;

SortedSet<Long> set = new TreeSet<Long>();

for(int j=0; j<nums.length; j++) {
SortedSet<Long> subSet =  set.subSet((long)nums[j]-t, (long)nums[j]+t+1);
if(!subSet.isEmpty()) return true;

if(j>=k) {
set.remove((long)nums[j-k]);
}
}
return false;
}
}
``````

## 9. Palindrome Number

### Description

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

``````Input: 121
Output: true
``````

Example 2:

``````Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
``````

Example 3:

``````Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
``````

### Solution

``````class Solution {
public boolean isPalindrome(int x) {
if(x<0){
return false;
}
String s = String.valueOf(x);
int i = 0;
int j = s.length()-1;
char[] charList = s.toCharArray();
while(i<=j){
if(charList[i]!=charList[j]){
return false;
}
i++;
j--;
}
return true;
}
}
``````
``````class Solution {
public boolean isPalindrome(int x) {
if (x<0 || (x!=0 && x%10==0)) return false;
int rev = 0;
while(x>rev){
rev = rev * 10 + x %10;
x = x/10;
}
return (x==rev||x == rev/10);
}
}
``````

## 0. Check Palindrome

``````bool IsPalindrome(const char *s, int n)
{
//非法输入
if (s == NULL || n < 1)
return false;
char *front, *back;

//初始化头指针和尾指针
front = s;
back = s + n - 1;

while (front < back)
{
if (*front != *back)
return false; // 不是回文，立即返回
++front;
--back;
}
return true; // 是回文
}
``````

``````bool IsPalindrome2(const char *s, int n)
{
if (s == NULL || n < 1)
return false; // 非法输入
char *first, *second;

int m = ((n >> 1) - 1) >= 0 ? (n >> 1) - 1 : 0; // m is the middle point of s
first = s + m;
second = s + n - 1 - m;

while (first >= s)
if (s[first--] != s[second++])
return false; // not equal, so it's not apalindrome
return true; // check over, it's a palindrome
}
``````

# 2019-03-06

## 266. Palindrome Permutation

Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

EXAMPLE

``````Input:  Tact Coa
Output: True (permutations: "taco cat", "atco cta", etc.)
DETAIL:

check if it is ANSI or Unicode
``````

``````/**
* It is also possible to finish the whole process within one pass, but as
* it is not always a optimal solution. I skip it here. What's more, bit
* vector can be used here too, but again, it is the same strategy and
* increase the opportunity of writing wrong code(bit operations are always
* easy to become a mess and hard to understand
*/
public static boolean isPalindromePermutation(String str){
String newStr = str.toLowerCase();
int[] alphabet = new int;
int oddCount = 0;
// 1 - pass
for (int i = 0; i < newStr.length(); i++){
if (newStr.charAt(i) != ' ') {
alphabet[newStr.charAt(i)]++;
}
}
// 2 - pass
for (int i = 0; i < alphabet.length; i++){
if (alphabet[i] != 0){
if (alphabet[i] % 2 != 0){
oddCount++;
}
}
}
if (oddCount > 1){
return false;
}

return true;
}
``````

## 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

``````Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
``````
``````class Solution {

int N;
int[] Nums;
public List<List<Integer>> permuteUnique(int[] nums) {
Nums = nums;
N = nums.length;
List<List<Integer>> res = new ArrayList();
//to Avoid duplication.
boolean[] used = new boolean[N];
//in order to avoid duplication need to sort and check the one befor is the same.
Arrays.sort(nums);
helper(used,new ArrayList(),res);
return res;
}

public void helper(boolean[] used,List<Integer> temp, List<List<Integer>> res){
//if temp is full ,add to res.But remember to copy it instead of add it to res directly.
if(temp.size() == N){
List<Integer> a = new ArrayList(temp);
}
for(int i = 0; i<N; i++){
// if the last one is same and not used then continue so it will only appear once.
if(i>0 && Nums[i-1]==Nums[i] && !used[i-1]) continue;
if(!used[i]){
used[i] = true;
helper(used,temp,res);
temp.remove(temp.size()-1);
used[i] = false;
}
}
}
}
``````

## 36. Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Example 1:

Input: [ [“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”], [“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”], [”.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”], [“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”], [“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”], [“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”], [”.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”], [”.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”], [”.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”] ] Output: true Example 2:

Input: [ [“8”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”], [“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”], [”.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”], [“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”], [“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”], [“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”], [”.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”], [”.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”], [”.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”] ] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid. Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules. The given board contain only digits 1-9 and the character ‘.’. The given board size is always 9x9.

``````class Solution {
/**
* @param board: the board
@return: wether the Sudoku is valid
*/
public boolean isValidSudoku(char[][] board) {
if(board == null || board.length == 0 || board.length == 0) return false;

int m = 9, n = 9;
// check row
boolean[] visited = new boolean;
for(int i = 0; i < m; i++){
Arrays.fill(visited, false);
for(int j = 0; j < n; j++){
if(!precess(visited, board[i][j])) return false;
}
}

for(int i = 0; i < n; i++){
Arrays.fill(visited, false);
for(int j = 0; j < m; j++){
if(!precess(visited, board[j][i])) return false;
}
}

for(int i = 0; i < m; i+=3){

for(int j = 0; j < n; j+=3){
Arrays.fill(visited, false);
for(int k = 0; k < 9; k++){
if(!precess(visited, board[i+k/3][j+k%3])) return false;
}

}
}
return true;

}

private boolean precess(boolean[] visited, char c){
if(c == '.') return true;
int num = c - '0';
if(num > 9 || num < 1 || visited[num-1]) return false;
visited[num-1] = true;
return true;
}
};
``````

## 38. Count and Say

### Description

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
2. 11
3. 21
4. 1211
5. 111221 1 is read off as “one 1” or 11. 11 is read off as “two 1s” or 21. 21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

``````Input: 1
Output: "1"
``````

Example 2:

``````Input: 4
Output: "1211"
``````

### Solution

``````class Solution {
public String countAndSay(int n) {
if(n == 1){
return "1";
}
StringBuffer sb = new StringBuffer("1");
for(int i = 1;i<n;i++){
String temp = sb.toString();
sb = new StringBuffer();
char c = temp.charAt(0);
int count  = 1;
int size = temp.length();
for(int j = 1;j<size;j++){
if(temp.charAt(j)==c){
count++;
}else{
sb.append(count);
sb.append(c);
count = 1;
c = temp.charAt(j);
}
}
sb.append(count);
sb.append(c);
}
return sb.toString();
}
}
``````

## 150. Evaluate Reverse Polish Notation

### Description

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation. Example 1:

``````Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
``````

Example 2:

``````Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
``````

Example 3:

``````Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
``````

### Solution

``````class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> s = new Stack();
for(int i = 0;i<tokens.length;i++){
String c = tokens[i];
if(c.equals("+")){
int a = s.pop();
int b = s.pop();
s.push(a+b);
}else if(c.equals("-")){
int a = s.pop();
int b = s.pop();
s.push(b-a);
}else if(c.equals("*")){
int a = s.pop();
int b = s.pop();
s.push(a*b);
}else if(c.equals("/")){
int a = s.pop();
int b = s.pop();
s.push(b/a);
}else{
s.push(Integer.parseInt(tokens[i]));
}
}
return s.pop();
}
}
``````

## 49. Group Anagrams

### Description

Given an array of strings, group anagrams together.

Example:

``````Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]

``````

### Solution

``````class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<Integer>> map = new HashMap();
List<List<String>> res = new ArrayList();
for(int i = 0;i<strs.length;i++){
String s = strs[i];
char[] c = s.toCharArray();
Arrays.sort(c);
s = new String(c);
List<Integer> l = map.getOrDefault(s,new ArrayList<Integer>());
map.put(s,l);
}
for(Map.Entry<String,List<Integer>> e: map.entrySet()){
List<String> temp = new ArrayList();
for(int i : e.getValue()){
}
}
return res;
}
}
``````

## 289. Game of Life

### Description

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

``````Input:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
Output:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
``````

Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

### Solution

0 : 上一轮是0，这一轮过后还是0 1 : 上一轮是1，这一轮过后还是1 2 : 上一轮是1，这一轮过后变为0 3 : 上一轮是0，这一轮过后变为1

``````class Solution {
public void gameOfLife(int[][] board) {
//     before  after
// 0    0       0
// 1    1       1
// 2    1       0
// 3    0       1
int m = board.length, n = board.length;
for(int i = 0; i<m;i++){
for(int j = 0;j<n ;j++){
int count = findLivingNeibor(board, i,j);
if(board[i][j]==1){
if(count == 2|| count==3){
board[i][j] = 1;
}else{
board[i][j] = 2;
}
}else{
if(count == 3){
board[i][j] = 3;
}
}
}
}
for(int i = 0; i<m;i++){
for(int j = 0;j<n ;j++){
board[i][j] = board[i][j]%2;
}
}
}

public int findLivingNeibor(int[][] board, int i,int j){
int count = 0;
int m = board.length, n = board.length;
if(i>0){
count += board[i-1][j]==1||board[i-1][j]==2?1:0;
}
if(i<m-1){
count += board[i+1][j]==1||board[i+1][j]==2?1:0;
}
if(j>0){
count += board[i][j-1]==1||board[i][j-1]==2?1:0;
}
if(j<n-1){
count += board[i][j+1]==1||board[i][j+1]==2?1:0;
}
if(i>0 && j>0){
count += board[i-1][j-1]==1||board[i-1][j-1]==2?1:0;
}
if(i>0 && j<n-1){
count += board[i-1][j+1]==1||board[i-1][j+1]==2?1:0;
}
if(i<m-1 && j>0){
count += board[i+1][j-1]==1||board[i+1][j-1]==2?1:0;
}
if(i<m-1 && j<n-1){
count += board[i+1][j+1]==1||board[i+1][j+1]==2?1:0;
}
return count;

}
}
``````

# 2019-03-09

## 274. H-Index

### Description

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

``````Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining
two with no more than 3 citations each, her h-index is 3.
``````

Note: If there are several possible values for h, the maximum one is taken as the h-index.

### Solution

``````class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
if(citations == null || len == 0) return 0;
int[] record  = new int[len+1];
for(int c : citations){
if(c>len){
record[len]++;
}else{
record[c] ++;
}
}

if(record[len]>=len){
return len;
}else{
for(int i = len-1;i>=0;i--){
record[i] += record[i+1];
if(record[i]>=i){
return i;
}
}
}
return 0;
}
}
``````

### FollowUp

what if the citations are now guaranteed to be sorted in ascending order? solve it in logarithmic time complexity.

### Solution-2

``````class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
int low = 0, high = len-1;
while(low<=high){
int mid = (low+high)/2;
if((len-mid)>citations[mid]){
low = mid + 1;
}else{
high = mid-1;
}
}
return len-low;
}

}
``````

## 00.Heapify

O(n)的时间复杂度完成堆化

### Solution

Heapify的基本思路就是：Given an array of N values, a heap containing those values can be built by simply “sifting” each internal node down to its proper location：

start with the last internal node swap the current internal node with its smaller child, if necessary then follow the swapped node down continue until all internal nodes are done Complexity 时间复杂度 O(n)，空间复杂度 O(1)

``````public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
public void heapify(int[] A) {
int start = A.length/2;
for (int i=start;i>=0;i--)
shiftDown(i, A);
}

private void shiftDown(int ind, int[] A){
int size = A.length;
int left = ind*2+1;
int right = ind*2+2;
while (left<size || right<size){
int leftVal = (left<size) ? A[left] : Integer.MAX_VALUE;
int rightVal = (right<size) ? A[right] : Integer.MAX_VALUE;
int next = (leftVal<=rightVal) ? left : right;
if (A[ind]<A[next]) break;
else {
swap(A, ind,next);
ind = next;
left = ind*2+1;
right = ind*2+2;
}
}
}

private void swap(int[] A, int x, int y){
int temp = A[x];
A[x] = A[y];
A[y] = temp;
}
}
``````

## 57. Insert Interval

### Description

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

``````Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
``````

Example 2:

``````Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
``````

### Solution

``````/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if(intervals==null || newInterval==null){
return null;
}
List<Interval> res = new ArrayList();
int insertIndex = 0;
//there are only three possible situation, where an interval is to the new interval left/right/intervaled.
for(Interval interval : intervals){
//it means this interval is left to the newone.
if(interval.end < newInterval.start){
insertIndex++;
}else if(interval.start > newInterval.end){
//it means this interval is right to the newone.
}else{
//overlapped.
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);
}
}
//insert to the right position.
return res;
}
}
``````

# 2019-03-15

## 273. Integer to English Words

### Description

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

Example 1:

``````Input: 123
Output: "One Hundred Twenty Three"
``````

Example 2:

``````Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"
``````

Example 3:

``````Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
``````

Example 4:

``````Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"
``````

### Solution

``````class Solution {
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
String[] bigs = {" Thousand", " Million", " Billion"};
StringBuilder sb = new StringBuilder();
// handle less than 1000
sb.append(intToWords(num % 1000));
num /= 1000;
int i = 0;
while (num > 0) {
if (num % 1000 != 0) {
sb.insert(0, intToWords(num % 1000) + bigs[i]);
}
i++;
num /= 1000;
}
// need to trim or willl have space at the head or tail.
return sb.toString().trim();
}

private String intToWords(int num) {
StringBuilder sb = new StringBuilder();
// Don't forget the space so it will format the string.
String[] digits = {
"", " One", " Two", " Three", " Four", " Five", " Six", " Seven", " Eight", " Nine"
};
String[] tenth = {
" Ten",
" Eleven",
" Twelve",
" Thirteen",
" Fourteen",
" Fifteen",
" Sixteen",
" Seventeen",
" Eighteen",
" Nineteen"
};
String[] tenMutipleDigit = {
"", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", " Seventy", " Eighty", " Ninety"
};
// handle if has three digits.
if (num >= 100) {
sb.append(digits[num / 100]).append(" Hundred");
num %= 100;
}
// handle number like 12, 13
if (num > 9 && num < 20) {
sb.append(tenth[num - 10]);
} else {
if (num >= 20) {
sb.append(tenMutipleDigit[num / 10]);
num %= 10;
}
sb.append(digits[num]);
}
return sb.toString();
}
}

``````

## 56. Merge Intervals

### Description

Given a collection of intervals, merge all overlapping intervals.

Example 1:

``````Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
``````

Example 2:

``````Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
``````

### Solution

``````/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
if(intervals == null || intervals.size()<=1){
return intervals;
}
List<Interval> res  = new ArrayList();
//sort based on their start.
intervals.sort((i1,i2) -> (i1.start - i2.start));
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for(Interval i : intervals){
//if overlapped, update max end.
if(i.start <= end){
end = Math.max(end,i.end);
}else{
//if not overlapped, then add to res and restart start and end.
start = i.start;
end  = i.end;
}
}
return res;
}
}
``````

## 205. Isomorphic Strings

### Description

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

``````Input: s = "egg", t = "add"
Output: true
``````

Example 2:

``````Input: s = "foo", t = "bar"
Output: false
``````

Example 3:

``````Input: s = "paper", t = "title"
Output: true
``````

Note: You may assume both s and t have the same length.

### Solution

``````class Solution1 {
public boolean isIsomorphic(String s, String t) {
int[] map_a = new int;
int[] map_b = new int;
int N = s.length();
if(s.length()!=t.length()){
return false;
}
for(int i = 0; i<N; ++i){
char a = s.charAt(i);
char b = t.charAt(i);
if(map_a[a] != map_b[b]){
return false;
}
map_a[a] = i+1;
map_b[b] = i+1;
}
return true;
}
}
``````

## 179. Largest Number

### Description

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

``````Input: [10,2]
Output: "210"
``````

Example 2:

``````Input: [3,30,34,5,9]
Output: "9534330"
``````

Note: The result may be very large, so you need to return a string instead of an integer.

### Solution

``````class Solution {
public String largestNumber(int[] nums) {
int size = nums.length;
if(size == 0){
return "";
}
if(size == 1){
return String.valueOf(nums);
}
//create own comparator based on their combined value;
Comparator<Integer> com = new Comparator<Integer>(){
public int compare(Integer n1, Integer n2){
String ab = "" + n1 + n2;
String ba = "" + n2 + n1;
return ba.compareTo(ab);
}
};
Integer[] in = new Integer[size];
for(int i = 0;i<size;i++){
in[i] = nums[i];
}
Arrays.sort(in,com);
StringBuilder sb = new StringBuilder();
int i = 0;
//remove 0 before, in case [0,0,0]=>0
while((i<size-1) && in[i]==0)i++;
while (i < size) sb.append(in[i++]);
return sb.toString();
}
}
``````

## 14. Longest Common Prefix

### Description

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

``````Input: ["flower","flow","flight"]
Output: "fl"
``````

Example 2:

``````Input: ["dog","racecar","car"]
Output: ""
``````

Explanation: There is no common prefix among the input strings.

All given inputs are in lowercase letters a-z.

### Solution

``````class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0){
return "";
}
//try every prefix from first element.
for(int i = 0;i<strs.length();i++){
//use element to compare with other elements.
for(int j = 0;j<strs.length;j++){
if(i>=strs[j].length() || strs[j].charAt(i)!=strs.charAt(i)){
return strs.substring(0,i);
}
}
}
return strs;
}
}
``````

# 2019-03-19

## 128. Longest Consecutive Sequence

### Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

``````Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
``````

### Solution

``````class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer,Integer> map = new HashMap();
int max = 0;
for(int n:nums){
if(!map.containsKey(n)){
//get right boundry of left side.
int left = map.getOrDefault(n-1,0);
//left boundry of right side.
int right = map.getOrDefault(n+1,0);
int sum = left+ right + 1;
//means n is in a consequetive subsequence of length sum.
map.put(n,sum);
//store max value;
max = Math.max(max,sum);
//set boundries
map.put(n-left,sum);
map.put(n+right,sum);
}
}
return max;
}
}
``````

## 120. Triangle

### Description

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

``````[
,
[3,4],
[6,5,7],
[4,1,8,3]
]
``````

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

when doing dp with memorization, should think both bottom-up and yop-down, cause maybe one of them will be much easier.

``````class Solution {
//it would be better if try bottom-up instead of top-down.
//which would be easier.
public int minimumTotal(List<List<Integer>> triangle) {
int N = triangle.size();
int M = triangle.get(N-1).size();
int[] dp = new int[M];
for(int i=0;i<M;i++){
dp[i] = triangle.get(N-1).get(i);
}
for(int i = N-2;i>=0;i--){
List<Integer> cur = triangle.get(i);
for(int j=0;j<cur.size();j++){
dp[j] = Math.min(dp[j],dp[j+1])+cur.get(j);
}
}
return dp;

}
}
``````

## 283. Move Zeroes

### Description

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

``````Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
``````

Note:

You must do this in-place without making a copy of the array. Minimize the total number of operations.

### Solution

``````public class Solution {
//track with two pointer.
public void moveZeroes(int[] nums) {
int i = 0, j = 0;
while (j < nums.length) {
if (nums[j] != 0) {
swap(i++, j, nums);
}
j++;
}
}

public void swap(int i, int j, int[] nums) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
``````

## 43. Multiply Strings

### Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

``````Input: num1 = "2", num2 = "3"
Output: "6"
``````

Example 2:

``````Input: num1 = "123", num2 = "456"
Output: "56088"
``````

Note:

The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself. You must not use any built-in BigInteger library or convert the inputs to integer directly.

### Solution

``````class Solution {
public String multiply(String num1, String num2) {
int l1 = num1.length();
int l2 = num2.length();
StringBuilder sb = new StringBuilder();
//if one of it is empty.
if(l1==0||l2==0){
return "";
}
//if one of them is 0.
if(num1.equals("0")||num2.equals("0")){
return "0";
}
int[] multi = new int[l1+l2];
//store multiply at an array, the smaller index is the larger its value are.
for(int i=0;i<l1;i++){
for(int j = 0;j<l2;j++){
multi[i+j+1] += (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
}
}
int carry = 0;
//use carry to store info about last one.
for(int i = multi.length-1;i>=1;i--){
multi[i] += carry;
carry = multi[i] /10;
multi[i] %= 10;
sb.append(multi[i]);
}
if(carry != 0){
sb.append(carry);
}
//need to reverse.
return sb.reverse().toString();
}
}
``````

## 0.One Way

### Description

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away

EXAMPLE

``````pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bake -> false
``````

### Solution

``````public static boolean isOneWay(String str1, String str2) {
//zero edit.
if (str1.equals(str2)) {
return true;
}
//cannot insert/remove more than one char.
if (str1.length() - str2.length() > 1 ||
str2.length() - str1.length() > 1){
return false;
}
int l1 = str1.length();
int l2 = str2.length();
String s1 = null, s2 = null;
//set s1 to be the shorter one.
if (l1 < l2) {
s1 = str1;
s2 = str2;
} else {
s1 = str2;
s2 = str1;
}
int i1 = 0, i2 = 0;
//only allow one dif.
boolean isDif = false;
while (i1 < l1 && i2 < l2) {
if (s1.charAt(i1) != s2.charAt(i2)) {
//if meet second dif, then it's a no-no.
if (isDif) {
return false;
}
isDif=true;
if(l1==l2){
i1++;
}
}else {
i1++;
}
i2++;
}
return true;
}

``````

# 2019-03-20

## 162. Find Peak Element

### Description

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

``````Input: nums = [1,2,3,1]
Output: 2
``````

Explanation: 3 is a peak element and your function should return the index number 2. Example 2:

``````Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
``````

Note:

Your solution should be in logarithmic complexity.

### Solution

``````class Solution {
//can use binary search, and for every mid point, choose the side where goes up.
public int findPeakElement(int[] nums) {
int low = 0;
int high = nums.length-1;
while(low<high){
int mid1 = (low+high)/2;
int mid2 = mid1 + 1;
if(nums[mid1]<nums[mid2]){
low = mid2;
}else{
high=mid1;
}
}
return low;
}
}
``````

## 26. Remove Duplicates from Sorted Array

### Solution

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

``````Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.
Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
``````

It doesn’t matter what values are set beyond the returned length. Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy) int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements.

``````for (int i = 0; i < len; i++) {
print(nums[i]);
}
``````

### Solution

``````class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0){
return 0;
}
int count = 1;
int slow=0,fast=1;
while(fast<nums.length){
if(nums[slow]==nums[fast]){
fast++;
}else{
//move to the next slot.
nums[++slow] = nums[fast++];
count++;
}
}
return count;
}
}
`

//general solution.
class Solution2 {
public int removeDuplicates(int[] nums) {
if(nums.length <=1){
return nums.length;
}
int idx = 1;
for(int i =1;i<nums.length;i++){
if(nums[i]!=nums[idx-1]){
nums[idx++] = nums[i];
}
}
return idx;
}
}
``````

## 80. Remove Duplicates from Sorted Array II

### Description

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

``````Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.
Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.
``````

### Solution

``````class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length <=2){
return nums.length;
}
int idx = 2;
for(int i = 2;i<nums.length;i++){
if(nums[i]!=nums[idx-2]){
nums[idx++] = nums[i];
}
}
return idx;
}
}
``````

# 2019-03-21

## 27. Remove Element

### Description

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

``````Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.
Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
``````

Note that the order of those five elements can be arbitrary.

It doesn’t matter what values are set beyond the returned length.

### Solution

``````class Solution {
public int removeElement(int[] nums, int val) {
int N = nums.length;
int idx = 0;
for(int i = 0;i<N;i++){
if(nums[i]!=val){
nums[idx++] = nums[i];
}
}
return idx;
}
}
``````

## 7. Reverse Integer

### Description

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

``````Input: 123
Output: 321
Example 2:

Input: -123
Output: -321
Example 3:

Input: 120
Output: 21
``````

Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

### Solution

``````public class Solution {
public int reverse(int x) {
int flag = 0;
if (x > 0){
flag = 1;
} else if (x < 0) {
flag = -1;
}
//to avoid overflow
long tmp = (long)x;
tmp *= flag;
while(tmp > 0){
tmp /= 10;
if (answer > Integer.MAX_VALUE || flag * answer < Integer.MIN_VALUE) return 0;
}
}
}
``````

## 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"
``````

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.
``````

### Solution

``````class Solution {
//get a word at a time.
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
StringBuilder res = new StringBuilder();
for(int  i =s.length()-1;i>=0;i--){
char c = s.charAt(i);
if(c!=' '){
sb.append(c);
}
//break point where to store the word.
if(c == ' '){
String temp = sb.reverse().toString();
res.append(temp);
//means there are multiple space, and " "should not be added to res.
if(!temp.equals("")){
res.append(' ');
}
//clear the sb everytime a word has been put to res.
sb = new StringBuilder();
}
}
res.append(sb.reverse().toString());
return res.toString().trim();

}
}
``````

## 73. Set Matrix Zeroes

### Description

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

``````Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
``````

Example 2:

``````Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
``````

A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?

### Solution

``````class Solution {
public void setZeroes(int[][] matrix) {
int rowN = matrix.length;
int colN = matrix.length;
//use firsr row and col to store information, but will lose info itself.
//keep track whether the first rol/col contains 0;
boolean row = false;
boolean col = false;
//whether first row contains 0.
for(int n : matrix){
if(n==0){
row = true;
break;
}
}
//whether first col contains 0.
for(int i = 0;i<colN;i++){
if(matrix[i]==0){
col = true;
break;
}
}
//check each elemnts, if contains 0, put 0 to first col and row;
for(int i = 0;i<rowN;i++){
for(int j = 0;j<colN;j++){
if(matrix[j][i]==0){
matrix[i] = 0;
matrix[j] = 0;
}
}
}
//set entire col to 0.
for(int i = 1;i<rowN;i++){
if(matrix[i]==0){
for(int j = 0;j<colN;j++){
matrix[j][i] = 0;
}
}
}
//set entire row to 0.
for(int j = 1;j<colN;j++){
if(matrix[j]==0){
Arrays.fill(matrix[j],0);
}
}
//see whether first row/col is 0;
if(row){
Arrays.fill(matrix,0);
}
if(col){
for(int j = 0;j<colN;j++){
matrix[j] = 0;
}
}
}
}
``````

# 2019-03-22

## 214. Shortest Palindrome

### Description

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

``````Input: "aacecaaa"
Output: "aaacecaaa"
``````

Example 2:

``````Input: "abcd"
Output: "dcbabcd"
``````

### Solution

``````class Solution {
public String shortestPalindrome(String s) {
if(s.length()<2)return s;
int mid = (s.length()-1)/2;
String res = "";
for(int i = mid;i>=0;i--){
if(s.charAt(i) == s.charAt(i+1)){
res = check(s,i,i+1);
if(res!=null)return res;
}

res = check(s,i,i);
if(res!=null)return res;

}
return res;
}
//check the longest palindorome centered at l and r.
private String check(String s, int l, int r){
int i  =1;
//iterate to find the longest palindrome.
while(l>=0 && r<s.length()){
if(s.charAt(l)!= s.charAt(r)){
break;
}
l--;
r++;
}
//if l is not 0, then it's impossible to do the perform.
if(l>=0){
return null;
}else{
StringBuilder sb = new StringBuilder(s.substring(r));
//reverse.
sb.reverse();
return sb.toString() + s;
}
}
}

``````

## 443. String Compression

### Description

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up: Could you solve it using only O(1) extra space?

Example 1:

``````Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
``````

Example 2:

``````Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.
``````

Example 3:

``````Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.
``````

Note:

All characters have an ASCII value in [35, 126]. 1 <= len(chars) <= 1000.

### Solution

``````class Solution {
public int compress(char[] chars) {
int indexAns = 0,index =0;
while(index<chars.length){
char cur  = chars[index];
int count  =0 ;
while(index < chars.length && chars[index] == cur){
index++;
count++;
}
chars[indexAns++] = cur;
if(count!=1){
for(char c : String.valueOf(count).toCharArray()){
chars[indexAns++] = c;
}
}
}
return indexAns;
}
}

``````

# 2019-03-23

### Description

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

``````board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
``````

### Solution

``````class Solution {

public boolean exist(char[][] board, String word) {
char[] w = word.toCharArray();
boolean[][] visited = new boolean[board.length][board.length];
for (int y=0; y<board.length; y++) {
for (int x=0; x<board[y].length; x++) {
if (exist(board,w,visited, x, y, 0)) return true;

}
}
return false;
}

private boolean exist(char[][] board, char[] w, boolean[][] visited, int x, int y, int index){
//reach the goal, word found.
if(index == w.length){
return true;
}
//out of bound and alrealdy visited
if(x<0|| y<0||y>=board.length||x>=board[y].length||visited[y][x]){
return false;
}
//not the same char.
if(board[y][x]!=w[index]){
return false;
}
visited[y][x] = true;
//search four different directions.
boolean exist = exist(board,w,visited,x-1,y,index+1)||
exist(board,w,visited,x+1,y,index+1)||
exist(board,w,visited,x,y-1,index+1)||
exist(board,w,visited,x,y+1,index+1);
//unvisited current position.
visited[y][x] = false;
return exist;
}
}

``````

## 212. Word Search II

### Description

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

``````Input:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]

Output: ["eat","oath"]
``````

### Solution

``````class Solution {

//Global variable for recursion use.
char[][] board;
int N;
int M;
List<String> res;

public List<String> findWords(char[][] board, String[] words) {
this.board = board;
N = board.length;
M = board.length;
res = new ArrayList<String>();
TrieNode t = buildTree(words);
for (int x = 0; x < N; x++) {
for (int y = 0; y < M; y++) {
find(x, y, t);
}
}
return res;
}

private void find(int x, int y, TrieNode p) {
//out of boarder.
if (x < 0 || y < 0 || x >= N || y >= M) {
return;
}
char c = board[x][y];
//if cur position is already visited or does not exist in the trie.
if (c == '#' || p.next[c - 'a'] == null) {
return;
}
p = p.next[c - 'a'];
//if found a word.
if (p.word != null) {
//prevent duplication.
p.word = null;
}
board[x][y] = '#';
find(x + 1, y, p);
find(x - 1, y, p);
find(x, y + 1, p);
find(x, y - 1, p);
board[x][y] = c;

}

class TrieNode {

TrieNode[] next = new TrieNode;
String word;
}

public TrieNode buildTree(String[] words) {
TrieNode root = new TrieNode();
//iterate over words
for (String w : words) {
//construct from root
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
//to build each char into next.
if (p.next[i] == null) {
p.next[i] = new TrieNode();
}
p = p.next[i];
}
//if it's the end of the path, the word will exist.
p.word = w;
}
return root;
}

}
``````

## 139. Word Break

### Description

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. Example 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();
Set<String> set = new HashSet();
boolean[] dp = new boolean[len + 1];
//must set first to be true of every next one will be false;
dp = true;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j <= len; j++) {
//dp[j] will be true if:
//2. dp[i] is true and substring(i,j) is in Dict.
dp[j] = dp[j] || (dp[i] && set.contains(s.substring(i, j)));
}
}
return dp[len];
}
}
``````

## 140. Word Break II

### Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

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. Example 1:

``````Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
``````

Example 2:

``````Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
``````

Example 3:

``````Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]
``````

### Solution

``````class Solution {

public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet();
//add all words to set for O(1) look up.
//store all the result to prevent duplicated search.
Map<String, List<String>> map = new HashMap();
return dfs(set, s, map);

}

private List<String> dfs(Set<String> set, String s, Map<String, List<String>> map) {
//if already searched, can just return.
//prevent duplication.
if (map.containsKey(s)) {
return map.get(s);
}
List<String> res = new ArrayList();
//s itself is a word. still need to search other possibility.
if (set.contains(s)) {
}
for (int i = 1; i < s.length(); i++) {
//for every possible prefix of s.
String t = s.substring(0, i);
if (set.contains(t)) {
//find all possible break down for the rest of the string.
List<String> tempList = dfs(set, s.substring(i), map);
//construct the result.
//if the rest of the string cannot return any result, then t wil not be added.
for (String temp : tempList) {
res.add(t + " " + temp);
}
}
}
//put into map to prevent duplication.
map.put(s, res);
return res;
}
}
``````

# 2019-03-24

### Description

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note:

Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. Example 1:

``````Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
``````

Example 2:

``````Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
``````

### Solution

``````class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet(wordList);
//reached set will update for each step.
//means the words reached by nth step.
Set<String> reached = new HashSet();
//loop while didn't reach the endWord.
while (!reached.contains(endWord)) {
//for every reached word by last step.
for (String s : reached) {
//for a word, try to change a char in every position.
for (int i = 0; i < s.length(); i++) {
char[] c = s.toCharArray();
//change a char each time.
for (char t = 'a'; t <= 'z'; t++) {
c[i] = t;
String newStr = new String(c);
//if the new word is an unreached one.
if (words.contains(newStr)) {
//remove to prevent loop or duplication.
words.remove(newStr);
}
}
}
}
//if cur ladder cannot reach anywhere, means cannot reach the endWord.
return 0;
}
//update reached.
}
}
}
``````

## 300. Longest Increasing Subsequence

### Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

``````Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
``````

Note:

There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity?

### Solution

`tails` is an array storing the smallest tail of all increasing subsequences with length `i+1` in `tails[i]`. For example, say we have `nums = [4,5,6,3]`, then all the available increasing subsequences are:

``````len = 1   :      , , ,    => tails = 3
len = 2   :      [4, 5], [5, 6]       => tails = 5
len = 3   :      [4, 5, 6]            => tails = 6
``````

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

``````(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]
``````

Doing so will maintain the tails invariant. The the final answer is just the size.

O(nlogn) Binary Search solution

``````    public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
//use binary search to find out which tails[i] should update.
for(int n:nums){
int i = 0;
int j = size;
while(i<j){
int mid = (i+j)/2;
if(tails[mid]<n){
i = mid+1;
}else{j = mid;}
}
tails[j] = n;
//if j is larger than anyone else, just append to the end and size++.
if(j==size)size++;
}
return size;
}
``````

O(n^2) DP solution

``````public int lengthofLIS2(int[] nums) {
if (nums.length == 0) {
return 0;
}

int n = nums.length;
int[] dp = new int[n];
//itself is a solution woth length 1.
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
//main
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
int maxRes = 0;
for (int i = 0; i < n; i++) {
maxRes = Math.max(maxRes, dp[i]);
}
return maxRes;
}
``````

## 673. Number of Longest Increasing Subsequence

### Description

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

``````Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
``````

Example 2:

``````Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
``````

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

### Solution

``````class Solution {
public int findNumberOfLIS(int[] nums) {
int N = nums.length;
int[] len = new int[N];
int[] cnt = new int[N];
int max_len = Integer.MIN_VALUE;
int count = 0;
//search from begining
for(int  i = 0;i<N;i++){
len[i] = 1;
cnt[i] = 1;
for(int j = 0;j<i;j++){
//if it's an increasing subsequence.
if(nums[i]>nums[j]){
//if they are the same length, add up.
if(len[i]==len[j]+1){
cnt[i] += cnt[j];
//if length of i is smaller, update it.
}else if(len[i]<len[j]+1){
len[i] = len[j]+1;
cnt[i] = cnt[j];
}
}
}
if(len[i]==max_len){
count += cnt[i];
}else if(len[i]>max_len){
count = cnt[i];
max_len = len[i];
}
}
return count;
}
}
``````

## 75. Sort Colors

### Description

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

``````Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
``````

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s. Could you come up with a one-pass algorithm using only constant space?

### Solution

It’s more like maintaining two pivot to indicate the boundry of 0 and 2 so before pivot_0 is all 0 and after pivot_2 is all 2.

and while iterate through the array, we just nee dto decide which side we tose it to. if 1 than do nothing.

``````public void sortColors(int[] nums) {
int N = nums.length;
if(N==0){
return;
}
int zero = 0;
int sec = N-1;
int i = 0;
while(i<=sec){
while(nums[i]==2 && i<sec){
swap(nums,i,sec--);
}
while(nums[i]==0 && i>zero){
swap(nums,i,zero++);
}
i++;
}
return;
}

private void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
``````

## 380. Insert Delete GetRandom O(1)

### Description

Design a data structure that supports all following operations in average O(1) time.

`insert(val): Inserts an item val to the set if not already present.` `remove(val): Removes an item val from the set if present.` `getRandom: Returns a random element from current set of elements.` `Each element must have the same probability of being returned.` Example:

``````// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains .
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
``````

### Solution

``````class RandomizedSet {

List<Integer> list;
Map<Integer,Integer> map;
java.util.Random rand = new java.util.Random();

/** Initialize your data structure here. */
public RandomizedSet() {
list = new ArrayList<Integer>();
map = new HashMap();
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)) return false;
map.put(val,list.size());
return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)) return false;
int last = list.get(list.size()-1);
int loc = map.get(val);
//replace the removed one and last one, update map
list.set(loc,last);
map.put(last,loc);
//and then can remove it.
list.remove(list.size()-1);
map.remove(val);
return true;
}

/** Get a random element from the set. */
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
``````

# 2019-03-25

## 198. House Robber

### Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. Example 1:

``````Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
``````

Example 2:

``````Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
``````

### Solution

``````class Solution {
public int rob(int[] nums) {
int N =nums.length;
if(N==0){
return 0;
}
if(N == 1){
return nums;
}
int[] dp = new int[N+1];
dp = 0;
dp = nums;
//take the best out of two choice.
for(int i = 2;i<N+1;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
}
return dp[N];
}
}
``````
``````class Solution {
public int rob(int[] nums) {
int N =nums.length;
if(N==0){
return 0;
}
if(N == 1){
return nums;
}
int include = 0,exclude = 0;
int one = nums;
int two = 0;
//actually you just need to remember the last two step.
//to save more space.
for(int i = 1;i<N;i++){
int temp = one;
one = Math.max(one,nums[i]+two);
two = temp;
}
return Math.max(one,two);
}
}
``````

## 213. House Robber II

### Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. Example 1:

``````Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
``````

Example 2:

``````Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
``````

### Solution

``````class Solution {
public int rob(int[] nums) {
int N = nums.length;
if (N == 1) return nums;
//Since every house is either robbed or not robbed and at least half of the houses are not robbed
//the solution is simply the larger of two cases with consecutive houses
//i.e. house i not robbed, break the circle, solve it, or house i + 1 not robbed
//Hence, the following solution. chose i = n and i + 1 = 0 for simpler coding
return Math.max(
rob(nums,0,N-2),
rob(nums,1,N-1)
);
}

private int rob(int[] num, int lo, int hi) {
int include = 0, exclude = 0;
for (int j = lo; j <= hi; j++) {
int i = include;
include = exclude + num[j];
exclude = Math.max(exclude, i);
}
return Math.max(include, exclude);
}
}
``````

## 337. House Robber III

### Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police. Example 1:

``````Input: [3,2,3,null,3,null,1]

3
/ \
2 3
\ \
3 1

Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
``````

Example 2:

``````Input: [3,4,5,1,3,null,1]

3
/ \
4 5
/ \ \
1 3 1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
``````

### Solution

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
if(root == null){
return 0;
}
return Math.max(include(root),exclude(root));
}

public int include(TreeNode root){
if(root == null){
return 0;
}
return exclude(root.left) + exclude(root.right) + root.val;
}

public int exclude(TreeNode root){
if(root == null){
return 0;
}
return rob(root.left)+rob(root.right);
}
}
``````

## 1. Two Sum

### Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

``````Given nums = [2, 7, 11, 15], target = 9,

Because nums + nums = 2 + 7 = 9,
return [0, 1].
``````

### Solution

``````class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i]) && map.get(target-nums[i])!=i){
int[] res = {i,map.get(target-nums[i])};
return res;
}
}
return new int[] {};
}
}
``````

# 2019-03-26

## 19. Remove Nth Node From End of List

### Description

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

``````Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
``````

### Solution

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//will have to use dummy head
//in case of head being deleted.
ListNode dummy = new ListNode(0);
ListNode slow = dummy;
ListNode fast = dummy;
for(int i = 0;i<n;i++){
fast = fast.next;
}
while(fast.next!=null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
``````

## 22. Generate Parentheses

### Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

``````[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
``````

### Solution

``````class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList();
if(n==0){
return res;
}

helper("",n,n,res);
return res;
}

//recursively build all possible combinations.
//open -> numbers '(' left and can be used.
//close -> numbers ')' left and can be used.
private void helper(String candidate, int open, int close,List<String> res){
//left cannot left more than right, it means current candidate have more right than left.
//it's invalid one, just return.
if(open>close){
return;
}
//have unuesd left one.
if(open>0){
helper(candidate+"(",open-1,close,res);
}
if(close>0){
helper(candidate+")",open,close-1,res);
}
//reach the end and can guarante it's valid.
if(open ==0 && close == 0 ){
}
}
}
``````

## 24. Swap Nodes in Pairs

### Description

You may not modify the values in the list’s nodes, only nodes itself may be changed.

``````Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.
``````

### Solution

``````class Solution {
//recursively call swap.
}
//append the rest result to its end.
return n;
}
}
``````

# 2019-03-27

## 30. Substring with Concatenation of All Words

### Description

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

``````Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
``````

Example 2:

``````Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
``````

### Solution

``````class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int num = words.length;
int len = words.length();
List<Integer> res = new ArrayList();
if(num==0){
return res;
}
//count word in words.
final Map<String,Integer> word_map = new HashMap();
for(final String word:words){
word_map.put(word,word_map.getOrDefault(word,0)+1);
}
//try every possible position. s.length()-num*len is the last possible one.
for(int i =0;i<s.length()-num*len+1;i++){
//set seen map to empty.
final Map<String, Integer> seen = new HashMap<>();
int j = 0;
while(j<num){
//find the next word.
final String w = s.substring(i + j * len, i + (j + 1) * len);
if(word_map.containsKey(w)){
seen.put(w, seen.getOrDefault(w, 0) + 1);
//if seen more words than expected, it's false.
if (seen.get(w) > word_map.getOrDefault(w, 0)) {
break;
}
}else{
break;
}
j++;
}
//reach the end and all words match.
if(j==num){
}
}
return res;
}
}
``````

## 32. Longest Valid Parentheses

### Description

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

``````Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
``````

Example 2:

``````Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
``````

### Solution

``````class Solution {
public int longestValidParentheses(String s) {
int N = s.length();
if(N<2){
return 0;
}
int[] dp = new int[N];
int max = 0;
for(int i =1;i<N;i++){
//only need to consider ')'
if(s.charAt(i)==')'){
//if last one is left, then just need to add 2 to dp[i-2].
if(s.charAt(i-1)=='('){
dp[i] = (i-2>=0)?dp[i-2]+2:2;
}else{
//if i-1 is ')',than we need to find the far leftmost position and search the previous.
//get i-dp[i-1]-1, if left then it's pair.
if(i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1)=='('){
dp[i] = dp[i-1] + 2 + (i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0);
}
}
}
//else it's '(', and it's always 0.
max = Math.max(max,dp[i]);
}
return max;
}
}
``````

# 2019-03-28

## 42. Trapping Rain Water

### Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

``````Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
``````

### Solution

``````class Solution {
public int trap(int[] height) {
int a = 0;
int b = height.length-1;
int leftMax = 0;
int rightMax= 0;
int sum = 0;
//iterate through the array.
while(a<=b){
leftMax = Math.max(leftMax,height[a]);
rightMax = Math.max(rightMax,height[b]);
if(leftMax<rightMax){
sum += (leftMax-height[a]);
a++;
}else{
sum += (rightMax-height[b]);
b--;
}
}
return sum;
}
}
``````

## general approach to backtracking questions

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){
for(int i = start; i < nums.length; 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){
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
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){
} else{
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // element already exists, skip
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){
} 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;
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++){
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
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())
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
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;
}
``````

## 46. Permutations

### 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]
]
``````

### Solution

``````class Solution {

public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
helper(list, nums,new ArrayList<>());
return list;
}

public void helper(List<List<Integer>> res,int[] nums, List<Integer> temp){
if(temp.size()==nums.length){
return;
}
for(int i = 0;i<nums.length;i++){
//prevent duplication
if(temp.contains(nums[i])) continue;
helper(res,nums,temp);
temp.remove(temp.size()-1);
}
}
}
``````

## 47. Permutations II

### Description

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

``````Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
``````

### Solution

``````class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
helper(list, nums,new ArrayList<>(),used);
return list;
}

public void helper(List<List<Integer>> res,int[] nums, List<Integer> temp,boolean[] used){
if(temp.size()==nums.length){
return;
}
for(int i = 0;i<nums.length;i++){
//two situation should be prevented:
//2. nums[i]=nums[i-1] AND !used[i-1]
//!used[i-1] means i-1 is not in temp, so should only use once and that would be the first one where i!=i-1.
if(used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i - 1]) ) continue;
used[i] = true;
helper(res,nums,temp,used);
temp.remove(temp.size()-1);
used[i] = false;
}
}
}
``````

## 53. Maximum Subarray

### Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

``````Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
``````

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

### Solution

``````class Solution {
public int maxSubArray(int[] nums) {
int preMax = nums;
int max = nums;
for(int i = 1;i<nums.length;i++){
//if premax is positive than add to it, ortherwise it would be better to leave it out and be 0.
preMax = nums[i] + (preMax>0?preMax:0);
max = Math.max(max,preMax);
}
return max;
}
}
``````

# 2019-03-29

## 55. Jump Game

### Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

``````Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
``````

Example 2:

``````Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index
``````

### Solution

``````class Solution {
public boolean canJump(int[] nums) {
int max = 0;
for(int i = 0;i<nums.length;i++){
if(i>max)return false;
//try to find the deepest place one can reach;
max = Math.max(nums[i]+i,max);
}
return true;
}
}
``````

## 58. Length of Last Word

### Description

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

``````Input: "Hello World"
Output: 5
``````

### Solution

``````class Solution {
public int lengthOfLastWord(String s) {
int N = s.length();
if(N==0) return 0;
int tail = N-1;
int len = 0;
while(tail>=0&& s.charAt(tail)==' ') tail--;
while(tail>=0 && s.charAt(tail)!=' '){
len++;
tail--;
}
return len;
}
}
``````

## 61. Rotate List

### Description

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

``````Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
``````

Example 2:

``````Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
``````

### Solution

``````/**
* Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int
* x) { val = x; } }
*/
class Solution {

public ListNode rotateRight(ListNode head, int n) {
}
ListNode dummy = new ListNode(0);
ListNode fast = dummy, slow = dummy;

int i;
for (i = 0; fast.next != null; i++)//Get the total length
{
fast = fast.next;
}

for (int j = i - n % i; j > 0; j--) //Get the i-n%i th node
{
slow = slow.next;
}

fast.next = dummy.next; //Do the rotation
dummy.next = slow.next;
slow.next = null;

return dummy.next;
}
}
``````

# 2019-03-31

## 62. Unique Paths

### Description

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

### Solution

``````class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[n][m];
for(int i =0;i<m;i++){
dp[i] = 1;
}
for(int i =0;i<n; i++){
dp[i] = 1;
}
//add up two block -> up and left
for(int i = 1;i<n;i++){
for(int j = 1;j<m;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
}
}
``````

## 63. Unique Paths II

### Description

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner:

1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

### Solution

``````class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid.length;
int[][] dp = new int[n][m];
for(int i =0;i<m;i++){
//block on its way, then rest of it are all unreachable.
if(obstacleGrid[i]==1){
break;
}
dp[i] = 1;
}
for(int i =0;i<n; i++){
//same, unreachable for the rest.
if(obstacleGrid[i]==1){
break;
}
dp[i] = 1;
}
//add up two block -> up and left
for(int i = 1;i<n;i++){
for(int j = 1;j<m;j++){
if(obstacleGrid[i][j]==1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[n-1][m-1];
}
}
``````

## 64. Minimum Path Sum

### Description

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

``````Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
``````

### Solution

``````class Solution {
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid.length;
int[][] dp = new int[n][m];
dp = grid;
for(int i =1;i<m;i++){
dp[i] = dp[i-1] + grid[i];
}
for(int i =1;i<n; i++){
dp[i] = dp[i-1] + grid[i];
}
for(int i = 1;i<n;i++){
for(int j = 1;j<m;j++){
//find the minimum way from upper or left grid.
dp[i][j] = Math.min(dp[i-1][j] ,dp[i][j-1]) + grid[i][j];

}
}
return dp[n-1][m-1];
}
}
``````

## 69. Sqrt(x)

### Description

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

``````Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
``````

### Solution

``````class Solution {
public int mySqrt(int x) {
if(x==0){
return 0;
}
int left = 1;
int right = x;
while(true){
int mid = left + (right-left)/2;
if(mid > x/mid){
right = mid - 1;
}else{
if((mid+1) > x/(mid+1)){
return mid;
}
left = mid + 1;
}
}

}
}
``````

## 70. Climbing Stairs

### Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

``````Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
``````

Example 2:

``````Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
``````

### Solution

``````class Solution {
public int climbStairs(int n) {
if(n==1){
return 1;
}
if(n==2){
return 2;
}
int[] dp = new int[n];
dp = 1;
dp = 2;

for(int i=2;i<n;i++){
//two way to get to pisition i:
//1. 1 step from i-1
//2. two step from i-2
//sum up.
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
}
``````