2. 两数相加

  1. ListNode virtualNode = new ListNode(0);
  2.         int flag=0;
  3.         ListNode temp=virtualNode;
  4.         while (l1!=null||l2!=null){
  5.             if(l1!=null&&l2!=null){
  6.                 int value=l1.val+l2.val+flag;
  7.                 temp.next=new ListNode(value%10);
  8.                 if(value>=10){
  9.                     flag=1;
  10.                 }else{
  11.                     flag=0;
  12.                 }
  13.                 temp=temp.next;
  14.                 l1=l1.next;
  15.                 l2=l2.next;
  16.             }else if(l1!=null&&l2==null){
  17.                 int value=l1.val+flag;
  18.                 temp.next=new ListNode(value%10);
  19.                 if(value>=10){
  20.                     flag=1;
  21.                 }else{
  22.                     flag=0;
  23.                 }
  24.                 temp=temp.next;
  25.                 l1=l1.next;
  26.             }else{
  27.                 int value=l2.val+flag;
  28.                 temp.next=new ListNode(value%10);
  29.                 if(value>=10){
  30.                     flag=1;
  31.                 }else{
  32.                     flag=0;
  33.                 }
  34.                 temp=temp.next;
  35.                 l2=l2.next;
  36.             }
  37.         }
  38.         if(flag==1){
  39.             temp.next=new ListNode(1);
  40.         }
  41.         return virtualNode.next;

3. 无重复字符的最长子串

  1. if(s.length()==0){
  2.   return 0;
  3. }
  4. Map<Character,Integer>map=new HashMap<>();
  5. char[] chars = s.toCharArray();
  6. map.put(chars[0],0);
  7. int[]dp=new int[s.length()];
  8. dp[0]=1;
  9. int res=1;
  10. for(int i=1;i<chars.length;i++){
  11.   if(map.containsKey(chars[i])){
  12.     dp[i]=Math.min(dp[i-1]+1,i-map.get(chars[i]));
  13.   }else{
  14.     dp[i]=dp[i-1]+1;
  15.   }
  16.   map.put(chars[i],i);
  17.   res=Math.max(res,dp[i]);
  18. }
  19. return res;

4. 寻找两个正序数组的中位数

  1. class Solution {
  2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3.         int totalLength=nums1.length+nums2.length;
  4.         if(totalLength%2==1){
  5.             return findRes(nums1,0,nums2,0,totalLength/2+1);
  6.         }else{
  7.            int res1= findRes(nums1,0,nums2,0,totalLength/2);
  8.            int res2= findRes(nums1,0,nums2,0,totalLength/2+1);
  9.            return (res1+res2)/2.0;
  10.         }
  11.     }
  12.     private int findRes(int[]nums1,int start1,int[]nums2,int start2,int k){
  13.         int length1=nums1.length-start1;
  14.         int length2=nums2.length-start2;
  15.         if(length1>length2){
  16.             return findRes(nums2,start2,nums1,start1,k);
  17.         }
  18.         if(length1==0){
  19.             return nums2[start2+k-1];
  20.         }
  21.         if(k==1){
  22.             return Math.min(nums1[start1],nums2[start2]);
  23.         }
  24.         int newStart1=start1+Math.min(length1,k/2)-1;
  25.         int newStart2=start2+Math.min(length2,k/2)-1;
  26.         if(nums1[newStart1]>nums2[newStart2]){
  27.             return findRes(nums1,start1,nums2,newStart2+1,k-(newStart2-start2+1));
  28.         }else{
  29.             return findRes(nums1,newStart1+1,nums2,start2,k-(newStart1-start1+1));
  30.         }
  31.     }
  32. }

5. 最长回文子串

  1. boolean[][]dp=new boolean[s.length()][s.length()];
  2.         int res=0;
  3.         String ans="";
  4.         for(int j=0;j<s.length();j++){
  5.             for(int i=0;i<=j;i++){
  6.                 if(s.charAt(i)==s.charAt(j)&&(j-i<2||dp[i+1][j-1])){
  7.                     dp[i][j]=true;
  8.                     if(j-i+1>res){
  9.                         res=j-i+1;
  10.                         ans=s.substring(i,j+1);
  11.                     }
  12.                 }
  13.             }
  14.         }
  15.         return ans;

10. 正则表达式匹配

  1. class Solution {
  2.     public boolean isMatch(String s, String p) {
  3.         boolean[][]dp=new boolean[p.length()+1][s.length()+1];
  4.         dp[0][0]=true;
  5.         for(int i=2;i<=p.length();i++){
  6.             if(p.charAt(i-1)=='*'&&dp[i-2][0]){
  7.                 dp[i][0]=true;
  8.             }
  9.         }
  10.         for(int i=1;i<=p.length();i++){
  11.             for(int j=1;j<=s.length();j++){
  12.                 if(p.charAt(i-1)=='.'&&dp[i-1][j-1]){
  13.                     dp[i][j]=true;
  14.                 }else if(p.charAt(i-1)=='*'){
  15.                     if(dp[i-1][j]||dp[i-2][j]){
  16.                         dp[i][j]=true;
  17.                     }else if((p.charAt(i-2)==s.charAt(j-1)||p.charAt(i-2)=='.')&&dp[i][j-1]) {
  18.                         dp[i][j] = true;
  19.                     }
  20.                 }else if(p.charAt(i-1)==s.charAt(j-1)&&dp[i-1][j-1]){
  21.                     dp[i][j]=true;
  22.                 }
  23.             }
  24.         }
  25.         return dp[dp.length-1][dp[0].length-1];
  26.     }
  27. }

15. 三数之和

  1. class Solution {
  2.     private List<List<Integer>>res=new ArrayList<>();
  3.     public List<List<Integer>> threeSum(int[] nums) {
  4.         if(nums.length<3){
  5.             return res;
  6.         }
  7.         Arrays.sort(nums);
  8.         for(int i=0;i<nums.length-2;i++){
  9.             if(nums[i]>0){
  10.                 break;
  11.             }
  12.             if(i>0&&nums[i]==nums[i-1]){
  13.                 continue;
  14.             }
  15.             int left=i+1;
  16.             int right=nums.length-1;
  17.             while (left<right){
  18.                 if(nums[i]+nums[left]+nums[right]<0){
  19.                     left++;
  20.                 }else if(nums[i]+nums[left]+nums[right]>0){
  21.                     right--;
  22.                 }else{
  23.                     res.add(Arrays.asList(nums[i],nums[left],nums[right]));
  24.                     while (left<right&&nums[right]==nums[right-1]){
  25.                         right--;
  26.                     }
  27.                     while (left<right&&nums[left]==nums[left+1]){
  28.                         left++;
  29.                     }
  30.                     right--;
  31.                     left++;
  32.                 }
  33.             }
  34.         }
  35.         return res;
  36.     }
  37. }

22. 括号生成

  1. class Solution {
  2.     private List<String>res=new ArrayList<>();
  3.     private StringBuilder sb=new StringBuilder();
  4.     public List<String> generateParenthesis(int n) {
  5.         backTrack(0,0,n);
  6.         return res;
  7.     }
  8.     private void backTrack(int left,int right,int n){
  9.         if(left==n&&right==n){
  10.             res.add(sb.toString());
  11.             return;
  12.         }
  13.         if(right>left){
  14.             return;
  15.         }
  16.         if(left<=n){
  17.             sb.append("(");
  18.             backTrack(left+1,right,n);
  19.             sb.deleteCharAt(sb.length()-1);
  20.         }
  21.         if(right<=n){
  22.             sb.append(")");
  23.             backTrack(left,right+1,n);
  24.             sb.deleteCharAt(sb.length()-1);
  25.         }
  26.     }
  27. }

23. 合并K个升序链表

  1. if(lists==null||lists.length==0){
  2.   return null;
  3. }
  4. PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
  5.   @Override
  6.   public int compare(ListNode o1, ListNode o2) {
  7.     return o1.val-o2.val;
  8.   }
  9. });
  10. for (ListNode list : lists) {
  11.   if(list!=null){
  12.     queue.add(list);
  13.   }
  14. }
  15. ListNode virtualNode = new ListNode(0);
  16. ListNode temp=virtualNode;
  17. while (!queue.isEmpty()){
  18.   ListNode node = queue.poll();
  19.   temp.next=node;
  20.   temp=temp.next;
  21.   if(node.next!=null) {
  22.     node=node.next;
  23.     queue.add(node);
  24.   }
  25. }
  26. return virtualNode.next;

31. 下一个排列

image.png

  1. int length=nums.length-1;
  2. for(int i=length;i>0;i--){
  3.   if(nums[i]>nums[i-1]){
  4.     Arrays.sort(nums,i,length+1);
  5.   }
  6.   for(int j=i;j<=length;j++){
  7.     if(nums[j]>nums[i-1]){
  8.       int temp=nums[i-1];
  9.       nums[i-1]=nums[j];
  10.       nums[j]=temp;
  11.       return;
  12.     }
  13.   }
  14. }
  15. Arrays.sort(nums);
  16. return;

32. 最长有效括号

  1. class Solution {
  2.     public int longestValidParentheses(String s) {
  3.         if(s.length()==0){
  4.             return 0;
  5.         }
  6.         char[] chars = s.toCharArray();
  7.         boolean[]dp=new boolean[chars.length];
  8.         Stack<Integer> stack = new Stack<>();
  9.         for(int i=0;i<chars.length;i++){
  10.             if(stack.isEmpty()){
  11.                 stack.push(i);
  12.             }else if(chars[i]==')'&&chars[stack.peek()]=='('){
  13.                 dp[stack.pop()]=true;
  14.                 dp[i]=true;
  15.             }else{
  16.                 stack.push(i);
  17.             }
  18.         }
  19.         int res=0;
  20.         int count=0;
  21.         for(int i=0;i<dp.length;i++){
  22.             if(dp[i]){
  23.                 count++;
  24.                 res=Math.max(res,count);
  25.             }else{
  26.                 count=0;
  27.             }
  28.         }
  29.         return res;
  30.     }
  31. }

33. 搜索旋转排序数组

  1. int left=0;
  2. int right=nums.length-1;
  3. int mid;
  4. while (left<=right){
  5.   mid=(left+right)/2;
  6.   if(target==nums[mid]){
  7.     return mid;
  8.   }
  9.   //前半部分有序，比如2345671
  10.   if(nums[left]<=nums[mid]){ //还存在2个数的情况，比如3 1
  11.     if(target>=nums[left]&&target<nums[mid]){
  12.       right=mid-1;
  13.     }else{
  14.       left=mid+1;
  15.     }
  16.     //后半部分有序，比如6712345
  17.   }else{
  18.     if(target<=nums[right]&&target>nums[mid]){
  19.       left=mid+1;
  20.     }else{
  21.       right=mid-1;
  22.     }
  23.   }
  24. }
  25. return -1;

34. 在排序数组中查找元素的第一个和最后一个位置

  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.         if(nums.length==0){
  4.             return new int[]{-1,-1};
  5.         }
  6.         int left=0;
  7.         int right=nums.length-1;
  8.         int mid=0;
  9.         while (left<=right){
  10.             mid=(left+right)/2;
  11.             if(nums[mid]==target){
  12.                 int start=mid;
  13.                 while (start>=0&&nums[start]==target){
  14.                     start--;
  15.                 }
  16.                 int end=mid;
  17.                 while (end<nums.length&&nums[end]==target){
  18.                     end++;
  19.                 }
  20.                 return new int[]{start+1,end-1};
  21.             }else if(target>nums[mid]){
  22.                 left=mid+1;
  23.             }else {
  24.                 right=mid-1;
  25.             }
  26.         }
  27.         return new int[]{-1,-1};
  28.     }
  29. }

48. 旋转图像

  1. if(matrix.length==1){
  2.   return;
  3. }
  4. int len=matrix.length;
  5. int temp;
  6. //对角线交换元素
  7. for(int i=0;i<len;i++){
  8.   for(int j=len-1;j>i;j--){
  9.     temp=matrix[i][j];
  10.     matrix[i][j]=matrix[j][i];
  11.     matrix[j][i]=temp;
  12.   }
  13. }
  14. for(int i=0;i<len/2;i++){
  15.   for(int j=0;j<len;j++){
  16.     temp=matrix[j][i];
  17.     matrix[j][i]=matrix[j][len-i-1];
  18.     matrix[j][len-i-1]=temp;
  19.   }
  20. }

75. 颜色分类

  1. //先使用2来填充，然后替换成1,0，并递增下标。
  2. int zero=0;
  3. int one=0;
  4. int temp;
  5. for(int i=0;i<nums.length;i++){
  6.   temp=nums[i];
  7.   nums[i]=2;
  8.   if(temp<=1){
  9.     nums[one]=1;
  10.     one++;
  11.   }
  12.   if(temp==0){
  13.     nums[zero]=0;
  14.     zero++;
  15.   }
  16.  }

76. 最小覆盖子串

  1. class Solution {
  2.     private Map<Character, Integer> map = new HashMap<>();
  3.     public String minWindow(String s, String t) {
  4.         if(s.length()<t.length()){
  5.             return "";
  6.         }
  7.         for (char c : t.toCharArray()) {
  8.             map.put(c,map.getOrDefault(c,0)+1);
  9.         }
  10.         int left=0;
  11.         int right=0;
  12.         int length=Integer.MAX_VALUE;
  13.         int start=0;
  14.         char[] chars = s.toCharArray();
  15.         while (right<chars.length){
  16.             if(map.containsKey(chars[right])){
  17.                 map.put(chars[right],map.get(chars[right])-1);
  18.             }
  19.             right++;
  20.             while (check(map)){
  21.                 if(right-left<length){
  22.                     start=left;
  23.                     length=right-left;
  24.                 }
  25.                 if(map.containsKey(chars[left])){
  26.                     map.put(chars[left],map.get(chars[left])+1);
  27.                 }
  28.                 left++;
  29.             }
  30.         }
  31.         if(length==Integer.MAX_VALUE){
  32.             return "";
  33.         }else{
  34.             return s.substring(start,start+length);
  35.         }
  36.     }
  37.     private boolean check(Map<Character,Integer>map){
  38.         for (Integer value : map.values()) {
  39.             if(value>0){
  40.                 return false;
  41.             }
  42.         }
  43.         return true;
  44.     }
  45. }

79. 单词搜索

  1. package Hot_100._79exist;
  3. class Solution {
  4.     private int[][]direction=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
  5.     public boolean exist(char[][] board, String word) {
  6.         boolean[][] vis = new boolean[board.length][board[0].length];
  7.         int index=0;
  8.         for(int row=0;row<board.length;row++){
  9.             for(int col=0;col<board[0].length;col++){
  10.                 if(board[row][col]==word.charAt(index)){
  11.                     vis[row][col]=true;
  12.                     if(backTrack(row,col,index+1,board,vis,word)){
  13.                         return true;
  14.                     }else{
  15.                         vis[row][col]=false;
  16.                     }
  17.                 }
  18.             }
  19.         }
  20.         return false;
  21.     }
  22.     private boolean backTrack(int row,int col,int index,char[][]board,boolean[][]vis,String word){
  23.         if(index==word.length()){
  24.             return true;
  25.         }
  26.         for (int[] ints : direction) {
  27.             int newRow=row+ints[0];
  28.             int newCol=col+ints[1];
  29.             if(newRow>=0&&newRow<board.length&&newCol>=0&&newCol<board[0].length&&!vis[newRow][newCol]) {
  30.                 if (word.charAt(index) == board[newRow][newCol]) {
  31.                     vis[newRow][newCol] = true;
  32.                     if (backTrack(newRow, newCol, index+1, board, vis, word)) {
  33.                         return true;
  34.                     }
  35.                     vis[newRow][newCol] = false;
  36.                 }
  37.             }
  38.         }
  39.         return false;
  40.     }
  41. }

84. 柱状图中最大的矩形

  1. int[]dp=new int[heights.length+2];
  2. for(int i=0;i<heights.length;i++){
  3.   dp[i+1]=heights[i];
  4. }
  5. Stack<Integer> stack = new Stack<>();
  6. int res=0;
  7. stack.push(0);
  8. for(int i=1;i<dp.length;i++){
  9.   while (dp[i]<dp[stack.peek()]){
  10.     Integer index = stack.pop();
  11.     int left=stack.peek();
  12.     int right=i;
  13.     int width=right-left-1;
  14.     int height=dp[index];
  15.     dp[index]=width*height;
  16.     res=Math.max(res,dp[index]);
  17.   }
  18.   stack.push(i);
  19. }
  20. return res;

86. 分隔链表

  1. ListNode moreVirtualNode = new ListNode(0);
  2. ListNode lessVirtualNode = new ListNode(0);
  3. ListNode moreTemp=moreVirtualNode;
  4. ListNode lessTemp=lessVirtualNode;
  5. ListNode temp=head;
  6. while (temp!=null){
  7.   if(temp.val<x){
  8.     lessTemp.next=temp;
  9.     lessTemp=lessTemp.next;
  10.   }else{
  11.     moreTemp.next=temp;
  12.     moreTemp=moreTemp.next;
  13.   }
  14.   temp=temp.next;
  15. }
  16. if(moreTemp.next!=null){
  17.   moreTemp.next=null;
  18. }else if(lessTemp.next!=null){
  19.   lessTemp.next=null;
  20. }
  21. lessTemp.next=moreVirtualNode.next;
  22. return lessVirtualNode.next;

114. 二叉树展开为链表

  1. //题目就是二叉的前序遍历使用迭代法
  2. if(root==null){
  3.   return;
  4. }
  5. Stack<TreeNode> stack = new Stack<>();
  6. stack.push(root);
  7. TreeNode virtualNode = new TreeNode(0);
  8. TreeNode temp=virtualNode;
  9. while (!stack.isEmpty()){
  10.   int size=stack.size();
  11.   for(int i=0;i<size;i++){
  12.     TreeNode node = stack.pop();
  13.     if(node.right!=null){
  14.       stack.push(node.right);
  15.     }
  16.     if(node.left!=null){
  17.       stack.push(node.left);
  18.     }
  19.     temp.left=null;
  20.     temp.right=node;
  21.     temp=temp.right;
  22.   }
  23. }
  24. root=virtualNode.right;

124. 二叉树中的最大路径和

  1. if(root==null){
  2.   return 0;
  3. }
  4. int left=Math.max(0,dfs(root.left));
  5. int right=Math.max(0,dfs(root.right));
  6. //单个子树的最大值
  7. res=Math.max(res,root.val+left+right);
  8. //返回给上层只能左右节点选一
  9. return root.val+Math.max(left,right);