Leetcode Medium Questions Review
Published:
Algorithms – Leetcode Medium Questions Review
Leetcode Medium Questions Review
2. Add Two Numbers
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head1 = l1;
ListNode head2 = l2;
int flag = 0;
ListNode res = new ListNode();
ListNode head = res;
while (head1!=null || head2!=null || flag>0) {
head.val=0;
if(head1!=null){
head.val+=head1.val;
}
if(head2!=null){
head.val+=head2.val;
}
if(flag>0){
head.val+=flag;
flag=0;
}
if(head.val>=10){
head.val-=10;
flag+=1;
}
if(head1!=null){
head1=head1.next;
}
if(head2!=null){
head2=head2.next;
}
if(head1!=null || head2!=null || flag>0){
head.next=new ListNode();
head=head.next;
}
}
return res;
}
}
3. Longest Substring Without Repeating Characters
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) {
return 0;
}
int i=0;
int j=0;
Set<Character> charSets = new HashSet<>();
int maxLen = 0;
while(i<=j&&j<s.length()){
if(charSets.contains(s.charAt(j))){
charSets.remove(s.charAt(i));
i++;
}
else{
charSets.add(s.charAt(j));
j++;
}
if(j-i>maxLen){
maxLen=j-i;
}
}
return maxLen;
}
}
5. Longest Palindromic Substring
class Solution {
public String longestPalindrome(String s) {
if(s==null||s.length()==0) {
return "";
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxI = 0;
int maxJ = 0;
for(int i=0;i<n;i++){
dp[i][i]=true;
if(i+1<n){
dp[i][i+1]=s.charAt(i)==s.charAt(i+1);
if(dp[i][i+1]&&1>maxJ-maxI){
maxJ=i+1;
maxI=i;
}
}
}
for(int l=3;l<=n;l++){
for(int i=0;i<=n-l;i++){
int j=i+l-1;
if(s.charAt(i)!=s.charAt(j)){
dp[i][j]=false;
}
else{
dp[i][j]=dp[i+1][j-1];
}
if(dp[i][j]&&j-i>maxJ-maxI){
maxJ=j;
maxI=i;
}
}
}
return s.substring(maxI,maxJ+1);
}
}
6. ZigZag Conversion
class Solution {
public String convert(String s, int numRows) {
if(s==null||s.length()==0||numRows<=0){
return null;
}
int n = s.length();
if(n<=numRows||numRows==1){
return s;
}
List<StringBuffer> list = new ArrayList<>();
int index = 0;
int temp = 1;//+1 or -1
for(int i=0;i<numRows;i++){
list.add(new StringBuffer());
}
for(int i=0;i<n;i++){
list.get(index).append(s.charAt(i));
index+=temp;
if(index==numRows||index<0){
index = index-temp-temp;
temp = -temp;
}
}
return list.stream().reduce(StringBuffer::append).get().toString();
}
}
7. Reverse Integer
class Solution {
public int reverse(int x) {
if(x==0){
return x;
}
long flag = x>0?1L:-1L;
x=Math.abs(x);
long res = 0;
while(x>0){
int temp = x%10;
x=x/10;
res = res*10L+temp;
}
res=res*flag;
if(res<(long)Integer.MIN_VALUE||res>(long)Integer.MAX_VALUE){
return 0;
}
return (int)res;
}
}
8. String to Integer (atoi)
class Solution {
public int myAtoi(String s) {
if(s==null||s.length()==0){
return 0;
}
long res = 0L;
long flag = 1L;
boolean hasNumber = false; //if hasNumber=true, no +/- permitted
int j = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c==' '&&res==0L&&!hasNumber){
continue;
} else if(c=='+'&&!hasNumber){
flag=1L;
hasNumber=true;
} else if(c=='-'&&!hasNumber){
flag=-1L;
hasNumber=true;
} else if(Character.isDigit(c)){
hasNumber = true;
int temp = c-'0';
res = res*10L+temp;
if(res!=0L) j++;
if(j>10){
break;
}
} else{
break;
}
}
res = flag*res;
if(res<(long)Integer.MIN_VALUE||res>(long)Integer.MAX_VALUE){
if(res<0) res = (long)Integer.MIN_VALUE;
else res = (long)Integer.MAX_VALUE;
}
return (int)res;
}
}
11. Container With Most Water
class Solution {
public int maxArea(int[] height) {
if(height==null||height.length==0){
return 0;
}
int i =0;
int j = height.length-1;
int maxArea = 0;
while(i<j){
int tempArea = (j-i)*Math.min(height[i],height[j]);
if(tempArea>maxArea){
maxArea=tempArea;
}
if(height[i]<height[j]){
i++;
}
else{
j--;
}
}
return maxArea;
}
}
12. Integer to Roman
class Solution {
public String intToRoman(int num) {
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuffer sb = new StringBuffer();
for(int i=0;i<values.length;i++){
int cur = values[i];
String str = symbols[i];
while(num>=cur){
sb.append(str);
num-=cur;
}
if(num==0){
break;
}
}
return sb.toString();
}
}
15. 3Sum
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null||nums.length==0){
return res;
}
Arrays.sort(nums);
int n = nums.length;
//i,l,r nums[i]+nums[l]+nums[r]
//i<l<r
for(int i=0;i<n;i++){
if(nums[i]>0){
break;
}
if(i>0&&nums[i]==nums[i-1]){
continue;
}
int l=i+1;
int r=n-1;
while(l<r){
if(nums[i]+nums[l]+nums[r]==0){
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[l]);
temp.add(nums[r]);
res.add(temp);
// move l,r to the last position of same value
while(l<r&&nums[l+1]==nums[l]){
l++;
}
while(l<r&&nums[r-1]==nums[r]){
r--;
}
l++;
r--;
} else if(nums[i]+nums[l]+nums[r]>0){
r--;
} else {
l++;
}
}
}
return res;
}
}
16. 3Sum Closest
class Solution {
public int threeSumClosest(int[] nums, int target) {
if(nums==null||nums.length==0){
return 0;
}
Arrays.sort(nums);
//i<j<k,a[i]+a[j]+a[k]==target
int n = nums.length;
int res = 0;
int abs = Integer.MAX_VALUE;
for(int i=0;i<n;i++){
int j=i+1;
int k=n-1;
while(j<k){
int sum = nums[i]+nums[j]+nums[k];
if(sum==target){
return sum;
}
if(Math.abs(sum-target)<abs){
abs=Math.abs(sum-target);
res=sum;
}
if(sum<target){
j++;
} else{
k--;
}
}
}
return res;
}
}
17. Letter Combinations of a Phone Number
class Solution {
public List<String> mapToString(char c){
List<String> res = new ArrayList<>();
switch(c){
case '2':
res.add("a");
res.add("b");
res.add("c");
break;
case '3':
res.add("d");
res.add("e");
res.add("f");
break;
case '4':
res.add("g");
res.add("h");
res.add("i");
break;
case '5':
res.add("j");
res.add("k");
res.add("l");
break;
case '6':
res.add("m");
res.add("n");
res.add("o");
break;
case '7':
res.add("p");
res.add("q");
res.add("r");
res.add("s");
break;
case '8':
res.add("t");
res.add("u");
res.add("v");
break;
case '9':
res.add("w");
res.add("x");
res.add("y");
res.add("z");
break;
}
return res;
}
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits==null||digits.length()==0){
return res;
}
traceback(res,0,digits,new StringBuffer());
return res;
}
public void traceback(List<String> res, int index, String digits, StringBuffer tmp){
if(index==digits.length()){
res.add(tmp.toString());
}
else{
char c = digits.charAt(index);
List<String> tmpList = mapToString(c);
int n = tmpList.size();
for(int i=0;i<n;i++){
tmp.append(tmpList.get(i));
traceback(res,index+1,digits,tmp);
tmp.deleteCharAt(index);
}
}
}
}
18. 4Sum
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null||nums.length<4){
return res;
}
int n = nums.length;
Arrays.sort(nums);
//a[i]+a[j]+a[l]+a[r]=target,i<j<l<r
for(int i=0;i<n-3;i++){
if(i>0&&nums[i]==nums[i-1]){
continue;
}
if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){
break;
}
if((long)nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target){
continue;
}
for(int j=i+1;j<n-2;j++){
if(j>i+1&&nums[j]==nums[j-1]){
continue;
}
if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target){
break;
}
if((long)nums[i]+nums[j]+nums[n-2]+nums[n-1]<target){
continue;
}
int l=j+1;
int r=n-1;
while(l<r){
long sum=(long)nums[i]+nums[j]+nums[l]+nums[r];
if(sum==target){
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[l]);
temp.add(nums[r]);
res.add(temp);
while(l<r&&nums[l+1]==nums[l]){
l++;
}
while(l<r&&nums[r-1]==nums[r]){
r--;
}
l++;
r--;
} else if(sum<target){
l++;
} else{
r--;
}
}
}
}
return res;
}
}
19. Remove Nth Node From End of List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null||n<=0){
return null;
}
ListNode p1 = head;
ListNode p2 = head;
for(int i=0;i<n;i++){
p1=p1.next;
if(i<n-1&&p1==null){
return null;
}
}
if(p1==null){
// the list has N nodes
// delete the head
return head.next;
}
while(p1.next!=null){
p1=p1.next;
p2=p2.next;
}
p2.next=p2.next.next;
return head;
}
}
22. Generate Parentheses
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if(n<1){
return res;
}
traceback(res,new StringBuffer(),0,0,n);
return res;
}
public void traceback(List<String> res, StringBuffer cur, int left, int right, int max) {
// corner case
if(cur.length()==max*2){
res.add(cur.toString());
return;
}
if(left<max){
cur.append("(");
traceback(res,cur,left+1,right,max);
cur.deleteCharAt(cur.length()-1);
}
if(right<left){
cur.append(")");
traceback(res,cur,left,right+1,max);
cur.deleteCharAt(cur.length()-1);
}
}
}
24. Swap Nodes in Pairs
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode one = head;
ListNode two = one.next;
ListNode three = two.next;
two.next = one;
one.next = swapPairs(three);
return two;
}
}
29. Divide Two Integers
class Solution {
public int divide(int dividend, int divisor) {
// Overflow cases are handled separately
if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
// If the divisor is 1, return the dividend directly
if (divisor == 1) return dividend;
// Determine if the result is positive or negative
boolean flag = true;
if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) flag = false;
// In order to prevent overflow, all numbers are converted to negative numbers for processing
dividend = dividend > 0 ? -dividend : dividend;
divisor = divisor > 0 ? -divisor : divisor;
// Because the signs are turned into negative, the signs here are reversed
int res = 0;
while (dividend <= divisor) {//>
int temp = divisor;
int cnt = 1;
while (temp >= dividend - temp) {//<
// increase multiply
temp += temp;
cnt += cnt;
}
// get new dividend
dividend -= temp;
res += cnt;
}
return flag == true ? res : -res;
}
}
31. Next Permutation
class Solution {
public void nextPermutation(int[] nums) {
if(nums==null||nums.length==0){
return;
}
int n = nums.length;
int i = n-2;
//find the decreasing element
while(i>=0&&nums[i+1]<=nums[i]){
i--;
}
if(i>=0){
int j = n-1;
//find the last j, such that nums[j]>nums[i]
while(j>=0&&nums[j]<=nums[i]){
j--;
}
//swap nums[j],nums[i]
swap(nums,i,j);
}
//reverse from i+1
int l=i+1;
int r=n-1;
while(l<r){
swap(nums,l,r);
l++;
r--;
}
}
public void swap(int[] a,int i,int j){
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
33. Search in Rotated Sorted Array
class Solution {
public int search(int[] nums, int target) {
if(nums==null||nums.length==0){
return -1;
}
int n = nums.length;
int left = 0;
int right = n-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target){
return mid;
}
// mid on left half (left .. mid in order)
if(nums[mid]>nums[right]){
if(target<nums[mid]&&target>=nums[left]){
//target on left .. mid
right = mid-1;
}
else{
//target on mid .. right
left = mid+1;
}
}
//mid on right half (mid .. right in order)
else{
if(target>nums[mid]&&target<=nums[right]){
//target on mid .. right
left = mid+1;
}
else{
//target on left .. mid
right = mid-1;
}
}
}
return -1;
}
}
34. Find First and Last Position of Element in Sorted Array
class Solution {
public int[] searchRange(int[] nums, int target) {
int index = binarySearch(nums,target);
if(index<0){
return new int[]{-1,-1};
}
int leftIndex = index;
int rightIndex = index;
while(leftIndex>0&&nums[leftIndex-1]==target){
leftIndex--;
}
while(rightIndex<nums.length-1&&nums[rightIndex+1]==target){
rightIndex++;
}
return new int[]{leftIndex,rightIndex};
}
public int binarySearch(int[] nums, int target) {
if(nums==null||nums.length==0){
return -1;
}
int l = 0;
int r = nums.length -1;
while(l<=r){
int mid = (l+r)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
l=mid+1;
}
else{
r=mid-1;
}
}
return -1;
}
}
36. Valid Sudoku
class Solution {
public boolean isValidSudoku(char[][] board) {
if(board==null||board.length==0){
return false;
}
int[][] rows = new int[9][9];
int[][] cols = new int[9][9];
int[][][] subBoxs = new int[3][3][9];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char c=board[i][j];
if(c!='.'){
int index=c-'0'-1;
rows[i][index]++;
cols[j][index]++;
subBoxs[i/3][j/3][index]++;
if(rows[i][index]>1||cols[j][index]>1||subBoxs[i/3][j/3][index]>1){
return false;
}
}
}
}
return true;
}
}
38. Count and Say
class Solution {
public String countAndSay(int n) {
String str = "1";
for(int i=2;i<=n;i++){
StringBuffer sb = new StringBuffer();
int start =0;
int pos=0;
while(pos<str.length()){
while(pos<str.length()&&str.charAt(start)==str.charAt(pos)){
pos++;
}
sb.append(pos-start).append(str.charAt(start));
start=pos;
}
str = sb.toString();
}
return str;
}
}
39. Combination Sum
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if(candidates==null||candidates.length==0){
return res;
}
Arrays.sort(candidates);
dfs(candidates,target,0,new ArrayList<>(),res);
return res;
}
public void dfs(int[] candidates, int target, int begin, List<Integer> path, List<List<Integer>> res) {
if(target<0){
return;
}
if(target==0){
res.add(new ArrayList(path));
return;
}
for(int i=begin;i<candidates.length;i++){
if(candidates[i]>target){
break;
}
path.add(candidates[i]);
dfs(candidates,target-candidates[i],i,path,res);
path.remove(path.size()-1);
}
}
}
40. Combination Sum II
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if(candidates==null||candidates.length==0){
return res;
}
Arrays.sort(candidates);
dfs(candidates, target, 0, new ArrayList<>(), res);
return res;
}
public void dfs(int[] candidates, int target, int begin, List<Integer> path, List<List<Integer>> res){
if(target<0){
return;
}
if(target==0){
res.add(new ArrayList(path));
return;
}
for(int i=begin;i<candidates.length;i++){
if(candidates[i]>target){
return;
}
if(i>begin&&candidates[i]==candidates[i-1]){
continue;
}
path.add(candidates[i]);
dfs(candidates,target-candidates[i],i+1,path,res);
path.remove(path.size()-1);
}
}
}
43. Multiply Strings
class Solution {
public String multiply(String num1, String num2) {
if(num1==null||num1.length()==0){
return "0";
}
if(num2==null||num2.length()==0){
return "0";
}
if(num1.equals("0")||num2.equals("0")){
return "0";
}
int m = num1.length();
int n = num2.length();
int[] res = new int[m+n];
for(int i=m-1;i>=0;i--){
int value1 = num1.charAt(i)-'0';
for(int j=n-1;j>=0;j--){
int value2 = num2.charAt(j)-'0';
int mult = res[i+j+1] + value1*value2;
res[i+j+1]=mult%10;
res[i+j]+=mult/10;
}
}
StringBuffer sb = new StringBuffer();
for(int i=0;i<res.length;i++){
if(res[i]==0&&sb.isEmpty()){
continue;
}
sb.append(res[i]);
}
return sb.toString();
}
}
45. Jump Game II
class Solution {
public int jump(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int n = nums.length;
int maxPos = 0;
int end = 0;
int num = 0;
for(int i=0;i<n-1;i++){
maxPos = Math.max(maxPos,nums[i]+i);
if(i==end){
end = maxPos;
num++;
}
}
return num;
}
}
46. Permutations
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null||nums.length==0){
return res;
}
dfs(nums,new boolean[nums.length],new ArrayList<>(),res);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res){
if(path.size()==nums.length){
res.add(new ArrayList(path));
return;
}
for(int i=0;i<nums.length;i++){
if(!used[i]){
path.add(nums[i]);
used[i] = true;
dfs(nums,used,path,res);
path.remove(path.size()-1);
used[i] = false;
}
}
}
}
47. Permutations II
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null||nums.length==0){
return res;
}
int n=nums.length;
boolean[] used = new boolean[n];
dfs(nums,used,new ArrayList<>(),res);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res){
if(path.size()==nums.length&&!res.contains(path)){
res.add(new ArrayList(path));
return;
}
for(int i=0;i<nums.length;i++){
if(!used[i]){
used[i]=true;
path.add(nums[i]);
dfs(nums,used,path,res);
path.remove(path.size()-1);
used[i]=false;
}
}
}
}
48. Rotate Image
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// horizontal flip
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// main diagonal flip
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
49. Group Anagrams
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs)
.collect(Collectors.groupingBy(str -> {
// Returns the sorted result of str.
// Grouping by is done according to the sorted results, and the operator is similar to group by in sql.
char[] array = str.toCharArray();
Arrays.sort(array);
return new String(array);
})).values());
}
}
50. Pow(x, n)
class Solution {
public double myPow(double x, int n) {
if(n==0){
return 1;
} else if(n<0){
return 1.0/myPosPositive(x,-n);
}
return myPosPositive(x,n);
}
public double myPosPositive(double x, int n){
if(n==0){
return 1;
}
if(n==1){
return x;
}
double temp = myPosPositive(x,n/2);
if(n%2==0){
return temp*temp;
} else{
return x*temp*temp;
}
}
}
54. Spiral Matrix
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<Integer>();
if(matrix == null || matrix.length == 0)
return list;
int m = matrix.length;
int n = matrix[0].length;
int top=0;
int bottom=m-1;
int left=0;
int right=n-1;
while(top<=bottom&&left<=right){
for(int col=left;col<=right;col++){
list.add(matrix[top][col]);
}
for(int row=top+1;row<=bottom;row++){
list.add(matrix[row][right]);
}
if(top<bottom&&left<right){
for(int col=right-1;col>left;col--){
list.add(matrix[bottom][col]);
}
for(int row=bottom;row>top;row--){
list.add(matrix[row][left]);
}
}
top++;
left++;
right--;
bottom--;
}
return list;
}
}
55. Jump Game
class Solution {
public boolean canJump(int[] nums) {
if(nums==null||nums.length==0){
return true;
}
int n = nums.length;
int[] dp = new int[n];//dp[i] denotes that farest location of from before nums[i] (included)
for(int i=0;i<n;i++){
dp[i]=i+nums[i];
for(int j=0;j<i;j++){
if(dp[j]>=i){
dp[i]=Math.max(dp[i],dp[j]);
}
}
if(dp[i]>=n-1){
return true;
}
if(dp[i]<=i){
return false;
}
}
return false;
}
}
56. Merge Intervals
class Solution {
public int[][] merge(int[][] intervals) {
//corner case
if(intervals==null||intervals.length==0){
return intervals;
}
for(int i=0;i<intervals.length;i++){
if(intervals[i].length!=2){
return intervals;
}
}
List<int[]> intervalList = Arrays.asList(intervals);
List<int[]> tempList = new ArrayList<>(intervalList);
// sort intervals by the first element
tempList.sort((o1,o2)->o1[0]-o2[0]);
int i=0;
List<int[]> curInterval = new ArrayList<>();
//iterate over intervals i->left pointer, j->right pointer
while(i<tempList.size()){
int t=tempList.get(i)[1];// t denotes the right border of an interval
int j=i+1;
while(j<tempList.size()&&tempList.get(j)[0]<=t){
t=Math.max(t,tempList.get(j)[1]);
j++;
}
curInterval.add(new int[]{tempList.get(i)[0],t});
i=j;
}
int[][] res = curInterval.toArray(new int[curInterval.size()][2]);
return res;
}
}
57. Insert Interval
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
//corner case
if(newInterval==null){
return intervals;
}
int left=newInterval[0];
int right=newInterval[1];
List<int[]> ans =new ArrayList<>();
boolean placed =false;
for(int[] interval:intervals){
if(interval[0]>right){
//inserted on the left
if(!placed){
ans.add(new int[]{left,right});
placed=true;
}
ans.add(interval);
} else if(interval[1]<left){
//inserted on the right
ans.add(interval);
} else{
left = Math.min(left,interval[0]);
right = Math.max(right,interval[1]);
}
}
if(!placed){
ans.add(new int[]{left,right});
}
int[][] res = new int[ans.size()][2];
for (int i = 0; i < ans.size(); ++i) {
res[i] = ans.get(i);
}
return res;
}
}
59. Spiral Matrix II
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int top=0;
int bottom=n-1;
int left=0;
int right=n-1;
int num=1;
while(top<=bottom&&left<=right){
for(int col=left;col<=right;col++){
matrix[top][col]=num;
num++;
}
for(int row=top+1;row<=bottom;row++){
matrix[row][right]=num;
num++;
}
// if(top<bottom&&left<right){
for(int col=right-1;col>left;col--){
matrix[bottom][col]=num;
num++;
}
for(int row=bottom;row>top;row--){
matrix[row][left]=num;
num++;
}
// }
top++;
left++;
right--;
bottom--;
}
return matrix;
}
}
61. Rotate List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null||head.next==null){
return head;
}
if(k==0){
return head;
}
ListNode tail = head;
int n=1;
while(tail.next!=null){
tail=tail.next;
n++;
}
tail.next=head;
ListNode newTail=head;
for(int i=0;i<n-k%n-1;i++){
newTail=newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
62. Unique Paths
class Solution {
public int uniquePaths(int m, int n) {
if(m<=0||n<=0){
return 0;
}
int[][] dp=new int[m][n];
for(int i=0;i<m;i++){
dp[i][0]=1;
}
for(int i=0;i<n;i++){
dp[0][i]=1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
63. Unique Paths II
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid==null||obstacleGrid.length==0){
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp=new int[m][n];
dp[0][0]=obstacleGrid[0][0]!=1?1:0;
for(int i=1;i<m;i++){
dp[i][0]=obstacleGrid[i][0]!=1?dp[i-1][0]:0;
}
for(int i=1;i<n;i++){
dp[0][i]=obstacleGrid[0][i]!=1?dp[0][i-1]:0;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=obstacleGrid[i][j]!=1?(dp[i-1][j]+dp[i][j-1]):0;
}
}
return dp[m-1][n-1];
}
}
71. Simplify Path
class Solution {
public String simplifyPath(String path) {
if(path==null||path.length()==0){
return path;
}
String[] pathArr = path.split("/");
Deque<String> stack = new ArrayDeque<>();
for(String s:pathArr){
if(s.equals("..")){
if(!stack.isEmpty()) {
stack.pollLast();
}
} else if(s.length()>0&&!s.equals(".")){
stack.offerLast(s);
}
}
StringBuffer sb = new StringBuffer();
if(stack.isEmpty()){
sb.append("/");
} else {
while(!stack.isEmpty()){
sb.append("/");
sb.append(stack.pollFirst());
}
}
return sb.toString();
}
}
73. Set Matrix Zeroes
class Solution {
public void setZeroes(int[][] matrix) {
List<int[]> zeroPositions = new ArrayList<>();
if(matrix==null||matrix.length==0||matrix[0].length==0){
return;
}
int m = matrix.length;
int n = matrix[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==0){
zeroPositions.add(new int[]{i,j});
}
}
}
for(int[] pos: zeroPositions){
int row = pos[0];
int col = pos[1];
for(int i=0;i<n;i++){
matrix[row][i]=0;
}
for(int i=0;i<m;i++){
matrix[i][col]=0;
}
}
}
}
74. Search a 2D Matrix
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null||matrix.length==0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int begin = 0;
int end = m*n-1;
while(begin<=end){
int mid = (begin+end)/2;
int ele = matrix[mid/n][mid%n];
if(ele==target){
return true;
} else if(ele>target){
end=mid-1;
} else{
begin=mid+1;
}
}
return false;
}
}
75. Sort Colors
class Solution {
public void sortColors(int[] nums) {
if(nums==null||nums.length==0){
return;
}
//partition:
// all in [0, zero) = 0
// all in [zero, i) = 1
// all in [two, len - 1] = 2
int zero = -1;
int i = 0;
int two = nums.length -1;
while(i<=two){
if(nums[i]==0){
zero++;
swap(nums,zero,i);
i++;
} else if(nums[i]==1) {
i++;
} else{
swap(nums,i,two);
two--;
}
}
}
public void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
77. Combinations
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if(k<=0||n<=0){
return res;
}
dfs(n,k,1,new ArrayList<>(),res);
return res;
}
public void dfs(int n, int k, int start, List<Integer> path, List<List<Integer>> res){
if(k==path.size()){
res.add(new ArrayList(path));
return;
}
for(int i=start;i<=n;i++){
path.add(i);
dfs(n,k,i+1,path,res);
path.remove(path.size()-1);
}
}
}
78. Subsets
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null||nums.length==0){
return res;
}
dfs(nums,0,new ArrayList<>(),res);
return res;
}
public void dfs(int[] nums, int cur, List<Integer> path, List<List<Integer>> res){
if(cur==nums.length){
res.add(new ArrayList<>(path));
return;
}
dfs(nums,cur+1,path,res);
path.add(nums[cur]);
dfs(nums,cur+1,path,res);
path.remove(path.size()-1);
}
}
79. Word Search
class Solution {
public boolean exist(char[][] board, String word) {
if(board==null||board.length==0||word==null||word.length()==0){
return false;
}
int n = board.length;
int m = board[0].length;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
boolean[][] visited = new boolean[n][m];
if(dfs(board,word.toCharArray(),visited,0,i,j)){
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, char[] word, boolean[][] visited, int cur, int i, int j){
if(cur==word.length){
return true;
}
if(i<0||i>=board.length||j<0||j>=board[i].length||visited[i][j]||word[cur]!=board[i][j]){
return false;
}
visited[i][j]=true;
boolean res = dfs(board,word,visited,cur+1,i-1,j) || dfs(board,word,visited,cur+1,i+1,j) || dfs(board,word,visited,cur+1,i,j-1) || dfs(board,word,visited,cur+1,i,j+1);
visited[i][j]=false;
return res;
}
}
80. Remove Duplicates from Sorted Array II
class Solution {
public int removeDuplicates(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int n = nums.length;
int j=2;
for(int i=2;i<n;i++){
//x x x ... x y
//j-2 j-1 j i-1 i
if(nums[j-2]!=nums[i]){
nums[j]=nums[i];
j++;
}
}
return j;
}
}
81. Search in Rotated Sorted Array II
class Solution {
public boolean search(int[] nums, int target) {
if(nums==null||nums.length==0){
return false;
}
int n = nums.length;
int left = 0;
int right = n-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target){
return true;
} else if(nums[mid]>nums[right]){
//[left..mid] in order
if(target>=nums[left]&&target<=nums[mid]){
right=mid-1;
} else{
left=mid+1;
}
} else if(nums[mid]<nums[right]){
//[mid..right] in order
if(target>=nums[mid]&&target<=nums[right]){
left=mid+1;
} else{
right=mid-1;
}
} else {
right--;
}
}
return false;
}
}
82. Remove Duplicates from Sorted List II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode preHead = new ListNode(-1,head);
ListNode cur = preHead;
while(cur!=null&&cur.next!=null&&cur.next.next!=null){
if(cur.next.val==cur.next.next.val){
int x = cur.next.val;
while(cur.next!=null&&cur.next.val==x){
cur.next=cur.next.next;
}
} else {
cur=cur.next;
}
}
return preHead.next;
}
}
86. Partition List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if(head==null){
return null;
}
ListNode small = new ListNode(-1);
ListNode large = new ListNode(-1);
ListNode smallHead = small;
ListNode largeHead = large;
while(head!=null){
if(head.val<x){
small.next=head;
small=small.next;
} else {
large.next=head;
large=large.next;
}
head=head.next;
}
small.next=largeHead.next;
large.next=null;
return smallHead.next;
}
}
89. Gray Code
class Solution {
public List<Integer> grayCode(int n) {
/**
First, analyze the binary difference between two adjacent numbers. The difference is that the first 0 that appears in the low-to-high order becomes 1, and all 1s before it become 0 (+1 bit operation effect)
This is a continuous inversion change starting from the least significant bit
Then if the Gray code takes the XOR of the adjacent two bits (displaced XOR), if both of these two bits are inverted or neither are inverted, the corresponding bit of the Gray code remains unchanged.
And only one bit can change (XOR of adjacent two bits, the high bit is not reversed, and the low bit is reversed)
Therefore, only one bit of adjacent Gray codes may change, which conforms to the definition of Gray codes.
*/
List<Integer> ret = new ArrayList<>();
for (int i = 0; i < 1 << n; i++) {
ret.add((i >> 1) ^ i);
}
return ret;
}
}
90. Subsets II
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null||nums.length==0){
return res;
}
dfs(nums,0,new ArrayList<>(),new ArrayList<>(),res);
return res;
}
public void dfs(int[] nums, int cur, List<Integer> path, List<List<Integer>> midRes, List<List<Integer>> res){
if(cur==nums.length){
List<Integer> temp = new ArrayList<>(path);
temp.sort((t1,t2)->t1-t2);
if(!midRes.contains(temp)){
midRes.add(temp);
res.add(new ArrayList<>(path));
}
return;
}
dfs(nums,cur+1,path,midRes,res);
path.add(nums[cur]);
dfs(nums,cur+1,path,midRes,res);
path.remove(path.size()-1);
}
}
91. Decode Ways
class Solution {
public int numDecodings(String s) {
if(s==null||s.length()==0){
return 0;
}
int n = s.length();
int[] dp = new int[n+1];//dp[i] denotes numDecodings[0..i-1]
dp[0]=1;//base case
dp[1]=s.charAt(0)!='0'?1:0;
for(int i=2;i<=n;i++){
char c1=s.charAt(i-1);
char c2=s.charAt(i-2);
if(c1>='1'&&c1<='9'){
dp[i]+=dp[i-1];
}
if(c2=='1'||(c2=='2'&&c1<='6')){
dp[i]+=dp[i-2];
}
}
return dp[n];
}
}
92. Reverse Linked List II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// Use of virtual head nodes avoids complex taxonomy discussions because head nodes are subject to change
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
// Step 1: Take left - 1 steps from the virtual head node to the node before the left node
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
// Step 2: Take right - left + 1 steps from pre to the right node
ListNode rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// Step 3: Cut off a child linked list (intercept linked list)
ListNode leftNode = pre.next;
ListNode curr = rightNode.next;
// Note: cut link
pre.next = null;
rightNode.next = null;
// Step 4: Reverse the subranges of the linked list
reverseLinkedList(leftNode);
// Step 5: Connect back to the original linked list
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
}
private void reverseLinkedList(ListNode head) {
// You can also reverse a linked list using recursion
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
}
93. Restore IP Addresses
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> ans=new ArrayList<>();
dfs(s,0,ans,new ArrayList<>());
return ans;
}
public void dfs(String s,int begin,List<String> ans,List<String> temp){
if(temp.size()==4){
if(begin==s.length()){
ans.add(String.join(".",temp));
}
return;
}
for(int i=begin;i<begin+3&&i<s.length();i++){
String sub = s.substring(begin,i+1);
if(!isRange(sub)){
continue;
}
temp.add(sub);
dfs(s,i+1,ans,temp);
temp.remove(temp.size()-1);
}
}
public boolean isRange(String sub){
if(sub.length()!=1&&sub.charAt(0)=='0'){
return false;
}
return Integer.parseInt(sub)<=255?true:false;
}
}
95. Unique Binary Search Trees II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n<=0){
return new ArrayList<>();
} else {
return build(1,n);
}
}
public List<TreeNode> build(int left, int right){
List<TreeNode> res = new ArrayList<>();
if(left>right){
res.add(null);
return res;
}
for(int i=left;i<=right;i++){
List<TreeNode> leftTrees = build(left,i-1);
List<TreeNode> rightTrees = build(i+1,right);
for(TreeNode leftNode: leftTrees){
for(TreeNode rightNode: rightTrees){
TreeNode node = new TreeNode(i);
node.left=leftNode;
node.right=rightNode;
res.add(node);
}
}
}
return res;
}
}
96. Unique Binary Search Trees
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public int numTrees(int n) {
if (n == 0 || n == 1){
return 1;
}
if (map.containsKey(n)){
return map.get(n);
}
int count = 0;
for (int i = 1; i <= n; i++) {
int leftNum = numTrees(i-1);
int rightNum = numTrees(n-i);
count+=leftNum*rightNum;
}
map.put(n,count);
return count;
}
}
97. Interleaving String
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length(), m = s2.length(), t = s3.length();
if (n + m != t) {
return false;
}
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (i > 0) {
dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i+j-1));
}
if (j > 0) {
dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i+j-1));
}
}
}
return dp[n][m];
}
}
98. Validate Binary Search Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidTree(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isValidTree(TreeNode node, long low, long high){
if(node==null){
return true;
}
if(node.val<=low||node.val>=high){
return false;
}
return isValidTree(node.left,low,node.val) && isValidTree(node.right,node.val,high);
}
}
99. Recover Binary Search Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// Record the two exchanged nodes separately
TreeNode first = null, second = null;
// Determine the ordering of in-order traversal
TreeNode prev = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
inOrder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
public void inOrder(TreeNode root){
if (root == null) {
return;
}
inOrder(root.left);
// In-order traverse the code position to find the two nodes
if (root.val < prev.val) {
// root is not ordered
if (first == null) {
// The first dislocation node is prev
first = prev;
}
// The second misplaced node is root
second = root;
}
prev = root;
inOrder(root.right);
}
}
102. Binary Tree Level Order Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root==null){
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> level = new ArrayList<>();
int n = queue.size();
for(int i=0;i<n;i++){
TreeNode node = queue.poll();
level.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
ret.add(level);
}
return ret;
}
}
103. Binary Tree Zigzag Level Order Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root==null){
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean revert = false;
while(!queue.isEmpty()){
List<Integer> level = new ArrayList<>();
int n = queue.size();
for(int i=0;i<n;i++){
TreeNode node = queue.poll();
if(revert){
level.add(0,node.val);
} else{
level.add(node.val);
}
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
ret.add(level);
revert=!revert;
}
return ret;
}
}
105. Construct Binary Tree from Preorder and Inorder Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null||preorder.length==0||inorder==null||inorder.length==0){
return null;
} else{
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
}
TreeNode build(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd){
if(preEnd<preStart||inEnd<inStart){
return null;
}
int rootVal = preOrder[preStart];
int index = -1;
for(int i=inStart;i<=inEnd;i++){
if(inOrder[i]==rootVal){
index=i;
break;
}
}
if(index<0){
return null;
}
int leftSize = index-inStart;
TreeNode root = new TreeNode(rootVal);
root.left=build(preOrder,preStart+1,preStart+leftSize,inOrder,inStart,index-1);
root.right=build(preOrder,preStart+leftSize+1,preEnd,inOrder,index+1,inEnd);
return root;
}
}
106. Construct Binary Tree from Inorder and Postorder Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder==null||inorder.length==0||postorder==null||postorder.length==0){
return null;
} else {
return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
}
public TreeNode build(int[] inOrder, int inStart, int inEnd, int[] postOrder, int postStart, int postEnd){
if(inStart>inEnd||postStart>postEnd||inStart<0||postStart<0){
return null;
}
int rootVal = postOrder[postEnd];
int index = -1;
for(int i=inEnd;i>=inStart;i--){
if(inOrder[i]==rootVal){
index=i;
break;
}
}
if(index<0){
return null;
}
// int leftSize = index-inStart-1;
int rightSize = inEnd-index;
TreeNode root = new TreeNode(rootVal);
root.left=build(inOrder,inStart,index-1,postOrder,postStart,postEnd-rightSize-1);
root.right=build(inOrder,index+1,inEnd,postOrder,postEnd-rightSize,postEnd-1);
return root;
}
}
107. Binary Tree Level Order Traversal II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root==null){
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> level = new ArrayList<>();
int n = queue.size();
for(int i=0;i<n;i++){
TreeNode node = queue.poll();
level.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
ret.add(0,level);
}
return ret;
}
}
109. Convert Sorted List to Binary Search Tree
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
return build(head,null);
}
//[begin,end)
public TreeNode build(ListNode begin, ListNode end){
if(begin==end){
return null;
}
ListNode mid = getMid(begin,end);
TreeNode root = new TreeNode(mid.val);
root.left=build(begin,mid);
root.right=build(mid.next,end);
return root;
}
public ListNode getMid(ListNode begin, ListNode end){
ListNode slow = begin;
ListNode fast = begin;
while(fast!=end&&fast.next!=end){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}
113. Path Sum II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if(root==null){
return res;
}
dfs(root,targetSum,new ArrayList<>(),res);
return res;
}
public void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res){
if (root == null) return;
int remain = sum - root.val;
if (root.left == null && root.right == null) {
if (remain == 0) {
// find a path
path.add(root.val);
res.add(new ArrayList<>(path));
path.remove(path.size()-1);
}
return;
}
path.add(root.val);
dfs(root.left,remain,path,res);
dfs(root.right,remain,path,res);
path.remove(path.size()-1);
}
}
114. Flatten Binary Tree to Linked List
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if(root==null){
return;
}
//flatten left, right
flatten(root.left);
flatten(root.right);
TreeNode left = root.left;
TreeNode right = root.right;
root.right = left;
root.left = null;
TreeNode p = root;
while(p.right!=null){
p=p.right;
}
p.right=right;
}
}
116. Populating Next Right Pointers in Each Node
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
//level order
if(root==null){
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int n = queue.size();//how many elements in this level
Node prev = null;
for(int i=0;i<n;i++){
Node node = queue.poll();//current node
if(prev!=null){
prev.next=node;
}
prev=node;
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
}
return root;
}
}
117. Populating Next Right Pointers in Each Node II
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root==null){
return null;
}
Node cur = root;
while(cur!=null){
Node extra = new Node(-1);
Node pre = extra;
while(cur!=null){
if(cur.left!=null){
pre.next=cur.left;
pre=pre.next;
}
if(cur.right!=null){
pre.next=cur.right;
pre=pre.next;
}
cur=cur.next;
}
cur=extra.next;
}
return root;
}
}
120. Triangle
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle==null){
return 0;
}
int n=triangle.size();
int[][] dp=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
if(i>0&&j>0&&j<i){
dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);
} else if(i>0&&j>0){
dp[i][j]=dp[i-1][j-1]+triangle.get(i).get(j);
} else if(i>0){
dp[i][j]=dp[i-1][j]+triangle.get(i).get(j);
} else {
dp[i][j]=triangle.get(i).get(j);
}
}
}
int minValue = Integer.MAX_VALUE;
for(int i=0;i<n;i++){
if(dp[n-1][i]<minValue){
minValue=dp[n-1][i];
}
}
return minValue;
}
}
122. Best Time to Buy and Sell Stock II
class Solution {
public int maxProfit(int[] prices) {
int sum = 0;
if(prices==null||prices.length==0){
return sum;
}
int n = prices.length;
for(int i=1;i<n;i++){
if(prices[i]>prices[i-1]){
sum+=(prices[i]-prices[i-1]);
}
}
return sum;
}
}
128. Longest Consecutive Sequence
class Solution {
public int longestConsecutive(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
Set<Integer> hashSet = new HashSet<>();
for(int num:nums){
hashSet.add(num);
}
int res = 0;
for(int num:hashSet){
if(!hashSet.contains(num-1)){
int curLen = 1;
int curNum = num;
while(hashSet.contains(curNum+1)){
curLen++;
curNum++;
}
res = Math.max(res,curLen);
}
}
return res;
}
}
129. Sum Root to Leaf Numbers
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
if(root==null){
return 0;
}
List<Integer> val = new ArrayList<>();
dfs(root,new StringBuffer(),val);
int sum=0;
for(int item:val){
sum+=item;
}
return sum;
}
public void dfs(TreeNode node,StringBuffer path, List<Integer> val){
if(node==null){
return;
}
path.append(node.val);
if(node.left==null&&node.right==null){
val.add(Integer.parseInt(path.toString()));
}
dfs(node.left,path,val);
dfs(node.right,path,val);
path.deleteCharAt(path.length()-1);
}
}
131. Palindrome Partitioning
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> ret = new ArrayList<>();
if(s==null||s.length()==0){
return ret;
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
for(int i=0;i<n;i++){
Arrays.fill(dp[i],true);
}
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
dp[i][j]=dp[i+1][j-1]&&(s.charAt(i)==s.charAt(j));
}
}
dfs(s,0,dp,new ArrayList<>(),ret);
return ret;
}
public void dfs(String s, int cur, boolean[][] dp, List<String> temp, List<List<String>> res){
if(cur==s.length()){
res.add(new ArrayList(temp));
return;
}
for(int i=cur;i<s.length();i++){
if(dp[cur][i]){
temp.add(s.substring(cur,i+1));
dfs(s,i+1,dp,temp,res);
temp.remove(temp.size()-1);
}
}
}
}
133. Clone Graph
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
private HashMap <Node, Node> visited = new HashMap <> ();
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
// If the node has been visited, directly take out the corresponding clone node from the hash table and return
if (visited.containsKey(node)) {
return visited.get(node);
}
// Clone the node, noting that we don't clone the list of its neighbors in order to deep copy
Node cloneNode = new Node(node.val, new ArrayList());
// Hash table storage
visited.put(node, cloneNode);
// Traverse the node's neighbors and update the cloned node's neighbor list
for (Node neighbor: node.neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
}
134. Gas Station
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas==null||cost==null){
return -1;
}
int sum = 0;
int minSum = 0;
int n = gas.length;
int start = 0;
for(int i=0;i<n;i++){
sum+=gas[i]-cost[i];
if(sum<minSum){
start=i+1;
minSum=sum;
}
}
if(sum<0){
return -1;
}
return start%n;
}
}
138. Copy List with Random Pointer
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
Map<Node, Node> cachedNode = new HashMap<>();
public Node copyRandomList(Node head) {
if(head==null){
return null;
}
if(cachedNode.containsKey(head)){
return cachedNode.get(head);
}
Node node = new Node(head.val);
cachedNode.put(head,node);
node.next=copyRandomList(head.next);
node.random=copyRandomList(head.random);
return node;
}
}
139. Word Break
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if(s==null||s.length()==0){
return true;
}
if(wordDict==null||wordDict.size()==0){
return false;
}
Set<String> dictSet = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n+1];
//dp[i] denotes whether s.substring(i) can be breaked
dp[0] = true;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
if(dp[j]&&dictSet.contains(s.substring(j,i))){
dp[i]=true;
break;
}
}
}
return dp[n];
}
}
142. Linked List Cycle II
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null){
return null;
}
ListNode p1=head;//fast
ListNode p2=head;//slow
while(p1!=null&&p1.next!=null){
p1=p1.next.next;//2 steps
p2=p2.next;//1 step
if(p1==p2){
break;
}
}
if(p1==null||p1.next==null){
//no circle
return null;
}
//else conflicts
p1=head;
while(p1!=null&&p2!=null&&p1!=p2){
p1=p1.next;
p2=p2.next;
}
if(p1!=null&&p2!=null){
//p1==p2
return p1;
}
else{
//something wrong
return null;
}
}
}
143. Reorder List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
Stack<ListNode> stack = new Stack<>();
ListNode p = head;
while(p!=null){
stack.push(p);
p=p.next;
}
p = head;
while(p!=null){
ListNode last = stack.pop();
ListNode next = p.next;
if(last==next||last.next==next){
last.next=null;
break;
}
p.next = last;
last.next = next;
p = next;
}
}
}
146. LRU Cache
class LRUCache {
int cap;
Map<Integer,Integer> map = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if(!map.containsKey(key)){
return -1;
}
makeRecent(key);
return map.get(key);
}
public void put(int key, int value) {
if(map.containsKey(key)){
map.put(key,value);
makeRecent(key);
return;
}
if(map.size()>=this.cap){
int oldestKey = map.keySet().iterator().next();
map.remove(oldestKey);
}
map.put(key,value);
}
private void makeRecent(int key){
int value = map.get(key);
map.remove(key);
map.put(key,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);
*/
147. Insertion Sort List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null){
return null;
}
ListNode newHead = new ListNode(-1);
newHead.next = head;
ListNode lastSorted = head;
ListNode cur = head.next;
while(cur!=null){
if(lastSorted.val<=cur.val){
lastSorted = lastSorted.next;
cur = lastSorted.next;
} else {
ListNode prev = newHead;
while(prev.next.val<=cur.val){
prev=prev.next;
}
lastSorted.next = cur.next;
cur.next = prev.next;
prev.next = cur;
cur = lastSorted.next;
}
}
return newHead.next;
}
}
148. Sort List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head,null);
}
public ListNode sortList(ListNode head, ListNode tail){//[head,tail)
if(head==null){
return null;
}
if(head.next==tail){
head.next=null;
return head;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=tail&&fast.next!=tail){
slow=slow.next;
fast=fast.next;
if(fast!=tail){
fast=fast.next;
}
}
ListNode mid=slow;
ListNode list1=sortList(head,mid);
ListNode list2=sortList(mid,tail);
return merge(list1,list2);
}
public ListNode merge(ListNode list1, ListNode list2){
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode head = null;
if(list1.val>list2.val){
head=list2;
head.next=merge(list1,list2.next);
} else{
head=list1;
head.next=merge(list1.next,list2);
}
return head;
}
}
150. Evaluate Reverse Polish Notation
class Solution {
public int evalRPN(String[] tokens) {
if(tokens==null){
return 0;
}
Stack<Integer> stack = new Stack<>();
for(String token:tokens){
int op1 = 0;
int op2 = 0;
switch(token){
case "+":
op1 = stack.pop();
op2 = stack.pop();
stack.push(op2+op1);
break;
case "-":
op1 = stack.pop();
op2 = stack.pop();
stack.push(op2-op1);
break;
case "*":
op1 = stack.pop();
op2 = stack.pop();
stack.push(op2*op1);
break;
case "/":
op1 = stack.pop();
op2 = stack.pop();
stack.push(op2/op1);
break;
default:
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
151. Reverse Words in a String
class Solution {
public String reverseWords(String s) {
if(s==null||s.length()==0){
return s;
}
String[] words = s.split("\\s+");
StringBuffer sb = new StringBuffer();
for(int i=words.length-1;i>=0;i--){
sb.append(words[i].replaceAll(" ",""));
sb.append(" ");
}
return sb.toString().trim();
}
}
152. Maximum Product Subarray
class Solution {
public int maxProduct(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int n=nums.length;
//dp[i] at the location i, the value (must include nums[i])
int[] dpMax = new int[n];
int[] dpMin = new int[n];
dpMax[0]=nums[0];
dpMin[0]=nums[0];
for(int i=1;i<n;i++){
dpMax[i]=Math.max(dpMax[i-1]*nums[i],Math.max(nums[i],dpMin[i-1]*nums[i]));
dpMin[i]=Math.min(dpMin[i-1]*nums[i],Math.min(nums[i],dpMax[i-1]*nums[i]));
}
int ans = dpMax[0];
for(int i=1;i<n;i++){
ans=Math.max(ans,dpMax[i]);
}
return ans;
}
}
153. Find Minimum in Rotated Sorted Array
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int pivot = (low+high)/2;
if (nums[pivot] < nums[high]) {
high = pivot;
} else {
low = pivot + 1;
}
}
return nums[low];
}
}
162. Find Peak Element
class Solution {
public int findPeakElement(int[] nums) {
if(nums==null||nums.length==0){
return -1;
}
int n = nums.length;
int l = 0;
int r = n-1;
while(l<=r){
int i = (l+r)/2;
if((i==0||nums[i]>nums[i-1])&&(i==n-1||nums[i]>nums[i+1])){
return i;
}
if(i>0&&nums[i-1]>nums[i]){
r=i-1;
} else {
l=i+1;
}
}
return -1;
}
}
165. Compare Version Numbers
class Solution {
public int compareVersion(String version1, String version2) {
if(version1==null||version2==null){
return 0;
}
String[] v1 = version1.split("\\.");
String[] v2 = version2.split("\\.");
int m = v1.length;
int n = v2.length;
for(int i=0;i<Math.min(m,n);i++){
if(Integer.parseInt(v1[i])>Integer.parseInt(v2[i])){
return 1;
} else if(Integer.parseInt(v1[i])<Integer.parseInt(v2[i])){
return -1;
}
}
for(int i=Math.min(m,n);i<Math.max(m,n);i++){
if(i<m){
if(Integer.parseInt(v1[i])!=0){
return 1;
}
} else if(i<n){
if(Integer.parseInt(v2[i])!=0){
return -1;
}
}
}
return 0;
}
}
166. Fraction to Recurring Decimal
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
long a = numerator;
long b = denominator;
if(a%b==0){
return String.valueOf(a/b);
}
StringBuffer sb = new StringBuffer();
if(a*b<0){
sb.append("-");
}
a=Math.abs(a);
b=Math.abs(b);
sb.append(a/b);
sb.append(".");
a=a%b;
Map<Long,Integer> map = new HashMap<>();
while(a!=0){
map.put(a,sb.length());
a=a*10;
sb.append(a/b);
a=a%b;
if(map.containsKey(a)){
int u = map.get(a);
return String.format("%s(%s)", sb.substring(0, u), sb.substring(u));
}
}
return sb.toString();
}
}
167. Two Sum II - Input Array Is Sorted
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers==null||numbers.length==0){
return null;
}
int n = numbers.length;
int i = 0;
int j = n-1;
while(i<j){
if(numbers[i]+numbers[j]==target){
return new int[]{i+1,j+1};
} else if(numbers[i]+numbers[j]<target){
i++;
} else {
j--;
}
}
return null;
}
}
172. Factorial Trailing Zeroes
class Solution {
public int trailingZeroes(int n) {
int res = 0;
long divisor = 5;
while(divisor<=n){
res+=n/divisor;
divisor*=5;
}
return res;
}
}
173. Binary Search Tree Iterator
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class BSTIterator {
// Simulate recursion stack
private Stack<TreeNode> stk = new Stack<>();
// The left branch is smashed to the end
private void pushLeftBranch(TreeNode p) {
while (p != null) {
stk.push(p);
p = p.left;
}
}
public BSTIterator(TreeNode root) {
pushLeftBranch(root);
}
public int next() {
TreeNode p = stk.pop();
pushLeftBranch(p.right);
return p.val;
}
public boolean hasNext() {
return !stk.isEmpty();
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
179. Largest Number
class Solution {
public String largestNumber(int[] nums) {
if(nums==null||nums.length==0){
return "0";
}
int n = nums.length;
String[] numsArr = new String[n];
for (int i = 0; i < n; i++) {
numsArr[i] = String.valueOf(nums[i]);
}
Arrays.sort(numsArr,(num1,num2)->{
long pos1 = Long.parseLong(num1+num2);
long pos2 = Long.parseLong(num2+num1);
return (int)(pos2-pos1);
});
StringBuffer sb = new StringBuffer();
for(String s:numsArr){
if(sb.length()==0&&s.equals("0")){
continue;
}
sb.append(s);
}
return sb.length()==0?"0":sb.toString();
}
}
187. Repeated DNA Sequences
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> ans = new ArrayList<>();
if(s==null||s.length()==0){
return ans;
}
Map<String,Integer> map = new HashMap<>();
int n = s.length();
for(int i=0;i<=n-10;i++){
String sub = s.substring(i,i+10);
map.put(sub,map.getOrDefault(sub,0)+1);
if(map.get(sub)==2){
ans.add(sub);
}
}
return ans;
}
}
189. Rotate Array
class Solution {
public void rotate(int[] nums, int k) {
if(nums==null||nums.length==0){
return;
}
int n = nums.length;
k = k%n;
reverse(nums,0,n-1);
reverse(nums,0,k-1);
reverse(nums,k,n-1);
}
public void reverse(int[] nums, int start, int end){
while(start<=end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
199. Binary Tree Right Side View
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int n = queue.size();
for(int i=0;i<n;i++){
TreeNode node = queue.poll();
if(i==n-1){
res.add(node.val);
}
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
}
return res;
}
}
200. Number of Islands
class Solution {
public int numIslands(char[][] grid) {
if(grid==null||grid.length==0||grid[0].length==0){
return 0;
}
int n=grid.length;
int m=grid[0].length;
int res = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='1'){
res++;
dfs(grid,i,j);
}
}
}
return res;
}
public void dfs(char[][] grid, int i, int j){
if(i<0||j<0||i>=grid.length||j>=grid[i].length){
return;
}
if(grid[i][j]!='1'){
return;
}
grid[i][j]='0';
dfs(grid,i-1,j);
dfs(grid,i,j-1);
dfs(grid,i+1,j);
dfs(grid,i,j+1);
}
}
201. Bitwise AND of Numbers Range
class Solution {
public int rangeBitwiseAnd(int left, int right) {
String s1 = Integer.toBinaryString(left);
String s2 = Integer.toBinaryString(right);
if(s1.length()!=s2.length()){
return 0;
}
int res = left;
for(long i=(long)left+1;i<=(long)right;i++){
res = res & (int)i;
}
return res;
}
}
204. Count Primes
class Solution {
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
for (int i = 2; i * i < n; i++)
if (isPrime[i])
for (int j = i * i; j < n; j += i)
isPrime[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrime[i]) count++;
return count;
}
}
207. Course Schedule
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(prerequisites==null||numCourses<=0){
return true;
}
int[] visited = new int[numCourses];
List<List<Integer>> edges = new ArrayList<>();
for(int i=0;i<numCourses;i++){
edges.add(new ArrayList<>());
}
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
}
for(int i=0;i<numCourses;i++){
if(visited[i]==0){
boolean res = dfs(i,edges,visited);
if(!res){
return res;
}
}
}
return true;
}
public boolean dfs(int pos, List<List<Integer>> edges, int[] visited){
visited[pos]=1;//searching
for(int v:edges.get(pos)){
if(visited[v]==0){//univisted
boolean ret = dfs(v,edges,visited);
if(!ret){
return ret;
}
} else if(visited[v]==1){//searching
return false;
}
}
visited[pos]=2;//completed
return true;
}
}
208. Implement Trie (Prefix Tree)
class Trie {
private boolean isEnd;
private Trie[] next;
public Trie() {
isEnd = false;
next = new Trie[26];
}
public void insert(String word) {
// Start with the first node, which can be imagined as an empty node
Trie cur = this;
int len = word.length();
for (int i = 0; i < len; i++) {
char ch = word.charAt(i);
// If the next character of the current node has not been opened, create a new one
if (cur.next[ch-'a'] == null) {
cur.next[ch-'a'] = new Trie();
}
// Move the node pointer backward
cur = cur.next[ch-'a'];
}
// The loop ends, the character pointed to by the current node is the end character
cur.isEnd = true;
}
public boolean search(String word) {
Trie cur = prefixSearch(word);
// All characters match, and the last character is the end character
return cur != null && cur.isEnd;
}
public boolean startsWith(String prefix) {
// match all characters
return prefixSearch(prefix) != null;
}
// Method extraction, reuse of repetitive code
private Trie prefixSearch(String word) {
Trie cur = this;
int len = word.length();
for (int i = 0; i < len; i++) {
char ch = word.charAt(i);
// If the corresponding character of the current node has not been opened, it means that there is no corresponding word inserted.
if (cur.next[ch-'a'] == null) return null;
cur = cur.next[ch-'a'];
}
return cur;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
209. Minimum Size Subarray Sum
class Solution {
public int minSubArrayLen(int target, int[] nums) {
if(nums==null){
return 0;
}
int left = 0;
int right = 0;
int temp = 0;//[left,right)
int res = Integer.MAX_VALUE;
while(right<nums.length){
temp+=nums[right];
right++;
while(temp>=target&&left<right){
res=Math.min(res,right-left);
temp-=nums[left];
left++;
}
}
return res==Integer.MAX_VALUE?0:res;
}
}
211. Design Add and Search Words Data Structure
class WordDictionary {
private WordDictionary[] items;
boolean isEnd;
public WordDictionary() {
items = new WordDictionary[26];
}
public void addWord(String word) {
WordDictionary curr = this;
int n = word.length();
for(int i = 0; i < n; i++){
int index = word.charAt(i)-'a';
if(curr.items[index]==null)
curr.items[index] = new WordDictionary();
curr = curr.items[index];
}
curr.isEnd = true;
}
public boolean search(String word) {
return search(this,word,0);
}
private boolean search(WordDictionary curr, String word, int start){
int n = word.length();
if(start == n)
return curr.isEnd;
char c= word.charAt(start);
if(c!='.'){
WordDictionary item = curr.items[c-'a'];
return item!=null && search(item,word,start+1);
}
for(int j = 0; j < 26; j++){
if(curr.items[j]!=null && search(curr.items[j],word,start+1))
return true;
}
return false;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
213. House Robber II
class Solution {
public int rob(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int n = nums.length;
if(n==1){
return nums[0];
}
if(n==2){
return Math.max(nums[0],nums[1]);
}
return Math.max(robN(nums,0,n-2),robN(nums,1,n-1));
}
public int robN(int[] nums, int start, int end) {
if(nums==null||nums.length==0){
return 0;
}
int n =nums.length;
int[] dp=new int[n];//dp[i] denotes at the room i, the maximum value
dp[start]=nums[start];
if(start+1<=end){
dp[start+1]=Math.max(dp[start],nums[start+1]);
}
for(int i=start+2;i<=end;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[end];
}
}
215. Kth Largest Element in an Array
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums==null||nums.length==0||k<=0||k>nums.length){
return -1;
}
return quickSelect(nums,0,nums.length-1,nums.length-k);
}
public int quickSelect(int[] a,int l, int r, int index){
int q = partition(a,l,r);
if(q==index){
return a[q];
} else if(q<index){
return quickSelect(a,q+1,r,index);
} else{
return quickSelect(a,l,q-1,index);
}
}
public int partition(int[] a, int l, int r){
int x = a[r];
int i = l-1;
// i(included) left hand <=x, i right hand >x
for(int j=l;j<r;j++){
if(a[j]<=x){
i++;
swap(a,i,j);
}
}
swap(a,i+1,r);
//division point i+1
return i+1;
}
public void swap(int[] a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
216. Combination Sum III
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
boolean[] used = new boolean[9];
List<Set<Integer>> res = new ArrayList<>();
dfs(used,n,new ArrayList<>(),res);
List<List<Integer>> ans = new ArrayList<>();
res.forEach(e->{
if(e.size()==k){
ans.add(new ArrayList(e));
}
});
return ans;
}
public void dfs(boolean[] used, int target, List<Integer> temp, List<Set<Integer>> res){
if(target==0){
Set<Integer> cur = new HashSet(temp);
if(!res.contains(cur)){
res.add(cur);
}
return;
}
for(int i=0;i<9;i++){
//1..9
if(!used[i]){
used[i]=true;
temp.add(i+1);
dfs(used,target-(i+1),temp,res);
temp.remove(temp.size()-1);
used[i]=false;
}
}
}
}
220. Contains Duplicate III
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums==null||nums.length==0){
return false;
}
int n = nums.length;
TreeSet<Long> set = new TreeSet<>();
for(int i=0;i<n;i++){
Long ceiling = set.ceiling((long)nums[i]-t);
if(ceiling!=null&&ceiling<=(long)nums[i]+t){
return true;
}
set.add((long)nums[i]);
if(i>=k){
set.remove((long)nums[i-k]);
}
}
return false;
}
}
221. Maximal Square
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix==null||matrix.length==0||matrix[0].length==0){
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];//length
int maxLen = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='0'){
dp[i][j]=0;
} else if(matrix[i][j]=='1'){
if(i==0||j==0){
dp[i][j]=1;
}
else{
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
}
if(maxLen<dp[i][j]){
maxLen=dp[i][j];
}
}
}
return maxLen*maxLen;
}
}
222. Count Complete Tree Nodes
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
TreeNode left = root;
TreeNode right = root;
int countL = 0;
int countR = 0;
while(left!=null){
left=left.left;
countL++;
}
while(right!=null){
right=right.right;
countR++;
}
if(countL==countR){
return (int) Math.pow(2, countL) - 1;
}
return 1+countNodes(root.left)+countNodes(root.right);
}
}
223. Rectangle Area
class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int area1 = (ax2 - ax1) * (ay2 - ay1), area2 = (bx2 - bx1) * (by2 - by1);
int overlapWidth = Math.min(ax2, bx2) - Math.max(ax1, bx1), overlapHeight = Math.min(ay2, by2) - Math.max(ay1, by1);
int overlapArea = Math.max(overlapWidth, 0) * Math.max(overlapHeight, 0);
return area1 + area2 - overlapArea;
}
}
227. Basic Calculator II
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
char preSign = '+';
int num = 0;
int n = s.length();
for(int i=0;i<n;i++){
if(Character.isDigit(s.charAt(i))){
num=num*10+(s.charAt(i)-'0');
}
if(!Character.isDigit(s.charAt(i))&&s.charAt(i)!=' '||i==n-1){
switch(preSign){
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop()*num);
break;
case '/':
stack.push(stack.pop()/num);
break;
}
preSign = s.charAt(i);
num = 0;
}
}
int res = 0;
while(!stack.isEmpty()){
res+=stack.pop();
}
return res;
}
}
230. Kth Smallest Element in a BST
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
return search(root,k);
}
int rank = 0;
public Integer search(TreeNode root, int k){
if(root==null){
return null;
}
Integer res = search(root.left,k);
if(res!=null){
return res;
}
rank++;
if(rank==k){
return root.val;
}
return search(root.right,k);
}
}
236. Lowest Common Ancestor of a Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(root==p||root==q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left==null){
return right;
}
if(right==null){
return left;
}
return root;
}
}
238. Product of Array Except Self
class Solution {
public int[] productExceptSelf(int[] nums) {
if(nums==null||nums.length==0){
return null;
}
int n = nums.length;
int[] res = new int[n];
//calculate product of left-hand side
res[0]=1;
for(int i=1;i<n;i++){
res[i]=res[i-1]*nums[i-1];
}
//calculate product of right-hand side
int r = 1;
for(int i=n-1;i>=0;i--){
res[i]=res[i]*r;
r=r*nums[i];
}
return res;
}
}
240. Search a 2D Matrix II
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null||matrix.length==0||matrix[0].length==0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int x = 0;
int y = n-1;
while(x<m&&y>=0){
if(matrix[x][y]==target){
return true;
} else if(matrix[x][y]>target){
y--;
} else{
x++;
}
}
return false;
}
}
241. Different Ways to Add Parentheses
class Solution {
Map<String,List<Integer>> memo = new HashMap<>();
public List<Integer> diffWaysToCompute(String expression) {
List<Integer> res = new ArrayList<>();
if(expression==null||expression.length()==0){
return res;
}
if(memo.containsKey(expression)){
return memo.get(expression);
}
for(int i=0;i<expression.length();i++){
char c=expression.charAt(i);
if(c=='+'||c=='-'||c=='*'){
List<Integer> left = diffWaysToCompute(expression.substring(0,i));
List<Integer> right = diffWaysToCompute(expression.substring(i+1));
for(int a:left){
for(int b:right){
if(c=='+'){
res.add(a+b);
} else if(c=='-'){
res.add(a-b);
} else if(c=='*'){
res.add(a*b);
}
}
}
}
}
if(res.isEmpty()){
res.add(Integer.parseInt(expression));
}
memo.put(expression,res);
return res;
}
}
260. Single Number III
class Solution {
public int[] singleNumber(int[] nums) {
int xorsum = 0;
for (int num : nums) {
xorsum ^= num;
}
// Why take the least significant bit?
// Because it is a way for us to divide two numbers, when the XOR of two numbers is 1, there must be two numbers with different values in this bit
// We take the least significant bit, which is actually a kind of division, in fact, any bit can be taken
// Because it is more convenient to take the lowest 1 in bit operations, the lowest bit is usually selected when optional.
// Example: 5(100)B 2(10)B 3(11)B 3(11)B
// Answer [5,2], exclusive or: (110)B
// The value corresponding to the least significant bit is 2(10)B
// For 5 this bit is 0, for 2 this bit is 1, you can separate the two numbers
// Then we thought, is there any situation where this method does not work?
// 1. When the two numbers are equal, it does not hold, and the least significant bit cannot be found. But they are equal to violate the "occurrence once" title requirement
// 2. Not true when the remaining number appears twice in one of each of the two categories.
// But this is impossible, for the same number, one of its digits will not change, so it can only be classified into one category in the end
// Because the number will appear an even number of times in general, the 1 of each digit of it will also appear twice, and it can only be classified into one category
// will eventually cancel out and will not affect the result
// In the above example, 3 and 2(10)B and 2(10)B are not 0, and 2 is divided into a class
//3(11)B and 2(10)B are 0, divided into another class
// type1=[2,3,3] type2=[5]
// XOR the first part to get 2, XOR the second part to get 5, and return the result
// In summary, two numbers can be separated by getting the least significant bit
// prevent overflow
// Because binary has positive and negative 0, negative zero is used to represent one more negative number. If this negative number is reversed, it will overflow, so you cannot use a & (-a) to take the least significant bit
// The characteristic of negative 0 is that the first bit is 1 and the rest are 0, so its least significant bit is itself
int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
return new int[]{type1, type2};
}
}
264. Ugly Number II
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n+1];
dp[1]=1;
int p2 = 1;
int p3 = 1;
int p5 = 1;
for(int i=2;i<=n;i++){
int num2 = dp[p2]*2;
int num3 = dp[p3]*3;
int num5 = dp[p5]*5;
dp[i] = Math.min(Math.min(num2,num3),num5);
if(dp[i]==num2){
p2++;
}
if(dp[i]==num3){
p3++;
}
if(dp[i]==num5){
p5++;
}
}
return dp[n];
}
}
274. H-Index
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int h = 0;
for(int i=citations.length-1;i>=0;i--){
if(citations[i]>h){
h++;
} else {
break;
}
}
return h;
}
}
275. H-Index II
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int left = 0;
int right = n-1;
while(left<=right){
int mid = (left+right)/2;
if(citations[mid]<n-mid){
left=mid+1;
} else{
right=mid-1;
}
}
return n-left;
}
}
279. Perfect Squares
class Solution {
public int numSquares(int n) {
/*
For a perfect square k, dp[k]=1
For the remaining numbers, dp[i]=min(dp[i],dp[i-j*j]+dp[j*j]) = min(dp[i],dp[i-j*j]+1)
*/
if(n<=0){
return 0;
}
int[] dp = new int[n+1];
dp[0] = 0;
for(int i=1;i<=n;i++){
dp[i]=Integer.MAX_VALUE;
for(int j=1;i-j*j>=0;j++){
dp[i] = Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
284. Peeking Iterator
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> iterator;
private Integer nextElement;
public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
this.iterator = iterator;
this.nextElement = iterator.next();
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
return nextElement;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
Integer ret = nextElement;
nextElement = iterator.hasNext() ? iterator.next() : null;
return ret;
}
@Override
public boolean hasNext() {
return nextElement!=null;
}
}
287. Find the Duplicate Number
class Solution {
public int findDuplicate(int[] nums) {
if(nums==null||nums.length==0){
return -1;
}
int n = nums.length;
int slow = 0;
int fast = 0;
do{
slow = nums[slow];
if(nums[fast]>n){
break;
}
fast = nums[nums[fast]];
} while(slow<n&&fast<n&&slow!=fast);
if(slow!=fast){
return -1;
}
slow = 0;
while(slow<n&&fast<n&&slow!=fast){
slow = nums[slow];
fast = nums[fast];
}
if(slow==fast){
return slow;
} else{
return -1;
}
}
}
289. Game of Life
class Solution {
public void gameOfLife(int[][] board) {
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
int count = 0;
if(i>0&&j>0){
count+=Math.abs(board[i-1][j-1])==1?1:0;
}
if(i>0){
count+=Math.abs(board[i-1][j])==1?1:0;
}
if(i>0&&j<board[i].length-1){
count+=Math.abs(board[i-1][j+1])==1?1:0;
}
if(j>0){
count+=Math.abs(board[i][j-1])==1?1:0;
}
if(j<board[i].length-1){
count+=Math.abs(board[i][j+1])==1?1:0;
}
if(i<board.length-1&&j>0){
count+=Math.abs(board[i+1][j-1])==1?1:0;
}
if(i<board.length-1){
count+=Math.abs(board[i+1][j])==1?1:0;
}
if(i<board.length-1&&j<board[i].length-1){
count+=Math.abs(board[i+1][j+1])==1?1:0;
}
if(board[i][j]==1&&(count<2||count>3)){
board[i][j]=-1;
} else if(board[i][j]==0&&count==3){
board[i][j]=2;
}
}
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
if(board[i][j]>0){
board[i][j]=1;
} else {
board[i][j]=0;
}
}
}
}
}
299. Bulls and Cows
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0;
int[] cntS = new int[10];
int[] cntG = new int[10];
for (int i = 0; i < secret.length(); ++i) {
if (secret.charAt(i) == guess.charAt(i)) {
++bulls;
} else {
++cntS[secret.charAt(i) - '0'];
++cntG[guess.charAt(i) - '0'];
}
}
int cows = 0;
for (int i = 0; i < 10; ++i) {
cows += Math.min(cntS[i], cntG[i]);
}
return Integer.toString(bulls) + "A" + Integer.toString(cows) + "B";
}
}
300. Longest Increasing Subsequence
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int n = nums.length;
int[] dp = new int[n];//dp[i] denotes length of longest increasing substring which ends with nums[i]
int maxLen = 0;
for(int i=0;i<n;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
maxLen = Math.max(maxLen,dp[i]);
}
return maxLen;
}
}
309. Best Time to Buy and Sell Stock with Cooldown
class Solution {
public int maxProfit(int[] prices) {
if(prices==null||prices.length==0){
return 0;
}
int n = prices.length;
int[][] dp = new int[n][3];
//dp[i] denotes the profit at the end of day i
//dp[i][0] means by the end of day i, you hold a stock
//dp[i][1] means by the end of day i, you do not hold a stock and are in freezing period
//dp[i][2] means by the end of day i, you do not hold a stock and are not in freezing period
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
for(int i=1;i<n;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
dp[i][1]=dp[i-1][0]+prices[i];
dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);
}
return Math.max(dp[n-1][1],dp[n-1][2]);
}
}
322. Coin Change
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount==0){
return 0;
}
if(coins==null||coins.length==0){
return -1;
}
return solve(coins,amount,new HashMap<>());
}
//divide and conquer
public int solve(int[] coins, int amount, Map<Integer,Integer> map){
if(amount==0){
return 0;
}
if(amount<0){
return -1;
}
if(map.containsKey(amount)){
return map.get(amount);
}
int res = Integer.MAX_VALUE;
for(int coin:coins){
int tempRes = solve(coins, amount-coin, map);
if(tempRes==-1){
continue;
}
res = Math.min(res,tempRes+1);
}
map.put(amount,res == Integer.MAX_VALUE?-1:res);
return map.get(amount);
}
}
337. House Robber III
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
return solve(root,new HashMap<>());
}
public int solve(TreeNode root, Map<TreeNode,Integer> map){
if(root==null){
return 0;
}
if(map.containsKey(root)){
return map.get(root);
}
int robRes = root.val //current node value
//cannot rob root.left and root.right
+ (root.left==null?0:solve(root.left.left,map)+solve(root.left.right,map))
+ (root.right==null?0:solve(root.right.left,map)+solve(root.right.right,map));
int escapeRes = 0 + solve(root.left,map) + solve(root.right,map);
int res = Math.max(robRes, escapeRes);
map.put(root,res);
return res;
}
}
347. Top K Frequent Elements
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if(nums==null||nums.length==0||k<=0||k>nums.length){
return null;
}
Map<Integer,Integer> num2Frequency = new HashMap<>();
for(int num:nums){
if(num2Frequency.containsKey(num)){
num2Frequency.put(num,num2Frequency.get(num)+1);
} else{
num2Frequency.put(num,1);
}
}
PriorityQueue<Integer> pq = new PriorityQueue<>(
new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){
return num2Frequency.get(a)-num2Frequency.get(b);
}
}
);
for(Integer key:num2Frequency.keySet()){
if(pq.size()<k){
pq.add(key);
} else if(num2Frequency.get(key)>num2Frequency.get(pq.peek())){
pq.remove();
pq.add(key);
}
}
int[] res = new int[k];
for(int i=0;i<k;i++){
res[i]=pq.remove();
}
return res;
}
}
394. Decode String
class Solution {
public String decodeString(String s) {
if(s==null||s.length()==0){
return s;
}
Stack<Character> stack = new Stack<>();
for(char c: s.toCharArray()){
//push characters that are not ']'
if(c!=']'){
stack.push(c);//[,numbers,letters
} else{
//step 1 letters
StringBuffer sb = new StringBuffer();
while(!stack.isEmpty()&&Character.isLetter(stack.peek())){
sb.insert(0,stack.pop());//make sure order
}
String subStr = sb.toString();// all letters in []
//step 2 special characters
stack.pop();//remove '['
//step 3 numbers
sb = new StringBuffer();
while(!stack.isEmpty()&&Character.isDigit(stack.peek())){
sb.insert(0,stack.pop());
}
int count = Integer.valueOf(sb.toString());//how many times
while(count>0){
for(char tmp:subStr.toCharArray()){
stack.push(tmp);//push back to stack
}
count--;
}
}
}
//after loop 3[abc] -> abcabcabc
StringBuffer resultBuffer = new StringBuffer();
while(!stack.isEmpty()){
resultBuffer.insert(0,stack.pop());
}
return resultBuffer.toString();
}
}
406. Queue Reconstruction by Height
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] person1, int[] person2) {
if (person1[0] != person2[0]) {//height different
return person2[0] - person1[0];
} else {//height same
return person1[1] - person2[1];
}
}
});
List<int[]> ans = new ArrayList<int[]>();
for (int[] person : people) {
ans.add(person[1], person);//insert to the ki-th position
}
return ans.toArray(new int[ans.size()][]);
}
}
416. Partition Equal Subset Sum
class Solution {
public boolean canPartition(int[] nums) {
if(nums==null||nums.length==0){
return false;
}
int sum = 0;
for(int num:nums){
sum+=num;
}
if(sum%2==1){
return false;
}
sum/=2;
boolean[] dp=new boolean[sum+1];//dp[i] denotes whether exists a partition so that sum equals i
dp[0] = true;
if(nums[0]<=sum){
dp[nums[0]]=true;//sum is nums[0], partition set is {nums[0]}
}
for(int i=1;i<nums.length;i++){
for(int j=sum;j-nums[i]>=0;j--){
dp[j]=dp[j]|dp[j-nums[i]];//nums[i] not in set -->dp[j]; nums[i] in set -->dp[j-nums[i]]
}
}
return dp[sum];
}
}
437. Path Sum III
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int pathSum(TreeNode root, int targetSum) {
int result = 0;
if(root==null){
return result;
}
// Map<TreeNode,Map<Integer,Integer>> map = new HashMap<>();
result=rootNum(root,targetSum);
result+=pathSum(root.left,targetSum);
result+=pathSum(root.right,targetSum);
return result;
}
// must include root
public int rootNum(TreeNode root, int targetSum) {
int ret = 0;
if(root==null){
return ret;
}
// if(map.containsKey(root)){
// Map<Integer,Integer> target2Result = map.get(root);
// if(target2Result.containsKey(targetSum)){
// return target2Result.get(targetSum);
// }
// }
if(root.val==targetSum){
ret++;
}
ret+=rootNum(root.left,targetSum-root.val);
ret+=rootNum(root.right,targetSum-root.val);
// Map<Integer,Integer> target2ResultNew = map.getOrDefault(root, new HashMap<>());
// target2ResultNew.put(targetSum, ret);
// map.put(root,target2ResultNew);
return ret;
}
}
438. Find All Anagrams in a String
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if(s==null||s.length()==0||p==null||p.length()==0||p.length()>s.length()){
return result;
}
int pLen = p.length();
int sLen = s.length();
Map<Character,Integer> pMap = new HashMap<>();
Map<Character,Integer> sMap = new HashMap<>();
for(char c:p.toCharArray()){
int num = pMap.getOrDefault(c,0);
pMap.put(c,num+1);
}
for(int i=0;i<pLen;i++){
char c = s.charAt(i);
int num = sMap.getOrDefault(c,0);
sMap.put(c,num+1);
}
if(isSame(pMap,sMap)){
result.add(0);
}
int j=1;
while(j+pLen<=sLen){
char previous = s.charAt(j-1);
int num = sMap.getOrDefault(previous,0);
if(num>0){
sMap.put(previous,num-1);
}
char next = s.charAt(j+pLen-1);
num = sMap.getOrDefault(next,0);
sMap.put(next,num+1);
if(isSame(pMap,sMap)){
result.add(j);
}
j++;
}
return result;
}
public boolean isSame(Map<Character,Integer> map1,Map<Character,Integer> map2){
for(char c='a';c<='z';c++){
int num1 = map1.getOrDefault(c,0);
int num2 = map2.getOrDefault(c,0);
if(num1!=num2){
return false;
}
}
return true;
}
}
494. Target Sum
class Solution {
public int findTargetSumWays(int[] nums, int target) {
if(nums==null||nums.length==0){
return 0;
}
else {
return dfs(nums,0,target,new HashMap<>());
}
}
public int dfs(int[] nums, int pos, int remain, Map<String,Integer> map){
if(pos==nums.length){
if(remain==0){
return 1;
} else{
return 0;
}
}
String temp = pos + ";" +remain;
if(map.containsKey(temp)){
return map.get(temp);
}
int res = dfs(nums,pos+1,remain-nums[pos],map)+dfs(nums,pos+1,remain+nums[pos],map);
map.put(temp,res);
return res;
}
}
538. Convert BST to Greater Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root!=null){
//reserve mid-tranverse
convertBST(root.right);
sum+=root.val;
root.val=sum;
convertBST(root.left);
}
return root;
}
}
560. Subarray Sum Equals K
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
// presum array
int[] preSum = new int[n + 1];
preSum[0] = 0;
// The mapping of prefix sum to quantity, which is convenient to quickly find the desired prefix sum
HashMap<Integer, Integer> count = new HashMap<>();
count.put(0, 1);
// record number of subarrays with sum k
int res = 0;
// computes the prefix sum of nums
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
// If there is a prefix sum with the value need before
// shows that there are subarrays ending in nums[i-1] with a sum of k
int need = preSum[i] - k;
if (count.containsKey(need)) {
res += count.get(need);
}
// Store the current prefix sum in the hash table
if (!count.containsKey(preSum[i])) {
count.put(preSum[i], 1);
} else {
count.put(preSum[i], count.get(preSum[i]) + 1);
}
}
return res;
}
}
581. Shortest Unsorted Continuous Subarray
class Solution {
public int findUnsortedSubarray(int[] nums) {
//Maintain a maximum value max from left to right. Before entering the right segment, the nums[i] traversed is less than max, and the end we require is the position of the last element less than max in the traversal;
//Similarly, a minimum value min is maintained from right to left. Before entering the left segment, the traversed nums[i] are also greater than min, and the required begin is the position of the last element greater than min.
if(nums==null||nums.length==0){
return 0;
}
int n = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int left = 0;
int right = -1;
for(int i=0; i<n; i++){
if(nums[i]<max){
right = i;
} else {
max = nums[i];
}
if(nums[n-i-1]>min){
left = n-i-1;
} else {
min = nums[n-i-1];
}
}
return right-left+1;
}
}
621. Task Scheduler
class Solution {
public int leastInterval(char[] tasks, int n) {
if(tasks==null||tasks.length==0||n<0){
return 0;
}
Map<Character,Integer> map = new HashMap<>();
int maxTimes = 0;
for(char c:tasks){
int curTime = map.getOrDefault(c,0)+1;
map.put(c,curTime);
maxTimes = Math.max(maxTimes,curTime);
}
int maxCount = 0;
for(char c:map.keySet()){
if(map.getOrDefault(c,0)==maxTimes){
maxCount++;
}
}
return Math.max((maxTimes-1)*(n+1)+maxCount,tasks.length);
}
}
647. Palindromic Substrings
class Solution {
public int countSubstrings(String s) {
if(s==null||s.length()==0){
return 0;
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
int sum = 0;
for(int i=0;i<n;i++){
dp[i][i]=true;
sum++;
if(i+1<n){
dp[i][i+1]=s.charAt(i)==s.charAt(i+1);
if(dp[i][i+1]){
sum++;
}
}
}
for(int l=3;l<=n;l++){
for(int i=0;i<n-l+1;i++){
int r=i+l-1;
dp[i][r] = dp[i+1][r-1] && s.charAt(i)==s.charAt(r);
if(dp[i][r]){
sum++;
}
}
}
return sum;
}
}
739. Daily Temperatures
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length];
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < length; i++) {
int temperature = temperatures[i];
while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
int prevIndex = stack.pop();
ans[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return ans;
}
}