LeetCode Top Likes 100

1 Two Sum (Easy)
2 Add Two Numbers (Medium)
3 Longest Substring Without Repeating Characters (Medium)
4 Median of Two Sorted Arrays (Hard)
5 Longest Palindromic Substring (Medium)
10 Regular Expression Matching (Hard)
11 Container With Most Water (Medium)
15 3Sum (Medium)
17 Letter Combinations of a Phone Number (Medium)
19 Remove Nth Node From End of List (Medium)
20 Valid Parentheses (Easy)
21 Merge Two Sorted Lists (Easy)
22 Generate Parentheses (Medium)
23 Merge k Sorted Lists (Hard)
31 Next Permutation (Medium)
32 Longest Valid Parentheses (Hard)
33 Search in Rotated Sorted Array (Medium)
34 Find First and Last Position of Element in Sorted Array (Medium)
39 Combination Sum (Medium)
41 First Missing Positive (Hard)
42 Trapping Rain Water (Hard)
46 Permutations (Medium)
48 Rotate Image (Medium)
49 Group Anagrams (Medium)
53 Maximum Subarray (Easy)
55 Jump Game (Medium)
56 Merge Intervals （Medium)
62 Unique Paths (Medium)
64 Minimum Path Sum (Medium)
70 Climbing Stairs (Easy)
72 Edit Distance (Hard)
75 Sort Colors (Medium)
76 Minimum Window Substring (Hard)
78 Subsets (Medium)
79 Word Search (Medium)
84 Largest Rectangle in Histogram (Hard)
85 Maximal Rectangle （Hard)
94 Binary Tree Inorder Traversal (Medium)
96 Unique Binary Search Trees (Medium)
98 Validate Binary Search Tree (Medium)
Symmetric Tree (Easy)
102 Binary Tree Level Order Traversal (Medium)
104 Maximum Depth of Binary Tree (Easy)
105 Construct Binary Tree from Preorder and Inorder Traversal (Medium)
114 Flatten Binary Tree to Linked List (Medium)
121 Best Time to Buy and Sell Stock (Easy)
124 Binary Tree Maximum Path Sum (Hard)
128 Longest Consecutive Sequence (Hard)
136 Single Number (Easy)
138 Copy List with Random Pointer (Medium)
139 Word Break (Medium)
141 Linked List Cycle (Easy)
142 Linked List Cycle II （Medium）
146 LRU Cache （Medium）
148 Sort List (Medium)
152 Maximum Product Subarray (Medium)
155 Min Stack (Easy)
160 Intersection of Two Linked Lists (Easy)
169 Majority Element （Easy）
198 House Robber (Easy)
200 Number of Islands (Medium)
206 Reverse Linked List (Easy)
207 Course Schedule (Medium)
208 Implement Trie (Prefix Tree) (Medium)
215 Kth Largest Element in an Array (Medium)
221 Maximal Square (Medium)
226 Invert Binary Tree (Easy)
226 Palindrome Linked List (Easy)
236 Lowest Common Ancestor of a Binary Tree (Medium)
238 Product of Array Except Self (Medium)
239 Sliding Window Maximum (Hard)
240 Search a 2D Matrix II (Medium)
253 Meeting Rooms II (Medium)
279 Perfect Squares (Medium)
283 Move Zeroes （Easy）
287 Find the Duplicate Number (Medium)
295 FindMedianfromDataStream (Hard)
297 Serialize and Deserialize Binary Tree （Hard）
300 Longest Increasing Subsequence （Medium）
301 Remove Invalid Parentheses (Hard)
309 Best Time to Buy and Sell Stock with Cooldown （Medium）
312 Burst Balloons (Hard)
322 Coin Change （Medium）
337 House Robber III (Medium)
338 Counting Bits (Medium)
347. Top K Frequent Elements （Medium）
394. Decode String （Medium）
406. Queue Reconstruction by Height （Medium）
416. Partition Equal Subset Sum （Medium）
437. Path Sum III (Easy)
438. Find All Anagrams in a String (Medium)
448. Find All Numbers Disappeared in an Array (Easy)
461. Hamming distance （Easy）
494. Target Sum （Medium）
538. Change Binary Tree to Greater Tree (Easy)
543. Diameter of Binary Tree （Easy）
560. Subarray Sum Equals K （Medium）
581. Shortest Unsorted Continuous Subarray (Easy)
617. Merge Two Binary Trees (Easy)
621. Task Scheduler (Medium)
647. Palindromic Substrings (Medium)
739. Daily Temperatures （Medium）

1 Two Sum (Easy)

题目描述

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

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

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解法

利用HashMap存，以空间换时间，边存边判断之前存的是否有满足的，实现O(n)的复杂度。

代码

  public int[] twoSum(int[] nums, int target) {
      Map<Integer, Integer> map = new HashMap<>();
      for (int i = 0; i < nums.length; i++) {
          int complement = target - nums[i];
          if (map.containsKey(complement)) {
              return new int[] { map.get(complement), i };
          }
          map.put(nums[i], i);
      }
      throw new IllegalArgumentException("No two sum solution");
  }

2 Add Two Numbers (Medium)

题目描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
解法

注意进位即可

代码

自己写的：

  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
          ListNode result = new ListNode(0);
          ListNode tmpResult = result;
          boolean carry = false;
          while(l1!=null||l2!=null){
              int val1 = (l1==null)?0:l1.val;
              int val2 = (l2==null)?0:l2.val;
              if(carry){
                  tmpResult.val = val1+val2+1;
                  carry = false;
              }else{
                  tmpResult.val = val1+val2;
              }
              if(tmpResult.val>9){
                  carry = true;
                  tmpResult.val = tmpResult.val%10;
              }
              if(l1!=null) l1 = l1.next;
              if(l2!=null) l2 = l2.next;
              if(l1==null&&l2==null&&carry){
                  tmpResult.next = new ListNode(1);
              }else if(l1==null&&l2==null&&!carry){
                  tmpResult.next = null;
              }else{
                  tmpResult.next = new ListNode(0);
                  tmpResult = tmpResult.next;
              }
          }
          return result;
      }

标准答案：

  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      ListNode dummyHead = new ListNode(0);
      ListNode p = l1, q = l2, curr = dummyHead;
      int carry = 0;
      while (p != null || q != null) {
          int x = (p != null) ? p.val : 0;
          int y = (q != null) ? q.val : 0;
          int sum = carry + x + y;
          carry = sum / 10;
          curr.next = new ListNode(sum % 10);
          curr = curr.next;
          if (p != null) p = p.next;
          if (q != null) q = q.next;
      }
      if (carry > 0) {
          curr.next = new ListNode(carry);
      }
      return dummyHead.next;
  }

3 Longest Substring Without Repeating Characters (Medium)

题目描述

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
解法

双指针，一个指前一个指后，将两个指针内的元素存进set，当遇到重复的时候，移前面的指针

代码

  public int lengthOfLongestSubstring(String s) {
          int n=s.length();
          Set<Character> set = new HashSet<>();
          int ans=0,i=0,j=0;
          while(i<n&&j<n){
              if(!set.contains(s.charAt(j))){
                  set.add(s.charAt(j++));
                  ans = Math.max(ans,j-i);
              }else{
                  set.remove(s.charAt(i++));
              }
          }
          return ans;
      }

4 Median of Two Sorted Arrays (Hard)

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 1:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解法

left_part	right_part
A[0], A[1], …, A[i-1]	A[i], A[i+1], …, A[m-1]
B[0], B[1], …, B[j-1]	B[j], B[j+1], …, B[n-1]

len(left_part)=len(right_part)
max(left_part)≤min(right_part)

满足上面条件来说的话即：

i+j=m−i+n−j (或者: m - i + n - j + 1)
j=(m+n+1)/2−i
B[j−1]≤A[i] 并且 A[i−1]≤B[j]

代码

      public double findMedianSortedArrays(int[] A, int[] B) {
          int m = A.length;
          int n = B.length;
          if (m > n) { // to ensure m<=n
              int[] temp = A; A = B; B = temp;
              int tmp = m; m = n; n = tmp;
          }
          int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
          while (iMin <= iMax) {
              int i = (iMin + iMax) / 2;
              int j = halfLen - i;
              if (i < iMax && B[j-1] > A[i]){
                  iMin = i + 1; // i is too small
              }
              else if (i > iMin && A[i-1] > B[j]) {
                  iMax = i - 1; // i is too big
              }
              else { // i is perfect
                  int maxLeft = 0;
                  if (i == 0) { maxLeft = B[j-1]; }
                  else if (j == 0) { maxLeft = A[i-1]; }
                  else { maxLeft = Math.max(A[i-1], B[j-1]); }
                  if ( (m + n) % 2 == 1 ) { return maxLeft; }
    
                  int minRight = 0;
                  if (i == m) { minRight = B[j]; }
                  else if (j == n) { minRight = A[i]; }
                  else { minRight = Math.min(B[j], A[i]); }
    
                  return (maxLeft + minRight) / 2.0;
              }
          }
          return 0.0;
      }

5 Longest Palindromic Substring (Medium)

题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”
解法

以每个字符为中心向两边扩展，记录以每个字符为中心的最大长度，并比较

代码

      public String longestPalindrome(String s) {
          if(s==null||s.length()<1) return "";
          int start=0,end=0;
          for(int i=0;i<s.length();i++){
              int len1 = expandCore(s,i,i);
              int len2 = expandCore(s,i,i+1);
              int len = Math.max(len1,len2);
              if(len>end-start){
                  start = i-(len-1)/2;
                  end = i+len/2;
              }
          }
          return s.substring(start,end+1);
      }
    
      public int expandCore(String s,int left,int right){
          while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
              left--;
              right++;
          }
          return right-left-1;
      }

10 Regular Expression Matching (Hard)

题目描述

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

’.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:

Input: s = “aa”
p = “a”
Output: true
Explanation: ‘’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:

s = “ab”
p = “.”
Output: true
Explanation: “.” means “zero or more (*) of any character (.)”.

Example 4:

Input:
s = “aab”
p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.

Example 5:

Input:
s = “mississippi”
p = “misisp*.”
Output: false
解法

动态规划问题，分别记录两个字符串匹配到的位置，根据pattern的下一个字符是否是*来进行分情况讨论

代码

      public boolean isMatch(String s, String p) {
          return matchCore(s.toCharArray(),0,p.toCharArray(),0);
      }
    
      public boolean matchCore(char[] s,int sLen,char[] p,int pLen){
          if(sLen==s.length&&pLen==p.length){
              return true;
          }
          if(pLen==p.length){
              return false;
          }
    
          boolean next = (pLen+1<p.length&&p[pLen+1]=='*');
          if(next){
              if(sLen<s.length&&(s[sLen]==p[pLen]||p[pLen]=='.')){
                  return matchCore(s,sLen+1,p,pLen)||matchCore(s,sLen,p,pLen+2);
              }else {
                  return matchCore(s,sLen,p,pLen+2);
              }
          }else {
              if(sLen<s.length&&(s[sLen]==p[pLen]||p[pLen]=='.')){
                  return matchCore(s,sLen+1,p,pLen+1);
              }else {
                  return false;
              }
          }
      }

11 Container With Most Water (Medium)

题目描述

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.(Note: You may not slant the container and n is at least 2.)

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
解法

两头指针，往中间移，比较指针所在位置的高度，矮的走

代码

          public int maxArea(int[] height) {
              int pre=0,last=height.length-1;
              int result=0;
              while(pre!=last){
                  result = Math.max(result,Math.min(height[pre],height[last])*(last-pre));
                  if(height[pre]>height[last]){
                      last--;
                  }else{
                      pre++;
                  }
              }
              return result;
          }

15 3Sum (Medium)

题目描述

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
解法

3个数，固定一个数，另外两个数两头往中间走，头从固定数字的后一位开始，尾巴为数组的末尾

代码

      public List<List<Integer>> threeSum(int[] nums) {
          List<List<Integer>> result = new ArrayList<>();
          if(nums.length<3){
              return result;
          }
          Arrays.sort(nums);
          for(int i=0;i<nums.length-2;i++){
              int end = nums.length-1;
              int start = i+1;
              while(start<end){
                  int sum = nums[i] + nums[end];
                  if(sum+nums[start]==0){
                      ArrayList<Integer> tmpRes = new ArrayList<>();
                      tmpRes.add(nums[i]);
                      tmpRes.add(nums[start]);
                      tmpRes.add(nums[end]);
                      if(!result.contains(tmpRes)){
                          result.add(tmpRes);
                      }
                      start++;
                      end--;
                  }else if(sum+nums[start]<0){
                      start++;
                  }else{
                      end--;
                  }
              }
          }
          return result;
      }

17 Letter Combinations of a Phone Number (Medium)

题目描述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
解法

回溯法，递归里带for循环，终止条件是给的string用完了，先把电话号码的数字和对应的字母存进map，然后递归中先判断是否还有string，有的话拿出首字母，然后for循环首字母对应存在map中的字符

代码

      List<String> result = new ArrayList<>();
      HashMap<String,String> map = new HashMap<String,String>();
    
      public void combinationCore(String com,String digit){
          if(digit.length()==0){
              result.add(com);
              return;
          }
          String num = digit.substring(0,1);
          String letter = map.get(num);
          for(int i=0;i<letter.length();i++){
              String specificLetter = letter.substring(i,i+1);
              combinationCore(com+specificLetter,digit.substring(1));
          }
      }
    
      public List<String> letterCombinations(String digits) {
          if(digits.length()<1){
              return result;
          }
          combinationCore("",digits);
          return result;
      }

19 Remove Nth Node From End of List (Medium)

题目描述

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

Example:

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid.
解法

让前一个指针先走n步，可以利用“傻瓜节点”来避免越界问题

代码

      public ListNode removeNthFromEnd(ListNode head, int n) {
          ListNode dummyNode = new ListNode(0);
          dummyNode.next = head;
          ListNode pre = dummyNode,last=dummyNode;
          for(int i=0;i<n+1;i++){
                  pre = pre.next;
          }
          while(pre!=null){
              pre = pre.next;
              last = last.next;
          }
          last.next = last.next.next;
          return dummyNode.next;
      }

20 Valid Parentheses (Easy)

题目描述

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:
```
  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.   Note that an empty string is also considered valid.
```
Example 1:

Input: “()[]{}”
Output: true

Example 2:

Input: “([)]”
Output: false
解法

利用栈，最后判断栈是否为空即可

代码

      public boolean isValid(String s) {
          Stack stack = new Stack();
          int i=0;
          while(i<s.length()){
              if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){
                  stack.push(s.charAt(i));
                  i++;
              }else{
                  if(stack.isEmpty()){
                      return false;
                  }
                  if((char)stack.peek()=='('&&s.charAt(i)==')'){
                      stack.pop();
                  }else if((char)stack.peek()=='{'&&s.charAt(i)=='}'){
                      stack.pop();
                  }else if((char)stack.peek()=='['&&s.charAt(i)==']'){
                      stack.pop();
                  }else{
                      return false;
                  }
                  i++;
              }
          }
          if(stack.isEmpty()){
              return true;
          }else{
              return false;
          }
      }

21 Merge Two Sorted Lists (Easy)

题目描述

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
解法

因为是拼接原来的，所以用递归，而不是产生新的

代码

      public ListNode mergeTwoLists(ListNode l1, ListNode l2){
          if(l1 == null) return l2;
          if(l2 == null) return l1;
          if(l1.val < l2.val){
              l1.next = mergeTwoLists(l1.next, l2);
              return l1;
          } else{
              l2.next = mergeTwoLists(l1, l2.next);
              return l2;
          }
      }

22 Generate Parentheses (Medium)

题目描述

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

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

Example:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
解法

暴力解法，全排列所有的可能，为每一个判断是否合法利用回溯，优先产生左括号再产生右括号

代码

暴力解法：

      public List<String> generateParenthesis(int n) {
          List<String> combinations = new ArrayList();
          generateAll(new char[2 * n], 0, combinations);
          return combinations;
      }
    
      public void generateAll(char[] current, int pos, List<String> result) {
          if (pos == current.length) {
              if (valid(current))
                  result.add(new String(current));
          } else {
              current[pos] = '(';
              generateAll(current, pos+1, result);
              current[pos] = ')';
              generateAll(current, pos+1, result);
          }
      }
    
      public boolean valid(char[] current) {
          int balance = 0;
          for (char c: current) {
              if (c == '(') balance++;
              else balance--;
              if (balance < 0) return false;
          }
          return (balance == 0);
      }

回溯法：

      public List<String> generateParenthesis(int n) {
          List<String> ans = new ArrayList();
          backtrack(ans, "", 0, 0, n);
          return ans;
      }
    
      public void backtrack(List<String> ans, String cur, int open, int close, int max){
          if (cur.length() == max * 2) {
              ans.add(cur);
              return;
          }
    
          if (open < max)
              backtrack(ans, cur+"(", open+1, close, max);
          if (close < open)
              backtrack(ans, cur+")", open, close+1, max);
      }

23 Merge k Sorted Lists (Hard)

题目描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
解法

多路归并问题，先定义比较器，利用优先队列把头节点都压栈，然后循环优先队列，把出栈节点的下一个压栈即可

代码

      public ListNode mergeKLists(ListNode[] lists) {
          Comparator<ListNode> cmp = new Comparator<ListNode>(){
              public int compare(ListNode l1,ListNode l2){
                  return l1.val-l2.val;
              }
          };
          Queue<ListNode> que = new PriorityQueue<ListNode>(cmp);
          for(ListNode l:lists){
              if(l!=null){
                  que.add(l);
              }
          }
          ListNode dummyNode = new ListNode(0);
          ListNode head = dummyNode;
          while(!que.isEmpty()){
              ListNode tmp = que.poll();
              dummyNode.next = tmp;
              dummyNode = dummyNode.next;
              if(dummyNode.next!=null){
                  que.add(dummyNode.next);
              }
          }
          return head.next;
      }

31 Next Permutation (Medium)

题目描述

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

Example:

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解法

因为要找下一个大于原数的数字，先从右向左找第一个非单调递增的数字,之后反向从找到的点往右找，找到刚好大于非单调增的那个数，两个数交换位置，然后让反转后面的单调增的数字

代码

      public void nextPermutation(int[] nums) {
          int len = nums.length-1;
          for(;len>0;len--){
              if(nums[len]>nums[len-1]){
                  int j = len;
                  while(j<nums.length&&nums[len-1]<nums[j]){
                      j++;
                  }
                  swap(nums,len-1,j-1);
                  reverse(nums,len);
                  break;
              }
          }
          if(len==0){
              reverse(nums,0);
          }
      }
        
      public void reverse(int[] nums, int start){
          int i = start, j = nums.length-1;
          while(i<j){
              swap(nums,i,j);
              i++;
              j--;
          }
            
      }
        
      public void swap(int[] nums,int i,int j){
          int tmp = nums[i];
          nums[i] = nums[j];
          nums[j] = tmp;
      }

32 Longest Valid Parentheses (Hard)

题目描述

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

Example 1:

Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”

Example 2:

Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”
解法
1. 暴力解法，分别以每个字符为开头，尾一次往后移2个，判断子序列是否有效
2. 动态规划，只有遇到）才会可能是结果，所以判断遇到）时候的情况
  当s[i]=”)” 并且s[i-1]=”(“ 这时候dp[i] = dp[i-2]+2
  当s[i]=”)” 并且s[i-1]=”)” ,即”))”这种样子的时候
  如果s[i−dp[i−1]−1]=”(“ 可得dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2 (非常的难想到)

代码

暴力解法：

      public boolean isValid(String s) {
          Stack<Character> stack = new Stack<Character>();
          for (int i = 0; i < s.length(); i++) {
              if (s.charAt(i) == '(') {
                  stack.push('(');
              } else if (!stack.empty() && stack.peek() == '(') {
                  stack.pop();
              } else {
                  return false;
              }
          }
          return stack.empty();
      }
      public int longestValidParentheses(String s) {
          int maxlen = 0;
          for (int i = 0; i < s.length(); i++) {
              for (int j = i + 2; j <= s.length(); j+=2) {
                  if (isValid(s.substring(i, j))) {
                      maxlen = Math.max(maxlen, j - i);
                  }
              }
          }
          return maxlen;
      }

动态规划：

      public int longestValidParentheses(String s) {
          int result = 0;
          int[] dp = new int[s.length()];
          for(int i=1;i<s.length();i++){
              if(s.charAt(i)==')'){
                  if(s.charAt(i-1)=='('){
                      dp[i] = (i>=2?dp[i-2]:0)+2;
                  }else{
                      if(i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                          dp[i] = dp[i-1]+(i-dp[i-1]-2>0?dp[i-dp[i-1]-2]:0)+2;
                      }
                  }
                  result = Math.max(result,dp[i]);
              }
          }
          return result;
      }

33 Search in Rotated Sorted Array (Medium)

题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
解法

二分查找的扩展题，二分之后要先判断值是否属于前半段之中还是后半段之中，再修改头或者尾指针位置

代码

      public int search(int[] nums, int target) {
          int result = -1;
          if(nums.length==0||nums==null){
              return result;
          }
          int start =0,end = nums.length-1;
          while(start<=end){
              int mid = start+(end-start)/2;
              if(nums[mid]==target){
                  return mid;
              }
              if(nums[start]<=nums[mid]){
                  if(target>=nums[start]&&target<=nums[mid]){
                      end = mid - 1;
                  }else{
                      start = mid +1;
                  }
              }else{
                  if(target<=nums[end]&&target>=nums[mid]){
                      start = mid + 1;
                  }else{
                      end = mid -1;
                  }
              }
          }
          return result;
      }

34 Find First and Last Position of Element in Sorted Array (Medium)

题目描述

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

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

Example 2:

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

二分查找扩展，二分找头，二分找尾，中间的是结果

代码

      public int[] searchRange(int[] nums, int target) {
          int[] result = {-1,-1};
          if(nums.length==0||nums==null){
              return result;
          }
          int start = -1,end=-1;
          int pre=0,last = nums.length-1;
          while(pre<=last){
              int mid = pre + (last-pre)/2;
              if(nums[mid]==target){
                  if(mid==0){
                      start = 0;
                      break;
                  }else if(mid>0&&nums[mid-1]!=target){
                      start = mid;
                      break;
                  }else{
                      last = mid-1;
                  }
              }
              if(target>nums[mid]){
                  pre = mid+1;
              }
              if(target<nums[mid]){
                  last = mid-1;
              }
          }
          pre=0;
          last = nums.length-1;
          while(pre<=last){
              int mid = pre + (last-pre)/2;
              if(nums[mid]==target){
                  if(mid==nums.length-1){
                      end = nums.length-1;
                      break;
                  }else if(mid<nums.length-1&&nums[mid+1]!=target){
                      end = mid;
                      break;
                  }else{
                      pre = mid+1;
                  }
              }
              if(target>nums[mid]){
                  pre = mid+1;
              }
              if(target<nums[mid]){
                  last = mid-1;
              }
          }
          result[0]=start;
          result[1]=end;
          return result;
      }

39 Combination Sum (Medium)

题目描述

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

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

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

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

Example 2:

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

回溯法，递归中for循环，需要的参数candidate[],当前累加的值，目标值，和走到第几个candidate的index

代码

      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          List<List<Integer>> result = new ArrayList<>();
          List<Integer> tmp = new LinkedList<>();
          Arrays.sort(candidates);
          combination(candidates,result,tmp,target,0,0);
          return result;
      }
    
      public void combination(int[] candidates,List<List<Integer>> result,List<Integer> tmp,int target,int current,int index){
          if(current>target){
              return;
          }
          if(current==target){
              result.add(new LinkedList<>(tmp));
          }else{
              for(int i=index;i<candidates.length;i++){
                  tmp.add(candidates[i]);
                  combination(candidates,result,tmp,target,current+candidates[i],i);
                  tmp.remove(tmp.size()-1);
              }
    
          }
      }

41 First Missing Positive (Hard)

题目描述

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

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

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:
Your algorithm should run in O(n) time and uses constant extra space.
解法

数组中的数字应该满足nums[i]==nums[nums[i]-1]，为了满足时间复杂度，应该交换不满足此条件的数，然后遍历一遍数组

代码

      public int firstMissingPositive(int[] nums) {
          if(nums.length==0||nums==null){
              return 1;
          }
          for(int i =0;i<nums.length;i++){
              if(nums[i]==i+1){
                  continue;
              } else{
                  while(nums[i]>0&&nums[i]<nums.length&&nums[i]!=nums[nums[i]-1]){
                      int tmp = nums[nums[i]-1];
                      nums[nums[i]-1] = nums[i];
                      nums[i] = tmp;
                  }
              } 
          }
          int i=0;
          for(;i<nums.length;i++){
              if(nums[i]!=i+1){
                  return i+1;
              }
          }
          return i+1;
      }

42 Trapping Rain Water (Hard)

题目描述

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

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
解法

找到最高的点的高度和下标，然后算围出来的总面积，然后从两边往最高点走，减去图中白色面积，最后减去图中黑色面积即可

代码

      public int trap(int[] height) {
          int maxHeight=0,maxIndex=0;
          for(int i=0;i<height.length;i++){
              if(height[i]>maxHeight){
                  maxHeight=height[i];
                  maxIndex=i;
              }
          }
          int total=maxHeight*height.length;
          int tmpMax=0;
          for(int i=0;i<maxIndex;i++){
              tmpMax=Math.max(tmpMax,height[i]);
              total-=(maxHeight-tmpMax);
          }
          tmpMax=0;
          for(int i=height.length-1;i>maxIndex;i--){
              tmpMax=Math.max(tmpMax,height[i]);
              total-=(maxHeight-tmpMax);
          }
          for(int i=0;i<height.length;i++){
              total-=height[i];
          }
          return total;
      }

46 Permutations (Medium)

题目描述

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解法

回溯法，用一个数组记录数是否使用过，使用的时候标记已经访问过，用完之后要把访问记录删掉，并且字符串拼接中也要把数删掉

代码

  public List<List<Integer>> permute(int[] nums) {
          List<List<Integer>> result = new ArrayList<>();
          List<Integer> tmp = new LinkedList<>();
          Arrays.sort(nums);
          boolean[] visited = new boolean[nums.length];
          generateCore(nums,result,tmp,0,visited);
          return result;
      }
    
      public void generateCore(int[] nums,List<List<Integer>> result,List<Integer> tmp,int index,boolean[] visited){
          if(tmp.size()==nums.length){
              result.add(new LinkedList<>(tmp));
              return;
          }else{
              for(int i=0;i<nums.length;i++){
                  if(!visited[i]){
                      tmp.add(nums[i]);
                      visited[i]=true;
                      generateCore(nums,result,tmp,i,visited);
                      visited[i]=false;
                      tmp.remove(tmp.size()-1);
                  }
              }
          }
      }

48 Rotate Image (Medium)

题目描述

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

NOTE:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
解法

解法1：用顺时针打印矩阵的思想，按圈走，从外到内解法2：闭环交换的思想，找规律解法3：对角线交换，然后左右对称交换

代码

解法1：

  public void rotate(int[][] matrix) {
          int row = matrix.length;
          int circle = (row+1)/2;
          for(int i=0;i<circle;i++){
              //用于存储的数组
              int[] tmp = new int[row];
              int[] tmp2 = new int[row];
              //从左到右的记录
              for(int j=i;j<row-i;j++){
                  tmp[j]=matrix[i][j];
              }
              //从上到下替换，
              for(int j=i;j<row-i;j++){
                  tmp2[j]=matrix[j][row-i-1];
                  matrix[j][row-i-1]=tmp[j];
              }
              //从右到左的替换
              for(int j=i+1;j<row-i;j++){
                  tmp[j]=matrix[row-i-1][row-j-1];
                  matrix[row-i-1][row-j-1]=tmp2[j];
              }
              //从下到上的替换
              for(int j=i+1;j<row-i;j++){
                  tmp2[j]=matrix[row-j-1][i];
                  matrix[row-j-1][i]=tmp[j];
              }
              //从左到右替换
              for(int j=i+1;j<row-i;j++){
                  matrix[i][j]=tmp2[j];
              }
          }
      }

解法2：

  class Solution {
      public void rotate(int[][] matrix) {
          int length = matrix.length;
          for(int i=0;i<length/2;i++){ //想象i就是第一行的index，所以走一半就到中间了
              for(int j=i;j<length-i-1;j++){ //j的起始是i，j=i即是对角线，结束的时候走到少i个的地方，并且最后一个格是上一溜转出来的所以还要在减1
                  int temp = matrix[i][j];
                  matrix[i][j] = matrix[length-j-1][i];
                  matrix[length-j-1][i] = matrix[length-i-1][length-j-1];
                  matrix[length-i-1][length-j-1] = matrix[j][length-i-1];
                  matrix[j][length-i-1] = temp;
              }
          }
      }
  }

解法3：

      class Solution {
          public:
          void swap(int &a, int &b) {
            
            
            
              int idx = a;
              a = b;
              b = idx;
          }
          void rotate(vector<vector<int>>& matrix) {
              int n = matrix.size();
              if (n <= 1) {
                  return;
              }
              for (int i = 0; i < n; i++) {
                  for (int j = i; j < n; j++) {
                      swap(matrix[i][j], matrix[j][i]);
                  }
              }
              for (int i = 0; i < n; i++) {
                  for (int j = 0; j < n / 2; j++) {
                      swap(matrix[i][j], matrix[i][n - j - 1]);
                  }
              }
          }
      };

49 Group Anagrams (Medium)

题目描述

Given an array of strings, group anagrams together.

Example:

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output: [
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
解法

用一个hashmap前面放排序后的string，后面放list,每个词来后判断是否有这个string，有的话加入后面的list，最后返回HashMap的values即可

代码

  public List<List<String>> groupAnagrams(String[] strs) {
          if(strs.length==0) return new ArrayList<>();
          HashMap<String,List> res = new HashMap<>();
          for(String s:strs){
              char[] tmp = s.toCharArray();
              Arrays.sort(tmp);
              String key = String.valueOf(tmp);
              if(!res.containsKey(key)){
                  res.put(key,new ArrayList());
              }
              res.get(key).add(s);
          }
          return new ArrayList(res.values());
      }

53 Maximum Subarray (Easy)

题目描述

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

Example:

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

头尾指针，如果当前的和小于尾指针指的数字，则移动头指针指向当前的尾指针（即抛弃之前的数字）。

代码

      public int maxSubArray(int[] nums) {
          int sum=nums[0];
          int result = nums[0];
          for(int i=1;i<nums.length;i++){
              sum = Math.max(nums[i],sum+nums[i]);
              result = Math.max(result,sum);
          }
          return result;
      }

55 Jump Game (Medium)

题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

Example:

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

解法1：贪心算法，for循环，边界为能到达的位置，初始为0，在能到达的范围里i一步步走，并更新最远能到达的位置，如果在循环中超过了数组长度则返回true

解法2：回溯法,每次将走到的下标和数组穿过去，循环条件为能到的最远距离，回溯法可以实现先跳去最远然后往回找

解法3：动态规划，先标记最后1位可以到达，然后从后往前看，每个数跳跃范围内是否有可达节点，如果有此节点也为可达，没有的话则为不可达

代码

解法1：

      public boolean canJump(int[] nums) {
          if(nums.length<2||nums==null){
              return true;
          }
          int length = nums.length;
          int reach=0;
          for(int i=0;i<=reach;i++){
              if(reach<i+nums[i]){
                  reach=i+nums[i];
              }
              if(reach>=length-1){
                  return true;
              }
          }
          return false;
      }

解法2：

      public boolean canJumpFromPosition(int position, int[] nums) {
          if (position == nums.length - 1) {
              return true;
          }
    
          int furthestJump = Math.min(position + nums[position], nums.length - 1);
          //for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) { //跳的太近了
          for (int nextPosition = furthestJump; nextPosition > position; nextPosition--){//先跳去最远的再往回看
              if (canJumpFromPosition(nextPosition, nums)) {
                  return true;
              }
          }
    
          return false;
      }
        

解法3：

      public boolean canJump(int[] nums) {
               int[] dp = new int[nums.length]; // 认为值为0，则未知，每个点表示从这个点能不能到终点
               dp[dp.length-1] = 1;// 值为1就是能到
               for(int i=dp.length-2;i>=0;i--){
                   int maxJump = Math.min(i+nums[i],nums.length);
                   for(int j=i+1;j<=maxJump;j++){
                       if(dp[j]==1){
                           dp[i]=1;
                           break;
                       }
                   }
                   if(dp[i]==0) dp[i]=-1;
               }
               return dp[0]==1?true:false;
      }      

56 Merge Intervals （Medium)

题目描述

Given a collection of intervals, merge all overlapping intervals.

Example:

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

先把给的序列第一个数字进行排序，然后挨着合并

代码

自己一开始想着用栈来合并，后来想来并不需要

      public int[][] merge(int[][] intervals) {
          Comparator<int[]> comparator = new Comparator<int[]>() {
              @Override
              public int compare(int[] o1, int[] o2) {
                  return o1[0]-o2[0];
              }
          };
          Arrays.sort(intervals,comparator);
          int row = intervals.length;
          Stack<int[]> stack = new Stack<>();
          if(row<2){
              return intervals;
          }
          stack.push(intervals[0]);
          for(int i=1;i<row;i++){
              int start = stack.peek()[0];
              int end = stack.peek()[1];
              int nextStart = intervals[i][0];
              int nextEnd = intervals[i][1];
              if(end>=nextStart){
                  stack.pop();
                  int[] tmp = new int[2];
                  tmp[0] = Math.min(start,nextStart);
                  tmp[1] = Math.max(end,nextEnd);
                  stack.push(tmp);
              }else{
                  stack.push(intervals[i]);
              }
          }
          int[][] result = new int[stack.size()][2];
          int i =0;
          Stack<int[]> reverse = new Stack<>();
          while (!stack.isEmpty()){
              reverse.push(stack.pop());
          }
          while(!reverse.isEmpty()){
              result[i] = reverse.pop();
              i++;
          }
          return result;
      }

      public int[][] merge(int[][] intervals) {
          if (intervals.length <= 1) {
              return intervals;
          }
          Arrays.sort(intervals, new Comparator<int[]>(){
              public int compare(int[] i1,int[]i2){
                  return i1[0]-i2[0];
              }
          });
          //Arrays.sort(intervals, Comparator.comparingInt(o -> o[0])); 函数式接口速度远慢于原始的比较器
          List<int[]> list = new ArrayList<>();
          int i = 0;
          while(i < intervals.length){
              int[] in = new int[2];
              in[0] = intervals[i][0];
              in[1] = intervals[i][1];
              while(i<intervals.length-1 && in[1]>=intervals[i+1][0]){
                  in[1] = Math.max(intervals[i+1][1],in[1]);
                  i++;
              }
              i++;
              list.add(in);
          }
          return list.toArray(new int[0][]);
      }

62 Unique Paths (Medium)

题目描述

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Above is a 7 x 3 grid. How many possible unique paths are there?

Example:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1.Right -> Right -> Down
2.Right -> Down -> Right
3.Down -> Right -> Right
解法

一开始思路错了，以为是找路径的问题，去用回溯法了，的确也能做出啦，但是对空间的浪费太多了正确思路是动态规划，由于只能向右向下走，所以这个点的值是这个点上面和左边值得合

代码

一开始写的回溯方法：

      int result = 0;
      public int uniquePaths(int m, int n) {
          boolean[] visited = new boolean[m*n];
          generatePath(n,m,0,0,visited);
          return result;
      }
    
      public void generatePath(int row,int col,int curRow,int curCol,boolean[] visited){
          visited[curRow*col+curCol]=true;
          boolean[] tmpRight = Arrays.copyOf(visited,row*col);
          boolean[] tmpDown = Arrays.copyOf(visited,row*col);
          if(visited[row*col-1]){
              result++;
              return;
          }
          //向右走
          if(curCol<col-1){
              int tmpRow = curRow;
              int tmpCol = curCol+1;
              generatePath(row,col,tmpRow,tmpCol,tmpRight);
          }
          //向下走
          if(curRow<row-1){
              int tmpRow = curRow+1;
              int tmpCol = curCol;
              generatePath(row,col,tmpRow,tmpCol,tmpDown);
          }
      }

动态规划：

      public int uniquePaths(int m, int n) {
          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];
      }

64 Minimum Path Sum (Medium)

题目描述

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Example:

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

动态规划，上个题得扩展，这个点得数值是本身数值加上左边、上面两个点之中数值较小得那个

代码

      public int minPathSum(int[][] grid) {
          int row = grid.length;
          int col = grid[0].length;
          for(int j=1;j<col;j++){
              grid[0][j]+= grid[0][j-1];
          }
          for(int i=1;i<row;i++){
              grid[i][0]+= grid[i-1][0];
          }
          for(int i=1;i<row;i++){
              for(int j=1;j<col;j++){
                  grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]); 
              }
          }
          return grid[row-1][col-1];
      }

70 Climbing Stairs (Easy)

题目描述

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1.1 step + 1 step + 1 step
2.1 step + 2 steps
3.2 steps + 1 step
解法

斐波那契数列,注意用循环不要递归会超时，注意变种题，能认出来就行。

代码

  class Solution {
      //最直观的递归写法，但每次都要从头算，太慢了。
      public int climbStairs(int n) {
          if(n<=1) return 1;
          return climbStairs(n-1) + climbStairs(n-2);
      }
      //可以说算是动态规划，但其实就是找了个数组存一下中间结果罢了
      public int climbStairs2(int n) {
          int[] dp = new int[n+1];
          dp[0]=1; // 可以省略
          dp[1]=1;
          for(int i=2;i<=n;i++){
              dp[i] = dp[i-1]+dp[i-2];
          }
          return dp[n];
      }
  }

72 Edit Distance (Hard)

题目描述

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
解法

动态规划，dp[i][j]代表从0到i，j的这个两个词需要多少步能变成相同。所以dp[0][j]和dp[i][0]的值均为j或i（纯删除）。之后如果字母相同，证明无需调整，dp[i+1][j+1]=dp[i][j]。如果字母不相同会分三种情况：
- i的删掉一个
- j的删掉一个
- i和j的作替换
  
  所以dp[i+1][j+1]就变成了取dp[i][j+1],dp[i+1][j],dp[i][j]的最小值。

代码

  class Solution {
      public int minDistance(String word1, String word2) {
          int[][] dp = new int[word1.length()+1][word2.length()+1];
          if(word1.length()==0) return word2.length();
          if(word2.length()==0) return word1.length();
          for(int i = 0;i<=word1.length();i++){
              dp[i][0] = i;
          }
          for(int i = 0;i<=word2.length();i++){
              dp[0][i] = i;
          }
          for(int i =1;i<=word1.length();i++){
              for(int j=1;j<=word2.length();j++){
                  if(word1.charAt(i-1)==word2.charAt(j-1)){
                      dp[i][j] = dp[i-1][j-1];
                  }else{
                      dp[i][j] = 1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
                  }
              }
          }
          return dp[word1.length()][word2.length()];
      }
  }

75 Sort Colors (Medium)

题目描述

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

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

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

Example:

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

Follow up:

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

头尾指针，头指针指着排好0的末尾，尾指针指着排好2的头，从0走一遍走到2指针处即可停止。

代码

      public void sortColors(int[] nums) {
          int zeroIndex=0;
          int twoIndex=nums.length-1;
          for(int i=0;i<=twoIndex;i++){
              if(nums[i]==0){
                  swap(nums,zeroIndex,i);
                  zeroIndex++;
              }
              if(nums[i]==2){
                  swap(nums,twoIndex,i);
                  i--;t
                  twoIndex--;
              }
          }
            
      }
        
      public void swap(int[] nums,int index1,int index2){
          int tmp = nums[index1];
          nums[index1] = nums[index2];
          nums[index2] = tmp;
      }

76 Minimum Window Substring (Hard)

题目描述

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”
解法

用一个map来保存T的字符和出现的次数，当单个字符出现次数相等时form加1，当form和map的个数一样时，说明全部匹配上了

一开始窗口是向右扩展的，当上述条件满足时，将不再右扩展，左边的指针开始往右走，并且同时减小map中存的数，当form不满足的时候，回到之前的步骤，右边指针往右走

代码

  public String minWindow(String s, String t) {
    
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }
    
        // Dictionary which keeps a count of all the unique characters in t.
        Map<Character, Integer> dictT = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }
    
        // Number of unique characters in t, which need to be present in the desired window.
        int required = dictT.size();
    
        // Left and Right pointer
        int l = 0, r = 0;
    
        // formed is used to keep track of how many unique characters in t
        // are present in the current window in its desired frequency.
        // e.g. if t is "AABC" then the window must have two A's, one B and one C.
        // Thus formed would be = 3 when all these conditions are met.
        int formed = 0;
    
        // Dictionary which keeps a count of all the unique characters in the current window.
        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
    
        // ans list of the form (window length, left, right)
        int[] ans = {-1, 0, 0};
    
        while (r < s.length()) {
            // Add one character from the right to the window
            char c = s.charAt(r);
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count + 1);
    
            // If the frequency of the current character added equals to the
            // desired count in t then increment the formed count by 1.
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }
    
            // Try and contract the window till the point where it ceases to be 'desirable'.
            while (l <= r && formed == required) {
                c = s.charAt(l);
                // Save the smallest window until now.
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
    
                // The character at the position pointed by the
                // `Left` pointer is no longer a part of the window.
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }
    
                // Move the left pointer ahead, this would help to look for a new window.
                l++;
            }
    
            // Keep expanding the window once we are done contracting.
            r++;   
        }
    
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }

78 Subsets (Medium)

题目描述

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解法

经典回溯，循环，先加，进递归，后减

代码

      List<List<Integer>> result = new ArrayList<>();
      public List<List<Integer>> subsets(int[] nums) {
          Arrays.sort(nums);
          generateCore(new ArrayList<>(),nums,0);
          return result;
      }
    
      public void generateCore(List<Integer> tmp,int[] nums,int length){
          tmp = new ArrayList<>(tmp);
          result.add(tmp);
          for(int i=length;i<nums.length;i++){
              tmp.add(nums[i]);
              //注意是i+1
              generateCore(tmp,nums,i+1);
              tmp.remove(tmp.size()-1);
          }
      }

79 Word Search (Medium)

题目描述

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

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

Example:

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.
解法

回溯法，路径问题一般需要visit来存储是否访问过，由于每个点都可以是起点，所以在两个for循环中使用回溯。在回溯内部，上下左右走是递归的入口，如果能走返回true

代码

      boolean[] visited;
      public boolean exist(char[][] board, String word) {
          int row = board.length;
          int col = board[0].length;
          boolean result = false;
          visited = new boolean[row*col];
          for(int i=0;i<row;i++){
              for(int j=0;j<col;j++){
                  result = result||existCore(board,i,j,word,0);
              }
          }
          return result;
      }
    
      public boolean existCore(char[][] board,int row,int col,String word,int index){
          int boardRow = board.length;
          int boardCol = board[0].length;
          if(board[row][col]!=word.charAt(index)||visited[row*boardCol+col]){
              return false;
          }
          if(board[row][col]==word.charAt(index)&&index==word.length()-1){//第一个判断条件其实不用，因为如果不等上面的if已经返回
              return true;
          }
          visited[row*boardCol+col] = true;
          //向上走
          if(row>0&&existCore(board,row-1,col,word,index+1)) return true;
          //向下走
          if(row<boardRow-1&&existCore(board,row+1,col,word,index+1)) return true;
          //向左走
          if(col>0&&existCore(board,row,col-1,word,index+1)) return true;
          //向右走
          if(col<boardCol-1&&existCore(board,row,col+1,word,index+1)) return true;
          visited[row*boardCol+col] = false;
          return false;
      }

84 Largest Rectangle in Histogram (Hard)

题目描述

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10
解法

暴力解法：在每个非单调增的拐点处，计算可能的最大面积，从拐点处往前找，记录最小高度，并乘上当前距离，一直找到起点处正确解法：单调增栈，如果当前元素大于栈顶元素即可入栈，注意入栈的元素是当前的下标，而非高度，如果比栈顶小则弹出栈顶元素，并计算所围成的面积。（注意最后要压入0，把栈里剩余的元素都要计算）

代码

暴力解法：

      public int largestRectangleArea(int[] heights) {
          int res=0;
          for(int i=0;i<heights.length;i++){
              if(i+1<heights.length&&heights[i]<heights[i+1]){
                  continue;
              }
              int minHeight = heights[i];
              for(int j=i;j>=0;j--){
                  minHeight = Math.min(minHeight,heights[j]);
                  int area = minHeight*(i-j+1);
                  res = Math.max(res,area);
              }
          }
          return res;
      }

单调栈：

      public int largestRectangleArea(int[] heights){
          Stack<Integer> stack = new Stack<Integer>();
          int i = 0;
          int maxArea = 0;
          int[] h = new int[heights.length + 1];
          h = Arrays.copyOf(heights, heights.length + 1);
          while(i < h.length){
              if(stack.isEmpty() || h[stack.peek()] <= h[i]){
                  stack.push(i++);
              }else {
                  int t = stack.pop();
                  maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
              }
          }
          return maxArea;
      }

85 Maximal Rectangle （Hard)

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
[“1”,”0”,”1”,”0”,”0”],
[“1”,”0”,”1”,”1”,”1”],
[“1”,”1”,”1”,”1”,”1”],
[“1”,”0”,”0”,”1”,”0”]
]
Output: 6
解法

上一道题的扩展，每一行都看作是求直方图的最大面积，第二行时，看上面一行是0还是1，如果是1就累加，是0则为0

代码

      //最大直方图的扩展题，根据每一行构建直方图，然后调用最大直方图的方法进行计算
      public int maximalRectangle(char[][] matrix) {
          if(matrix==null||matrix.length==0||matrix[0].length==0){
              return 0;
          }
          int row = matrix.length;
          int col = matrix[0].length;
          int[] height = new int[col];
          int result =0;
          for(int i=0;i<row;i++){
              for(int j=0;j<col;j++){
                  if(matrix[i][j]=='0'){
                      height[j]=0;
                  }else{
                      height[j]++;
                  }
              }
              result = Math.max(result,largestRectangleArea(height));
          }
          return result;
      }
        
      public int largestRectangleArea(int[] heights){
          int result=0;
          int[] h = Arrays.copyOf(heights,heights.length+1);
          Stack<Integer> stack = new Stack<>();
          int i = 0;
          while(i<h.length){
              if(stack.isEmpty()||h[stack.peek()]<=h[i]){
                  stack.push(i++);
              }else{
                  int val = stack.pop();
                  result = Math.max(result,h[val]*(stack.isEmpty()?i:i-stack.peek()-1));
              }
          }
          return result;
      }

94 Binary Tree Inorder Traversal (Medium)

题目描述

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

不写了，要求不要用递归
解法

两层while循环+栈，外层while判断栈和节点是否空，内层while把先不要打印的“根节点”压入栈中，直到没有左节点为止

代码

      public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> result = new ArrayList<>();
          Stack<TreeNode> stack = new Stack<>();
          TreeNode currentNode = root;
          while(currentNode!=null||!stack.isEmpty()){
              while(currentNode!=null){
                  stack.push(currentNode);
                  currentNode = currentNode.left;
              }
              currentNode = stack.pop();
              result.add(currentNode.val);
              currentNode = currentNode.right;
          }
          return result;
      }

96 Unique Binary Search Trees (Medium)

题目描述

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST’s:
```
 1         3     3      2      1
  \       /     /      / \      \
   3     2     1      1   3      2
  /     /       \                 \
 2     1         2                 3
```
解法

题目比较难，动态规划思想比较好理解。需要推导以下公式：对于n>=2的情况，事实上，1,2,..n都可以作为根节点，若i作为根节点，根据BST的性质，左子树不为空时（左子树为空，只能是i=1），左子树的所有节点必须小于根节点，即[1,i-1]必须位于左子树，同时，右子数节点必须值必须大于根节点值，则[i+1,n]必须位于右子树；

所以 dp[n] = (求和1 - n) dp(i-1)*dp(n-i)

代码

  class Solution {
      public int numTrees(int n) {
          int[] dp = new int[n+1];
          dp[0] = 1;
          dp[1] = 1;
          //dp[n] = 求和1 - n dp(i-1)*dp(n-i)
          for(int i=2;i<=n;i++){
              for(int j=1;j<=i;j++){
                  dp[i]+=dp[j-1]*dp[i-j];
              }
          }
          return dp[n];
      }
  }

98 Validate Binary Search Tree (Medium)

题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example:

略
解法

解法1：中序遍历，看是否递增解法2：递归，返回值为递归函数（左节点，小值，当前节点）&&递归函数（右节点，当前节点值，大值）

代码

      public boolean isValidBST(TreeNode root) {
          if(root==null){
              return true;
          }
          return validCore(root,Long.MIN_VALUE,Long.MAX_VALUE);
      }
    
      public boolean validCore(TreeNode node,long low,long high){
          if(node==null){
              return true;
          }
          if(node.val<=low||node.val>=high) return false;
          return validCore(node.left,low,node.val)&&validCore(node.right,node.val,high);
      }

Symmetric Tree (Easy)

题目描述

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

Example:

略
解法

递归，如果值相等则返回递归函数（左，右）&&（右，左）

代码

      public boolean isSymmetric(TreeNode root) {
          return validCore(root,root);
      }
        
      public boolean validCore(TreeNode node1,TreeNode node2){
          if(node1==null&&node2==null){
              return true;
          }
          if(node1==null||node2==null){
              return false;
          }
          if(node1.val==node2.val){
              return validCore(node1.left,node2.right)&&validCore(node1.right,node2.left);
          }else{
              return false;
          }
      }

102 Binary Tree Level Order Traversal (Medium)

题目描述

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Example:

略
解法

解法1：记一下加入队列的个数，当加入结果的时候统计队列的个数，即是下一层的总个数，当前个数和上次统计队列个数一样的时候，触发加入结果的逻辑，并重置统计个数和队列长度。解法2：用两个栈

代码

解法1：

  class Solution {
      public List<List<Integer>> levelOrder(TreeNode root) {
          Queue<TreeNode> queue = new LinkedBlockingQueue<>();
          List<List<Integer>> lists = new ArrayList<>();
          if(root==null) return lists;
          List<Integer> list = new ArrayList<>();
          queue.add(root);
          int size = 1;
          int temp = 0;
          while(!queue.isEmpty()){
              TreeNode tree = queue.poll();
              temp++;
              list.add(tree.val);
              if(tree.left!=null){
                  queue.add(tree.left);
              }
              if(tree.right!=null){
                  queue.add(tree.right);
              }
              if(temp==size){
                  lists.add(list);
                  list = new ArrayList<>();
                  temp = 0;
                  size = queue.size();
              }
          }
          return lists;
      }
  }

解法2：

          public List<List<Integer>> levelOrder(TreeNode root) {
              Queue<TreeNode> que1 = new LinkedList<>();
              Queue<TreeNode> que2 = new LinkedList<>();
              List<List<Integer>> result = new ArrayList<>();
              if(root==null){
                  return result;
              }
              que1.add(root);
              while(!que1.isEmpty()||!que2.isEmpty()){
                  List<Integer> tmp1 = new ArrayList<>();
                  while(!que1.isEmpty()){
                      TreeNode node1 = que1.poll();
                      if(node1.left!=null) que2.add(node1.left);
                      if(node1.right!=null) que2.add(node1.right);
                      tmp1.add(node1.val);
                  }
                  if(tmp1.size()!=0) result.add(tmp1);
                  List<Integer> tmp2 = new ArrayList<>();
                  while(!que2.isEmpty()){
                      TreeNode node2 = que2.poll();
                      if(node2.left!=null) que1.add(node2.left);
                      if(node2.right!=null) que1.add(node2.right);
                      tmp2.add(node2.val);
                  }
                  if(tmp2.size()!=0) result.add(tmp2);
              }
              return result;
          }

104 Maximum Depth of Binary Tree (Easy)

题目描述

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

略
解法

解法1：递归，选左子和右子树深度大的那一个+1。解法2：层次遍历，数层数。

代码

解法1：

      public int maxDepth(TreeNode root) {
          if(root==null) return 0;
          return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
      }       

解法2：

      public int maxDepth(TreeNode root) {
          if(root==null) return 0;
          int res = 0;
          Queue<TreeNode> queue = new LinkedBlockingQueue<>();
          queue.add(root);
          while(!queue.isEmpty()){
              res++;
              for(int i = queue.size();i>0;--i){ //size会变注意一下
                  TreeNode temp = queue.poll();
                  if(temp.left!=null) queue.add(temp.left);
                  if(temp.right!=null) queue.add(temp.right);
              }
          }
          return res;
      }

105 Construct Binary Tree from Preorder and Inorder Traversal (Medium)

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Example:

略
解法

前序第一个是头节点，中序找到前序的第一个头节点的左边就是左树，右边是右树，知道左右树个数，可以回前序找到相应的左和右，递归即可

代码

  public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
      int root = pre[0];
      int index=-1;
      if(in!=null)
      for (int i =0;i<in.length;i++){
          if(in[i]==root){
              index = i;
          }
      }
      TreeNode treeNode = new TreeNode(root);
      int[] newPreLeft=null;
      int[] newinLeft = null;
      if(index>=1){
          newPreLeft = Arrays.copyOfRange(pre,1,index+1);
          newinLeft = Arrays.copyOfRange(in,0,index);
          treeNode.left = reConstructBinaryTree(newPreLeft,newinLeft);
      }
      int[] newPreRight = null;
      int[] newinRight = null;
      if(in.length-index>1&&index>-1){
          newPreRight = Arrays.copyOfRange(pre,index+1,pre.length);
          newinRight = Arrays.copyOfRange(in,index+1,in.length);
          treeNode.right = reConstructBinaryTree(newPreRight,newinRight);
      }
      return treeNode;
  }

  class Solution {
      //前序第一个是头节点，中序找到前序的第一个头节点就是左树的，中序跳多长，前序也跳多长，下一个就是头节点
      public TreeNode buildTree(int[] preorder, int[] inorder) {
          return helper(preorder,0, inorder, 0, preorder.length);
      }
      public TreeNode helper(int[] preorder, int preBegin, int[] inorder, int inBegin, int length){
          if(length<=0||preBegin>=preorder.length||inBegin>=preorder.length) return null;
          int headVal = preorder[preBegin];
          TreeNode head = new TreeNode(headVal);
          if(length==1) return head;
          int i=inBegin;
          for(;i<=inBegin+length-1;i++){
              if(inorder[i]==headVal){
                  break;
              }
          }
          head.left = helper(preorder, preBegin+1, inorder, inBegin, i-inBegin);
          head.right = helper(preorder, preBegin+i-inBegin+1, inorder, i+1,length-(i-inBegin)-1);
          return head;
      }
  }

114 Flatten Binary Tree to Linked List (Medium)

题目描述

Given a binary tree, flatten it to a linked list in-place.

Example:

略
解法

如果右子树不为空，则右子树最后肯定为左子树最有一个靠右的孩子节点的右子树，而左子树最后成为整棵树的右子树。这样，首先判断左子树是否为空，不为空就寻找到树根的左孩子节点，然后寻找该节点是否有右孩子，如果有继续寻找，直到找到属于叶子节点的右孩子，此时，该节点的右子树“指向”当前树的右子树，并将当前左子树变为树根的右孩子，将整棵树左孩子置为空。最后，根节点“指向”根节点的右孩子，继续上述操作，直到整棵树遍历完即得到结果。

代码

利用辅助空间：

      public void flatten(TreeNode root) {
          List<TreeNode> result = new ArrayList<>();
          preOrder(root,result);
          for(int i=0;i<result.size()-1;i++){
              TreeNode tmpNode = result.get(i);
              tmpNode.left = null;
              tmpNode.right = result.get(i+1);
          }
      }
        
      public void preOrder(TreeNode node,List<TreeNode> result){
          if(node==null){
              return;
          }
          result.add(node);
          preOrder(node.left,result);
          preOrder(node.right,result);
      }

不利用辅助空间：

 public void flatten(TreeNode root) {
 	while (root != null) {
 		if (root.left != null) {
 			TreeNode pre = root.left;
 			while (pre.right != null)
 				pre = pre.right;
 			pre.right = root.right;
 			root.right = root.left;
 			root.left = null;
 		}
 		root = root.right;
 	}
 }

121 Best Time to Buy and Sell Stock (Easy)

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
解法

记录一个最小值，遍历每次减一下就可以了。

代码

      public int maxProfit(int[] prices) {
          int min = Integer.MAX_VALUE;
          int maxPro = 0;
          for(int i=0;i<prices.length;i++){
              if(prices[i]<min){
                  min = prices[i];
              }else if(prices[i]-min>maxPro){
                  maxPro = prices[i]-min;
              }
          }
          return maxPro;
      }

124 Binary Tree Maximum Path Sum (Hard)

题目描述

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example:
解法

依此计算每个节点左通路，右通路的值。最大值有四种情况：它本身、它本身+左通路、它本身+右通路、它本身+左通路+右通路。

如果左边节点路径小于0，则舍弃，

代码

      int result = Integer.MIN_VALUE;
      public int maxPathSum(TreeNode root) {
          searchMax(root);
          return result;
      }
    
      public int searchMax(TreeNode node){
          if(node==null) return 0;
          int left = Math.max(searchMax(node.left),0);
          int right = Math.max(searchMax(node.right),0);
          result = Math.max(result,left+right+node.val);
          return Math.max(left,right)+node.val;
      }

        int max=Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            helper(root);
            return max;
        }
        public int helper(TreeNode root){
            if(root == null) return 0;
            int left = helper(root.left);
            int right = helper(root.right);
            int ans = Math.max(root.val,Math.max(left+root.val,right+root.val));//返回的是当前节点，当前节点左路，当前节点右路的最大值
            max = Math.max(max,Math.max(ans,left+right+root.val));//取最大，当前节点，当前节点左路，当前节点右路，当前节点+当前节点左路+当前节点右路的最大值
            return ans;
        }

128 Longest Consecutive Sequence (Hard)

题目描述

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

Your algorithm should run in O(n) complexity.

Example:

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

最简单的思路：放到一个set里，遍历数组找相邻得数。当没有比这个值小的时候才去找，避免了重复。

代码

      public int longestConsecutive(int[] nums) {
          if(nums.length==0||nums==null){
              return 0;
          }
          Set<Integer> set = new HashSet<>();
          for(int i=0;i<nums.length;i++){
              set.add(nums[i]);
          }
          if(set.size()==1){
              return 1;
          }
          int result=0;
          for(int i=0;i<nums.length;i++){
              int count=1;
              if(!set.contains(nums[i]-1)){
                  while(set.contains(nums[i]+count)){
                      set.remove(nums[i]+count);
                      count++;
                  }
              }
              result = Math.max(result,count);
          }
          return result;
      }

136 Single Number (Easy)

题目描述

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example:

Input: Input: [2,2,1]
Output: 1
解法

异或：相同是0，不同是1。其他都有两个异或就是0，所以最后剩下的值就是单个的值。

代码

      public int singleNumber(int[] nums) {
          int result = nums[0];
          for(int i=1;i<nums.length;i++){
              result = result^nums[i];
          }
          return result;
      }

138 Copy List with Random Pointer (Medium)

题目描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example:

Input:
{“$id”:”1”,”next”:{“$id”:”2”,”next”:null,”random”:{“$ref”:”2”},”val”:2},”random”:{“$ref”:”2”},”val”:1}
Explanation:
Node 1’s value is 1, both of its next and random pointer points to Node 2.
Node 2’s value is 2, its next pointer points to null and its random pointer points to itself.
解法

三次循环，第一次循环复制节点，第二次循环为复制的节点的随机值赋值，第三次循环拆开。

注意点，复制要连在原来的链表节点后面，拆开的时候不要破坏原来链表

代码

      public Node copyRandomList(Node head) {
          if(head==null){
              return null;
          }
          Node tmpHead = head;
          while(tmpHead!=null){
              Node newNode = new Node(tmpHead.val,null,null);
              newNode.next = tmpHead.next;
              tmpHead.next = newNode;
              tmpHead = tmpHead.next.next;
          }
          tmpHead = head;
          while(tmpHead!=null){
              if(tmpHead.random!=null){
                  tmpHead.next.random = tmpHead.random.next;
              }
              tmpHead = tmpHead.next.next;
          }
          tmpHead = head;
          Node result = tmpHead.next;
          while(tmpHead!=null){
              if(tmpHead.next.next!=null){
                  Node copyList = tmpHead.next;
                  tmpHead.next = tmpHead.next.next;
                  copyList.next = copyList.next.next;
                  tmpHead = tmpHead.next;
              }else {
                  tmpHead.next = null;
                  break;
              }
          }
          return result;
      }

139 Word Break (Medium)

题目描述

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Note that you are allowed to reuse a dictionary word.
解法

最一开始用了回溯法，但是当s=”aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”时会超时

正确解法为动态规划，创建一个数组来标记可以被分词得位置，两层循环，第一层为s得前分到的位置，在第二层循环中，将当前字符串分成 0~j 和 j~i ,并判断当前字符串是否包含在其中

代码

回溯法(超时)：

      String match = "";
      public boolean wordBreak(String s, List<String> wordDict) {
          return core(s,wordDict);
      }
    
      public boolean core(String s,List<String> wordDict){
          if(s.equals(match)){
              return true;
          }
          boolean result=false;
          for(int i=0;i<wordDict.size();i++){
              String dic = wordDict.get(i);
              match += dic;
              if(match.length()<=s.length()){
                  if(s.substring(0,match.length()).equals(match)){
                      result = core(s,wordDict);
                  }
              }
              if(!result){
                  match = match.substring(0,match.length()-dic.length());
              }
          }
          return result;
      }

动态规划：

      public boolean wordBreak(String s, List<String> wordDict) {
          Set<String> dict = new HashSet<>();
          for(String tmp:wordDict){
              dict.add(tmp);
          }
          int len = s.length();
          boolean [] dp = new boolean[len + 1];
          dp[0] = true;
    
      //  当前字符串：0~i 
          for(int i = 1; i <= len; i++){
        
      // 将当前的字符串再进行拆分，查看它是否包含在 dict 中
              for(int j = 0; j < i; j++){
        
              // dp[j] 是前面已经计算出来的结果
                  if(dp[j] && dict.contains(s.substring(j,i))){
                      dp[i] = true;
                      break;
                  }
              }
          }
          return dp[len];
      }

141 Linked List Cycle (Easy)

题目描述

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example:

略
解法

双指针，快的走两步，慢的一步，遇到了就是有圈。

代码

  public class Solution {
      public boolean hasCycle(ListNode head) {
          if(head == null) return false;
          ListNode fast = head;
          ListNode slow = head;
          while(true){
              if(fast==null||fast.next==null){
                  return false;
              }
              fast = fast.next.next;
              slow = slow.next;
              if(fast==slow){
                  break;
              }
          }
          return true;
      }
  }
    
      public boolean hasCycle(ListNode head) {
          if(head==null){
              return false;
          }
          ListNode pre=head,last=head;
          while(pre!=null){
              if(pre.next!=null){
                  pre=pre.next.next;
              }else{
                  break;
              }
              last=last.next;
              if(pre==last){
                  return true;
              }
          }
          return false;
      }

142 Linked List Cycle II （Medium）

题目描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example:

略
解法

双指针，一个快跑一个慢跑。快的一次跑两步，慢的一次跑一步，撞上了。

相遇点到环入口点的距离 = 链表起始点到环入口点的距离。所以再让一个指针回到头，两个同时慢走，再遇见就是起始点。数学巧妙

在剑指offer中，先判断出环的个数，然后让一个节点先走环的个数，再一步步走，相遇即入口。

代码

  public class Solution {
      public ListNode detectCycle(ListNode head) {
          if(head == null) return null;
          ListNode fast = head;
          ListNode slow = head;
          while(true){
              if(fast==null||fast.next==null){
                  return null;
              }
              fast = fast.next.next;
              slow = slow.next;
              if(fast==slow){
                  break;
              }
          }
          slow = head;
          while(slow!=fast){
              slow = slow.next;
              fast = fast.next;
          }
          return fast;
      }
  }

剑指offer思路：

  public ListNode detectCycle(ListNode head) {
      ListNode fast=head,slow=head;
      while(true){
          if(fast==null||fast.next==null){
              return null;
          }
          fast = fast.next.next;
          slow = slow.next;
          if(fast==slow){
              break;
          }
      }
      int circleNum=1;
      slow = slow.next;
      while(fast!=slow){
          slow = slow.next;
          circleNum++;
      }
      fast=head;
      slow=head;
      for(int i=0;i<circleNum;i++){
          fast = fast.next;
      }
      while(fast!=slow){
          fast = fast.next;
          slow = slow.next;
      }
      return fast;
  }

146 LRU Cache （Medium）

题目描述

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
解法

LRU是Least Recently Used 近期最少使用算法。内存管理的一种页面置换算法，对于在内存中但又不用的数据块（内存块）叫做LRU，操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。因为要O(1)复杂度，肯定用map，建立一个了链表，每个元素都与map绑定。当使用时断开链表，并放在头里。

代码

  class LRUCache {
      static class Node {
          private int key;
          private int value;
          Node prev, next;
          public Node(int key, int value) {
              this.key = key;
              this.value = value;
          }
      }
      private int capacity;
      private Map<Integer, Node> map;
      private Node dummyhead, dummytail;

      public LRUCache(int capacity) {
          this.capacity = capacity;
          this.map = new HashMap<>();
          this.dummyhead = new Node(-1, -1);
          this.dummytail = new Node(-1, -1);
          this.dummyhead.next = this.dummytail;
          this.dummytail.prev = this.dummyhead;
      }
      public int get(int key) {
          Node node = getNode(key);
          if(null == node) return -1;
          return node.value;
      }
      Node getNode(int key) {
          Node node = map.get(key);
          if(null == node) return null;
          disconnect(node);
          insertHead(node);
          return node;
      }
      void disconnect(Node node) {
          node.next.prev = node.prev;
          node.prev.next = node.next;
      }
      void insertHead(Node node) {
          node.next = dummyhead.next;
          dummyhead.next.prev = node;
          node.prev = dummyhead;
          dummyhead.next = node;
      }
      public void put(int key, int value) {
          Node node = getNode(key);
          if(null != node) {
              node.value = value;
          }
          else {
              node = new Node(key, value);
              insertHead(node);
              map.put(key, node);
              if(map.size() > capacity) {
                  Node tail = dummytail.prev;
                  disconnect(tail);
                  map.remove(tail.key);
              }
          }
      }
  }

148 Sort List (Medium)

题目描述

Sort a linked list in O(n log n) time using constant space complexity.

Example:

Input: 4->2->1->3
Output: 1->2->3->4
解法

看到nlogn想归并排序。把链表拆成两半，然后拆分后的链表比较大小进行排序

代码

          public ListNode sortList(ListNode head) {
             if(head==null||head.next==null){
                 return head;
             }
             ListNode fast = head,slow = head;
             /**
              * 拆成两半
              */
             while(fast.next!=null&&fast.next.next!=null){
                 slow = slow.next;
                 fast = fast.next.next;
             }
             fast = slow;
             slow = slow.next;
             fast.next = null;
             ListNode leftHand = sortList(head);
             ListNode rightHand = sortList(slow);
             return mergeList(leftHand,rightHand);
         }
       
         public ListNode mergeList(ListNode l,ListNode r){
             ListNode dummyNode = new ListNode(-1);
             /**
              * 合并两个链表
              */
             for(ListNode p=dummyNode;l!=null||r!=null;p=p.next){
                 int lValue = l==null?Integer.MAX_VALUE:l.val;
                 int rValue = r==null?Integer.MAX_VALUE:r.val;
                 if(lValue<=rValue){
                     p.next = l;
                     l = l.next;
                 }else{
                     p.next = r;
                     r = r.next;
                 }
             }
             return dummyNode.next;
         }

152 Maximum Product Subarray (Medium)

题目描述

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
解法

方法1：分治法，按0开始分段切割，切割之后如果那一段负数为偶数个，这一段直接相乘即可，切割之后为奇数，以第一个和最后一个负数分别为界限计算2个即可。（代码量较大）方法2：相比于之前的连续数组的最大和只需要增加记录最小值就可以了。因为乘积两个负数相乘可能是正数反而成为最大。

代码

方法1：

      int maxValue = Integer.MIN_VALUE;
      public int maxProduct(int[] nums){
          for(int i=0;i<nums.length;i++){
              if(nums[i]==0){
                  maxValue = 0;
              }
          }
          maxProductCore(nums);
          return maxValue;
      }
    
      public int maxProductCore(int[] nums) {
          if(nums==null||nums.length==0){
              return -1;
          }
          if(nums.length==1){
              maxValue = Math.max(maxValue,nums[0]);
          }else{
              int zero=-1;
              for(int i=0;i<nums.length;i++){
                  if(nums[i]==0){
                      zero = i;
                      break;
                  }
              }
              if(zero!=-1){
                  maxProductCore(Arrays.copyOfRange(nums,0,zero));
                  maxProductCore(Arrays.copyOfRange(nums,zero+1,nums.length));
              }else {
                  int numOfMinus=0;
                  for(int i=0;i<nums.length;i++){
                      if(nums[i]<0){
                          numOfMinus++;
                      }
                  }
                  if(numOfMinus%2==0){
                      int result =1;
                      for(int i=0;i<nums.length;i++){
                          result = result*nums[i];
                      }
                      maxValue = Math.max(maxValue,result);
                  }else{
                      int firstMinus=-1,lastMinus=-1;
                      for(int i=0;i<nums.length;i++){
                          if(nums[i]<0){
                              firstMinus = i;
                              break;
                          }
                      }
                      for(int i=nums.length-1;i>=0;i--){
                          if(nums[i]<0){
                              lastMinus = i;
                              break;
                          }
                      }
                      maxProductCore(Arrays.copyOfRange(nums,0,lastMinus));
                      maxProductCore(Arrays.copyOfRange(nums,firstMinus+1,nums.length));
                  }
              }
    
          }
          return maxValue;
      }

方法2：

  class Solution {
      public int maxProduct(int[] nums) {
          int max = nums[0];
          int maxCurrent = nums[0];
          int minCurrent = nums[0];
          for(int i=1;i<nums.length;i++){
              int tempMax = maxCurrent;
              int tempMin = minCurrent;
              maxCurrent = Math.max(tempMax*nums[i],Math.max(nums[i],tempMin*nums[i]));
              minCurrent = Math.min(tempMax*nums[i],Math.min(nums[i],tempMin*nums[i]));
              max = Math.max(maxCurrent,max);
          }
          return max;
      }
  }

155 Min Stack (Easy)

题目描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> Returns -3.
minStack.pop();
minStack.top(); –> Returns 0.
minStack.getMin(); –> Returns -2.
解法

由两个栈来实现，一个每次都存，一个只存当前位置的最小值。

如果只能用一个栈实现的话，可以设一个最小值，每次当有新的最小值时，先把老的最小值插入栈，再插入新值。这样当pop的时候，pop的值时最小值时，再pop一下就是新的最小值了。

代码

  class MinStack {
          Stack<Integer> stack1 = new Stack<>();
          Stack<Integer> stack2 = new Stack<>();
          /** initialize your data structure here. */
          public MinStack() {
          }
        
          public void push(int x) {
              stack1.push(x);
              int min = stack2.peek();
              if(min<x){
                  stack2.push(min);
              }else{
                  stack2.push(x);
              }
          }
        
          public void pop() {
              stack1.pop();
              stack2.pop();
          }
        
          public int top() {
              return stack1.peek();
          }
        
          public int getMin() {
              return stack2.peek();
          }
  }

  /**
  * Your MinStack object will be instantiated and called as such:
  * MinStack obj = new MinStack();
  * obj.push(x);
  * obj.pop();
  * int param_3 = obj.top();
  * int param_4 = obj.getMin();
  */
  public class MinStack {
      private int min_val = Integer.MAX_VALUE;
      private Stack<Integer> s = new Stack<>();

      /** initialize your data structure here. */
      public MinStack() {}

      public void push(int x) {
          if (x <= min_val) {
              s.push(min_val);
              min_val = x;
          }
          s.push(x);
      }

      public void pop() {
          if (s.pop() == min_val) min_val = s.pop();
      }

      public int top() {
          return s.peek();
      }

      public int getMin() {
          return min_val;
      }
  }

160 Intersection of Two Linked Lists (Easy)

题目描述

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

Example:

略
解法

算出两个ListNode各自的长度，让长的先走差值步。再一起走，碰上了即是交点。

代码

  /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) {
  *         val = x;
  *         next = null;
  *     }
  * }
  */
  public class Solution {
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          ListNode a = headA;
          int countA = 0;
          while(a!=null){
              a=a.next;
              countA++;
          }
          ListNode b = headB;
          int countB = 0;
          while(b!=null){
              b=b.next;
              countB++;
          }
          if(countA>countB){
              for(int i=0;i<countA-countB;i++){
                  headA = headA.next;
              }
          }else{
              for(int i=0;i<countB-countA;i++){
                  headB = headB.next;
              }
          }
          while(headA!=headB){
              headA = headA.next;
              headB = headB.next;
          }
          return headA;
      }
  }

169 Majority Element （Easy）

题目描述

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example:

Input: [3,2,3]
Output: 3
解法

方法一：hashmap

方法二：排序，返回中间数就好了。O(nlogn) 0(1)

方法三：Boyer-Moore Voting Algorithm，用一个计数器记录当前“投票”最多的数字，相同的话+1，不同-1，当到0的时候换数字

代码

  public int majorityElement(int[] nums) {
      HashMap<Integer,Integer> map = new HashMap<>();
      for(int i=0;i<nums.length;i++){
          if(map.containsKey(nums[i])){
              int tmp = map.get(nums[i]);
              map.put(nums[i],tmp+1);
          }else{
              map.put(nums[i],1);
          }
      }
      for(Map.Entry<Integer,Integer> entry:map.entrySet()){
          int mapKey = entry.getKey();
          int mapValue = entry.getValue();
          if(mapValue>nums.length/2){
              return mapKey;
          }
      }
      return 0;
  }

  class Solution {
      public int majorityElement(int[] nums) {
          Arrays.sort(nums);
          return nums[nums.length/2];
      }
  }

  public int majorityElement(int[] nums) {
      int count = 0;
      Integer candidate = null;

      for (int num : nums) {
          if (count == 0) {
              candidate = num;
          }
          count += (num == candidate) ? 1 : -1;
      }

      return candidate;
  }

198 House Robber (Easy)

题目描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example:

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

动态规划，dp[i]表示0-i抢劫的钱，不要考虑后面没抢的，那在后面会考虑到。dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])。关键还是找准递推公式。

代码

  class Solution {
      public int rob(int[] nums) {
          if(nums.length==0) return 0;
          if(nums.length==1) return dp[0];
          int[] dp = new int[nums.length];
          dp[0] = nums[0];
          dp[1] = Math.max(nums[1],nums[0]);
          for(int i=2;i<nums.length;i++){
              dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
          }
          return dp[nums.length-1];
      }
  }

200 Number of Islands (Medium)

题目描述

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Input:
11000
11000
00100
00011
Output: 3
解法

当遇到一个1的时候，上下左右走把相邻的1设置为0，遍历数组的每一个点即可。

代码

      public int numIslands(char[][] grid) {
          if(grid==null||grid.length==0){
              return 0;
          }
          int res=0;
          int row = grid.length;
          int colum = grid[0].length;
          for(int i=0;i<row;i++){
              for(int j=0;j<colum;j++){
                  if(grid[i][j]=='1'){
                      DFS(grid,i,j);
                      res++;
                  }
              }
          }
          return res;
      }
        
      public void DFS(char[][] grid,int i,int j){
          if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]!='1'){
              return;
          }
          grid[i][j]='0';
          DFS(grid,i+1,j);
          DFS(grid,i-1,j);
          DFS(grid,i,j+1);
          DFS(grid,i,j-1);
      }

206 Reverse Linked List (Easy)

题目描述

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
解法

方法1：借用栈

方法二：循环，记录好上一个

代码

      public ListNode reverseList(ListNode head) {
          Stack<ListNode> stack = new Stack<>();
          while(head!=null){
              stack.push(head);
              head = head.next;
          }
          ListNode dummy = new ListNode(-1);
          ListNode res = dummy;
          while(!stack.isEmpty()){
              dummy.next = stack.pop();
              dummy = dummy.next;
          }
          dummy.next = null;
          return res.next;
      }
    
      public ListNode reverseList(ListNode head) {
          ListNode prev = null;
          ListNode curr = head;
          while (curr != null) {
              ListNode nextTemp = curr.next;
              curr.next = prev;
              prev = curr;
              curr = nextTemp;
          }
          return prev;
      }

207 Course Schedule (Medium)

题目描述

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
解法

解法1:同学写的方法，感觉这道题其实挺难的，由于没有学过图论，只能结合看的答案从自身的理解解释一下。目标就是解释清到最后所有的课程都可以不被依赖。首先先记录所有有被依赖到的课程，之后找到哪门课没有被任何课程依赖从他入手，如果所有课程都依赖于某一门课，那么一定在中间存在闭环，肯定不行。拿不被任何课程依赖的课程查看他的依赖，将他依赖的课程数量逐一再减下去，当减完后，他也就变成了只依赖别的课的课程。这样一门一门课的依赖去找。如果到最后还有某门课还存在依赖的课程没被减完，贼证明这门课和某一门课存在了闭环，谁都无法消下去了。

解法2:标准答案
bfs:1建立一个array list数组每一个list用于储存当前位置所有进阶课程（大小为 numcourse） 2建立一个数组储存当前位置需要的基础课程个数；（大小为numcourse） 3建立一个count 记录可以完成课程的个数用于最后与总课程数进行比较 4建立一个queue 进行层级遍历；先把2 步骤中值为0 的位置拿出来存入queue 中然后开始层级遍历，每次poll的课程找到他的进阶课程list进行筛选如果数组中此课程所需要的基础课程数值为0 则说明已经可以学习这门课程那么就把它放入queue中，以此方法遍历每次poll时count➕1 直到遍历结束比对count的值是否等于numcourse则可以得出结论；

代码

  class Solution {
      public boolean canFinish(int numCourses, int[][] prerequisites) {
          Map<Integer,List<Integer>> yilaiguanxi = new HashMap<>();//记录课程的依赖关系
          int[] yilaishuliang = new int[numCourses];//记录每门课程到现在还被依赖的数量
          //记录依赖关系和依赖数量
          for(int i=0;i<prerequisites.length;i++){
              int yilai = prerequisites[i][0];//依赖的课程
              int beiyilai = prerequisites[i][1];//被依赖的课程
              yilaishuliang[beiyilai]++;
              if(!yilaiguanxi.containsKey(yilai)){
                  List<Integer> list = new ArrayList<>();
                  list.add(beiyilai);
                  yilaiguanxi.put(yilai,list);
              }else{
                  yilaiguanxi.get(yilai).add(beiyilai);
              }
          }
          LinkedList<Integer> meibeiyilai = new LinkedList<>();//没被依赖的课程表，拿他去找依赖的课程让依赖的课程都解开最后也变成没被依赖的课程
          for(int i=0;i<numCourses;i++){ //找没被依赖的课程
              if(yilaishuliang[i] == 0){ //找到的没被依赖的课程
                  meibeiyilai.add(i); //这门课没被任何课依赖
              }
          }
          while(!meibeiyilai.isEmpty()){ //没被依赖的课都被算清之前，找依赖关系
              int zhaoyilai = meibeiyilai.removeFirst();//捋这个没被依赖的关系，并且这个找完关系了就给清出去
              yilaishuliang[zhaoyilai] = -1;//他没被任何依赖后，设为-1
              if(!yilaiguanxi.containsKey(zhaoyilai)){//他就没依赖任何家伙
                  continue;
              }
              List<Integer> list = yilaiguanxi.get(zhaoyilai);//拿到他所有依赖的课程
              for(int j=0;j<list.size();j++){
                  int beiyilaiIndex = list.get(j);//这个被依赖的课程
                  yilaishuliang[beiyilaiIndex]--;//这个课程被依赖的数量-1
                  if(yilaishuliang[beiyilaiIndex]==0){ //这门课的所有依赖课也都解开了，他也就成了没被任何课依赖的课
                      meibeiyilai.add(beiyilaiIndex);
                  }
              }
          }
          for(int i=0;i<numCourses;i++){ //最后再找一遍还有没被依赖的课
              if(yilaishuliang[i] != -1){ //如果某门课不是-1，证明他还存在着被依赖的关系，也就是之前的步骤没有进入他的环，它存在闭环关系
                  return false;
              }
          }
          return true;
      }
  }

  public boolean canFinish(int numCourses, int[][] prerequisites) {
      List[] postCourses = new ArrayList[numCourses];
      int[] degrees = new int[numCourses];
      int count = 0;
      Queue<Integer> q = new LinkedList<>();
      //先给list中每个都赋一个空值；
      for (int i = 0; i < numCourses; i++) {
          postCourses[i] = new ArrayList<Integer>();
      }
      for (int i = 0; i < prerequisites.length; i++) {
          postCourses[prerequisites[i][1]].add(prerequisites[i][0]);
          degrees[prerequisites[i][0]]++;
      }
      for (int i = 0; i < numCourses; i++) {
          if (degrees[i] == 0) {
              q.offer(i);
          }
      }
      while (!q.isEmpty()) {
          int temp = q.poll();
          count++;
          for (int i = 0; i < postCourses[temp].size(); i++) {
              int prevCourse = (int) postCourses[temp].get(i);
              degrees[prevCourse]--;
              if (degrees[prevCourse] == 0) {
                  q.offer(prevCourse);
              }
          }
      }
      return count == numCourses;
  }

208 Implement Trie (Prefix Tree) (Medium)

题目描述

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // returns true
trie.search(“app”); // returns false
trie.startsWith(“app”); // returns true
trie.insert(“app”);
trie.search(“app”); // returns true
解法

一开始自己写了个hashmap存，也能出结果，但没啥意义

字典树，每个树的树枝都有26个字母，有这个字母就见这个对象。当一个词在这里完结的时候，给他附上一个结束标志为表示这里有结束的单词。

代码

自己写的：

  class Trie {
        
      HashSet<String> set = new HashSet<String>();
      /** Initialize your data structure here. */
      public Trie() {
            
      }
        
      /** Inserts a word into the trie. */
      public void insert(String word) {
          set.add(word);
      }
        
      /** Returns if the word is in the trie. */
      public boolean search(String word) {
          return set.contains(word);
      }
        
      /** Returns if there is any word in the trie that starts with the given prefix. */
      public boolean startsWith(String prefix) {
          boolean result = false;
          for(String s:set){
              int length = prefix.length()<=s.length()?prefix.length():s.length();
              if(s.substring(0,length).equals(prefix)){
                  result = true;
                  break;
              }
          }
          return result;
      }
  }

正确写法：

  class Trie {

      TrieNode root = new TrieNode();
      /** Initialize your data structure here. */
      public Trie() {
      }
      /** Inserts a word into the trie. */
      public void insert(String word) {
          root.insert(word,0);
      }
      /** Returns if the word is in the trie. */
      public boolean search(String word) {
          TrieNode trie = root.findChar(word,0);
          if(trie!=null && trie.wordEnd == true) return true;
          return false;
      }
      /** Returns if there is any word in the trie that starts with the given prefix. */
      public boolean startsWith(String prefix) {
          TrieNode trie = root.findChar(prefix,0);
          if(trie!=null) return true;
          return false;
      }
  }

  class TrieNode{
      TrieNode[] children = new TrieNode[26];
      boolean wordEnd = false;
      public void insert(String word, int index){
          if(index == word.length()){
              wordEnd = true;
              return;
          }
          int pos = word.charAt(index)-'a';
          if(children[pos]==null){
              children[pos] = new TrieNode();
          }
          children[pos].insert(word, index+1);
      }
      public TrieNode findChar(String word, int index){
          if(index == word.length()){
              return this;
          }
          int pos = word.charAt(index)-'a';
          if(children[pos]==null) return null;
          return children[pos].findChar(word,index+1);
      }
  }

  /**
  * 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);
  */

215 Kth Largest Element in an Array (Medium)

题目描述

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
解法

方法一：利用库函数，速度最快

方法二：利用快排的分区思想

方法三：完整快排,
选取一个基准元素（pivot）
比pivot小的放到pivot左边，比pivot大的放到pivot右边
对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2

方法四：优先队列（最大堆）/（最小堆）。

代码

方法一：

  public int findKthLargest(int[] nums, int k) {
      Arrays.sort(nums);
      return nums[nums.length-k];
  }

方法二：

  public int findKthLargest(int[] nums, int k) {
      int target = nums.length-k;
      int left=0;
      int right=nums.length-1;
      while(true){
          int i = partition(nums,left,right);
          if(i<target){
              left = i + 1;
          }else if(i>target){
              right = i - 1;
          }else{
              return nums[i];
          }
      }
  }
    
  public int partition(int[] nums,int left,int right){
      int index = nums[left];
      int l = left;
      for(int i=left+1;i<=right;i++){
          if(nums[i]<index){
              l++;
              swap(nums,l,i);
          }
      }
      swap(nums,left,l);
      return l;
  }
    
  public void swap(int[] nums,int l,int r){
      int tmp = nums[l];
      nums[l] = nums[r];
      nums[r] = tmp;
  }

方法三：

  public int findKthLargest(int[] nums, int k) {
      int target = nums.length-k;
      quickSort(nums,0,nums.length-1);
      return nums[target];
  }
    
  public void quickSort(int[] nums,int low,int high){
      if(low<high){
          int index = partition(nums,low,high);
          quickSort(nums,low,index-1);
          quickSort(nums,index+1,high);
      }
  }
    
  public int partition(int[] nums,int low,int high){
      int index = nums[low];
      while(low<high){
          while(low<high&&nums[high]>=index){
              high--;
          }
          nums[low]=nums[high];
          while(low<high&&nums[low]<=index){
              low++;
          }
          nums[high]=nums[low];
      }
      nums[low]=index;
      return low;
  }

方法四：

  public int findKthLargest(int[] nums, int k) {
      PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
      for (int num : nums) {
          priorityQueue.add(num);
          if(priorityQueue.size()==k+1){
              priorityQueue.poll();
          }
      }
      return priorityQueue.peek();
  }

221 Maximal Square (Medium)

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:
解法

动态规划，但是递推公式有一点难推。dp[i][j]看作是以i，j为右下角时，可以形成的最大正方形面积的边长。递推时就看左，上以及左上的长度。取这三个长度的最小值即为他们三临近都为1的最大长/宽/斜线，再加1就是他所可以围成的正方形最大边长。即dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;

代码

  class Solution {
      //动态规划，dp[i][j]表示以i，j为右下角时能组成的最大正方形边长，既然能组成正方形，也就是保证左边点，上边点以及斜上边点为右下角能组成正方形的最小值+1（因为只要这三点有一个组成中有问题，这正方形就组不起来）
      public int maximalSquare(char[][] matrix) {
          int[][] dp = new int[matrix.length][matrix[0].length];
          int max = 0;//最大边的长度
          for(int i=0;i<matrix.length;i++){
              for(int j=0;j<matrix[0].length;j++){
                  if(matrix[i][j]=='1'){
                      if(i==0||j==0){
                          dp[i][j] = 1;
                      }else{
                          dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                      }
                  }
                  max=Math.max(max,dp[i][j]);
              }
          }
          return max*max;
      }
  }

226 Invert Binary Tree (Easy)

题目描述

Invert a binary tree.

Example:

略
解法

左右树互换在递归就好了。

代码

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
  public TreeNode invertTree(TreeNode root) {
      if(root==null){
          return null;
      }else{
          TreeNode tmp = root.left;
          root.left = root.right;
          root.right = tmp;
      }
      invertTree(root.left);
      invertTree(root.right);
      return root;
  }

226 Palindrome Linked List (Easy)

题目描述

Given a singly linked list, determine if it is a palindrome.

Follow up:Could you do it in O(n) time and O(1) space?

Example:

Input: 1->2->2->1
Output: true
解法

方法一：O(n)空间复杂度，借用栈，把链表全部压栈，再从头遍历和栈比较即可

方法二：O(1)空间复杂度，反转链表得扩展题，快慢指针先得到中间位置，把后半部分链表反转，然后和头指针挨个比较。

代码

方法一：

  public boolean isPalindrome(ListNode head) {
      if(head==null||head.next==null){
          return true;
      }
      Stack<ListNode> stack = new Stack<>();
      ListNode current = head;
      while(current!=null){
          stack.push(current);
          current = current.next;
      }
      current = head;
      while(current!=null){
          ListNode judge = stack.pop();
          if(judge.val!=current.val) return false;
          current = current.next;
      }
      return true;
  }

  public boolean isPalindrome(ListNode head) {
      if(head==null||head.next==null){
          return true;
      }
      ListNode slow=head,fast=head;
      while(fast.next!=null&&fast.next.next!=null){
          slow = slow.next;
          fast = fast.next.next;
      }
      fast = slow.next;
      slow = head;
      ListNode prev = null;
      while(fast!=null){
          ListNode tmp = fast.next;
          fast.next = prev;
          prev = fast;
          fast = tmp;
      }
      while(prev!=null){
          if(prev.val!=slow.val){
              return false;
          }
          prev = prev.next;
          slow = slow.next;
      }
      return true;
  }

236 Lowest Common Ancestor of a Binary Tree (Medium)

题目描述 Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example:

略
解法

深度搜索，只有分别深度搜索左右节点，只有左右都有时，他就是最低公共节点，否则还在他的上级。

代码

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if(root==null||p==root||q==root){
          return root;
      }
      TreeNode left = lowestCommonAncestor(root.left,p,q);
      TreeNode right = lowestCommonAncestor(root.right,p,q);
      if(left!=null&&right!=null){
          return root;
      }
      return left==null?right:left;
  }

238 Product of Array Except Self (Medium)

题目描述 Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input: [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
解法

方法一：剑指offer也出现过的题，不用除法，以被除数为中心，分别计算左，右两边的乘积数组，再将乘积数组相乘即可。

方法二：对一的优化，O(1)空间复杂度

代码

  public int[] productExceptSelf(int[] nums) {
      if(nums==null||nums.length==0){
          return null;
      }
      int[] left = new int[nums.length];
      int[] right = new int[nums.length];
      left[0] = 1;
      for(int i=1;i<nums.length;i++){
          left[i] = left[i-1]*nums[i-1];
      }
      right[nums.length-1] = 1;
      for(int i=nums.length-2;i>=0;i--){
          right[i] = right[i+1]*nums[i+1];
      }
      int[] res = new int[nums.length];
      for(int i=0;i<nums.length;i++){
          res[i] = left[i]*right[i];
      }
      return res;
  }

  public int[] productExceptSelf(int[] nums) {
      int length = nums.length;
      int[] answer = new int[length];
      answer[0] = 1;
      for (int i = 1; i < length; i++) {
          answer[i] = nums[i - 1] * answer[i - 1];
      }
      int R = 1;
      for (int i = length - 1; i >= 0; i--) {
          answer[i] = answer[i] * R;
          R *= nums[i];
      }
      return answer;
  }

239 Sliding Window Maximum (Hard)

题目描述 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
解法

建一个双向链表（只保存序号），加数的时候比目前最后一个数小就加进去，比他大就从尾循环弹出，所以链表的头永远都是最大的，每次比较时只要在确定头的序号是在窗口内的就行。

代码

  public int[] maxSlidingWindow(int[] nums, int k) {
      if(nums.length == 0) return new int[]{};
      // deque is a window of at most size k that ends at index i
      LinkedList<int[]> dq = new LinkedList<>();
      int[] ret = new int[nums.length - k + 1];

      for(int i = 0; i < nums.length; i++) {
          // This keeps the deque a decreasing sequence
          while(!dq.isEmpty() && dq.getLast()[1] <= nums[i])
              dq.removeLast();

          // Add new element to deque
          dq.offerLast(new int[]{i, nums[i]});

          // Kick out elements that are not no longer in the window
          if(!dq.isEmpty() && dq.getFirst()[0] <= i - k)
              dq.removeFirst();

          // pick the first one in the window
          if(i >= k - 1) ret[i - k + 1] = dq.getFirst()[1];
      }
      return ret;
  }

240 Search a 2D Matrix II (Medium)

题目描述

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
  
  Example:
  
  Consider the following matrix: [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
  ]
  Given target = 5, return true.
  Given target = 20, return false.
解法

抓住每个元素左边比他小，下边比他大的特点，从右上角（即头）开始遍历。

代码

  public boolean searchMatrix(int[][] matrix, int target) {
      int row = matrix.length;
      if(row==0){
          return false;
      }
      int col = matrix[0].length;
      int i=0,j=col-1;
      while(i<row&&j>=0){
          if(matrix[i][j]==target){
              return true;
          }else if(matrix[i][j]>target){
              j--;
          }else{
              i++;
          }
      }
      return false;
  }

253 Meeting Rooms II (Medium)

题目描述

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

Example:

Given [[0, 30],[5, 10],[15, 20]], return 2.
解法

可以对全部元素按开始时间排序，之后将每个的结束时间放入优先队列，队列里有几个元素，代表正在有几个会议室使用中，并且记录的是结束时间。如果下一个的开始时间小于当前最早的结束时间，那么也就要加一个会议室。否则就是一个会议室已经结束了，把它剔除。

代码

  public class Solution {
      public static void main(String[] args) {
          Interval i1 = new Interval(2,10);
          Interval i2 = new Interval(3,6);
          Interval i3 = new Interval(12,19);
          Interval i4 = new Interval(13,20);
          Interval[] in = {i1,i2,i3,i4};
          Solution s= new Solution();
          s.minMeetingRooms(in);
      }
      public int minMeetingRooms(Interval[] intervals) {
          //先对时间排序，之后创一个优先队列。如果下一个的开始时间比这个的结束时间小，就证明要加一个会议室了。否则的话，就证明这个时间段已经过了，下一个时间的可以用这个会议室，这个的结束时间就更新了，也就是剔除这个时间
          Arrays.sort(intervals, Comparator.comparingInt(i -> i.start));
          PriorityQueue<Integer> queue = new PriorityQueue<>();
          int num = 0;
          for(int i=0;i<intervals.length;i++){
              queue.add(intervals[i].end);
              if(intervals[i].start<queue.peek()){
                  num++;
              }else{
                  queue.poll();
              }
          }
          return num;//或者是queue.size()
      }
      public static class Interval {
          int start;
          int end;
          Interval() { start = 0; end = 0; }
          Interval(int s, int e) { start = s; end = e; }
      }
  }

279 Perfect Squares (Medium)

题目描述

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. Example:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
解法

动态规划，计算从0-n得每个数需要几个数sum，递推式min=Math.min(min,dp[i-j*j]+1)

代码

  public int numSquares(int n) {
      if(n==0) return 0;
      int[] dp = new int[n+1];
      for(int i=1;i<=n;i++){
          int min = i;
          for(int j=1;j*j<=i;j++){
              min = Math.min(min,dp[i-j*j]+1);
          }
          dp[i] = min;
      }
      return dp[n];
  }

283 Move Zeroes （Easy）

题目描述

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

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
解法

遇到非0的数的时候，根据指向非0数字的指针位置，将数字放置即可

代码

  public void moveZeroes(int[] nums) {
      int lastNonZeroIndex = 0;
      for(int i=0;i<nums.length;i++){
          if(nums[i]!=0){
              nums[lastNonZeroIndex++]=nums[i];
          }
      }
      for(int i=lastNonZeroIndex;i<nums.length;i++){
          nums[i] = 0;
      }
  }

287 Find the Duplicate Number (Medium)

题目描述

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example:

IInput: [1,3,4,2,2]
Output: 2

Note:
1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.
解法

挨个比，时间复杂度O(n2) 排序，然后挨个比O(nlogn) 利用Set,空间复杂O(n)时间复杂O(n) 以上均是比较容易想到的，但是不满足要求

最优解法：看成含环链表找入口节点的题

代码

  public int findDuplicate(int[] nums) {
      int slow=nums[0],fast=nums[0];
      do{
          slow = nums[slow];
          fast = nums[nums[fast]];
      }while(slow!=fast);
      slow=nums[0];
      while(slow!=fast){
          slow = nums[slow];
          fast = nums[fast];
      }
      return slow;
  }    

295 FindMedianfromDataStream (Hard)

题目描述

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Example:

[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5

Note:
1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.
解法

剑指 offer 原题，一个大队列，一个小队列分别保存小一半的数和大一半的数，插入时比较看是大一半还是小一半的最多就交换下顺序。

代码

  public Queue<Integer> max = new PriorityQueue<Integer>(Collections.reverseOrder());
  public Queue<Integer> min = new PriorityQueue<Integer>();

  public void addNum(int num) {
      if(max.size()<min.size()){
          max.add(num);
          min.add(max.poll());
          max.add(min.poll());
      }else{
          min.add(num);
          max.add(min.poll());
          min.add(max.poll());
      }
  }

  public double findMedian() {
      if(max.size()<min.size()){
          return min.peek();
      }else if(max.size()>min.size()){
          return max.peek();
      }else{
          return (double)(max.peek()+min.peek())/2;
      }
  }
  /**
  * Your MedianFinder object will be instantiated and called as such:
  * MedianFinder obj = new MedianFinder();
  * obj.addNum(num);
  * double param_2 = obj.findMedian();
  */

297 Serialize and Deserialize Binary Tree （Hard）

题目描述

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

略
解法

第一种方式，前序遍历，注意一个基础知识点，java函数传递方式是Pass-by-value，但是当因传递的是引用变量的时候，相当于一台电视一个遥控器，复制了一个遥控器，最后还是能能对同一个电视操作，即其实最后还是修改的地址。string的+=操作内存地址会改变，但StringBuilder的append不会改变内存地址。

代码

前序遍历：

  public String serialize(TreeNode root) {
      if(root==null) return "";
      String result = "";
      Stack<TreeNode> stack = new Stack<>();
      while(root!=null||!stack.isEmpty()){
          while(root!=null){
              result += root.val+",";
              stack.push(root);
              root = root.left;
          }
          result+="#,";
          if(!stack.isEmpty()){
              root = stack.pop().right;
          }
      }
      result+="#";
      return result;
  }

  // Decodes your encoded data to tree.
  int index = 0;
  public TreeNode deserialize(String data) {
      if(data.length()==0||data==null){
          return null;
      }
      String[] treeString = data.split(",");
      return helper(treeString);
  }
    
  public TreeNode helper(String[] treeString){
      if(treeString[index].equals("#")) return null;
      TreeNode root = new TreeNode(Integer.valueOf(treeString[index]));
      index++;
      root.left = helper(treeString);
      index++;
      root.right = helper(treeString);
      return root;
  }

      public String serialize(TreeNode root) {
          if(root == null) return "";
          StringBuilder s = new StringBuilder();
          Stack<TreeNode> stack = new Stack<>();
          stack.add(root);
          while(!stack.isEmpty() || root!=null){
              while(root!=null){
                  s.append(root.val+",");
                  stack.add(root);
                  root = root.left;
              }
              s.append("#,");
              if(!stack.isEmpty()){
                  root = stack.pop();
                  root = root.right;
              }
          }
          return s.toString().substring(0,s.length()-1);
      }

      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
          if(data.equals("")) return null;
          int[] index = {0}; //注意这里是数组的原因，是为了传递地址
          String[] trees = data.split(",");
          return helper(trees,index);
      }
      public TreeNode helper(String[] trees, int[] index){
          if(trees[index[0]].equals("#")) return null;
          TreeNode tree = new TreeNode(Integer.valueOf(trees[index[0]]));
          ++index[0];
          tree.left = helper(trees,index);
          ++index[0];
          tree.right = helper(trees,index);
          return tree;
      }

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
  public class Codec {

      // 前序遍历
      public String serialize(TreeNode root) {
          if(root == null) return "";
          StringBuilder s = new StringBuilder();
          Stack<TreeNode> stack = new Stack<>();
          stack.add(root);
          while(!stack.isEmpty() || root!=null){
              while(root!=null){
                  s.append(root.val+",");
                  stack.add(root);
                  root = root.left;
              }
              s.append("#,");
              if(!stack.isEmpty()){
                  root = stack.pop();
                  root = root.right;
              }
          }
          return s.toString().substring(0,s.length()-1);
      }

      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
          if(data.equals("")) return null;
          int[] index = {0};
          String[] trees = data.split(",");
          return helper(trees,index);
      }
      public TreeNode helper(String[] trees, int[] index){
          if(trees[index[0]].equals("#")) return null;
          TreeNode tree = new TreeNode(Integer.valueOf(trees[index[0]]));
          ++index[0];
          tree.left = helper(trees,index);
          ++index[0];
          tree.right = helper(trees,index);
          return tree;
      }
  }

  // Your Codec object will be instantiated and called as such:
  // Codec codec = new Codec();
  // codec.deserialize(codec.serialize(root));

  /**
   * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
  public class Codec {

      // 前序遍历
      public String serialize(TreeNode root) {
          if(root == null) return "";
          StringBuilder s = new StringBuilder();
          LinkedList<TreeNode> q = new LinkedList<>();
          q.add(root);
          while(q.size()>0){
              TreeNode t = q.poll();
              if(t==null){
                  s.append("#,");
                  continue;
              }
              s.append(t.val+",");
              q.add(t.left);
              q.add(t.right);
          }
          return s.toString().substring(0,s.length()-1);
      }

      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
          if(data.equals("")) return null;
          String[] datas = data.split(",");
          int index = 0;
          TreeNode tree = new TreeNode(Integer.parseInt(datas[index]));
          index++;
          LinkedList<TreeNode> queue = new LinkedList<>();
          queue.add(tree);
          while(queue.size()>0){
              TreeNode node = queue.poll();
              if(node==null) continue;
              if(!datas[index].equals("#")){
                  TreeNode temp = new TreeNode(Integer.parseInt(datas[index]));
                  node.left = temp;
                  queue.add(temp);
              }else{
                  node.left = null;
                  queue.add(null);
              }
              index++;
              if(!datas[index].equals("#")){
                  TreeNode temp = new TreeNode(Integer.parseInt(datas[index]));
                  node.right = temp;
                  queue.add(temp);
              }else{
                  node.right = null;
                  queue.add(null);
              }
              index++;
          }
          return tree;
      }
  }

  // Your Codec object will be instantiated and called as such:
  // Codec codec = new Codec();
  // codec.deserialize(codec.serialize(root));

300 Longest Increasing Subsequence （Medium）

题目描述

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

Example:

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

动态规划，dp[i] 表示以 nums[i] 为结尾的数字最大递增子序列，然后从头到 i 再算。当一个数比 i 小，证明这个数的 dp 可以加 1 作为 dp[i]。递推公式即为：dp[i] = Math.max(dp[i],dp[j]+1)

第二种思路是可以想象，求最大的递增序列中，新来的一个数替换已有序列中最小的比该数大的数，该序列都不会受影响，因为序列能在增长只有当比最右边数大即可以了，所以利用这一原理，用 TreeSet 可以直接解决这一问题。ceiling 即是找最小的比该数大的数，每个数都加进去，替换掉比他大的最小的数，如果没得替换，也就序列长度加一了。

代码

  class Solution {
    
  public int lengthOfLIS(int[] nums) {
      if(nums.length==0||nums==null){
          return 0;
      }
      int[] dp = new int[nums.length];
      for(int i=0;i<nums.length;i++){
          for(int j=i-1;j>=0;j--){
              if(nums[i]>nums[j]){
                  dp[i] = Math.max(dp[i],dp[j]+1);
              }
          }
      }
      int max =0;
      for(int i=0;i<dp.length;i++){
          max = Math.max(max,dp[i]);
      }
      return max+1;
  }
    
      public int lengthOfLIS2(int[] nums) {
          //递增序列可以想为，一个新数，替换里面一个最小的比他大的数，也不会影响整体结果，所以可以用天然排序的 treeset 来做。ceiling 方法即是返回一个最小的比他大的数
          TreeSet<Integer> set = new TreeSet<>();
          for(int num:nums){
              Integer ceil = set.ceiling(num);
              if(ceil!=null) set.remove(ceil);
              set.add(num);
          }
          return set.size();
      }
  }
    

301 Remove Invalid Parentheses (Hard)

题目描述

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Example:

Input: “(a)())()”
Output: [“(a)()()”, “(a())()”]
解法

此题可以用深度优先和广度优先，只看懂了广度优先。需要用到队列，set，先把string放进队列，取队列头，判断是否有效，如果无效，则删除string中的非字母的一个元素，并把所有删除结果放入队列，此处需要用set判断是否重复。如果在一层中找到了符合的，就不用继续删除找小的了。

代码

  public List<String> removeInvalidParentheses(String s) {
      HashSet<String> set = new HashSet<>();
      LinkedList<String> q = new LinkedList<String>();
      List<String> result = new ArrayList<>();
      q.add(s);
      set.add(s);
      boolean found = false;
      while(!q.isEmpty()){
          String ss = q.removeFirst();
          if(isValid(ss)){
              result.add(ss);
              found = true;
          }
          if(found) continue;
          for(int i=0;i<ss.length();i++){
              if(ss.charAt(i)!='('&&ss.charAt(i)!=')') continue;
              String tmp = ss.substring(0,i)+ss.substring(i+1);
              if(!set.contains(tmp)){
                  set.add(tmp);
                  q.add(tmp);
              }
          }
      }
      return result;
  }
    
  public boolean isValid(String s){
      int count=0;
      for(int i=0;i<s.length();i++){
          if(s.charAt(i)=='('){
              count++;
          }else if(s.charAt(i)==')'){
              count--;
              if(count<0){
                  return false;
              }
          }
      }
      return count==0;
  }   

309 Best Time to Buy and Sell Stock with Cooldown （Medium）

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
解法

buy[i]表示在第i天之前最后一个操作是买，此时的最大收益。

sell[i]表示在第i天之前最后一个操作是卖，此时的最大收益。

rest[i]表示在第i天之前最后一个操作是冷冻期，此时的最大收益。

我们写出递推式为：

buy[i] = max(rest[i-1] - price, buy[i-1])

sell[i] = max(buy[i-1] + price, sell[i-1])

rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

代码

  public int maxProfit(int[] prices) {
      if(prices.length==0||prices.length==1){
          return 0;
      }
      int[] buy = new int[prices.length];
      int[] sell = new int[prices.length];
      int[] rest = new int[prices.length];
      buy[0] = -prices[0];
      sell[0] = 0;
      rest[0] = 0;
      for(int i=1;i<prices.length;i++){
          buy[i] = Math.max(rest[i-1]-prices[i],buy[i-1]);
          sell[i] = Math.max(buy[i-1]+prices[i],sell[i-1]);
          rest[i] = Math.max(buy[i-1],Math.max(sell[i-1],rest[i-1]));
      }
      return Math.max(sell[prices.length-1],rest[prices.length-1]);     
  }

312 Burst Balloons (Hard)

题目描述

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Example:

Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [] coins = 315 + 358 + 138 + 181 = 167
解法

从 i 到 j 的最大值可以看为剔除中间一个数后，两边的最大值的和加上剔除数乘上两边的数。这样就可以推导出动态规划的公式：dp[i][k-1] + nums[k]nums[i-1]nums[j+1] + dp[k+1][j] , i<=k<=j。

但是动态规划时需要保证从小到大都能覆盖上，也就是控制 i 和 j 的差由小变大。这样 [i][j] 的范围就是从小变大。所以循环最外层应该是 [i][j] 的差从 1 到最大。

动态规划从小往大算，先找到小是如何定义的。在本题中也就是 i j 的差是从小开始，所以 i j 的差要从小变大，即放到了最外层循环。

代码

  class Solution {
      public int maxCoins(int[] nums) {
          //遍历每一长串 i 到 j，每次选中一个 k 当不打，打剩下的。这样这个问题就变成了 dp[i][k-1] + nums[k]*nums[i-1]*nums[j+1] + dp[k+1][j] , i<=k<=j
          int length = nums.length;
          int[] nums2 = new int[length+2]; //头尾附上 1
          for(int i=0;i<length;i++){
              nums2[i+1] = nums[i];
          }
          nums2[0] = 1;
          nums2[length+1] = 1;
          int[][] dp = new int[length+2][length+2]; //头尾附上 1
          for(int delta = 1;delta<=length;delta++){// 差值越来越大，逐渐拉大 i j 的距离。这样是由小变大走
              for(int i=1;i<=length-delta+1;i++){
                  int j = i+delta-1;
                  for(int k=i;k<=j;k++){
                      dp[i][j] = Math.max(dp[i][j],dp[i][k-1] + nums2[k]*nums2[i-1]*nums2[j+1] + dp[k+1][j]);
                  }
              }
          }
          return dp[1][length];
      }
  }

322 Coin Change （Medium）

题目描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
解法

一开始想到的用回溯法，然后想找最大的数，然后往里头加，直到超过之后找次大的数，但是超时了

优化之后，最大的数利用除法先填满，然后用小的塞空

回溯成功后改为动态规划，用动态规划数据记录0-amount每个值最小的组合数，dp[i] = Math.min(dp[i],dp[i-coins])。

代码

超时代码：

  public int coinChange(int[] coins, int amount) {
      if(coins.length==0||coins==null) return -1;
      Arrays.sort(coins);
      int index = coins.length-1;
      int[] ans = {Integer.MAX_VALUE};
      helper(coins,amount,index,0,ans);
      return ans[0]==Integer.MAX_VALUE?-1:ans[0];
  }

  public void helper(int[] coins,int amount,int index,int current,int[] ans){
      if(amount==0){
          ans[0] = Math.min(ans[0],current);
          return;
      }
      if(index == -1||amount<0) return;
      for(int i=index;i>=0;i--){
          helper(coins,amount-coins[i],index,current+1,ans);
      }
  }

成功的回溯法：

  public int coinChange(int[] coins, int amount) {
      if(coins.length==0||coins==null) return -1;
      Arrays.sort(coins);
      int index = coins.length-1;
      int[] ans = {Integer.MAX_VALUE};
      helper(coins,amount,index,0,ans);
      return ans[0]==Integer.MAX_VALUE?-1:ans[0];
  }

  public void helper(int[] coins,int amount,int index,int current,int[] ans){
      if(amount==0){
          ans[0] = Math.min(ans[0],current);
          return;
      }
      if(index == -1||amount<0) return;
      int coin = coins[index];
      for(int i=amount/coin;i>=0&&current+i<ans[0];i--){
          helper(coins,amount-i*coin,index-1,current+i,ans);
      }
  }

动态规划：

  public int coinChange(int[] coins, int amount) {
      if(amount==0) return 0;
      int[] dp = new int[amount+1];
      Arrays.sort(coins);
      for(int i=0;i<coins.length;i++){
          if(coins[i]>amount) break;
          dp[coins[i]] = 1;
      }
      for(int i=0;i<dp.length;i++){
          if(dp[i]!=0) continue;
          int minCom = Integer.MAX_VALUE;
          for(int j=0;j<coins.length;j++){
              if(i-coins[j]<0||dp[i-coins[j]]==0){
                  continue;
              }
              minCom = Math.min(minCom,dp[i-coins[j]]+1);
          }
          if(minCom!=Integer.MAX_VALUE){
              dp[i] = minCom;
          }
      }
      return dp[amount]==0?-1:dp[amount];
  }

337 House Robber III (Medium)

题目描述

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

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example:
解法

最一开始以为是层序遍历，1，3，5，7.。。和2，4，6，8。。。最后比谁大就行了，后来发现了上图4-1-2-3的示例，以为再加个dp[i]=max(dp[i-2],dp[i-3])+i层就行了，可是又发现了2-1-3-4的情况，然后自己放弃了。看了答案

用c写的话就很清楚，java看起来会比较晦涩。

代码

自己写的有问题的思路

  public int rob(TreeNode root) {
      if(root==null) return 0;
      Stack<TreeNode> stack1 = new Stack<>();
      Stack<TreeNode> stack2 = new Stack<>();
      int depth = countDep(root);
      if(depth==1) return root.val;
      int[] dp = new int[depth];
      stack1.push(root);
      int currentDep = 0;
      while(!stack1.isEmpty()||!stack2.isEmpty()){
          int result1=0;
          int result2=0;
          while(!stack1.isEmpty()){
              TreeNode tmp = stack1.pop();
              result1+=tmp.val;
              if(tmp.left!=null) stack2.push(tmp.left);
              if(tmp.right!=null) stack2.push(tmp.right);

          }
          if(currentDep==0){
              dp[currentDep++]=result1;
          }else if(currentDep==2){
              dp[currentDep++]=dp[0]+result1;
          }else{
              dp[currentDep]=Math.max(dp[currentDep-2],dp[currentDep-3])+result1;
              currentDep++;
          }
          if(stack2.isEmpty()) break;
          while(!stack2.isEmpty()){
              TreeNode tmp = stack2.pop();
              result2+=tmp.val;
              if(tmp.left!=null) stack1.push(tmp.left);
              if(tmp.right!=null) stack1.push(tmp.right);
          }
          if(currentDep==1){
              dp[currentDep++]=result2;
          }else{
              dp[currentDep]=Math.max(dp[currentDep-2],dp[currentDep-3])+result2;
              currentDep++;
          }
      }
      return Math.max(dp[depth-1],dp[depth-2]);
  }

  public int countDep(TreeNode tmp){
      if(tmp==null){
          return 0;
      }
      int left = countDep(tmp.left);
      int right = countDep(tmp.right);
      return Math.max(left,right)+1;
  }

正确解法：

  public int rob(TreeNode root) {
      int[] rootChild = {0,0};
      return helper(root,rootChild);
  }

  public int helper(TreeNode node,int[] child){
      if(node==null){
          return 0;
      }
      int[] leftChild = {0,0};
      int[] rightChild = {0,0};
      child[0] = helper(node.left,leftChild);
      child[1] = helper(node.right,rightChild);
      return Math.max(node.val+leftChild[0]+leftChild[1]+rightChild[0]+rightChild[1],child[0]+child[1]);
  }

c的话：这里的 helper 函数返回当前结点为根结点的最大 rob 的钱数，里面的两个参数l和r表示分别从左子结点和右子结点开始 rob，分别能获得的最大钱数。在递归函数里面，如果当前结点不存在，直接返回0。否则对左右子结点分别调用递归函数，得到l和r。另外还得到四个变量，ll和lr表示左子结点的左右子结点的最大 rob 钱数，rl 和 rr 表示右子结点的最大 rob 钱数。那么最后返回的值其实是两部分的值比较，其中一部分的值是当前的结点值加上 ll, lr, rl, 和 rr 这四个值，这不难理解，因为抢了当前的房屋，则左右两个子结点就不能再抢了，但是再下一层的四个子结点都是可以抢的；另一部分是不抢当前房屋，而是抢其左右两个子结点，即 l+r 的值，返回两个部分的值中的较大值即可，参见代码如下：

  class Solution {
  public:
      int rob(TreeNode* root) {
          int l = 0, r = 0;
          return helper(root, l, r);
      }
      int helper(TreeNode* node, int& l, int& r) {
          if (!node) return 0;
          int ll = 0, lr = 0, rl = 0, rr = 0;
          l = helper(node->left, ll, lr);
          r = helper(node->right, rl, rr);
          return max(node->val + ll + lr + rl + rr, l + r);
      }
  };

338 Counting Bits (Medium)

题目描述

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:

Input: 5
Output: [0,1,1,2,1,2]
解法

方法一：动态规划，dp[i] 是 i/2 的值（偶数），奇数时 +1。

方法二：找规律，对于2^N的数，末尾N-1位的重复规律，正好等于前N-1个数的重复规律，而这时只需要加1即可

代码

  class Solution {
      public int[] countBits(int num) {
          int[] dp = new int[num+1];//递推公式为 dp[i]=dp[i/2]+i&1
          for(int i=1;i<=num;i++){
              dp[i]=dp[i/2]+(i&1);//(& 运算优先级在 + - 后)
          }
          return dp;
      }
        
      public int[] countBits2(int num) {
          int[] res = new int[num+1];
          res[0] = 0;
          int base=1;
          while(base<=num){
              for(int i=base;i<base*2&&i<=num;i++){
                  res[i] = res[i-base]+1;
              }
              base *=2;
          }
          return res;
      }    
  }

347. Top K Frequent Elements （Medium）

题目描述

Given a non-empty array of integers, return the k most frequent elements.

Example:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
解法

用map记录数字和出现次数，通过优先队列对Map中出现次数进行排列，此处可以用lambda表达式简化代码，最后队列里取出n个数即可。

代码

  public List<Integer> topKFrequent(int[] nums, int k) {
      HashMap<Integer,Integer> map = new HashMap<>();
      for(int i=0;i<nums.length;i++){
          if(map.containsKey(nums[i])){
              int count = map.get(nums[i])+1;
              map.put(nums[i],count);
          }else{
              map.put(nums[i],1);
          }
      }
      PriorityQueue<Map.Entry> que = new PriorityQueue<Map.Entry>(new Comparator<Map.Entry>() {
          @Override
          public int compare(Map.Entry o1, Map.Entry o2) {
              System.out.println((int)o1.getValue());
              System.out.println((int)o2.getValue());
              return (int)o1.getValue()-(int)o2.getValue();
          }
      });
      for(Map.Entry entry:map.entrySet()){
          que.add(entry);
      }
      /**
       * 可以用lambda来写简化代码
       */
      /*PriorityQueue<Integer> que = new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
      for(Integer key:map.keySet()){
          queue.add(key);
      }*/
      List<Integer> res = new ArrayList<>();
      for(int i=0;i<k;i++){
          res.add((int)que.poll().getKey());
      }
      return res;
  }

394. Decode String （Medium）

题目描述

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Example:

s = “3[a]2[bc]”, return “aaabcbc”.
s = “3[a2[c]]”, return “accaccacc”.
s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.
解法

一层一层的解开中括号，找到第一个 ]，然后找到与之对应的括号起点和数字，展开后，递归，直到解开所有括号

代码

  public String decodeString(String s) {
      StringBuilder sb = new StringBuilder(s);
      helper(sb);
      return sb.toString();
  }

  public void helper(StringBuilder sb){
      int firstBracketEnd = -1;
      int firstBracketStart = -1;
      for(int i=0;i<sb.length();i++){
          if(sb.charAt(i)==']'){
              firstBracketEnd = i;
              break;
          }
      }
      if(firstBracketEnd==-1) return;
      for(int i=firstBracketEnd;i>=0;i--) {
          if (sb.charAt(i) == '[') {
              firstBracketStart = i;
              break;
          }
      }
      int repeatTimeIndex = -1;
      for(int i=firstBracketStart-1;i>=0;i--) {
          if(i==0) repeatTimeIndex=0;
          if (!Character.isDigit(sb.charAt(i))) {
              repeatTimeIndex = i+1;
              break;
          }
      }
      int repeatTime = Integer.parseInt(sb.substring(repeatTimeIndex,firstBracketStart));
      StringBuilder repeatString = new StringBuilder();
      for(int i=0;i<repeatTime;i++){
          repeatString.append(sb.substring(firstBracketStart+1,firstBracketEnd));
      }
      sb = sb.delete(repeatTimeIndex,firstBracketEnd+1);
      sb = sb.insert(repeatTimeIndex,repeatString.toString());
      helper(sb);
  }

406. Queue Reconstruction by Height （Medium）

题目描述

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Example:

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
解法

题意是对数组排序，使得每个位置的数组的第二个数满足在他前面比他身高（第一个数）高或相等的个数等于他的第二个数。

可以先对数组排序，使得个子高的在前，如果身高相等，让第二个数小的在前。这样比如一开始 [7，0] [7，1] [7，2] 就会排好，然后比如说后面有一个 [6，1]，说明只有一个大于或等于它，又因为比6大的已经全部取出。所以把它放在位置1，这样就变成[7，0] [6，1] [7，1] [7，2]。然后比如又有一个[5，0]，就放在位置0，以此类推。

代码

  class Solution {
      public int[][] reconstructQueue(int[][] people) {
          Arrays.sort(people,(o1,o2)->{
              if(o1[0]!=o2[0]){
                  return o2[0]-o1[0];
              }
              return o1[1]-o2[1];
          });
          LinkedList<int[]> list = new LinkedList<>();
          for(int i=0;i<people.length;i++){
              list.add(people[i][1],people[i]); //add(index,value)
          }
          return list.toArray(new int[0][]);
      }
  }

416. Partition Equal Subset Sum （Medium）

题目描述

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example:

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

解法

由于可以被分成两半，所以总和必定是偶数，总和奇数会出现0.5所以不可能

动态规划。每一次循环相当于截止到目前的数能组合到的数字。dp[j] = dp[j]

dp[j - nums[i]] (nums[i] <= j <= target)

代码

      public boolean canPartition(int[] nums) {
          int sum=0;
          for(int i=0;i<nums.length;i++){
              sum+=nums[i];
          }
          if((sum&1)==1) return false;
          int target = sum>>1;
          boolean[] dp = new boolean[target+1];
          dp[0]=true;
          for(int i=0;i<nums.length;i++){
              for(int j=target;j>=nums[i];j--){
                  dp[j] = dp[j]||dp[j-nums[i]];
              }
          }
          return dp[target];
      }

437. Path Sum III (Easy)

题目描述

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:
解法

对每一个节点dfs

代码

  public int pathSum(TreeNode root, int sum) {
      if(root==null){
          return 0;
      }
      return dfs(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
  }
    
  public int dfs(TreeNode root, int sum){
      int result =0;
      if(root==null){
          return 0;
      }
      if(root.val==sum){
          result++;
      }
      result += dfs(root.left,sum-root.val);
      result += dfs(root.right,sum-root.val);
      return result;
  }

438. Find All Anagrams in a String (Medium)

题目描述

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example:

Input: s: “cbaebabacd” p: “abc”
Output:
[0, 6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
解法

暴力方法，统计字符串p中字符出现的次数，然后从s的开头开始，每次找p字符串长度个字符，来验证字符个数是否相同

巧妙的方法是利用两个数组和 Arrays.equals(arr1, arr2) 方法。首先把要比较的序列存储到一个数组中，之后遍历长字符串，当遍历的长度大于寻找的字符串长度时，开始比较两个数组是否相等。这样相当于一直有一个离最近的滑动窗口，只要窗口相等时也就相等了。

代码

  public List<Integer> findAnagrams(String s, String p) {
      int lengthP = p.length();
      HashMap<Character,Integer> mapP = new HashMap<Character,Integer>();
      for(int i=0;i<lengthP;i++){
          if(mapP.containsKey(p.charAt(i))){
              int tmp = mapP.get(p.charAt(i))+1;
              mapP.put(p.charAt(i),tmp);
          }else{
              mapP.put(p.charAt(i),1);
          }
      }
      List<Integer> result = new ArrayList<>();
      for(int i=0;i<=s.length()-lengthP;i++){
          if(mapP.containsKey(s.charAt(i))){
              boolean valid = validAnagram(mapP,s.substring(i,i+lengthP));
              if(valid) result.add(i);
              while(i+lengthP<s.length()&&s.charAt(i)==s.charAt(i+lengthP)){
                  result.add(++i);
              }
          }
      }
      return result;
  }
  public boolean validAnagram(HashMap<Character,Integer> map, String s){
      HashMap<Character,Integer> mapP = new HashMap<>(map);
      for(int i=0;i<s.length();i++){
          if(mapP.containsKey(s.charAt(i))){
              int count = mapP.get(s.charAt(i))-1;
              if(count==0){
                  mapP.remove(s.charAt(i));
              }else{
                  mapP.put(s.charAt(i),count);
              }
          }else{
              return false;
          }
      }
      return mapP.size()==0?true:false;
  }

      public List<Integer> findAnagrams2(String s, String p) {
          char[] ss = s.toCharArray();
          char[] ps = p.toCharArray();
          List<Integer> list = new LinkedList<>();
          if(ss.length<ps.length) return list;
          int[] snum = new int[26];
          int[] pnum = new int[26];//都跟他比，他是基准值
          for(char ptemp:ps){
              pnum[ptemp-'a']++;
          }
          for(int i=0;i<ss.length;i++){
              snum[ss[i]-'a']++;
              if(i>=ps.length) snum[ss[i-ps.length]-'a']--;
              if(i>=ps.length-1 && Arrays.equals(snum,pnum)){
                  list.add(i-ps.length+1);
              }
          }
          return list;
      }

448. Find All Numbers Disappeared in an Array (Easy)

题目描述

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
解法

判断nums[i]的值在对应下标是否正确，如正确往下，不正确则交换

代码

  public List<Integer> findDisappearedNumbers(int[] nums) {
      for(int i=0;i<nums.length;i++){
          while(nums[i]!=nums[nums[i]-1]){
              swap(nums,i,nums[i]-1);
          }
      }
      List<Integer> result = new ArrayList<>();
      for(int i=0;i<nums.length;i++){
          if(nums[i]!=i+1){
              result.add(i+1);
          }
      }
      return result;
  }
    
  public void swap(int[] nums,int a,int b){
      int tmp = nums[a];
      nums[a] = nums[b];
      nums[b] = tmp;
  }

461. Hamming distance （Easy）

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

Example:

输入: x = 1, y = 4 输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
解法

汉明距离也就是找二进制后的不一样，自然想到了异或，异或后 0 就是不一样的。

代码2

  class Solution {
      public int hammingDistance(int x, int y) {
          //汉明距离也就是找二进制后的不一样，自然想到了异或，异或后 0 就是不一样的
          String s = Integer.toBinaryString(x^y);
          int res = 0;
          for(int i=0;i<s.length();i++){
              if(s.charAt(i)=='1') res++;
          }
          return res;
          //return Integer.bitCount(x ^ y); //其实有这种数 1 的方法
      }
  }

494. Target Sum （Medium）

题目描述

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

Example:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解法

第一种深度优先的方式，第二种动态规划

代码

  public int findTargetSumWays(int[] nums, int S) {
      int[] res ={0};
      helper(nums,S,res,0,0);
      return res[0];
  }
    
  public void helper(int[] nums,int S,int[] res,int index,int currentSum){
      if(index==nums.length){
          if(currentSum == S){
              res[0]++;
          }
          return;
      }
      helper(nums,S,res,index+1,currentSum+nums[index]);
      helper(nums,S,res,index+1,currentSum-nums[index]);
  }

``` java public int findTargetSumWays(int[] nums, int S) { int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; } if (S > sum || (sum + S) % 2 == 1) return 0; return subsetSum(nums, (sum + S) / 2); }

private int subsetSum(int[] nums, int S) { int[] dp = new int[S + 1]; dp[0] = 1;//C(0,0)=1 for (int i = 0; i < nums.length; i++) { for (int j = S; j >= nums[i]; j–) { dp[j] += dp[j - nums[i]]; } } return dp[S]; }

```

538. Change Binary Tree to Greater Tree (Easy)

题目描述

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

Example:
解法

因为二叉搜索树右边节点比左边大，所有题意就变成了节点加上他的所有右节点了。这样就是中序遍历的反着了。

代码

  class Solution {
      public TreeNode convertBST(TreeNode root) {
          Stack<TreeNode> stack = new Stack<>();
          TreeNode node = root;
          int val = 0;
          while(stack.size()>0||node!=null){
              while(node!=null){
                  stack.add(node);
                  node=node.right;
              }
              if(stack.size()>0){
                  node = stack.pop();
                  val+=node.val;
                  node.val = val;
                  node =node.left;
              }
          }
          return root;
      }

      int sum = 0;
      //递归方式，与中序遍历相反
      public TreeNode convertBST(TreeNode root) {
          if(root==null) return null;
          convertBST(root.right);
          sum += root.val;
          root.val = sum;
          convertBST(root.left);
          return root;
      }
  }

543. Diameter of Binary Tree （Easy）

题目描述

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example:
解法

注意找的是节点间连线，最长的线的值

代码2

  public int diameterOfBinaryTree(TreeNode root) {
      int[] result = {0};
      helper(root,result);
      return result[0];
  }
    
  public int helper(TreeNode node,int[] result){
      if(node==null){
          return 0;
      }
      int left = helper(node.left,result);
      int right = helper(node.right,result);
      result[0] = Math.max(result[0],left+right);
      return 1+Math.max(left,right);
  }

560. Subarray Sum Equals K （Medium）

题目描述

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example:

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
解法

前缀和。比如说 3-5 的值就可以用 1-5 的前缀和减去 1-2 的前缀和。
一开始想的是利用数组记录走到每一项的合，然后向前找。然后发现时间效率过低。
优化方式，用map存储当前的合的值，用目标-当前合，去map中找是否有出现过寻找的值，出现了几次。

代码2

  public int subarraySum(int[] nums, int k) {
      int[] numsSum = new int[nums.length+1];
      int sum=0;
      for(int i=0;i<nums.length;i++){
          sum+=nums[i];
          numsSum[i+1]=sum;
      }
      int result = 0;
      for(int i=nums.length;i>=0;i--){
          for(int j=0;j<i;j++){
              int tmp = numsSum[i]-numsSum[j];
              if(tmp==k) result++;
          }
      }
      return result;
  }            

  class Solution {
      public int subarraySum(int[] nums, int k) {
          Map<Integer, Integer> map = new HashMap<>();
          // 用前缀和的差求有没有连续的数到达这个数，比如说 1-5 减去 1-2 的值就是 3-5 的值。
          int sum = 0;
          int res = 0;
          map.put(0,1); // 控制当 sum 和 k 相等时可以增加一个
          for(int num:nums){
              sum+=num;
              int x = sum - k;//求出需要找到的前缀和
              Integer xNum = map.get(x);
              if(xNum!=null){
                  res += xNum;
              }
              Integer sumNum = map.get(sum);
              map.put(sum,sumNum==null?1:sumNum+1);
          }
          return res;
      }
  }

581. Shortest Unsorted Continuous Subarray (Easy)

题目描述

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解法

方法一：复制数组，找第一个和最后一个不一样的

方法二：设定两个指针，一个从头走，一个从尾走。从头遍历数组，头指针记录最大值，如果当前值小于记录的最大值，找到右边界，尾指针记录最小值，如果当前值大于最小值，则找到左边界。

代码

  public int findUnsortedSubarray(int[] nums) {
      if(nums==null||nums.length==0) return 0;
      int begin=-1,last=-1;
      int[] copyNums = nums.clone();
      Arrays.sort(copyNums);
      for(int i=0;i<nums.length;i++){
          if(copyNums[i]!=nums[i]){
              begin=i;
              break;
          }
      }
      for(int i=nums.length-1;i>=0;i--){
          if(copyNums[i]!=nums[i]){
              last=i;
              break;
          }
      }
      if(begin==-1&&last==-1) return 0;
      int result = last-begin+1;
      return result;
  }

  public int findUnsortedSubarray(int[] nums) {
      int left=-1,right=-1;
      int getBig=nums[0];
      int getSmall=nums[nums.length-1];
      for(int i=0;i<nums.length;i++){
          getBig=Math.max(nums[i],getBig);
          getSmall=Math.min(nums[nums.length-i-1],getSmall);
          if(getBig>nums[i]){
              right=i;
          }
          if(getSmall<nums[nums.length-i-1]){
              left=nums.length-i-1;
          }
      }
      if(left==-1&&right==-1) return 0;
      return right-left+1;
  }

617. Merge Two Binary Trees (Easy)

题目描述

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example:
解法

用 t1 做返回值递归，不断为 t1 设定左右节点。当任何一个节点为空时，返回另一个节点。

代码

  public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
      TreeNode result = helper(t1,t2);
      return result;
  }

  public TreeNode helper(TreeNode t1,TreeNode t2){
      if(t1==null&&t2==null){
          return null;
      }
      int v1 = t1==null?0:t1.val;
      int v2 = t2==null?0:t2.val;
      TreeNode node =new TreeNode(v1+v2);
      node.left = helper(t1==null?null:t1.left,t2==null?null:t2.left);
      node.right = helper(t1==null?null:t1.right,t2==null?null:t2.right);
      return node;
  }

  class Solution {
      public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
          if(t1==null&&t2==null) return null;
          if(t1==null){
              return t2;
          }
          if(t2==null){
              return t1;
          }
          t1.val += t2.val;
          t1.left = mergeTrees(t1.left,t2.left);
          t1.right = mergeTrees(t1.right,t2.right);
          return t1;
      }
  }

621. Task Scheduler (Medium)

题目描述

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

输入: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
解法

这题可以找规律做。分两种情况：首先是 AAAABBBBCCCDE n=3 -> ABXX ABXX ABXX AB 共 (最长位数的字符-1)*(n+1)+最长重复个数像这里最后一个 AB 就是重复个数所以+2。但如果是 AAAABBBBCCCDE n=2 -> ABX ABX ABX ABX 是 12 位，不够总位数，所以剩下的数字还得往后面补。

代码

  public int leastInterval(char[] tasks, int n) {
      // 有两种情况，一种是最长就是 tasks 的长度，即全打乱排列，像 AAAABBBBCCCDE n=2
      // ABXABXABXABX 是 12 位，不够所有的位数
      // 第二种是 AAAABBBBCCCDE n=3 ABXXABXXABXXAB 共 (最长位数的字符-1)*(n+1)+最长重复个数 像这里最后一个 AB 就是重复个数所以+2
      int[] taskNum = new int[26];
      for(char c:tasks){
          taskNum[c-'A']++;
      }
      Arrays.sort(taskNum);
      int repeat = 0;
      for(int i=25;i>=0;i--){
          if(taskNum[i]==taskNum[25]) repeat++;
      }
      return Math.max(tasks.length,(taskNum[25]-1)*(n+1)+repeat);
  }

647. Palindromic Substrings (Medium)

题目描述

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example:

输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.
解法

以字符串每个字符为中心往外扩展查看是否还是回文。需要注意中心有可能是奇数或者偶数，当奇数的时候，中心是一个字符，当偶数的时候，中心是两个字符。

牛逼的算法是马拉车算法，字符间穿插#，没学懂

代码

  public int countSubstrings(String s) {
      char[] cs = s.toCharArray();
      int count=0;
      for(int i=0;i<cs.length;i++){
          count+=judge(i,i,cs);
          count+=judge(i,i+1,cs);
      }
      return count;
  }
    
  public int judge(int left,int right,char[] cs){
      int count=0;
      while(left>=0&&right<cs.length&&cs[left--]==cs[right++]){
          count++;
      }
      return count;
  }

739. Daily Temperatures （Medium）

题目描述

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
解法

栈存温度对应的 index。这样当一个新的温度比当前栈顶的温度大的时候，就依次剔除栈内的温度并跟 index 对比获取天数。最后记着清空一次栈赋值 0 就可以了。

代码

  public int[] dailyTemperatures(int[] T) {
      Stack<Integer> stack = new Stack<>();
      int[] res = new int[T.length];
      for(int i=0;i<T.length;i++){
          while(!stack.isEmpty()&&T[stack.peek()]<T[i]){
              int index = stack.pop();
              res[index] = i-index;
          }
          stack.push(i);
      }
      while(!stack.isEmpty()){
          res[stack.pop()]=0;
      }
      return res;
  }