2 两数相加 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 "" " 双指针 注意进位不为空 但两个数已经遍历完的情况 " "" class  Solution      public  ListNode addTwoNumbers (ListNode l1, ListNode l2)           ListNode res = new  ListNode(-1 );         ListNode cur = res;         int  jinwei = 0 ;         while  ((l1 != null  && l2 != null ) || jinwei != 0 ) {             int  l1Val = 0 , l2Val = 0 ;             if  (l1 != null ) {                 l1Val = l1.val;                 l1 = l1.next;             }             if  (l2 != null ) {                 l2Val = l2.val;                 l2 = l2.next;             }             int  sum = (l1Val + l2Val + jinwei) % 10 ;             jinwei = (l1Val + l2Val + jinwei) / 10 ;             cur.next = new  ListNode(sum);             cur = cur.next;         }         cur.next = l1 != null  ? l1 : l2;         return  res.next;     } } 
3  无重复字符的最长子串 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 "" " 双指针+map存数与index关系 方便查询是否出现过 " "" class  Solution      public  int  lengthOfLongestSubstring (String s)           if (s.length()<2 ) return  s.length();         int  left = 0 ;          int  res = 0 ;         HashMap<Character, Integer> map = new  HashMap<>();         for (int  i = 0 ; i<s.length(); i++){              if (map.containsKey(s.charAt(i))){                 left = Math.max(left, map.get(s.charAt(i))+1 );             }             map.put(s.charAt(i), i);             res = Math.max(res, i-left+1 );         }          return  res;     } } 
4  寻找两个正序数组的中位数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 "" " 二分 比较这两个数组的第K/2小的数字midVal1和midVal2的大小, 如果第一个数组的第K/2个数字小的话,那么说明我们要找的数字肯定不在nums1中的前K/2个数字,所以我们可以将其淘汰,将nums1的起始位置向后移动K/2个,并且此时的K也自减去K/2,调用递归。 反之,我们淘汰nums2中的前K/2个数字,并将nums2的起始位置向后移动K/2个,并且此时的K也自减去K/2,调用递归即可。 " "" class  Solution      public  double  findMedianSortedArrays (int [] nums1, int [] nums2)                    int  m=nums1.length,n=nums2.length;                                       int  k1=(m+n+1 )/2 ,k2=(m+n+2 )/2 ;          return  (findk(nums1,0 ,nums2,0 ,k1)+findk(nums1,0 ,nums2,0 ,k2))/2.0 ;     }               public  int  findk (int [] nums1,int  i,int [] nums2,int  j,int  k)                   if (i>=nums1.length) return  nums2[j+k-1 ];         if (j>=nums2.length) return  nums1[i+k-1 ];                  if (k==1 ) return  Math.min(nums1[i],nums2[j]);                  int  valid1=(i+k/2 -1 <nums1.length)?nums1[i+k/2 -1 ]:Integer.MAX_VALUE;         int  valid2=(j+k/2 -1 <nums2.length)?nums2[j+k/2 -1 ]:Integer.MAX_VALUE;         if (valid1<valid2) return  findk(nums1,i+k/2 ,nums2,j,k-k/2 );         else  return  findk(nums1,i,nums2,j+k/2 ,k-k/2 );     } } 
8 字符串转换整数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class  Solution      public  int  myAtoi (String s)           char [] str=s.toCharArray();         int  i=0 ;         int  len=str.length;         int  res=0 ;         int  flag=1 ;         while (i<len){             while (i<len&&str[i]==' ' ) i+=1 ;               if (i<len&&str[i]>='a' &&str[i]<='z' ) break ;                            if (i<len&&(str[i]=='+' ||str[i]=='-' ) {                 flag=str[i]=='-' ?-1 :1 ;                 i+=1 ;             }             while (i<len&&str[i]>='0' &&str[i]<='9' ) {                 int  digit=str[i]-'0' ;                                  if (res>(Integer.MAX_VALUE-digit)/10 ){                     if (flag<0 ) return  -2147483648 ;                     else  return  2147483647 ;                 }                 res=res*10 +str[i]-'0' ;                 i+=1 ;             }             break ;         }         return  res*flag;     } } 
11  盛最多水的容器 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 "" " 双指针  一开始ij指向两端  随后对应高度小的那个指针向内移动、 若height[i]<height[j]  i若固定不动,j向左移,则对应的水量一定小于原本的ij 若原本水量是height[i]*(j-i)  j移动后为j1的水量为min(height[i],height[j1])*(j1-i)必小于原来的          因为min(height[i],height[j1])<=height[i]              (j1-i)<(j-i) " "" class  Solution      public  int  maxArea (int [] height)           int  res=0 ;         int  i=0 ,j=height.length-1 ;         while (i<j){             res=Math.max(res,(Math.min(height[i],height[j])*(j-i)));                                                                 if (height[i]<height[j]) i++;              else  j--;         }         return  res;     } } 
15  三数之和 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 "" " 固定一个数  相当于求数组中是否存在两个数的和等于目标值 判断两数之和 用双指针+排序:     也是固定一个数下标为second 另一个数下标为third从最右边开始移动     因为排序过  所以nums[second]+nums[third]<nums[second+1]+nums[third]<nums[second+1]+nums[third+1] 所以third只要初始化一次即可  后续直接在上一个third的基础上继续往左移 注意跳过相同的数 " "" class  Solution      public  List<List<Integer>> threeSum(int [] nums) {         List<List<Integer>> res=new  LinkedList<>();         Arrays.sort(nums);          for (int  first=0 ;first<nums.length;first++){             if (first>0 &&nums[first]==nums[first-1 ]) continue ;              int  target=-nums[first];              int  third=nums.length-1 ;              for (int  second=first+1 ;second<nums.length;second++){                  if (second>first+1 &&nums[second]==nums[second-1 ]) continue ;                  while  (second<third&&nums[second]+nums[third]>target) third--;                  if (second==third) break ;                  if (nums[second]+nums[third]==target){                      List<Integer> tmp=new  LinkedList<>();                     tmp.add(nums[first]);                     tmp.add(nums[second]);                     tmp.add(nums[third]);                     res.add(tmp);                 }             }         }         return  res;     } } 
17  电话号码的字母组合 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 "" " 要全遍历 当然想到回溯 " "" class  Solution      Map<Character, String> phoneMap = new  HashMap<Character, String>() {{             put('2' , "abc" );             put('3' , "def" );             put('4' , "ghi" );             put('5' , "jkl" );             put('6' , "mno" );             put('7' , "pqrs" );             put('8' , "tuv" );             put('9' , "wxyz" );         }};     public  List<String> letterCombinations (String digits)            List<String> res = new  ArrayList<>();         if (digits.length()<1 ) return  res;         int  len = digits.length();         StringBuilder cur = new  StringBuilder();         backtrace(res, 0 , cur, digits);         return  res;     }     private  void  backtrace (List<String> res,int  index, StringBuilder cur, String digits)          if (index == digits.length()){             res.add(cur.toString());             return ;         }         String curStr = phoneMap.get(digits.charAt(index));         for (int  i = 0 ;i<curStr.length();i++){             cur.append(curStr.charAt(i));             backtrace(res, index+1 , cur, digits);             cur.deleteCharAt(index);         }     } } 
19  删除链表的倒数第N个节点 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 "" " 快慢指针  快指针先走n步 随后一起走  当快指针走到最后一个节点时,对应的慢指针指向要删除的节点的前一个节点 要注意假如要删除的是第一个指针 那直接返回head.next即可 " "" class  Solution      public  ListNode removeNthFromEnd (ListNode head, int  n)           ListNode fast=head;          ListNode slow=head;          while (n>0 ) {             fast=fast.next;             n-=1 ;         }         while (fast!=null &&fast.next!=null ){             fast=fast.next;             slow=slow.next;         }         if (fast==null ) return  slow.next;          slow.next=slow.next.next;         return  head;     } } 
20  有效的括号 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 用linkedlist模仿栈  因为linkedlist是双向链表 " "" class  Solution      public  boolean  isValid (String s)           LinkedList<Character> helper = new  LinkedList<>();         for (int  i = 0 ;i<s.length();i++){             char  c = s.charAt(i);             if (c == '('  || c=='['  || c=='{' ){                 helper.add(c);             }else {                 if (helper.isEmpty()) return  false ;                 if ((c == ')'  && helper.getLast()=='(' ) ||                 (c == ']'  && helper.getLast()=='[' ) ||                 (c == '}'  && helper.getLast()=='{' )){                     helper.removeLast();                     continue ;                 }                 return  false ;             }         }         return  helper.isEmpty();     } } 
21  合并两个有序链表 一、问题描述 二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 "" " 伪节点来统一空指针问题 " "" class  Solution      public  ListNode mergeTwoLists (ListNode l1, ListNode l2)           ListNode pHead = new  ListNode(-1 );         ListNode cur = pHead;         while (l1 != null  && l2 != null ){             if (l1.val < l2.val){                 cur.next = l1;                 l1 = l1.next;             }else {                 cur.next = l2;                 l2 = l2.next;             }             cur = cur.next;         }         cur.next = l1 == null  ? l2 : l1;          return  pHead.next;     } } 
22  括号生成 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 "" " 回溯  用两个计数器记录当前左括号和右括号的个数     如果左括号数量不大于n,我们可以放一个左括号。     如果右括号数量小于左括号的数量,我们可以放一个右括号。 左括号必然在右括号之前放  所以第一个判断条件在前。 " "" class  Solution      public  List<String> generateParenthesis (int  n)           List<String> res=new  ArrayList<>();         backtrace(res,new  StringBuilder(),0 ,0 ,n);         return  res;     }     public  void  backtrace (List<String> res,StringBuilder cur,int  open,int  close,int  max)          if (cur.length()==max*2 ){              res.add(cur.toString());         }                  if (open<max){             cur.append("(" );             backtrace(res,cur,open+1 ,close,max);             cur.deleteCharAt(cur.length()-1 );         }                  if (close<open){              cur.append(")" );             backtrace(res,cur,open,close+1 ,max);             cur.deleteCharAt(cur.length()-1 );         }     } } class  Solution      public  List<String> generateParenthesis (int  n)           List<String> res = new  ArrayList<String>();         generate(res, "" , 0 , 0 , n);         return  res;     }              public  void  generate (List<String> res , String ans, int  count1, int  count2, int  n)          if (count1 > n || count2 > n) return ;         if (count1 == n && count2 == n)  res.add(ans);         if (count1 >= count2){             String ans1 = new  String(ans);             generate(res, ans+"(" , count1+1 , count2, n);             generate(res, ans1+")" , count1, count2+1 , n);         }     } } 
23  合并k个有序链表 一、问题描述 二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 "" " k大的最小堆,k为lists的长度,每次弹出当前最小,然后把当前最小的next 若不为空 则入堆 " "" class  Solution      public  ListNode mergeKLists (ListNode[] lists)           PriorityQueue<ListNode> heap = new  PriorityQueue<>(new  Comparator<ListNode>(){             @Override              public  int  compare (ListNode o1, ListNode o2)                  return  o1.val - o2.val;             }         });         int  k = lists.length;         if (k<1 ) return  null ;         ListNode pHead = new  ListNode(-1 );         ListNode cur = pHead;         for (ListNode list : lists){             if (list == null ) continue ;             heap.add(list);         }         while (!heap.isEmpty()){             ListNode curMin = heap.poll();             if (curMin.next != null ){                   heap.add(curMin.next);             }             cur.next = curMin;             cur = curMin;         }         return  pHead.next;     } } 
31  下一个排列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 "" " 输出全排列的下一个排列 我们需要将一个左边的「较小数」与一个右边的「较大数」交换,以能够让当前排列变大,从而得到下一个排列。 同时我们要让这个「较小数」尽量靠右,而「较大数」尽可能小。当交换完成后,「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下,使变大的幅度尽可能小。 首先从后向前查找第一个顺序对 (i,i+1),满足 a[i]<a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。 如果找到了顺序对,那么在区间 [i+1,n) 中从后向前查找第一个元素 j满足a[i]<a[j]。这样「较大数」即为 a[j]。 交换 a[i]与 a[j],此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序,而无需对该区间进行排序。 " "" class  Solution      public  void  nextPermutation (int [] nums)           if (nums.length<2 ) return ;         int  i = nums.length - 2 ;         while (i>=0 ){             if (nums[i]<nums[i+1 ]){                 break ;             }             i--;         }         int  j = nums.length - 1 ;         if (i<0 ){              reverse(nums, 0 , nums.length-1 );             return ;         }         while (nums[j]<=nums[i]) j--;                  swap(nums, i, j);                  reverse(nums, i+1 , nums.length-1 );     }     private  void  reverse (int [] nums, int  left, int  right)          while (left<right){             swap(nums, left, right);             left++;             right--;         }     }     private  void  swap (int [] nums, int  i, int  j)          int  temp = nums[i];         nums[i] = nums[j];         nums[j] = temp;     } } 
32  最长有效括号 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class  Solution      public  int  longestValidParentheses (String s)                    int  left = 0 , right = 0 , res = 0 , startIdx = 0 ;         for (int  i=0 ;i<s.length();i++){             if (s.charAt(i)=='(' ) left++;             else { right++;                 if (right==left){                     res = Math.max(res, i-startIdx+1 );                 }                 if (right>left){                     startIdx = i+1 ;                       right = 0 ;                     left = 0 ;                 }             }         }                  left = 0 ;         right = 0 ;         startIdx = s.length()-1 ;         for (int  i=s.length()-1 ;i>=0 ;i--){             if (s.charAt(i)==')' ) right++;             else { left++;                 if (right==left){                     res = Math.max(res, startIdx-i+1 );                 }                 if (right<left){                     startIdx = i-1 ;                      right = 0 ;                     left = 0 ;                 }             }         }         return  res;     } } 
33  搜索旋转排序数组 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 "" " 如果中间的数小于最右边的数,则右半段是有序的, 若中间数大于最右边数,则左半段是有序的, 我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了 " "" class  Solution      public  int  search (int [] nums, int  target)           int  left = 0 , right = nums.length-1 ;         while (left<=right){             int  mid = (left+right)/2 ;             if (nums[mid]==target) return  mid;             else  if (nums[mid]<nums[right]){                 if (nums[mid]<target && target<=nums[right]) left = mid+1 ;                 else  right = mid - 1 ;             }else {                 if (nums[mid]>target && nums[left]<=target) right = mid - 1 ;                 else  left = mid + 1 ;              }         }         return  -1 ;     } } 
34 在排序数组中查找元素的第一个和最后一个位置 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 "" " 二分+双指针 " "" class  Solution      public  int [] searchRange(int [] nums, int  target) {         int  left = 0 , right = nums.length-1 ;         int [] res = new  int [2 ];         res[0 ] = -1 ;         res[1 ] = -1 ;         while (left<=right){             int  mid =left + (right-left)/2 ;             if (nums[mid] == target){                 left = mid-1 ;                 right = mid+1 ;                 while (left>=0 &&nums[left]==target) left--;                 while (right<nums.length&&nums[right]==target) right++;                 res[0 ] = left+1 ;                 res[1 ] = right-1 ;                 return  res;             }else {                 if (nums[mid]>target) right = mid - 1 ;                 else  left = mid + 1 ;             }         }         return  res;     } } 
42 接雨水 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 "" " 动态规划+双指针 " "" class  Solution      public  int  trap (int [] height)           int  ans = 0 ;         int  left = 0 , right = height.length - 1 ;         int  leftMax = 0 , rightMax = 0 ;         while  (left < right) {             leftMax = Math.max(leftMax, height[left]);             rightMax = Math.max(rightMax, height[right]);             if  (leftMax < rightMax) {                 ans += leftMax - height[left];                 ++left;             } else  {                 ans += rightMax - height[right];                 --right;             }         }         return  ans;     } } 
78  子集 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 "" " 从前往后遍历:遇到一个数就把所有子集加上该数组成新的子集,遍历完毕即是所有子集 " "" class  Solution      public  List<List<Integer>> subsets(int [] nums) {         List<List<Integer>> res = new  ArrayList<>();         res.add(new  ArrayList<>());          for  (int  i = 0 ; i < nums.length; i++) {            int  all = res.size();             for  (int  j = 0 ; j < all; j++) {                  List<Integer> tmp = new  ArrayList<>(res.get(j));                 tmp.add(nums[i]);                 res.add(tmp);             }         }         return  res;     } } "" " 回溯 " "" class  Solution      public  List<List<Integer>> subsets(int [] nums) {         List<List<Integer>> res=new  ArrayList<>();         res.add(new  ArrayList<>());         backtrace(res,new  ArrayList<>(),0 ,nums);         return  res;     }     public  void  backtrace (List<List<Integer>> res,List<Integer> cur,int  idx,int [] nums)          for (int  i=idx;i<nums.length;i++){             cur.add(nums[i]);             res.add(new  ArrayList<>(cur));             backtrace(res,cur,i+1 ,nums);             cur.remove(cur.size()-1 );         }     } } "" " 若包含重复元素 可以用hashset 自动去除重复子集 " "" class  Solution      public  List<List<Integer>> subsets(int [] nums) {         HashSet<ArrayList<Integer>> res=new  HashSet<>();         Arrays.sort(nums);         res.add(new  ArrayList<>());         backtrace(res,new  LinkedList<>(),0 ,nums);         return  new  ArrayList(res);     }     public  void  backtrace (HashSet<ArrayList<Integer>> res,List<Integer> cur,int  idx,int [] nums)          for (int  i=idx;i<nums.length;i++){             cur.add(nums[i]);             res.add(new  ArrayList<>(cur));             backtrace(res,cur,i+1 ,nums);             cur.remove(cur.size()-1 );         }     } } 
46  全排列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 "" " 回溯  用visited数组记录元素是否被访问过 " "" class  Solution      List<List<Integer>> res=new  ArrayList<>();     public  List<List<Integer>> permute(int [] nums) {         int [] visited=new  int [nums.length];         backtrace(res,new  ArrayList<>(),nums,visited);         return  res;     }     public  void  backtrace (List<List<Integer>> res,List<Integer> path,int [] nums,int [] visited)          if (path.size()==nums.length){              res.add(new  ArrayList<>(path));             return ;         }         for (int  i=0 ;i<nums.length;i++){              if (visited[i]==1 ) continue ;             path.add(nums[i]);              visited[i]=1 ;             backtrace(res,path,nums,visited);             path.remove(path.size()-1 );              visited[i]=0 ;         }     } } 
49  字母异位词分组 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 "" " 字母异位词每个字母出现的次数一致,于是拿字母与字母出现次数作为map 的key 比如eat ==>  a1e1t1    eeaatt ==> a2e2t2 " "" class  Solution      public  List<List<String>> groupAnagrams(String[] strs) {         Map<String, List<String>> map = new  HashMap<>();         for (String s : strs){             StringBuilder sb = new  StringBuilder();             int [] count = new  int [26 ];             for (int  i = 0 ;i<s.length();i++){                 count[s.charAt(i)-'a' ]+=1 ;             }             for (int  i=0 ;i<26 ;i++){                 if (count[i]>0 ){                     sb.append((char )('a' +i));                     sb.append(count[i]);                 }             }             String key = sb.toString();             List<String> temp = map.getOrDefault(key, new  ArrayList<String>());             temp.add(s);             map.put(key, temp);         }         return  new  ArrayList<List<String>>(map.values());     } } 
48  旋转图像 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 "" " 顺时针旋转90度=先水平翻转 再对角线翻转 " "" class  Solution      public  void  rotate (int [][] matrix)           int  m=matrix.length;         int  n=matrix[0 ].length;              for (int  i=0 ;i<m/2 ;i++){             for (int  j=0 ;j<n;j++){                 int  tmp=matrix[i][j];                 matrix[i][j]=matrix[m-i-1 ][j];                 matrix[m-i-1 ][j]=tmp;             }         }              for (int  i=0 ;i<m;i++){             for (int  j=i+1 ;j<n;j++){                 int  tmp=matrix[i][j];                 matrix[i][j]=matrix[j][i];                 matrix[j][i]=tmp;             }         }     } } 
39  组合总和  即可重复选择元素进行组合 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 "" " 回溯+去重 1、正常回溯不剪枝 利用hashset去重,每次把path先排序再加入hashset " "" class  Solution      public  List<List<Integer>> combinationSum(int [] candidates, int  target) {         HashSet<List<Integer>> res=new  HashSet<>();          backtrace(res,new  ArrayList<>(),0 ,candidates,target);         return  new  ArrayList<>(res);     }     public  void  backtrace (HashSet<List<Integer>> res,List<Integer> path,int  cur,int [] candidates,int  target)          if (cur==target){             List<Integer> tmp=new  ArrayList<>(path);             Collections.sort(tmp);              res.add(tmp);             return ;         }         if (cur>target) return ;         for (int  i=0 ;i<candidates.length;i++){              path.add(candidates[i]);             cur+=candidates[i];             backtrace(res,path,cur,candidates,target);             cur-=candidates[i];             path.remove(path.size()-1 );         }     } } "" " 2、对数组先排序 若和已大于target  后面的就不用再遍历了 因为一定更大 每次从begin开始遍历,不用倒回去 自然避免了重复 " "" class  Solution      List<List<Integer>> res=new  ArrayList<>();     public  List<List<Integer>> combinationSum(int [] candidates, int  target) {         Arrays.sort(candidates);          backtrace(new  ArrayList<>(),0 ,candidates,target,0 );         return  res;     }     public  void  backtrace (List<Integer> path,int  cur,int [] candidates,int  target,int  begin)          if (cur==target){             res.add(new  ArrayList<>(path));             return ;         }         for (int  i=begin;i<candidates.length;i++){             if (cur+candidates[i]<=target){                 path.add(candidates[i]);                 cur+=candidates[i];                 backtrace(path,cur,candidates,target,i);                 cur-=candidates[i];                 path.remove(path.size()-1 );             }             else  break ;          }      } } 
406  根据身高重建队列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 先按照身高降序 k升序进行排序 则k为该人的绝对位置 按照顺序插入结果队列中即可 " "" class  Solution      public  int [][] reconstructQueue(int [][] people) {        Arrays.sort(people, new  Comparator<int []>() {             @Override             public  int  compare (int [] o1, int [] o2)                  if (o1[0 ]!=o2[0 ]) return  o2[0 ]-o1[0 ];                else  return  o1[1 ]-o2[1 ];            }        });        List<int []> res=new  ArrayList<>();        for (int [] p:people){               res.add(p[1 ],p);        }        return  res.toArray(new  int [people.length][]);      } } 
238  除自身以外数组的乘积 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 遍历两次:     第一次用res数组存左乘积结果 res[i]=nums[0]*nums[1]*···*nums[i-1]     第二次用res数组存结果 即乘上右乘积的结果 res[i]=res[i]*nums[i+1]*... " "" class  Solution      public  int [] productExceptSelf(int [] nums) {         int  right=1 ;          int [] res=new  int [nums.length];         res[0 ]=1 ;          for (int  i=1 ;i<nums.length;i++){             res[i]=nums[i-1 ]*res[i-1 ];         }         for (int  i=nums.length-1 ;i>=0 ;i--){             res[i]=res[i]*right;              right=right*nums[i];          }         return  res;     } } 
208  实现Trie(前缀树) 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 "" " 前缀树是一种新的数据结构(又称字典树,前缀树,单词查找树 节点包含:     private boolean is_string=false;  //该节点是否是一个字符串的结尾     private Trie next[]=new Trie[26]; //该节点链接的二十六个字母指针(字母映射表) " "" public  class  Trie      private  boolean  is_string=false ;     private  Trie next[]=new  Trie[26 ];     public  Trie ()                     public  void  insert (String word)          Trie root=this ;         char  w[]=word.toCharArray();         for (int  i=0 ;i<w.length;++i){             if (root.next[w[i]-'a' ]==null )root.next[w[i]-'a' ]=new  Trie();             root=root.next[w[i]-'a' ];         }         root.is_string=true ;     }               public  boolean  search (String word)          Trie root=this ;         char  w[]=word.toCharArray();         for (int  i=0 ;i<w.length;++i){             if (root.next[w[i]-'a' ]==null )return  false ;             root=root.next[w[i]-'a' ];         }         return  root.is_string;     }          public  boolean  startsWith (String prefix)          Trie root=this ;         char  p[]=prefix.toCharArray();         for (int  i=0 ;i<p.length;++i){             if (root.next[p[i]-'a' ]==null )return  false ;             root=root.next[p[i]-'a' ];         }         return  true ;     } } 
56  合并区间 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 "" " 先把各区间按照开始排序 假如两个区间有重叠,则取最远的end作为新数组的end即可 假如没有重叠,则前面的start end构成一个区间,新的区间的start end由后面区间构成 " "" class  Solution       public  static  int [][] merge(int [][] intervals) {         Arrays.sort(intervals, Comparator.comparingInt(a -> a[0 ]));          List<int []> res = new  ArrayList<>();         int  start = intervals[0 ][0 ];         int  end = intervals[0 ][1 ];         for (int  i = 1 ;i<intervals.length;i++){               if (intervals[i][0 ]>end){                   res.add(new  int []{start, end});                 start = intervals[i][0 ];             }             end = Math.max(end,intervals[i][1 ]);         }         res.add(new  int []{start,end});         return   res.toArray(new  int [res.size()][2 ]);     } } 
62  不同路径 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 动态规划f(i,j)=f(i−1,j)+f(i,j−1) 当i=0或j=0的时候,只有一条路径 " "" class  Solution      public  int  uniquePaths (int  m, int  n)           int [][] dp = new  int [m][n];         dp[0 ][0 ] = 0 ;         for (int  i=0 ;i<m;i++){             for (int  j=0 ;j<n;j++){                 if (i==0 ||j==0 ){                     dp[i][j] = 1 ;                 }else {                     dp[i][j] = dp[i-1 ][j] + dp[i][j-1 ];                 }             }         }         return  dp[m-1 ][n-1 ];     } } 
64  最小路径和 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 "" " 动态规划  不过要注意初始化边界的时候:     dp[i][0]=dp[i-1][0]+grid[i][0];     dp[0][j]=dp[0][j-1]+grid[0][j]; 是累加的不是直接=grid[0][j] " "" class  Solution      public  int  minPathSum (int [][] grid)           int [][] dp=new  int [grid.length][grid[0 ].length];         dp[0 ][0 ]=grid[0 ][0 ];         for (int  i=1 ;i<grid.length;i++){             dp[i][0 ]=dp[i-1 ][0 ]+grid[i][0 ];         }         for (int  j=1 ;j<grid[0 ].length;j++){             dp[0 ][j]=dp[0 ][j-1 ]+grid[0 ][j];         }         for (int  i=1 ;i<grid.length;i++){             for (int  j=1 ;j<grid[0 ].length;j++){                 dp[i][j]=Math.min(dp[i-1 ][j],dp[i][j-1 ])+grid[i][j];             }         }         return  dp[grid.length-1 ][grid[0 ].length-1 ];     } } 
75  最小路径和 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 "" " 三路快排 " "" class  Solution      public  void  sortColors (int [] nums)           int  left = 0 ;         int  right = nums.length-1 ;         while (left<=right&&nums[left]==0 ) left++;         while (right>=left&&nums[right]==2 ) right--;         for (int  idx =left;idx<=right;idx++){             while (idx<=right && nums[idx] == 2 ){                   swap(nums, idx, right);                 right--;             }             if (nums[idx]==0 ){                 swap(nums, idx ,left);                 left++;             }         }     }     private  void  swap (int [] nums, int  i ,int  j)          int  temp = nums[i];         nums[i] = nums[j];         nums[j] = temp;     } } 
148  排序列表 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 "" " 时间复杂度nlogn 那只能堆排序 归并排序 快排(最差n2) 常数级复杂度 那就只能归并排序 自顶向下的归并排序一般用递归 空间复杂度为n  所以要用自底向上的归并排序方法:     1、首先求得链表的长度length,然后将链表拆分成子链表进行合并。     2、用subLength 表示每次需要排序的子链表的长度,初始时subLength=1。     每次将链表拆分成若干个长度为subLength 的子链表(最后一个子链表的长度可以小于subLength),按照每两个子链表一组进行合并,合并后即可得到若干个长度为subLength×2 的有序子链表(最后一个子链表的长度可以小于2subLength×2)。     3、将subLength 的值加倍,重复第 2 步,对更长的有序子链表进行合并操作,直到有序子链表的长度大于或等于length,整个链表排序完毕。 " "" class  Solution      public  ListNode sortList (ListNode head)           if  (head == null ) {             return  head;         }         int  length = 0 ;         ListNode node = head;         while  (node != null ) {              length++;             node = node.next;         }         ListNode dummyHead = new  ListNode(0 , head);         for  (int  subLength = 1 ; subLength < length; subLength <<= 1 ) {             ListNode prev = dummyHead, curr = dummyHead.next;              while  (curr != null ) {                 ListNode head1 = curr;                 for  (int  i = 1 ; i < subLength && curr.next != null ; i++) {                     curr = curr.next;                 }                 ListNode head2 = curr.next;                  curr.next = null ;                  curr = head2;                 for  (int  i = 1 ; i < subLength && curr != null  && curr.next != null ; i++) {                     curr = curr.next;                 }                 ListNode next = null ;                 if  (curr != null ) {                     next = curr.next;                     curr.next = null ;                  }                 ListNode merged = merge(head1, head2);                 prev.next = merged;                  while  (prev.next != null ) {                     prev = prev.next;                   }                 curr = next;              }         }         return  dummyHead.next;     }     public  ListNode merge (ListNode head1, ListNode head2)           ListNode dummyHead = new  ListNode(0 );         ListNode temp = dummyHead, temp1 = head1, temp2 = head2;         while  (temp1 != null  && temp2 != null ) {             if  (temp1.val <= temp2.val) {                 temp.next = temp1;                 temp1 = temp1.next;             } else  {                 temp.next = temp2;                 temp2 = temp2.next;             }             temp = temp.next;         }         if  (temp1 != null ) {             temp.next = temp1;         } else  if  (temp2 != null ) {             temp.next = temp2;         }         return  dummyHead.next;     } } "" " 自顶向下的归并 利用快慢指针得到中间节点 一个走两步 一个走一步 " "" class  Solution      public  ListNode sortList (ListNode head)           if (head==null  || head.next==null ) return  head;         ListNode slow = head, fast = head.next;         while (fast!=null  && fast.next!=null ){             slow = slow.next;             fast = fast.next.next;         }         ListNode head1 = slow.next;         slow.next = null ;                  return  merge(sortList(head),sortList(head1));     }     public  ListNode merge (ListNode head1, ListNode head2)           ListNode dummyHead = new  ListNode(0 );         ListNode temp = dummyHead, temp1 = head1, temp2 = head2;         while  (temp1 != null  && temp2 != null ) {             if  (temp1.val <= temp2.val) {                 temp.next = temp1;                 temp1 = temp1.next;             } else  {                 temp.next = temp2;                 temp2 = temp2.next;             }             temp = temp.next;         }         if  (temp1 != null ) {             temp.next = temp1;         } else  if  (temp2 != null ) {             temp.next = temp2;         }         return  dummyHead.next;     } } 
287  寻找重复数 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 "" " Floyd算法 龟兔赛跑 线性的时间复杂度 常数级的空间复杂度 一个fast指针每次走两步,一个slow指针每次走一步 终会在不是起点的地方相遇 相遇后slow回到起点  两个一起每次走一步  最终相与的点就是环入口 " "" class  Solution      public  int  findDuplicate (int [] nums)           int  slow=0 ,fast=0 ;         while (true ){             fast=nums[nums[fast]];             slow=nums[slow];             if (fast==slow){                 slow=0 ;                 while  (slow!=fast){                     slow=nums[slow];                     fast=nums[fast];                 }                 return  slow;             }         }     } } 
283  寻找重复数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 "" " 1、双指针 i指向第一个零 j指向为整理的第一个非零 交换即可 " "" class  Solution      public  void  moveZeroes (int [] nums)           int  i=0 ,j=0 ;         while (i<nums.length){             while (i<nums.length&&nums[i]!=0 ) i++;              while (j<nums.length&&nums[j]==0 ) j++;             if (j==nums.length||i==nums.length) return ;             if (i<j){                 int  temp=nums[j];                 nums[j]=nums[i];                 nums[i]=temp;              }             j++;         }     } } "" " 2、双指针 更好 因为末尾都是零 只需要把非零的全部移到前面即可(直接覆盖) 后面的用零覆盖 " "" class  Solution      public  void  moveZeroes (int [] nums)           int  j = 0 ;         for  (int  i = 0 ; i < nums.length; i++) {             if  (nums[i] != 0 ) {                 nums[j++] = nums[i];             }         }         while  (j<nums.length){             nums[j++]=0 ;         }     } } 
448  找到所有数组中消失的数字 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 "" " 利用数的范围都在1~n  将nums[nums[i]-1]转负数  nums[i]仍为正数的 那i+1就是没出现的 注意下标从0开始 " "" class  Solution      public  List<Integer> findDisappearedNumbers (int [] nums)           List<Integer> res=new  ArrayList<>();         int  len=nums.length;         for (int  i=0 ;i<len;i++){             int  tmp=Math.abs(nums[i])-1 ;             if (nums[tmp]>0 ) nums[tmp]=-nums[tmp];         }         for (int  i=0 ;i<len;i++){             if (nums[i]>0 ) res.add(i+1 );         }         return  res;     } } 
160  相交链表 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 "" " 1、神之方法:定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差) 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度   时间复杂度m(a的长度减去公共的)+n(b的长度减去公共的)+p(公共的) " "" public  class  Solution      public  ListNode getIntersectionNode (ListNode headA, ListNode headB)           ListNode pa=headA,pb=headB;         if (pa==null ||pb==null ) return  null ;         while  (pa!=pb){             pa=pa==null ?headB:pa.next;             pb=pb==null ?headA:pb.next;         }         return  pa;     } } "" " 2、分别计算两者的长度len_a,len_b 然后长的先走abs(len_a-len_b)步 随后a,b两者一起走,相交点就是交点 时间复杂度max(a+b)+abs(a-b)+min(a,b)-p " "" public  class  Solution      public  ListNode getIntersectionNode (ListNode headA, ListNode headB)           ListNode pa=headA;         ListNode pb=headB;         int  len_A=0 ;         int  len_B=0 ;         while (pa!=null ){             pa=pa.next;             len_A+=1 ;         }         while (pb!=null ){             pb=pb.next;             len_B+=1 ;         }         pa=headA;         pb=headB;         if (len_A>=len_B){             int  count=len_A-len_B;             while (count>0 ){                 pa=pa.next;                 count-=1 ;             }             while (pa!=pb){                 pa=pa.next;                 pb=pb.next;             }         }         else {             int  count=len_B-len_A;             while (count>0 ){                 pb=pb.next;                 count-=1 ;             }             while (pa!=pb){                 pa=pa.next;                 pb=pb.next;             }         }         return  pa;     } } 
java 正则表达式
(.)\1+ 表示 表示任意一个字符重复两次或两次以上(括号里的点表示任意字符,后面的 \1表示取第一个括号匹配的内容  ,后面的加号表示匹配1次或1次以上。二者加在一起就是某个字符重复两次或两次以上)
1 2 3 4 5 6 7 8 9 10 public  class  Main      public  static  void  main (String[] args)           Scanner scanner = new  Scanner(System.in);         int  line = scanner.nextInt();         scanner.nextLine();         for  (int  i = 0 ; i < line; i++) {             System.out.println(scanner.nextLine().replaceAll("(.)\\1+" ,"$1$1" ).replaceAll("(.)\\1(.)\\2" ,"$1$1$2" ));         }     } } 
万万没想到之抓捕孔连顺 
我们在字节跳动大街的N个建筑中选定3个埋伏地点。
为了相互照应,我们决定相距最远的两名特工间的距离不超过D。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 "" " 固定最左边的人i   让最右边的人移动 直到范围超出规定的distance   该段的埋伏方案=(j-i-1)*(long)(j-i-2)/2; 即组合公式 " "" import  java.util.Scanner;public  class  Main     public  static  void  main (String[] args)          Scanner input=new  Scanner(System.in);         int  numBuilding=input.nextInt();         int  maxLength=input.nextInt();         input.nextLine();         int [] distance=new  int [numBuilding];         for (int  k=0 ;k<numBuilding;k++){             distance[k]=input.nextInt();         }                  int  i=0 ,j=2 ;         long  res=0L ;         long  mod=99997867 ;         while (i<numBuilding-2 ){             while (j>=i+2 &&j<numBuilding&&(distance[j]-distance[i])<=maxLength){                 j+=1 ;             }             res+=(long )(j-i-1 )*(long )(j-i-2 )/2 ;             i+=1 ;         }         System.out.println(res%mod);     } } 
 
雀魂启动 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 import  java.util.*;"" " 回溯遍历 假如摸到某张牌 然后去判断是否能胡 判断是否能胡:     遍历 若该牌为雀头 是否能胡     若该牌为刻子 是否能胡     若该牌为顺子 是否能胡 最后若待匹配的牌为0  则能胡 " "" public  class  Main      private  void  sln ()           Scanner sc = new  Scanner(System.in);         int [] state = new  int [9 ];          int [] helpArr = new  int [9 ];         ArrayList<Integer> res = new  ArrayList<>();         for  (int  i = 0 ; i < 13 ; i++) {             int  num = sc.nextInt();             state[num - 1 ]++;         }         for  (int  i = 0 ; i < 9 ; i++) {             if  (state[i] < 4 ) {                 int  num = i + 1 ;                 System.arraycopy(state, 0 , helpArr, 0 , 9 );                 helpArr[i]++;                  if  (canHu(helpArr, 14 , false )) res.add(num);             }         }         if  (res.isEmpty()) System.out.println(0 );         else  {             StringBuffer sbf = new  StringBuffer();             sbf.append(res.get(0 ));             for  (int  i = 1 ; i < res.size(); i++) {                 sbf.append(" " );                 sbf.append(res.get(i));             }             System.out.println(sbf.toString());         }     }     "" "      arr 手上待匹配的牌     total 待匹配的牌数     hasHead  雀头已有     " ""     private  boolean  canHu (int [] arr, int  total, boolean  hasHead)           if  (total == 0 ) return  true ;         if  (!hasHead) {             for  (int  i = 0 ; i < 9 ; i++) {                 if  (arr[i] >= 2 ) {                     arr[i] -= 2 ;                      if  (canHu(arr, total - 2 , true )) return  true ;                     arr[i] += 2 ;                  }             }             return  false ;         } else  {             for  (int  i = 0 ; i < 9 ; i++) {                 if  (arr[i] > 0 ) {                     if  (arr[i] >= 3 ) {                         arr[i] -= 3 ;                          if  (canHu(arr, total - 3 , true )) return  true ;                         arr[i] += 3 ;                     }                     if  (i + 2  < 9  && arr[i + 1 ] > 0  && arr[i + 2 ] > 0 ) {                         arr[i]--;                         arr[i + 1 ]--;                         arr[i + 2 ]--;                         if  (canHu(arr, total - 3 , true )) return  true ;                         arr[i]++;                         arr[i + 1 ]++;                         arr[i + 2 ]++;                     }                 }             }         }         return  false ;     }     public  static  void  main (String[] args)           new  Main().sln();     } } 
链表k反转 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 "" " 头插法   按块反转  pre是前一块最后的节点 cur指向本块最后一个节点 cur.next==temp temp是待头插节点 " "" import  java.util.*;public  class  Solution           public  ListNode reverseKGroup  (ListNode head, int  k)                    if (head==null ||k==1 ||head.next==null ) return  head;         ListNode pc=head;         int  len=0 ;         while (pc!=null ){             len+=1 ;             pc=pc.next;         }         ListNode p=new  ListNode(-1 );         p.next=head;         ListNode pre=p;         ListNode cur=head;         ListNode temp;         for (int  i=0 ;i<len/k;i++){             for (int  j=1 ;j<k;j++){                 temp=cur.next;                 cur.next=temp.next;                 temp.next=pre.next;                 pre.next=temp;                               }             pre=cur;             cur=cur.next;         }         return  p.next;              } } 
 
判断链表是否有环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public  class  Solution      public  boolean  hasCycle (ListNode head)           if (head==null ||head.next==null ||head.next.next==null ) return  false ;         ListNode fast=head;         ListNode slow=head;         while (fast!=null &&fast.next!=null ){             fast=fast.next.next;             slow=slow.next;             if (slow==fast)  return  true ;         }         return  false ;     } } 
去重+排序 —TreeSet 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import  java.util.*;public  class  Main     public  static  void  main (String args[])          Scanner in =new  Scanner(System.in);         while (in.hasNext()){             int  len=in.nextInt();             Set<Integer> set=new  TreeSet<>();             for (int  i=0 ;i<len;i++){                 int  num=in.nextInt();                 set.add(num);             }             set.forEach((T)->{System.out.println(T);});                      }     } } 
十六进制转十进制 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import  java.util.*;public  class  Main     public  static  void  main (String args[])          Scanner in =new  Scanner(System.in);         while (in.hasNext()){             String s=in.nextLine();             int  len=s.length();             int  res=0 ;             int  t;             for (int  i=2 ;i<len;i++){                 char  temp=s.charAt(i);                 if (temp>='A' ) t=temp-'A' +10 ;                   else  t=temp-'0' ;                  res=res*16 +t;             }             System.out.println(res);         }     } } 
leecode 27 移除元素 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 "" " left为不含val的数组右侧下标 假如遍历到的idx>left代表中间有val,那就移动idx的元素到left  " "" class  Solution      public  int  removeElement (int [] nums, int  val)           int  left = 0 ;         for (int  i = 0 ;i<nums.length;i++){             if (nums[i]==val){                 continue ;             }             if (i>left){                 nums[left] = nums[i];             }             left++;         }         return  left;     } } 
leecode 45 跳跃游戏 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class  Solution      public  int  jump (int [] nums)           int  step = 0 ;         int  maxJumpedIdx = 0 ;         int  end = 0 ;         for (int  i = 0 ; i < nums.length-1 ; i++){             maxJumpedIdx = Math.max(maxJumpedIdx, i+nums[i]);              if (i==end){                   end = maxJumpedIdx;                 step+=1 ;             }         }         return  step;     } } 
leecode 55 跳跃游戏 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 class  Solution      public  boolean  canJump (int [] nums)           int  maxJumpIdx = 0 ;          for (int  i = 0 ;i<nums.length-1 ;i++){             if (i>maxJumpIdx) return  false ;              if (maxJumpIdx>=nums.length-1 ) return  true ;               maxJumpIdx = Math.max(maxJumpIdx, i+nums[i]);          }         return  maxJumpIdx>=nums.length-1 ;       } } 
leecode 76 跳跃游戏 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 "" " 滑动窗口 " "" class  Solution      public  String minWindow (String s, String t)           Map<Character, Integer> need = new  HashMap<>();          Map<Character, Integer> window = new  HashMap<>();          int  valid = 0 ,len = Integer.MAX_VALUE;           for (char  c : t.toCharArray()){             need.put(c, need.getOrDefault(c,0 )+1 );         }         int  start = 0 , left=0 , right = 0 ;           while (right<s.length()){               char  c = s.charAt(right);             right+=1 ;             if (need.containsKey(c)){                  int  c_count = window.getOrDefault(c, 0 ) + 1 ;                 window.put(c, c_count);                 if (c_count == need.get(c)){                      valid += 1 ;                 }             }                          while (need.size()==valid){                   if (right-left<len){                     start = left;                     len = right-left;                 }                 char  cl = s.charAt(left);                 left++;                 if (need.containsKey(cl)){                                           if (window.get(cl).equals(need.get(cl))){                         valid-=1 ;                     }                     window.put(cl, window.get(cl)-1 );                 }             }         }         return  len==Integer.MAX_VALUE?"" :s.substring(start, start+len);     } } 
leecode 123 买卖股票的最佳时机 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 "" " 分为k要遍历和 不需要遍历(0、1、无穷) k=2 动态规划 fb first buy sb second buy " "" class  Solution      public  int  maxProfit (int [] prices)           int  fb = Integer.MIN_VALUE, fs=0 ;         int  sb = Integer.MIN_VALUE, ss=0 ;         for (int  price:prices){             fb = Math.max(fb, -price);             fs = Math.max(fs, fb + price);             sb = Math.max(sb, fs - price);             ss = Math.max(ss, sb + price);         }         return  ss;     } } class  Solution      public  int  maxProfit (int [] prices)           int  k=2 ;         int  len=prices.length;         if (len<1 ) return  0 ;         int [][][] dp = new  int [prices.length][k+1 ][2 ];         for  (int  i = 0 ; i < prices.length; i++) {             for  (int  i1 = 0 ; i1 <= k; i1++) {                                  if (i==0 ){                     dp[0 ][i1][0 ] = 0 ;                     dp[0 ][i1][1 ] = -prices[0 ];                     continue ;                 }                 if (i1==0 ){                     dp[i][0 ][0 ] = 0 ;                     dp[i][0 ][1 ] = -prices[i];                     continue ;                 }                                  dp[i][i1][0 ] = Math.max(dp[i-1 ][i1][0 ], dp[i-1 ][i1][1 ]+prices[i]);                 dp[i][i1][1 ] = Math.max(dp[i-1 ][i1][1 ], dp[i][i1-1 ][0 ]-prices[i]);             }         }         return  dp[prices.length-1 ][k][0 ];     } } "" " k笔  0 <= k <= 100 交易次数 k 最多有多⼤呢? ⼀次交易由买⼊和卖出构成,⾄少需要两天。所以说有效的限制 k 应该不超过 n/2,如果超过,就没有约束作⽤了,相当于 k = +infinity。这种情况是之前解决过的。 " "" class  Solution      public  int  maxProfit (int  k, int [] prices)           int  len=prices.length;         if (len<1 ) return  0 ;         if  (k>len/2 ) return  maxProfit_infi(prices);                  int [][][] dp = new  int [prices.length][k+1 ][2 ];         for  (int  i = 0 ; i < prices.length; i++) {             for  (int  i1 = 0 ; i1 <= k; i1++) {                                  if (i==0 ){                     dp[0 ][i1][0 ] = 0 ;                     dp[0 ][i1][1 ] = -prices[0 ];                     continue ;                 }                 if (i1==0 ){                     dp[i][0 ][0 ] = 0 ;                     dp[i][0 ][1 ] = -prices[i];                     continue ;                 }                                  dp[i][i1][0 ] = Math.max(dp[i-1 ][i1][0 ], dp[i-1 ][i1][1 ]+prices[i]);                 dp[i][i1][1 ] = Math.max(dp[i-1 ][i1][1 ], dp[i][i1-1 ][0 ]-prices[i]);             }         }         return  dp[len-1 ][k][0 ];          }          public  int  maxProfit_infi (int [] prices)           int [] dp = new  int [2 ];         dp[0 ] = 0 ;         dp[1 ] = -prices[0 ];         for  (int  price : prices) {             dp[0 ] = Math.max(dp[0 ],dp[1 ]+price);             dp[1 ] = Math.max(dp[1 ],dp[0 ]-price);         }         return  dp[0 ];     } } "" " 动态规划 k无穷+手续费 第i天手上没有股票的最大利润=max(第i-1天没有股票的最大利润,第i-1天有股票的最大利润+第i天买了股票赚的钱(股票价格-手续费) 第i天手上有股票的最大利润=max(第i-1天有股票的最大利润,第i-1天没有股票的最大利润-第i天买股票的钱(股票价格) " "" class  Solution      public  int  maxProfit (int [] prices, int  fee)           int  have=-prices[0 ];         int  nohave=0 ;         for (int  i=1 ;i<prices.length;i++){             int  temp=have;             have=Math.max(have,nohave-prices[i]);             nohave=Math.max(nohave,temp+prices[i]-fee);         }         return  nohave;     } } 
leecode 309 买卖股票的最佳时机含冷冻期 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 "" " k = +infinity 并且含有冷冻期 动态规划 今天买入的 = max(昨天买入的,前天卖出的-今天的价格) 今天卖出的 = max(昨天卖出的,昨天买入的+今天的价格) " "" class  Solution      public  int  maxProfit (int [] prices)           int  lb = Integer.MIN_VALUE, ls = 0 ;         int  ps = 0 ;         for (int  price : prices){             int  temp = ls;              lb = Math.max(lb, ps-price);             ls = Math.max(ls, lb+price);             ps = temp;         }         return  ls;     } } 
leecode 139 单词拆分 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 "" " dp[i] 转移条件 dp[j]==true 并且 子串[j,i]存在于单词表中(遍历j) " "" class  Solution      public  boolean  wordBreak (String s, List<String> wordDict)           boolean [] dp = new  boolean [s.length()+1 ];         Arrays.fill(dp, false );         dp[0 ] = true ;         for (int  i=1 ;i<=s.length();i++){             for (int  j=i-1 ;j>=0 ;j--){                 if (dp[j] && wordDict.contains(s.substring(j,i))){                     dp[i] = true ;                     break ;                 }             }         }         return  dp[s.length()];     } } 
leecode 152 乘积最大子数组 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 class  Solution      public  int  maxProduct (int [] nums)           int  mxNum = nums[0 ], minNum = nums[0 ], res = nums[0 ];         for (int  i = 1 ; i<nums.length; i++){             int  tmpMax = mxNum, tmpMin = minNum;             mxNum = Math.max(tmpMax*nums[i], Math.max(tmpMin*nums[i], nums[i]));             minNum = Math.min(tmpMin*nums[i], Math.min(tmpMax*nums[i], nums[i]));             res = Math.max(res, mxNum);         }         return  res;     } } 
leecode 207 课程表 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 "" " 有向图判断是否有环   邻接表存 " "" class  Solution      public  boolean  canFinish (int  numCourses, int [][] prerequisites)                    int [] indegrees = new  int [numCourses];          Arrays.fill(indegrees, 0 );         Queue<Integer> queue = new  LinkedList<>();         List<List<Integer>> adjList = new  ArrayList<>();         for (int  i = 0 ;i<numCourses;i++){             adjList.add(new  ArrayList<>());         }         for (int [] rel : prerequisites){             indegrees[rel[0 ]]++;             adjList.get(rel[1 ]).add(rel[0 ]);         }                           for (int  i = 0 ;i<indegrees.length;i++){             if (indegrees[i]==0 ) queue.add(i);         }                  while (!queue.isEmpty()){             int  nowClass = queue.poll();             numCourses-=1 ;             for (int  nextClass : adjList.get(nowClass)){                 indegrees[nextClass]-=1 ;                 if (indegrees[nextClass]==0 ) queue.add(nextClass);             }         }                  return  numCourses==0 ;     } } 
leecode 292 Nim游戏 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 '' ' 要赢的话  你必须要拿到n-4 n-8 n-4*k 所以当n-4*k==0时 代表你必须要拿到第0颗石子 但你是先手 你拿到的必是第一颗石子  必失败  于是当石子个数为4的倍数的时候 你必输 堆中恰好有四块石头,你就会失败。因为在这种情况下不管你取走多少石头,总会为你的对手留下几块,使得他可以在游戏中打败你。因此,要想获胜,在你的回合中,必须避免石头堆中的石子数为 4 的情况。 同样地,如果有五块、六块、或是七块石头,你可以控制自己拿取的石头数,总是恰好给你的对手留下四块石头,使他输掉这场比赛。但是如果石头堆里有八块石头,你就不可避免地会输掉,因为不管你从一堆石头中挑出一块、两块还是三块,你的对手都可以选择三块、两块或一块,以确保在再一次轮到你的时候,你会面对四块石头。 ' '' class  Solution      public  boolean  canWinNim (int  n)           return  n%4 !=0 ;     } } 
leecode 300 最长递增子序列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 '' ' 1、动态规划 dp[i] 为考虑前 i 个元素,以第 i 个数字结尾的最长上升子序列的长度,注意 nums[i] 必须被选 dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i] 整个数组的最长上升子序列即所有dp[i] 中的最大值。 ' '' class  Solution      public  int  lengthOfLIS (int [] nums)           if  (nums.length == 0 ) {             return  0 ;         }         int [] dp = new  int [nums.length];         dp[0 ] = 1 ;         int  maxans = 1 ;         for  (int  i = 1 ; i < nums.length; i++) {             dp[i] = 1 ;             for  (int  j = 0 ; j < i; j++) {                 if  (nums[i] > nums[j]) {                     dp[i] = Math.max(dp[i], dp[j] + 1 );                 }             }             maxans = Math.max(maxans, dp[i]);         }         return  maxans;     } } "" " 贪心 + 二分 维护一个数组 d[i] ,表示长度为 ii 的最长上升子序列的末尾元素的最小值,用 len 记录目前最长上升子序列的长度,起始时 len 为 1,d[1]=nums[0]。                                                                 无序列表最关键的一句在于: 数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值,即在数组 1,2,3,4,5,6中长度为3的上升子序列可以为 1,2,3也可以为 2,3,4等等但是d[3]=3,即子序列末尾元素最小为3。 设当前已求出的最长上升子序列的长度为len(初始时为 11),从前往后遍历数组nums,在遍历到nums[i] 时: 如果nums[i]>d[len] ,则直接加入到 d 数组末尾,并更新 len=len+1; 否则,在 dd 数组中二分查找,找到第一个比nums[i] 小的数d[k] ,并更新 d[k+1]=nums[i] " "" 
leecode 322 零钱兑换 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 '' ' 动态规划 dp[i] 代表凑成总金额i所需的 最少的硬币个数 有转移方程: ' '' class  Solution      public  int  coinChange (int [] coins, int  amount)           int [] dp = new  int [amount+1 ];         Arrays.fill(dp, amount+1 );         dp[0 ] = 0 ;         for (int  i=1 ;i<=amount;i++){             for (int  j=0 ;j<coins.length;j++){                 if (i>=coins[j]){                     dp[i] = Math.min(dp[i],dp[i-coins[j]]+1 );                 }             }         }         return  dp[amount]>amount?-1 :dp[amount];     } } 
leecode 319 灯泡游戏 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 '' ' 也就是第一轮 切换全部开关 第二轮 切换为2的倍数的开关 第二轮 切换为3的倍数的开关 。。。 即每个开关会被切换k次 k为该开关的因子个数 比如第6个开关会被切换4次  最终为关闭状态 (1,2,3,6) 所以最终亮着的灯泡的特征是因子个数为奇数 也就是存在平方根  比如9(1,3,9)  那n有几个这样的数呢  有sqrt(n)个---(1*1,2*2,...,sqrt(n)*sqrt(n)) ' '' class  Solution      public  int  bulbSwitch (int  n)           return  (int )Math.sqrt(n);     } } 
leecode 331 验证二叉树的前序序列化 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 '' ' 二叉树的根节点入度为0,出度为2 非叶子节点 入度为1  出度为2 叶子节点 入度为1 出度为0 所有节点的入度和==出度和 ' '' class  Solution      public  boolean  isValidSerialization (String preorder)           int  diff = 1 ;         String[] arr = preorder.split("," );         for (int  i = 0 ; i < arr.length; i++){             diff-=1 ;             if (diff<0 ) return  false ;             if (!arr[i].equals("#" )){                 diff+=2 ;             }         }         return  diff == 0 ;     } } 
leecode 394 字符串解码 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 '' ' 字符串栈 存 待重复字符串 数字栈 存 重复次数 遇到[时入栈 遇到]时  ' '' class  Solution      public  String decodeString (String s)           Stack<String> strStack = new  Stack<>();         Stack<Integer> numStack = new  Stack<>();         StringBuilder str = new  StringBuilder();         int  mulit = 0 ;         for (char  c : s.toCharArray()){             if (Character.isDigit(c)){                 mulit = mulit*10 +c-'0' ;               }else  if (Character.isLetter(c)){                   str.append(c);             }else  if (c=='[' ) {                   strStack.push(str.toString());                 str = new  StringBuilder();                   numStack.push(mulit);                   mulit = 0 ;             }             else  {                                   int  count = numStack.pop();                  StringBuilder tmpStr = new  StringBuilder();                  tmpStr.append(strStack.pop());                  while (count>0 ){                      tmpStr.append(str.toString());                      count--;                  }                  str = tmpStr;               }         }         return  str.toString();     } } 
leecode 413 等差数列划分 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 '' ' 这道题主要是需要找到其规律,从小的例子出发,仔细观察,会发现当整个数组为(1, 2, 3, 4, 5, 6)的时候, 我们先取出前三个,(1, 2, 3)的等差数列的个数为1, (1, 2, 3, 4)的等差数列的个数为3, (1, 2, 3, 4, 5)的等差数列的个数为6, (1, 2, 3, 4, 5, 6)的等差数列个数为10, 以此类推我们可以很容易的发现在一个等差数列中加入一个数字,如果还保持着等差数列的特性,每次的增量都会加1,如果刚加进来的数字与原先的序列构不成等差数列,就将增量置为0,接下来继续循环,执行以上的逻辑即可. ' '' class  Solution      public  int  numberOfArithmeticSlices (int [] nums)           if (nums.length<3 ) return  0 ;         int  res = 0 ;         int  add = 0 ;         for (int  i = 1 ;i<nums.length-1 ;i++){             if (nums[i]-nums[i-1 ]==nums[i+1 ]-nums[i]){                 res+= (++add);             }else {                 add = 0 ;             }         }         return  res;     } } 
leecode 438 找到字符串中所有字母异位词 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 '' '  滑动窗口 ' '' class  Solution      public  List<Integer> findAnagrams (String s, String p)           List<Integer> res = new  ArrayList<>();         Map<Character, Integer> need = new  HashMap<>();         Map<Character, Integer> window = new  HashMap<>();         for (char  c : p.toCharArray()){             need.put(c, need.getOrDefault(c, 0 )+1 );         }         int  left = 0 , right = 0 , valid=0 ;         while (right<s.length()){             char  cr = s.charAt(right);             if (need.containsKey(cr)){                 window.put(cr, window.getOrDefault(cr, 0 )+1 );                 if (window.get(cr).equals(need.get(cr))){                     valid+=1 ;                 }             }             right++;             while (right-left>=p.length()){                 if (valid==need.size()){                       res.add(left);                 }                 char  cl = s.charAt(left);                  if (need.containsKey(cl)){                     if (need.get(cl).equals(window.get(cl))){                         valid-=1 ;                     }                     window.put(cl, window.get(cl)-1 );                 }                 left++;             }         }         return  res;     } } 
leecode 516 最长回文子序列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 '' ' 动态规划 if (s[i] == s[j])     // 它俩一定在最长回文子序列中     dp[i][j] = dp[i + 1][j - 1] + 2; else     // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长?     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); ' '' class  Solution      public  int  longestPalindromeSubseq (String s)           int  len = s.length();         int [][] dp = new  int [len][len];         for (int  i =len - 1  ;i>=0 ;i--){             dp[i][i] = 1 ;             for (int  j = i+1 ;j<len;j++){                 if (s.charAt(i) == s.charAt(j)){                     dp[i][j] = dp[i+1 ][j-1 ] + 2 ;                 }else {                     dp[i][j] = Math.max(dp[i][j-1 ],dp[i+1 ][j]);                 }             }         }         return  dp[0 ][len-1 ];     } } 
leecode 567 字符串的排列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 '' '  滑动窗口 ' '' class  Solution      public  boolean  checkInclusion (String s1, String s2)           Map<Character,Integer> needMap = new  HashMap<Character,Integer>();         Map<Character,Integer> windowsMap = new  HashMap<Character,Integer>();                  for (char  c : s1.toCharArray()){             needMap.put(c,needMap.getOrDefault(c,0 )+1 );         }                  int  left = 0 ,right = 0 ;                  int  valid = 0 ;         while (right <s2.length()){                          char  c = s2.charAt(right);                          right++;                          if (needMap.containsKey(c)){                 windowsMap.put(c,windowsMap.getOrDefault(c,0 )+1 );                                  if (windowsMap.get(c).equals(needMap.get(c))){                     valid++;                 }             }                          while (right - left >= s1.length()){                 if (valid == needMap.size()){                     return  true ;                 }                                  char  d = s2.charAt(left);                                  left++;                                  if (windowsMap.containsKey(d)){                     if (windowsMap.get(d).equals(needMap.get(d))){                         valid--;                     }                     windowsMap.put(d,windowsMap.getOrDefault(d,0 )-1 );                 }              }         }         return  false ;     } } 
leecode 583 两个字符串的删除操作 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 '' ' 动态规划 ' '' public  class  Solution      public  int  minDistance (String s1, String s2)           int [][] dp = new  int [s1.length() + 1 ][s2.length() + 1 ];         for (int  i=0 ;i<s1.length()+1 ;i++){             for (int  j=0 ;j<s2.length()+1 ;j++){                 if (i==0 ||j==0 ){                     dp[i][j] = i+j;                 }else  if (s1.charAt(i-1 )==s2.charAt(j-1 )) dp[i][j] = dp[i-1 ][j-1 ];                 else  dp[i][j] = Math.min(dp[i-1 ][j],dp[i][j-1 ])+1 ;             }         }         return  dp[s1.length()][s2.length()];     } } 
leecode 684 冗余连接 并查集 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class  Solution      public  int [] findRedundantConnection(int [][] edges) {         int [] parent = new  int [edges.length+1 ];          for (int  i=1 ;i<edges.length;i++){              parent[i] = i;         }         int [] res = new  int [2 ];         for (int [] curEdge : edges){             if (find(parent, curEdge[0 ])==find(parent, curEdge[1 ])){                                  res[0 ] = curEdge[0 ];                 res[1 ] = curEdge[1 ];             }else {                                  union(parent, curEdge[0 ], curEdge[1 ]);             }         }         return  res;     }          private  int  find (int [] parent, int  index)          if (parent[index]!=index){             return  find(parent, parent[index]);         }         return  index;     }          private  void  union (int [] parent, int  node1, int  node2)          int  parent1 = find(parent, node1);         int  parent2 = find(parent, node2);         if (parent1 != parent2){             parent[parent1] = parent2;         }     } } 
leecode 785 二分图 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public  boolean  isBipartite (int [][] graph)      int [] colors = new  int [graph.length];       Arrays.fill(colors, -1 );     for  (int  i = 0 ; i < graph.length; i++) {           if  (colors[i] == -1  && !isBipartite(i, 0 , colors, graph)) {             return  false ;         }     }     return  true ; } private  boolean  isBipartite (int  curNode, int  curColor, int [] colors, int [][] graph)      if  (colors[curNode] != -1 ) {         return  colors[curNode] == curColor;     }     colors[curNode] = curColor;     for  (int  nextNode : graph[curNode]) {         if  (!isBipartite(nextNode, 1  - curColor, colors, graph)) {             return  false ;         }     }     return  true ; } 
leecode 1312 让字符串成为回文串的最少插入次数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 当前字符串要变成回文,那只要把不一样的找出来就好了.即:求出反过来的字符串和当前字符串的最长公共子序列,然后减一下. " "" class  Solution      public  int  minInsertions (String s)           int  len = s.length();         int [][] dp = new  int [len][len];         for (int  i =len - 1  ;i>=0 ;i--){             dp[i][i] = 1 ;             for (int  j = i+1 ;j<len;j++){                 if (s.charAt(i) == s.charAt(j)){                     dp[i][j] = dp[i+1 ][j-1 ] + 2 ;                 }else {                     dp[i][j] = Math.max(dp[i][j-1 ],dp[i+1 ][j]);                 }             }         }         return  len - dp[0 ][len-1 ];     } } 
例1、二进制手表 
例2、N皇后问题 
例3、全排列 
例4、搜索 
例5、将数组拆分成斐波那契数列 
例1、二进制手表 github 401题 一、问题描述 
使用回溯 算法
一般:
dfs(全部可取节点borad,当前节点下标ij,节点状态visited,目标路径,path,已走到路径的下标idx)参考了labuladong大佬的算法框架 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 result = [] def backtrack (路径, 选择列表) :     if  满足结束条件:         result.add (路径)          return     for  选择 in 选择列表:         做选择         backtrack (路径, 选择列表)          撤销选择 private  void  backtrack ("原始参数" )           if  ("终止条件" ) {                  return ;     }     for  (int  i = "for循环开始的参数" ; i < "for循环结束的参数" ; i++) {                                    backtrack("新的参数" );                       } } 作者:sdwwld 链接:https: 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 
框架链接  
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 class  Solution (object ):    def  readBinaryWatch (self, num ):         """          :type num: int         :rtype: List[str]         """         nums=[8 ,4 ,2 ,1 ,32 ,16 ,8 ,4 ,2 ,1 ]           self.res=[]         track=[]           def  backtrack (nums,track,num ):             if  len(track)==num:                 h=0                  f=0                  for  i in  track:                     if  i <=3 :                         h+=nums[i]                        else :                         f+=nums[i]                    if  f<10 :                      temp=str(h)+":0" +str(f)                 else :                     temp=str(h)+":" +str(f)                 self.res.append(temp)                 return              for  i in  range(len(nums)):                 if  not  isValid(track,i):                     continue                  track.append(i)                 backtrack(nums,track,num)                 track.pop()         def  isValid (track,i ):             if  track==[]:                 return  True              if  i <=track[-1 ]:                  return  False              res=0              if  i<=3 :                       for  j in  track:                     if  j<=3 :                         res+=nums[j]                 res+=nums[i]                 if  res<12 :                      return  True                  else :                     return  False              else :                 for  j in  track:                     if  j>3 :                         res+=nums[j]                 res+=nums[i]                 if  res<60 :                       return  True                  else :                     return  False          backtrack(nums,track,num)         return  self.res 
例2、N皇后问题 github 51题 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 class  Solution      List<List<String>> res = new  ArrayList<>();          public  List<List<String>> solveNQueens(int  n) {                  char [][] board = new  char [n][n];         for  (char [] c : board) {             Arrays.fill(c, '.' );         }         backtrack(board, 0 );         return  res;     }     public  void  backtrack (char [][] board, int  row)                    if  (row == board.length) {             res.add(charToList(board));               return ;         }         int  n = board[row].length;                  for  (int  col = 0 ; col < n; col++) {                          if  (!isValid(board, row, col)) {                 continue ;             }                          board[row][col] = 'Q' ;                          backtrack(board, row + 1 );                          board[row][col] = '.' ;         }     }          public  boolean  isValid (char [][] board, int  row, int  col)           int  n = board.length;                  for  (int  i = 0 ; i < n; i++) {             if  (board[i][col] == 'Q' ) {                 return  false ;             }         }                  for  (int  i = row - 1 , j = col + 1 ; i >=0  && j < n; i--, j++) {             if  (board[i][j] == 'Q' ) {                 return  false ;             }         }                  for  (int  i = row - 1 , j = col - 1 ; i >= 0  && j >= 0 ; i--, j--) {             if  (board[i][j] == 'Q' ) {                 return  false ;             }         }         return  true ;     }     public  List charToList (char [][] board)           List<String> list = new  ArrayList<>();         for  (char [] c : board) {             list.add(String.valueOf(c));         }         return  list;     } } 
例3、全排列 一、问题描述 给定n,返回n的全排列
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class  Solution      List<List<Integer>> res=new  ArrayList<>();     public  List<List<Integer>> permute(int [] nums) {         int [] visited=new  int [nums.length];         backtrace(res,new  ArrayList<>(),nums,visited);         return  res;     }     public  void  backtrace (List<List<Integer>> res,List<Integer> path,int [] nums,int [] visited)          if (path.size()==nums.length){             res.add(new  ArrayList<>(path));             return ;         }         for (int  i=0 ;i<nums.length;i++){             if (visited[i]==1 ) continue ;             path.add(nums[i]);             visited[i]=1 ;             backtrace(res,path,nums,visited);             path.remove(path.size()-1 );             visited[i]=0 ;         }     } } 
47_1 全排列II 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 "" " 回溯+剪枝 private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res)     int[] nums:输入的待排列数组     int len:最终终止时数组长度     int depth:目前数组的长度     boolean[] used:记录哪些数字被使用过 使用过true 没使用过false     path:记录已选的数字     res:记录全部结果  " "" import  java.util.ArrayDeque;import  java.util.ArrayList;import  java.util.Arrays;import  java.util.Deque;import  java.util.List;public  class  Solution      public  List<List<Integer>> permuteUnique(int [] nums) {         int  len = nums.length;         List<List<Integer>> res = new  ArrayList<>();         if  (len == 0 ) {             return  res;         }                  Arrays.sort(nums);         boolean [] used = new  boolean [len];                  Deque<Integer> path = new  ArrayDeque<>(len);         dfs(nums, len, 0 , used, path, res);         return  res;     }     private  void  dfs (int [] nums, int  len, int  depth, boolean [] used, Deque<Integer> path, List<List<Integer>> res)           if  (depth == len) {             res.add(new  ArrayList<>(path));             return ;         }         for  (int  i = 0 ; i < len; ++i) {             if  (used[i]) {                 continue ;             }                                       if  (i > 0  && nums[i] == nums[i - 1 ] && !used[i - 1 ]) {                 continue ;             }             path.addLast(nums[i]);             used[i] = true ;             dfs(nums, len, depth + 1 , used, path, res);                          used[i] = false ;             path.removeLast();         }     } } ### 剑指 Offer 38 字符串的全排列 #### 一、问题描述  #### 二、具体代码 ```Java "" " 回溯+剪枝 " "" import  java.util.ArrayList;import  java.util.Arrays;import  java.util.List;public  class  Solution      public  String[] permutation(String s) {         int  len = s.length();         if  (len == 0 ) {             return  new  String[0 ];         }                  char [] charArr = s.toCharArray();                  Arrays.sort(charArr);                  StringBuilder path = new  StringBuilder();         boolean [] used = new  boolean [len];                  List<String> res = new  ArrayList<>();         dfs(charArr, len, 0 , used, path, res);                  return  res.toArray(new  String[0 ]);     }          private  void  dfs (char [] charArr,                       int  len,                      int  depth,                      boolean [] used,                      StringBuilder path,                      List<String> res)          if  (depth == len) {                          res.add(path.toString());             return ;         }         for  (int  i = 0 ; i < len; i++) {             if  (!used[i]) {                 if  (i > 0  && charArr[i] == charArr[i - 1 ] && !used[i - 1 ]) {                     continue ;                 }                 used[i] = true ;                 path.append(charArr[i]);                 dfs(charArr, len, depth + 1 , used, path, res);                                  path.deleteCharAt(path.length() - 1 );                 used[i] = false ;             }         }     } } 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ## 例4、搜索  ### 一、问题描述  ### 二、具体代码 ```Python class Solution:     def exist(self, board, word):         def check(i, j, k):  #判断从(i,j)处开始搜索 能否匹配到word[k:]             if board[i][j] != word[k]:                 return False             if k == len(word) - 1:                 return True             visited.add((i, j))             result = False             for di, dj in directions:                 newi, newj = i + di, j + dj                 if 0 <= newi < len(board) and 0 <= newj < len(board[0]):                     if (newi, newj) not in visited:                         if check(newi, newj, k + 1):                             result = True                             break             visited.remove((i, j))             return result         directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]         h, w = len(board), len(board[0])         visited = set()         for i in range(h):             for j in range(w):                 if check(i, j, 0):                     return True         return False 
例5、将数组拆分成斐波那契数列 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 "" " 回溯 " ""     public  List<Integer> splitIntoFibonacci (String S)           List<Integer> res = new  ArrayList<>();         backtrack(S.toCharArray(), res, 0 );         return  res;     }     public  boolean  backtrack (char [] digit, List<Integer> res, int  index)                    if  (index == digit.length && res.size() >= 3 ) {             return  true ;         }         for  (int  i = index; i < digit.length; i++) {                          if  (digit[index] == '0'  && i > index) {                 break ;             }                          long  num = subDigit(digit, index, i + 1 );                          if  (num > Integer.MAX_VALUE) {                 break ;             }             int  size = res.size();                          if  (size >= 2  && num > res.get(size - 1 ) + res.get(size - 2 )) {                 break ;             }             if  (size <= 1  || num == res.get(size - 1 ) + res.get(size - 2 )) {                                  res.add((int ) num);                                  if  (backtrack(digit, res, i + 1 ))                       return  true ;                                  res.remove(res.size() - 1 );              }         }         return  false ;     }          private  long  subDigit (char [] digit, int  start, int  end)           long  res = 0 ;         for  (int  i = start; i < end; i++) {             res = res * 10  + digit[i] - '0' ;         }         return  res;     } 
每日一题 0926 路径总和 II 
每日一题 0927 二叉搜索树的最近公共祖先 
每日一题 0928 填充每个节点的下一个右侧节点指针II 
每日一题 0930 二叉搜索树中的插入操作 
每日一题 1009 环形链表 
每日一题 1010 环形链表II 
每日一题 1011 分割等和子集 
每日一题 1014 查找常用字符 
每日一题 1016 有序数组的平方 
每日一题 1126 最大间距 
每日一题 1127 四数相加|| 
每日一题 1130 重构字符串 
每日一题 1201 重构字符串 
每日一题 1202 拼接最大数 
每日一题 1203 计数质数 
每日一题 1204 分割数组为连续子序列 
每日一题 1206 杨辉三角 
每日一题 1207 杨辉三角 
每日一题 1208 将数组拆分成斐波那契数列 
每日一题 1209 不同路径 
每日一题 1210 柠檬水找零 
每日一题 1211 Dota2 参议院 
每日一题 1212 摆动序列 
每日一题 1213 存在重复元素 
每日一题 1214 字母异位词分组 
每日一题 1215 单调递增的数字 
每日一题 1216 单词规律 
每日一题 1217 买卖股票的最佳时机含手续费 
每日一题 1218 找不同 
每日一题 1219 旋转图像 
每日一题 1221 使用最小花费爬楼梯 
每日一题 1222 二叉树的锯齿形层序遍历 
每日一题 1224 分发糖果 
每日一题 1225 分发饼干 
每日一题 1226 最大矩形 
每日一题 1227 同构字符串 
每日一题 1228 买卖股票的最佳时机 
每日一题 1229 按要求补齐数组 
每日一题 1230 最后一块石头的重量 
每日一题 0102 滑动窗口最大值 
每日一题 0103 分割链表 
每日一题 0104 斐波那契数列 
每日一题 0105 较大分组的位置 
每日一题 0106 除法求值 
每日一题 0107 省份数量 
每日一题 0108 旋转数组 
每日一题 0110 旋转数组 
每日一题 0115 移除最多的同行或同列石头 
每日一题 0122 旋转数组 
每日一题 0201 公平的糖果棒交换 
每日一题 0228 公平的糖果棒交换 
每日一题 0301 公平的糖果棒交换 
每日一题 0302 公平的糖果棒交换 
每日一题 0303 比特位计数 
每日一题 0304 俄罗斯套娃信封问题 
每日一题 0926 二叉树中和为某一值的路径 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ''' dfs到每个叶子节点 判断路径和是否等于sum ''' class  Solution (object ):    def  pathSum (self, root, sum ):         self.path=[]         self.res=[]         def  dfs (root,sum ):             if  root==None :                 return               self.path.append(root.val)               sum-=root.val             if  root.left==None  and  root.right==None  and  sum==0 :                 self.res.append(list(self.path))               dfs(root.left,sum)             dfs(root.right,sum)             self.path.pop()           dfs(root,sum)         return  self.res 
每日一题 0927 二叉搜索树的最近公共祖先 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ''' 若根节点的值在两个节点中间,则根节点为最近公共祖先 若根节点大于两者的最大值,则最近公共祖先在根节点的右子树中 反之 小于最小值,在左子树中 ''' class  Solution (object ):    def  lowestCommonAncestor (self, root, p, q ):         m=p.val          n=q.val         if  root==p or  root==q:             return  root         if  root.val < min(m,n):             return  self.lowestCommonAncestor(root.right,p,q)         elif  root.val >max(m,n):             return  self.lowestCommonAncestor(root.left,p,q)         else :             return  root 
每日一题 0928 填充每个节点的下一个右侧节点指针II 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ''' 每次遍历当前层时记录下一层的节点总数  省一个栈的层序遍历 ''' class  Solution (object ):    def  connect (self, root ):         if  root==None :             return  None          stack=[root]         now_count=1            next_count=0           while  stack:             p=stack.pop(0 )               now_count-=1              if   p.left:                 stack.append(p.left)                 next_count+=1              if   p.right:                 stack.append(p.right)                 next_count+=1              while   now_count>0 :                 cur=stack.pop(0 )                 p.next=cur                   p=cur                 now_count-=1                  if  p.left:                     stack.append(p.left)                     next_count+=1                  if  p.right:                     stack.append(p.right)                     next_count+=1              now_count=next_count             next_count=0          return  root 
每日一题 0930 二叉搜索树中的插入操作 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 ''' 每次遍历当前层时记录下一层的节点总数  省一个栈的层序遍历 ''' class  Solution (object ):    def  insertIntoBST (self, root, val ):         if  root==None :             root=TreeNode(val)         else :             if  root.val<val:                 root.right=self.insertIntoBST(root.right,val)             else :                 root.left=self.insertIntoBST(root.left,val)         return  root  
每日一题 1009 环形链表 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ''' 快慢指针 我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。 初始时,慢指针在位置 head,而快指针在位置 head.next。这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。 ''' class  Solution (object ):    def  hasCycle (self, head ):         """          :type head: ListNode         :rtype: bool         """         if  not  head or  not  head.next:             return  False          slow=head         fast=head.next         while  slow!=fast:             if  not  fast or  not  fast.next:                 return  False               slow=slow.next             fast=fast.next.next         return  True  
每日一题 1010 环形链表II 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ''' 快慢指针 分两步,第一步利用快慢指针判断是否是环形链表:     我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。     初始时,慢指针,快指针在位置 head,这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。 第二步是找环形的第一个节点:     当发现 slow 与 fast 相遇时,我们再额外使用一个指针ptr。起始,它指向链表头部;随后,它和slow 每次向后移动一个位置。最终,它们会在入环点相遇。 ''' class  Solution (object ):    def  detectCycle (self, head ):         if  not  head or  not  head.next:             return  None          slow=head         fast=head         while  slow.next and  fast.next and  fast.next.next and  slow.next!=fast.next.next:              slow=slow.next             fast=fast.next.next         if  slow.next==None  or  fast.next==None  or  fast.next.next==None   :                 return  None            pre=head         while  pre!=slow.next:               pre=pre.next             slow=slow.next         return  pre 
每日一题 1011 分割等和子集 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ''' 动态规划 转化为0-1背包问题   能否在一系列配重中选择子集,使其刚好为和的一半 dp[i][j] 代表在0~i的配重中选择子集 能否使其和等于j 因为存在j=0 的情况 所以数组大小开为[len(nums)][sum+1] 分为两种情况:     1、前i-1个配重已经可以满足和的要求  即不需要第i个配重-->>dp[i-1][j]      2、需要第i个配重  则前i-1个配重只需要满足和=j-nums[i]-->>dp[i-1][j-nums[i]] ''' class  Solution (object ):    def  canPartition (self, nums ):         all_sum=0          for  i in  range(len(nums)):             all_sum+=nums[i]         if  all_sum%2 ==1 :             return  False          part_sum=all_sum//2          if  max(nums)>part_sum:             return  False          dp=[[False  for  col in  range(part_sum+1 )] for  row in  range(len(nums))]         for  i in  range(len(nums)):             dp[i][0 ]=True          dp[0 ][nums[0 ]]=True          for  i in  range(len(nums)):             for  j in  range(part_sum+1 ):                 if  dp[i][j]==True :                     continue                  if  dp[i-1 ][j] or  dp[i-1 ][j-nums[i]]:                     dp[i][j]=True          return  dp[len(nums)-1 ][part_sum] 
每日一题 1014 查找常用字符 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ''' 即各字符串的交集 ''' class  Solution (object ):    def  commonChars (self, A ):         c_dict=[0 ]*26            res=[]         flag=1            c="abcdefghijklmnopqrstuvwxyz"           for  i in  A:             temp=[0 ]*26                for  j in  i:                 index=ord(j)-ord('a' )                 if  flag==1 :                     c_dict[index]+=1                  else :                     temp[index]+=1              for  index in  range(len(c)):                  if  flag==1 :                     break                  if  c_dict[index]>temp[index]:                     c_dict[index]=temp[index]             flag=0          for  i in  range(len(c_dict)):             while  c_dict[i] >0 :                  res.append(c[i])                 c_dict[i]-=1          return  res 
每日一题 1016 有序数组的平方 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 '' ' 双指针 最大的值一定在两侧  ' '' class  Solution      public  int [] sortedSquares(int [] A) {         int  start=0 ;         int  end=A.length;         int  i=end-1 ;         int [] res=new  int [end--];         while (i>=0 ){             res[i--]=A[start]*A[start]>=A[end]*A[end]?A[start]*A[start++]:A[end]*A[end--];         }         return  res;     } } 
每日一题 1126 最大间距 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 '' ' 桶排序 ' '' class  Solution           public  int  maximumGap (int [] nums)           int  l=nums.length;         if (l<2 ){             return  0 ;         }         int  n_min=Integer.MAX_VALUE,n_max=-1 ;                  for (int  i:nums){             if  (i>n_max){                 n_max=i;             }             if  (i<n_min){                 n_min=i;             }         }         if  ((n_max-n_min)==0 ){             return  0 ;         }                  int  b_size=(int )Math.ceil((double )(n_max-n_min)/(l-1 ));                  int  b_num=l-1 ;         int [] b_min=new  int [b_num];         int [] b_max=new  int [b_num];         Arrays.fill(b_max,-1 );         Arrays.fill(b_min,Integer.MAX_VALUE);         for  (int  i:nums){             if (i==n_max || i==n_min) continue ;             int  index=(i-n_min)/b_size;              b_max[index]=Math.max(b_max[index],i);             b_min[index]=Math.min(b_min[index],i);         }         int  res=0 ;         int  premax=n_min;         for (int  i=0 ;i<b_num;i++){             if (b_max[i]==-1 ) continue ;             res=Math.max(b_min[i]-premax,res);             premax=b_max[i];         }         res=Math.max(n_max-premax,res);         return   res;     } } class  Solution      public  int  maximumGap (int [] nums)           int  n = nums.length;         if  (n < 2 ) {             return  0 ;         }         int  minVal = Arrays.stream(nums).min().getAsInt();         int  maxVal = Arrays.stream(nums).max().getAsInt();         int  d = Math.max(1 , (maxVal - minVal) / (n - 1 ));         int  bucketSize = (maxVal - minVal) / d + 1 ;         int [][] bucket = new  int [bucketSize][2 ];         for  (int  i = 0 ; i < bucketSize; ++i) {             Arrays.fill(bucket[i], -1 );          }         for  (int  i = 0 ; i < n; i++) {             int  idx = (nums[i] - minVal) / d;             if  (bucket[idx][0 ] == -1 ) {                 bucket[idx][0 ] = bucket[idx][1 ] = nums[i];             } else  {                 bucket[idx][0 ] = Math.min(bucket[idx][0 ], nums[i]);                 bucket[idx][1 ] = Math.max(bucket[idx][1 ], nums[i]);             }         }         int  ret = 0 ;         int  prev = -1 ;         for  (int  i = 0 ; i < bucketSize; i++) {             if  (bucket[i][0 ] == -1 ) {                 continue ;             }             if  (prev != -1 ) {                 ret = Math.max(ret, bucket[i][0 ] - bucket[prev][1 ]);             }             prev = i;         }         return  ret;     } } 
每日一题 1127 四数相加|| 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 '' ' 遍历 A 和 B 所有元素和的组合情况,并记录在 ab_map 中,ab_map 的 key 为两数和,value 为该两数和出现的次数 遍历 C 和 D 所有元素和的组合情况,取和的负值判断其是否在 ab_map 中,若存在则取出 ab_map 对应的 value 值,count = count + value ' '' class  Solution      public  int  fourSumCount (int [] A, int [] B, int [] C, int [] D)           Map<Integer, Integer> countAB = new  HashMap<Integer, Integer>();         for  (int  u : A) {             for  (int  v : B) {                 countAB.put(u + v, countAB.getOrDefault(u + v, 0 ) + 1 );             }         }         int  ans = 0 ;         for  (int  u : C) {             for  (int  v : D) {                 if  (countAB.containsKey(-u - v)) {                     ans += countAB.get(-u - v);                 }             }         }         return  ans;     } } 
每日一题 1130 重构字符串 一、问题描述 
问题思路 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 '' ' 遍历 A 和 B 所有元素和的组合情况,并记录在 ab_map 中,ab_map 的 key 为两数和,value 为该两数和出现的次数 遍历 C 和 D 所有元素和的组合情况,取和的负值判断其是否在 ab_map 中,若存在则取出 ab_map 对应的 value 值,count = count + value ' '' class  Solution      public   String reorganizeString (String S)           int  all_l=S.length();                  if (all_l<2 ){             return  S;         }                           int [] charnum=new  int [26 ];         for (int  i=0 ;i<all_l;i++){             char  ch=S.charAt(i);             charnum[(int )(ch-'a' )]++;             if (charnum[(int )(ch-'a' )]>(all_l+1 )/2 ){                 return  "" ;             }         }                  PriorityQueue<Character> queue=new  PriorityQueue<Character>(new  Comparator<Character>() {             @Override              public  int  compare (Character o1, Character o2)                   return  charnum[(int )(o2-'a' )]-charnum[(int )(o1-'a' )];             }         });                  for (int  i=0 ;i<26 ;i++){             if (charnum[i]>0 ){                 queue.offer((char )(i+97 ));             }         }                  StringBuilder res=new  StringBuilder();         while  (queue.size()>1 ){             char  q1=queue.poll();             char  q2=queue.poll();             res.append(q1);             res.append(q2);             if (--charnum[q1-'a' ]>0 ){                   queue.offer(q1);             }             if (--charnum[q2-'a' ]>0 ){                 queue.offer(q2);             }         }         if (queue.size()>0 ){               res.append(queue.poll());         }         return  res.toString();     } } 
每日一题 1201 重构字符串 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 '' ' 二分查找找到该数后  向两边拓展找到全部数字 ' '' class  Solution      public  int [] searchRange(int [] nums, int  target) {            int  low=0 ;         int  high=nums.length-1 ;         int  pivot=(low+high)/2 ;         int [] res={-1 ,-1 };         if (nums.length==0 ){             return  res;         }         while (nums[pivot]!=target){             if (nums[pivot]>target){                 high=pivot-1 ;             }             else {                 low=pivot+1 ;             }             if (high<low){                    return  res;             }             pivot=(low+high)/2 ;         }         low=pivot-1 ;         high=pivot+1 ;         while (low>=0  && nums[low]==target)low--;            while (high<nums.length&&nums[high]==target)high++;         res[0 ]=low+1 ;         res[1 ]=high-1 ;         return  res;     } } 
每日一题 1202 拼接最大数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 "" " 为了找到长度为 k 的最大数,需要从两个数组中分别选出最大的子序列,这两个子序列的长度之和为 k,然后将这两个子序列合并得到最大数。两个子序列的长度最小为 0,最大不能超过 kk 且不能超过对应的数组长度。 " "" class  Solution      public   int [] maxNumber(int [] nums1, int [] nums2, int  k) {         int  l1=nums1.length;         int  l2=nums2.length;         int  start=Math.max(0 ,k-l2);           int  end=Math.min(k,l1);             int [] maxres=new  int [k];         for (int  i=start;i<=end;i++){               int [] sub1=maxSub(nums1,i);             int [] sub2=maxSub(nums2,k-i);             int [] tempmax=merge(sub1,sub2);             if (compare(tempmax,0 ,maxres,0 )>0 ){                 System.arraycopy(tempmax,0 ,maxres,0 ,k);             }         }         return  maxres;     }               public   int [] maxSub(int [] nums,int  k ){           int [] stack=new  int [k];         int  top=-1 ;         int  remain=nums.length-k;         for (int  i=0 ;i<nums.length;i++){             int  num=nums[i];                          while  ( top>=0  && stack[top]<num && remain>0 ){                 top--;                 remain--;             }             if (top<k-1 ){                 stack[++top]=num;             }             else {                 remain--;             }         }         return  stack;     }          public   int [] merge(int [] sub1,int [] sub2){         int  l1=sub1.length;         int  l2=sub2.length;         int [] res=new  int [l1+l2];         if (l1==0 ){             return  sub2;         }         if (l2==0 ){             return  sub1;         }         int  i=0 ;         int  index1=0 ;         int  index2=0 ;         while (index1<l1||index2<l2){             if (compare(sub1,index1,sub2,index2)>0 ){                 res[i]=sub1[index1++];             }             else  {                 res[i]=sub2[index2++];             }             i++;         }         return  res;     }          public   int  compare (int [] sub1,int  index1,int [] sub2,int  index2)          while  (index1<sub1.length&&index2<sub2.length){             if (sub1[index1]!=sub2[index2]){                 return  sub1[index1]-sub2[index2];             }             index1++;             index2++;         }         return  (sub1.length-index1)-(sub2.length-index2);     } } 
每日一题 1203 计数质数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 "" " 方法一:枚举  判断每一个数是否为质数  判断方法是看[2,根号x]是否为其因数 " "" class  Solution      public  int  countPrimes (int  n)           int  res=0 ;         for (int  i=2 ;i<n;i++){             res+=isPrime(i)?1 :0 ;         }         return  res;     }     public  boolean  isPrime (int  num)          for (int  i=2 ;i*i<=num;i++){             if (num%i==0 ){                 return  false ;             }         }         return  true ;     } } "" " 方法二:埃氏筛  若一个数为质数 则其倍数都为合数 从x*x开始赋为合数  因为其余的2x  3x都会在x之前就被其他数的倍数标记过了,例如2 的所有倍数,3 的所有倍数等。 " "" class  Solution      public  static  int  countPrimes (int  n)           int  res=0 ;         int [] prime=new  int [n];         Arrays.fill(prime,1 );         for (int  i=2 ;i<n;i++){             if (prime[i]==1 ){                 res+=1 ;                 if ((long )i*i<n){                     for (int  x=i*i;x<n;x+=i){                         prime[x]=0 ;                     }                 }             }         }         return  res;     } } 
每日一题 1204 分割数组为连续子序列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 "" " 贪心 对于数组中的元素 x,如果存在一个子序列以x−1 结尾,则可以将 x加入该子序列中。将 x 加入已有的子序列总是比新建一个只包含 x 的子序列更优,因为前者可以将一个已有的子序列的长度增加 1,而后者新建一个长度为 1 的子序列,而题目要求分割成的子序列的长度都不小于 3,因此应该尽量避免新建短的子序列。 " "" public  static  boolean  isPossible (int [] nums)               HashMap<Integer,Integer> numscntmap=new  HashMap<Integer,Integer>();                HashMap<Integer,Integer> numsendmap=new  HashMap<Integer,Integer>();         for (int  num:nums){             numscntmap.put(num,numscntmap.getOrDefault(num,0 )+1 );         }         for (int  num:nums){             if (numscntmap.get(num)==0 ) {                  continue ;             }             numscntmap.put(num,numscntmap.get(num)-1 );             if (numsendmap.containsKey(num-1 )&& numsendmap.get(num-1 )>0 ){                  numsendmap.put(num-1 ,numsendmap.get(num-1 )-1 );                 numsendmap.put(num,numsendmap.getOrDefault(num,0 )+1 );             }                          else  if  (numscntmap.containsKey(num+1 )&&numscntmap.get(num+1 )>0 &&numscntmap.containsKey(num+2 )&&numscntmap.get(num+2 )>0 ){                 numsendmap.put(num+2 ,numsendmap.getOrDefault(num+2 ,0 )+1 );                 numscntmap.put(num+1 ,numscntmap.get(num+1 )-1 );                 numscntmap.put(num+2 ,numscntmap.get(num+2 )-1 );             }             else  {                 return  false ;             }         }         return  true ;     } 
每日一题 1206 杨辉三角 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 主要是二维集合的初始化和赋值 杨辉三角就是第i层的元素个数都为i 第i层第j个元素的值等于 第i-1层第j-1个元素+第i-1层第j个元素 注意j的范围[1,i-1] " "" class  Solution      public  List<List<Integer>> generate(int  numRows) {         ArrayList<ArrayList<Integer>> res = new  ArrayList<ArrayList<Integer>>();         for  (int  i = 0 ; i < numRows; i++) {             ArrayList<Integer> temp = new  ArrayList<Integer>();             temp.add(1 );             for  (int  j = 1 ; j < i; j++) {                 int  sumnum = res.get(i - 1 ).get(j - 1 ) + res.get(i - 1 ).get(j);                 temp.add(sumnum);             }             if  (i > 0 ) {                 temp.add(1 );             }             res.add(temp);         }         return  (List)res;      } } 
每日一题 1207 杨辉三角 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 贪心  理清逻辑思路  不需要实际去改变矩阵 " "" class  Solution      public  int  matrixScore (int [][] A)           int  m=A.length;         int  n=A[0 ].length;         int  res=m*(1 <<(n-1 ));          for (int  i=1 ;i<n;i++){             int  temp_num=0 ;             for (int  j=0 ;j<m;j++){                 if (A[j][0 ]==0 ){                       temp_num+=1 -A[j][i];                 }                 else {                       temp_num+=A[j][i];                 }             }             temp_num=Math.max(temp_num,m-temp_num);               res+=temp_num*(1 <<(n-1 -i));          }         return  res;     } } 
每日一题 1208 将数组拆分成斐波那契数列 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 "" " 回溯 " ""     public  List<Integer> splitIntoFibonacci (String S)           List<Integer> res = new  ArrayList<>();         backtrack(S.toCharArray(), res, 0 );         return  res;     }     public  boolean  backtrack (char [] digit, List<Integer> res, int  index)                    if  (index == digit.length && res.size() >= 3 ) {             return  true ;         }         for  (int  i = index; i < digit.length; i++) {                          if  (digit[index] == '0'  && i > index) {                 break ;             }                          long  num = subDigit(digit, index, i + 1 );                          if  (num > Integer.MAX_VALUE) {                 break ;             }             int  size = res.size();                          if  (size >= 2  && num > res.get(size - 1 ) + res.get(size - 2 )) {                 break ;             }             if  (size <= 1  || num == res.get(size - 1 ) + res.get(size - 2 )) {                                  res.add((int ) num);                                  if  (backtrack(digit, res, i + 1 ))                       return  true ;                                  res.remove(res.size() - 1 );              }         }         return  false ;     }          private  long  subDigit (char [] digit, int  start, int  end)           long  res = 0 ;         for  (int  i = start; i < end; i++) {             res = res * 10  + digit[i] - '0' ;         }         return  res;     } 
每日一题 1209 不同路径 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 动态规划  只能通过左边或者上面到达当前节点:dp[i][j]=dp[i][j-1]+dp[i-1][j]; " "" class  Solution      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][j-1 ]+dp[i-1 ][j];             }         }         return  dp[m-1 ][n-1 ];     } } 
每日一题 1210 柠檬水找零 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 "" " 用两个int变量存老板手上5元和10元张数 " "" class  Solution      public  boolean  lemonadeChange (int [] bills)           int  five=0 ;         int  ten=0 ;         for (int  bill:bills){                          if (bill==5 ){                 five+=1 ;             }                          else  if (bill==10 ){                 if (five<0 ) return  false ;                 else {                     five-=1 ;                     ten+=1 ;                 }             }                          else {                 if (ten>0 &&five>0 ){                     ten-=1 ;                     five-=1 ;                 }                 else  if (five>=3 ){                     five-=3 ;                 }                 else {                     return  false ;                 }             }         }         return  true ;     } } 
每日一题 1211 Dota2 参议院 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 "" " 贪心算法:每个R阵营的参议员禁止下一个离他最近的D阵营的参议员,反之亦然。      * 算法流程:      *  使用两个队列分别保存R阵营和D阵营的参议员索引,      *  在每一轮循环中,比较相邻两个R和D阵营的参议员的索引,      *      保留索引小(min)的,并将该(min + senate.length)添加到该阵营队列尾部      *      去除索引大的,即不添加到末尾。 " "" class  Solution      public  String predictPartyVictory (String senate)           Queue<Integer> r=new  LinkedList<Integer>();         Queue<Integer> d=new  LinkedList<Integer>();         for (int  i=0 ;i<senate.length();i++){             if (senate.charAt(i)=='R' ){                 r.offer(i);             }             else  {                 d.offer(i);             }         }         while (!r.isEmpty()&&!d.isEmpty()){             int  r_idx=r.remove();             int  d_idx=d.remove();             if (r_idx<d_idx) r.add(r_idx+senate.length());             else  d.add(d_idx+senate.length());         }         return  r.isEmpty()?"Dire" :"Radiant" ;     } } 
每日一题 1212 摆动序列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 "" " 动态规划 谷:nums[i]<nums[i-1] 峰:nums[i]>nums[i-1] 若是谷:     1、上一个峰+1(把i纳入序列)     2、上一个谷(不纳入序列)     选择12中大的更新谷 峰相反即可。 " "" class  Solution      public  int  wiggleMaxLength (int [] nums)           int  down=1 ,up=1 ;         if (nums.length<2 ){             return  nums.length;         }         for (int  i=1 ;i<nums.length;i++){             if (nums[i]<nums[i-1 ]){                 down=Math.max(down,up+1 );             }             else  if (nums[i]>nums[i-1 ]){                 up=Math.max(down+1 ,up);             }         }         return  Math.max(up,down);     } } 
每日一题 1213 存在重复元素 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 class  Solution      public  boolean  containsDuplicate (int [] nums)           Set<Integer> set = new  HashSet<Integer>();         for  (int  x : nums) {             if  (!set.add(x)) {                 return  true ;             }         }         return  false ;     } } 
每日一题 1214 字母异位词分组 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 "" " 排序 " "" class  Solution      public  List<List<String>> groupAnagrams(String[] strs) {         List <List<String>> res= new  ArrayList<>();          int  idx=0 ;                  Map<String,Integer> map=new  HashMap<>();          for (int  i=0 ;i<strs.length;i++){             String temp=sortstring(strs[i]);             if (map.containsKey(temp)){                  List<String> strtemp=new  ArrayList<>();                                  strtemp=res.get(map.get(temp));                 strtemp.add(strs[i]);                 res.set(map.get(temp),strtemp);             }             else {                  map.put(temp,idx);                 List<String> res_temp=new  ArrayList<>();                 res_temp.add(strs[i]);                 res.add(res_temp);                 idx+=1 ;             }         }         return  res;     }          public  String sortstring (String s)          char [] temp=s.toCharArray();         Arrays.sort(temp);         return  s.valueOf(temp);     } } "" " 大神简易写法 直接用map 存字母异位词 以及对应的字符串list 最后再把map转二维list " "" class  Solution      public  List<List<String>> groupAnagrams(String[] strs) {         Map<String, List<String>> map = new  HashMap<String, List<String>>();         for  (String str : strs) {             char [] array = str.toCharArray();             Arrays.sort(array);             String key = new  String(array);             List<String> list = map.getOrDefault(key, new  ArrayList<String>());             list.add(str);             map.put(key, list);         }         return  new  ArrayList<List<String>>(map.values());     } } 
每日一题 1215 单调递增的数字 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 "" " 使用贪心法 若原本单调递增则直接返回 如果前面的值大于后面的值就把当前位数减一然后把后面的值变成9 " "" "" " 我自己写的 很多可以直接用内置函数完成 " "" public  int  monotoneIncreasingDigits (int  N)          if (N<10 ){             return  N;         }         int [] ori=new  int [10 ];         int [] res=new  int [10 ];         int  idx=0 ;         while (N>0 ){             ori[idx]=N%10 ;             N=N/10 ;             idx+=1 ;         }         System.out.println(Arrays.toString(ori));         int  len=idx;         idx-=1 ;         for (int  i=idx;i>=0 ;i--){             if (i>0 &&ori[i]>ori[i-1 ]){                 while (i<len&&ori[i]-1 <ori[i+1 ]){                     i+=1 ;                 }                 res[i]=ori[i]-1 ;                 i-=1 ;                 while (i>=0 ){                     res[i]=9 ;                     i-=1 ;                 }                 break ;             }             else  {                 res[i]=ori[i];             }         }         System.out.println(Arrays.toString(res));         int  result=0 ;         for (int  i=len-1 ;i>=0 ;i--){             result=result*10 ;             result+=res[i];         }         return  result;     } "" " 大神简易版 " ""     public  int  monotoneIncreasingDigits (int  N)           char [] ori=String.valueOf(N).toCharArray();         int  len=ori.length;         for (int  i=len-1 ;i>0 ;i--){             if (ori[i]<ori[i-1 ]){                 ori[i-1 ]-=1 ;                 for (int  j=i;j<len;j++){                     ori[j]='9' ;                 }             }         }         return  Integer.parseInt(String.valueOf(ori));     } 
每日一题 1216 单词规律 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class  Solution      public  boolean  wordPattern (String pattern, String s)           String[] s1=s.split(" " );          char [] p1=pattern.toCharArray();          if (s1.length!=p1.length){               return  false ;         }         Map<Character,String> map=new  HashMap<>();           for (int  i=0 ;i<p1.length;i++){             for (char  key:map.keySet()){                 String value=map.get(key);             }             if (map.containsKey(p1[i])){                  if (map.get(p1[i]).equals(s1[i])){                     continue ;                 }                 else  return  false ;             }             else {                 if (map.containsValue(s1[i])){                      return  false ;                 }                 else  map.put(p1[i],s1[i]);             }         }         return  true ;     } } 
每日一题 1217 买卖股票的最佳时机含手续费 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 "" " 动态规划 第i天手上没有股票的最大利润=max(第i-1天没有股票的最大利润,第i-1天有股票的最大利润+第i天买了股票赚的钱(股票价格-手续费) 第i天手上有股票的最大利润=max(第i-1天有股票的最大利润,第i-1天没有股票的最大利润-第i天买股票的钱(股票价格) " "" class  Solution      public  int  maxProfit (int [] prices, int  fee)           int  have=-prices[0 ];         int  nohave=0 ;         for (int  i=1 ;i<prices.length;i++){             int  temp=have;             have=Math.max(have,nohave-prices[i]);             nohave=Math.max(nohave,temp+prices[i]-fee);         }         return  nohave;     } } 
每日一题 1218 找不同 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 "" " 1、求和 求字符串各个字符的和 两个和之差就是答案 " "" class  Solution      public  char  findTheDifference (String s, String t)           int  sums=0 ,sumt=0 ;         for (int  i=0 ;i<s.length();i++){             sums+=s.charAt(i);             sumt+=t.charAt(i);         }         sumt+=t.charAt(s.length());         return  (char )(sumt-sums);     } } "" " 2、位运算 将字符串拼接起来 用位运算 就成了找出现字符次数为奇数的字符问题了  异或就可以 " "" class  Solution      public  char  findTheDifference (String s, String t)           int  res=0 ;         for (int  i=0 ;i<s.length();i++){             res=res^(int )s.charAt(i);         }         for (int  i=0 ;i<t.length();i++){             res=res^(int )t.charAt(i);         }         return  (char )res;     } } 
每日一题 1219 旋转图像 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 顺时针选择90度=先水平翻转 再主对角线翻转 " "" class  Solution      public  void  rotate (int [][] matrix)                    int  len=matrix.length;         for (int  i=0 ;i<len/2 ;i++){             for (int  j=0 ;j<len;j++){                 int  temp=matrix[i][j];                 matrix[i][j]=matrix[len-i-1 ][j];                 matrix[len-i-1 ][j]=temp;             }         }                  for (int  i=0 ;i<len;i++){             for (int  j=len-1 ;j>i;j--){                 int  temp=matrix[i][j];                 matrix[i][j]=matrix[j][i];                 matrix[j][i]=temp;             }         }     } } 
每日一题 1221 使用最小花费爬楼梯 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 动态规划 dp2=Math.min(dp1+cost[idx-2],dp2+cost[idx-1]);//取从下两级迈步和下一级迈步中的最小值 dp代表到达第几级所需的体力  还没有迈步 cost代表从第几级迈步所需的体力 (题目描述有点问题 记得动态规划就可以) " "" class  Solution      public  int  minCostClimbingStairs (int [] cost)           int  dp1=0 ,dp2=0 ;         int  idx=2 ;         while (idx<=cost.length){             int  temp=dp2;             dp2=Math.min(dp1+cost[idx-2 ],dp2+cost[idx-1 ]);             dp1=temp;             idx+=1 ;         }         return  dp2;     } } 
每日一题 1222 二叉树的锯齿形层序遍历 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 "" " 二叉树的单栈层序遍历  由于知道每层的个数 直接在遍历本层的时候 赋值list  用boolean变量标记头入还是尾入 " "" class  Solution      public  List<List<Integer>> zigzagLevelOrder(TreeNode root) {         List<List<Integer>> res=new  LinkedList<>();          Queue<TreeNode> nowstack=new  LinkedList<>();         if (root!=null ) nowstack.offer(root);         Boolean flag=true ;         while (!nowstack.isEmpty()){             Deque<Integer> temp=new  LinkedList<>();              int  len=nowstack.size();              while (len>0 ){                 TreeNode p=nowstack.poll();                 if (flag)temp.offerLast(p.val);                  else  temp.offerFirst(p.val);                  if (p.left!=null ){                     nowstack.offer(p.left);                 }                 if (p.right!=null ){                     nowstack.offer(p.right);                 }                 len--;             }             flag=!flag;             res.add(new  LinkedList<Integer> (temp));         }         return  res;     } } 
每日一题 1224 分发糖果 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 "" " 波谷必为1  至于波峰要看左右两个波谷递增上来 取其最大值 " "" class  Solution      public  int  candy (int [] ratings)           int  res=0 ;         int  len=ratings.length;         int [] left=new  int [len];         left[0 ]=1 ;         int [] right=new  int [len];         right[len-1 ]=1 ;         for (int  i=1 ;i<len;i++){              if (ratings[i]>ratings[i-1 ]) left[i]=left[i-1 ]+1 ;             else   left[i]=1 ;         }         for (int  i=len-1 ;i>0 ;i--){              if (ratings[i-1 ]>ratings[i]) right[i-1 ]=right[i]+1 ;             else  right[i-1 ]=1 ;         }         for (int  i=0 ;i<len;i++){              res+=Math.max(right[i],left[i]);         }         return  res;     } } 
每日一题 1225 分发饼干 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 排序+贪心 每次将最小满足该孩子的饼干 分给孩子 " "" class  Solution      public  int  findContentChildren (int [] g, int [] s)           Arrays.sort(g);         Arrays.sort(s);         int  i=0 ,j=0 ;         int  count=0 ;         while  (i<g.length&&j<s.length){             while  (j<s.length&&g[i]>s[j]) j++;             if (j==s.length) break ;             count+=1 ;             i++;             j++;         }         return  count;     } } 
每日一题 1226 最大矩形 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 "" " 暴力  left[i][j]记录节点ij左边的1的个数(包括本身 " "" class  Solution      public  int  maximalRectangle (char [][] matrix)           if (matrix.length==0 ||matrix[0 ].length==0 ) return  0 ;         int  m=matrix.length,n=matrix[0 ].length;         int [][] left = new  int [m][n];         int  width=0 ,area=0 ,res=0 ;                  for (int  i=0 ;i<m;i++){             for (int  j=0 ;j<n;j++){                 if (matrix[i][j]=='0' ){                     continue ;                 }                 else {                     left[i][j]=(j==0 ?0 :left[i][j-1 ])+1 ;                 }             }         }         for (int  i=0 ;i<m;i++){             for (int  j=0 ;j<n;j++) {                 if (matrix[i][j]=='0' ) continue ;                 width=left[i][j];                 area=width;                 for (int  k=i-1 ;k>=0 ;k--){                     width=Math.min(width,left[k][j]);                     area=Math.max(area,width*(i-k+1 ));                 }                 res=Math.max(res,area);             }         }         return  res;     } } "" " 2、单调栈 " "" class  Solution      public  int  maximalRectangle (char [][] matrix)           if (matrix.length==0 ||matrix[0 ].length==0 ) return  0 ;         int  m=matrix.length,n=matrix[0 ].length;         int [][] left = new  int [m][n];         int  width=0 ,area=0 ,res=0 ;                  for (int  i=0 ;i<m;i++){             for (int  j=0 ;j<n;j++){                 if (matrix[i][j]=='0' ){                     continue ;                 }                 else {                     left[i][j]=(j==0 ?0 :left[i][j-1 ])+1 ;                 }             }         }                  Deque<Integer> stack=new  ArrayDeque<>();         int [] tmp=new  int [m+2 ];         for (int  j=0 ;j<n;j++){             for (int  i=0 ;i<m;i++){                 tmp[i+1 ]=left[i][j];             }             for (int  i=0 ;i<m+2 ;i++){                 while (!stack.isEmpty()&&tmp[i]<tmp[stack.peek()]){                     int  h=tmp[stack.pop()];                     area=Math.max(area,(i-stack.peek()-1 )*h);                 }                 stack.push(i);             }             res=Math.max(res,area);         }         return  res;     } } 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 "" " 单调栈 " "" class  Solution      public  int  largestRectangleArea (int [] heights)                    int [] tmp = new  int [heights.length + 2 ];         System.arraycopy(heights, 0 , tmp, 1 , heights.length);                   Deque<Integer> stack = new  ArrayDeque<>();         int  area = 0 ;         for  (int  i = 0 ; i < heights.length+2 ; i++) {                                                    while  (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {                 int  h = tmp[stack.pop()];                 area = Math.max(area, (i - stack.peek() - 1 ) * h);                }             stack.push(i);         }         return  area;     } } 
每日一题 1227 同构字符串 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 "" " 用map存映射 若存在则判断是否一致  若不存在先判断t对应的字符是否已有对应 若有 则直接报错 因为不能两个字符映射到同一个字符 " ""  class  Solution       public  boolean  isIsomorphic (String s, String t)           Map<Character,Character> map=new  HashMap<>();         for (int  i=0 ;i<s.length();i++){             char  s1=s.charAt(i);             if (map.containsKey(s1)){                 if (map.get(s1)==t.charAt(i)) continue ;                 else  return  false ;             }             else {                 if (map.containsValue(t.charAt(i))) return  false ;                 map.put(s1,t.charAt(i));             }         }         return  true ;     }  } 
每日一题 1228 买卖股票的最佳时机 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 "" " 不考虑k次交易限制 用两个一维数组存  have:第i天有股票的最大利润 free:第i天没有股票的最大利润 状态转移公式为:     free[i]=Math.max(free[i-1],have[i-1]+prices[i]);     have[i]=Math.max(have[i-1],free[i-1]-prices[i]); " "" class  Solution      public  int  maxProfit (int  k, int [] prices)                   int  len=prices.length;         if (len<1 ) return  0 ;         int [] free=new  int [len];         int [] have=new  int [len];         free[0 ]=0 ;         have[0 ]=-prices[0 ];         for (int  i=1 ;i<len;i++){             free[i]=Math.max(free[i-1 ],have[i-1 ]+prices[i]);             have[i]=Math.max(have[i-1 ],free[i-1 ]-prices[i]);         }         return  free[len-1 ];     } } "" " 考虑交易次数的限制 买入+卖出算一次交易次数 用二维数组存 free[i][j] 代表第i天手上没有股票 且交易了j次最大的利润 " "" class  Solution      public  int  maxProfit (int  k, int [] prices)           int  len=prices.length;         if (len<1 ) return  0 ;         k=Math.min(k,len/2 );         int [][] free=new  int [len][k+1 ];         int [][] have=new  int [len][k+1 ];         free[0 ][0 ]=0 ;         have[0 ][0 ]=-prices[0 ];          for (int  i=1 ;i<=k;i++){             free[0 ][i]=Integer.MIN_VALUE/2 ;             have[0 ][i]=Integer.MIN_VALUE/2 ;         }         for (int  i=1 ;i<len;i++){             have[i][0 ]=Math.max(free[i-1 ][0 ]-prices[i],have[i-1 ][0 ]);             for (int  j=1 ;j<=k;j++){                 free[i][j]=Math.max(free[i-1 ][j],have[i-1 ][j-1 ]+prices[i]);                 have[i][j]=Math.max(have[i-1 ][j],free[i-1 ][j]-prices[i]);             }         }         int  res=0 ;         for (int  i=0 ;i<=k;i++){             if (res<free[len-1 ][i]) res=free[len-1 ][i];         }         return  res;     } } 
每日一题 1229 按要求补齐数组 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 "" " 贪心 一个数组[a1,a2,a3...an]当前能用和表示的数字区间为[1,cur_range],此时往数组内补充新数num,则此时能表示的区间为[1,cur_range]∩[num,cur_range + num] 所以若插入num=cur_range+1,覆盖的区间就为[1,cur_range+cur_range+1] 每次若已能覆盖的最大长度cur_range小于待实现的数num,并且已拥有的nums[pos]大于num,也就是需要插入值    统一插入cur_range+1这个数 不然的话 就用nums[pos]来增加覆盖的最大长度cur_range=cur_range+nums[pos]     当前能表示的最大数字为cur_range,则下一个需要达到的目标数字是cur_range + 1,而当前(未使用)的数组元素为num = nums[pos]     判断num与目标值cur_range + 1的大小关系:         1、如果num > cur_range + 1,则说明[cur_range + 1, num - 1]区间内的数字无法表示,必须补充插入新数。为了使插入的新数既能表示ach + 1,又能尽可能覆盖更多的数组(贪心的关键之处),插入的数字就是cur_range + 1,更新cur_range = cur_range + cur_range + 1         2、如果num < cur_range + 1,说明当前的目标值cur_range + 1必然可以实现(因为num >= 1),此时更新cur_range = cur_range + num " "" class  Solution      public  int  minPatches (int [] nums, int  n)           long  cur_range=0 ;         int  pos=0 ;         int  res=0 ;         while (cur_range<n){             if (pos>=nums.length||nums[pos]>cur_range+1 ){                  res+=1 ;                 cur_range+=cur_range+1 ;             }             else  {                 cur_range+=nums[pos];                 pos+=1 ;             }            }         return  res;     } } 
每日一题 1230 最后一块石头的重量 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 "" " 用大堆来模拟过程 " "" class  Solution      public  int  lastStoneWeight (int [] stones)           if (stones.length<1 ) return  0 ;                           PriorityQueue<Integer> queue =new  PriorityQueue<Integer>(new  Comparator<Integer>() {         @Override              public  int  compare (Integer o1, Integer o2)                   return  o2-o1;             }         });         for (int  i=0 ;i<stones.length;i++){             queue.offer(stones[i]);         }         while (queue.size()>1 ){             int  m1=queue.poll();             int  m2=queue.poll();             if (m1!=m2) queue.offer(m1-m2);         }         return  queue.size()>0 ?queue.poll():0 ;              } } 
每日一题 0102 滑动窗口最大值 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 "" " 单调队列 用双端队列存一个递减队列对应的下标 " "" class  Solution      public  int [] maxSlidingWindow(int [] nums, int  k) {         int  idx=0 ;         int [] res=new  int [nums.length-k+1 ];         Deque<Integer> queue=new  ArrayDeque<>();         for (int  i=0 ;i<k;i++){               while (!queue.isEmpty()&&nums[queue.getLast()]<=nums[i]){                 queue.removeLast();             }             queue.addLast(i);         }         res[idx]=nums[queue.getFirst()];         for (int  i=k;i<nums.length;i++){                          while (!queue.isEmpty()&&nums[queue.getLast()]<=nums[i]){                 queue.removeLast();             }             queue.add(i);                          while (!queue.isEmpty()&&queue.peekFirst()<=i-k) queue.removeFirst();             res[++idx]=nums[queue.peekFirst()];         }         return  res;     } } 
每日一题 0103 分割链表 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 "" " 维护两个链表 一个是小于x的节点  一个是大于等于x的节点 最后将小于x节点的尾结点next指向大于x的头结点即可 增加虚拟节点来统一头结点为空不为空的情况。 " "" class  Solution      public  ListNode partition (ListNode head, int  x)           ListNode lhead=new  ListNode(0 );          ListNode hhead=new  ListNode(0 );          ListNode tmp=head;         ListNode tmpl=lhead;          ListNode tmph=hhead;           while (tmp!=null ){             if (tmp.val<x) {                 tmpl.next=tmp;                 tmpl=tmp;             }             else  {                 tmph.next=tmp;                 tmph=tmp;             }             tmp=tmp.next;         }         tmph.next=null ;          tmpl.next=hhead.next;          return  lhead.next;      } } 
每日一题 0104 斐波那契数列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 "" " 动态规划 用两个变量存状态即可 " "" class  Solution      public  int  fib (int  n)           int  dp0=0 ,dp1=1 ,idx=2 ;         if (n<2 ) return  n;         while (idx<=n){             int  tmp=dp1;             dp1=dp0+dp1;             dp0=tmp;             idx+=1 ;         }         return  dp1;     } } 
每日一题 0105 较大分组的位置 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 一次遍历 用l指针指向重复字符的第一个位置 idx指向最后一个位置 idx-l+1即为连续字符的长度 " "" class  Solution      public  List<List<Integer>> largeGroupPositions(String s) {         char [] arr=s.toCharArray();         List<List<Integer>> res=new  ArrayList<>();         int  l=0 ,idx=0 ;         while (idx<arr.length){             while  (idx+1 <arr.length&&arr[idx]==arr[idx+1 ]) {                 idx+=1 ;             }             if (idx-l+1 >=3 ){                 List<Integer> tmp=new  ArrayList<>();                 tmp.add(l);                 tmp.add(idx);                 res.add(new  ArrayList<>(tmp));             }             l=idx+1 ;             idx=idx+1 ;         }         return  res;     } } 
每日一题 0106 除法求值 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 "" " 图 利用除法的传递性 变量就是节点 商就是边的权值 建立图后 两个变量的商就是图中两个节点的路径乘积 " "" class  Solution      public  double [] calcEquation(List<List<String>> equations, double [] values, List<List<String>> queries) {         Map<String,Integer> variables=new  HashMap<>();         List<String> tmp_val=new  ArrayList<>(2 );         int  vid=0 ;                  for (int  i=0 ;i<equations.size();i++){             tmp_val=equations.get(i);             if (!variables.containsKey(tmp_val.get(0 ))){                 variables.put(tmp_val.get(0 ),vid++);             }             if (!variables.containsKey(tmp_val.get(1 ))){                 variables.put(tmp_val.get(1 ),vid++);             }         }                           List<Pair>[] edges=new  List[vid];                  for (int  i=0 ;i<vid;i++){             edges[i]=new  ArrayList<Pair>();         }         for (int  i=0 ;i<equations.size();i++){                          int  ia=variables.get(equations.get(i).get(0 )),ib=variables.get(equations.get(i).get(1 ));             edges[ia].add(new  Pair(ib, values[i]));             edges[ib].add(new  Pair(ia,1 /values[i]));         }         int  ia,ib;         double [] res=new  double [queries.size()];         Arrays.fill(res,-1.0 );         for (int  i=0 ;i<queries.size();i++){             String sa=queries.get(i).get(0 ),sb=queries.get(i).get(1 );             if (variables.containsKey(sa)&&variables.containsKey(sb)){                 ia=variables.get(sa);                 ib=variables.get(sb);                 if (ia==ib) {                      res[i]=1 ;                     continue ;                 }                                  Queue<Integer> queue=new  LinkedList<>();                  queue.add(ia);                 double [] ratios=new  double [vid];                  Arrays.fill(ratios,-1.0 );                 ratios[ia]=1.0 ;                 while  (!queue.isEmpty()&&ratios[ib]<0 ){                     int  start=queue.poll();                     for (Pair pair:edges[start]){                          if (ratios[pair.endid]<0 ){                             ratios[pair.endid]=ratios[start]*pair.val;                              queue.add(pair.endid);                          }                     }                 }                 res[i]=ratios[ib];             }         }         return  res;     } } class  Pair     int  endid;     double  val;     public  Pair (int  e,double  v)          endid=e;         val=v;     } } 
每日一题 0107 省份数量 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 "" " 题目就是求图的连通分量个数 用dfs或者bfs 1、dfs 遍历所有城市,对于每个城市,如果该城市尚未被访问过,则从该城市开始深度优先搜索。 通过矩阵isConnected 得到与该城市直接相连的城市有哪些,这些城市和该城市属于同一个连通分量,然后对这些城市继续深度优先搜索,直到同一个连通分量的所有城市都被访问到,即可得到一个省份。 遍历完全部城市以后,即可得到连通分量的总数,即省份的总数。 " "" class  Solution      public  int  findCircleNum (int [][] isConnected)           int  res=0 ;         int  num=isConnected.length;         boolean [] visited=new  boolean [num];         for (int  i=0 ;i<num;i++){             if (visited[i]==false ){                 dfs(visited,i,isConnected);                 res+=1 ;             }         }         return  res;     }     public  void  dfs (boolean [] visited,int  cur,int [][]isConnected)          for (int  j=0 ;j<visited.length;j++){             if (isConnected[cur][j]==1 &&visited[j]==false ){                 visited[j]=true ;                 dfs(visited,j,isConnected);             }         }     } } "" " 2、bfs 对于每个城市,如果该城市尚未被访问过,则从该城市开始广度优先搜索,直到同一个连通分量中的所有城市都被访问到,即可得到一个省份。 " "" class  Solution      public  int  findCircleNum (int [][] isConnected)           int  res = 0 ;         int  num = isConnected.length;         boolean [] visited = new  boolean [num];         Queue<Integer> queue=new  LinkedList<>();         for (int  i=0 ;i<num;i++){             if (visited[i]==false ){                 queue.add(i);                 res+=1 ;                 while  (!queue.isEmpty()){                       int  j=queue.poll();                     for (int  k=0 ;k<num;k++){                         if (isConnected[j][k]==1 &&visited[k]==false ){                             queue.add(k);                             visited[k]=true ;                         }                     }                 }             }         }         return  res;     } } 
每日一题 0108 旋转数组 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 "" " 1、翻转数组 向右旋转  相当于全部翻转 然后各自翻转  0~k-1   k~nums.length-1 " ""     public  void  rotate_2 (int [] nums, int  k)           int  n = nums.length;         k %= n;         reverse(nums, 0 , n - 1 );         reverse(nums, 0 , k - 1 );         reverse(nums, k, n - 1 );     }     private  void  reverse (int [] nums, int  start, int  end)           while  (start < end) {             int  temp = nums[start];             nums[start++] = nums[end];             nums[end--] = temp;         }     } "" " 2、双重循环  每次只移动一位 " ""     public  void  rotate_1 (int [] nums, int  k)           int  n = nums.length;         k %= n;         for  (int  i = 0 ; i < k; i++) {              int  temp = nums[n - 1 ];             for  (int  j = n - 1 ; j > 0 ; j--) {                 nums[j] = nums[j - 1 ];             }             nums[0 ] = temp;         }     } 
每日一题 0110 汇总区间 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 "" " 用start指向连续区间开头  每次判断nums[i]是不是区间末尾 " "" class  Solution      public  List<String> summaryRanges (int [] nums)           List<String> res=new  ArrayList<>();         if (nums.length<1 ) return  res;         int  start=nums[0 ];         for (int  i=0 ;i<nums.length;i++){             if ((i<nums.length-1 &&nums[i]+1 !=nums[i+1 ])||i==nums.length-1 ){                 StringBuilder tmp=new  StringBuilder();                 if (start!=nums[i]){                       tmp.append(start).append("->" ).append(nums[i]);                 }                 else  tmp.append(nums[i]);                  res.add(tmp.toString());                 if (i<nums.length-1 ) start=nums[i+1 ];               }         }         return  res;     } } 
每日一题 0115 移除最多的同行或同列石头 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 "" " 将同行或同列的石头连接起来成图 也就是求联通分量 所有横坐标为 x 的石头和所有纵坐标为 y 的石头都属于同一个连通分量。 需要在并查集里区分「横坐标」和「纵坐标」,它们在并查集里不能相等,根据题目的提示 0 <= x_i, y_i <= 10^4,可以把其中一个坐标 映射 到另一个与 [0, 10000] 不重合的区间,可以的做法是把横坐标全部减去 10001 或者全部加上 10001     用并查集       init  初始化     find  查找节点的父节点(联通的根节点)     union 合并两个节点所在的联通分量(根节点合并)     新建节点时联通分量+1,合并节点时联通分量-1 " "" class  Solution      public  int  removeStones (int [][] stones)           UnionFind uf=new  UnionFind();         for (int [] stone:stones){             uf.union(stone[0 ]+10001 ,stone[1 ]);         }         return  stones.length-uf.getCount();     } } class  UnionFind     private  Map<Integer,Integer> parent;       private  int  count;           public  UnionFind ()          this .parent=new  HashMap<>();         this .count=0 ;     }      public  int  getCount ()          return  count;     }          public  int  find (int  x)          if (!parent.containsKey(x)){             parent.put(x,x);               count++;         }         if (x!=parent.get(x)){             parent.put(x,find(parent.get(x)));          }         return  parent.get(x);     }     public  void  union (int  x,int  y)          int  px=find(x);         int  py=find(y);         if (px==py) return ;          parent.put(px,py);          count-=1 ;     } } 
每日一题 0122 数组形式的整数加法 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 "" " 方法1 将数组的末尾以此加到数K上 去加的结果的末尾给res 也就是将进位直接体现在数K上 " "" class  Solution      public  List<Integer> addToArrayForm (int [] A, int  K)           LinkedList<Integer> res=new  LinkedList<>();         int  tmp;         int  idx=A.length-1 ;         int  jinwei=0 ;         while (K>0 ||idx>=0 ){             if (idx>=0 ){                 K+=A[idx];             }             res.addFirst(K%10 );             K/=10 ;             idx-=1 ;         }         return  res;     } } "" " 方法2 分类讨论  无技巧 " "" class  Solution      public  List<Integer> addToArrayForm (int [] A, int  K)           List<Integer> res=new  LinkedList<>();         int  tmp;         int  idx=A.length-1 ;         int  jinwei=0 ;         while  (K>0 &&idx>=0 ){               tmp=K%10 ;             int  tmp_add=tmp+A[idx]+jinwei;             if (tmp_add<10 ){                 res.add(0 ,tmp_add);                 jinwei=0 ;             }             else  {                 res.add(0 ,tmp_add-10 );                 jinwei=1 ;             }             idx-=1 ;             K=K/10 ;         }         while (idx>=0 ){               int  tmp_add=A[idx]+jinwei;             if (tmp_add>9 ){                 jinwei=1 ;                 res.add(0 ,tmp_add-10 );             }             else {                 jinwei=0 ;                 res.add(0 ,tmp_add);             }             idx-=1 ;         }         while (K>0 ){              int  tmp_add=K%10 +jinwei;             if (tmp_add>9 ){                 jinwei=1 ;                 res.add(0 ,tmp_add-10 );             }             else {                 jinwei=0 ;                 res.add(0 ,tmp_add);             }             K/=10 ;         }         if (jinwei>0 ){                                 res.add(0 ,jinwei);         }         return  res;     } } 
每日一题 0201 公平的糖果棒交换 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class  Solution      public  int [] fairCandySwap(int [] A, int [] B) {        int  sumA=Arrays.stream(A).sum();        int  sumB=Arrays.stream(B).sum();        int  delta=(sumA-sumB)/2 ;        int [] res=new  int [2 ];        Set<Integer> tmp=new  HashSet<>();        for (int  i=0 ;i<A.length;i++){            tmp.add(A[i]);        }        for (int  b:B){            if (tmp.contains(b+delta)){                res[0 ]=b+delta;                res[1 ]=b;                return   res;            }        }        return  res;     } } 
每日一题 0228 公平的糖果棒交换 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class  Solution      public  boolean  isMonotonic (int [] A)           if (A.length<2 ) return  true ;         int  flag=0 ;           int  i=1 ,len=A.length;         while (i<len){             if (A[i-1 ]>A[i]) {                 if (flag==-1 )  return   false ;                   flag=1 ;             }             if (A[i-1 ]<A[i]) {                 if (flag==1 ) return  false ;                 flag=-1 ;             }             i+=1 ;         }         return  true ;     } } 
每日一题 0301 公平的糖果棒交换 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class  NumArray      int [] res;     public  NumArray (int [] nums)           if (nums.length<1 ) return ;         res=new  int [nums.length+1 ];         for (int  i=0 ;i<nums.length;i++){             res[i+1 ]=res[i]+nums[i];         }     }     public  int  sumRange (int  i, int  j)           return  res[j+1 ]-res[i];     } } 
每日一题 0302 公平的糖果棒交换 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class  NumMatrix      public  int [][] mat;     public  int [][] presum;      public  NumMatrix (int [][] matrix)           this .mat=matrix;         int  m=matrix.length;         if (m>0 ){                     int  n=matrix[0 ].length;             presum=new  int [m][n+1 ];             for (int  i=0 ;i<m;i++){                 for (int  j=0 ;j<n;j++){                     presum[i][j+1 ]=presum[i][j]+matrix[i][j];                 }             }         }      }          public  int  sumRegion (int  row1, int  col1, int  row2, int  col2)           int  sum=0 ;         for (int  i=row1;i<=row2;i++){             sum+=presum[i][col2+1 ]-presum[i][col1];         }         return  sum;     } } 
每日一题 0303 比特位计数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 class  Solution      public  int [] countBits(int  num) {         int [] dp=new  int [num+1 ];         for (int  i=0 ;i<=num/2 ;i++){             dp[i*2 ]=dp[i];             if (i*2 +1 <=num){                 dp[i*2 +1 ]=dp[i]+1 ;             }         }         return  dp;     } } 
每日一题 0304 俄罗斯套娃信封问题 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 "" " 动态规划   首先我们将所有的信封按照 w 值第一关键字升序、h 值第二关键字降序进行排序; 随后我们就可以忽略 w 维度,求出 h 维度的最长严格递增子序列,其长度即为答案。 " "" class  Solution      public  int  maxEnvelopes (int [][] envelopes)           int  len=envelopes.length;         if (len<2 ) return  len;                   Arrays.sort(envelopes, new  Comparator<int []>() {             public  int  compare (int [] e1, int [] e2)                   if  (e1[0 ] != e2[0 ]) {                     return  e1[0 ] - e2[0 ];                 } else  {                     return  e2[1 ] - e1[1 ];                 }             }         });         int  res=1 ;         int [] dp=new  int [len];         Arrays.fill(dp,1 );                  for (int  i=1 ;i<len;i++){             for (int  j=0 ;j<i;j++){                 if (envelopes[i][1 ]>envelopes[j][1 ]){                     dp[i]=Math.max(dp[j]+1 ,dp[i]);                 }             }             res=Math.max(res,dp[i]);         }         return  res;     } } 
技巧: 1、求中间下标用low + (high - low) // 2 而不是 (high + low) // 2,是为了防止low+high溢出
树遍历 层序遍历 1、单栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import  java.util.*;public  class  Solution      public  ArrayList<Integer> PrintFromTopToBottom (TreeNode root)           Queue<TreeNode> queue = new  LinkedList<>();         ArrayList<Integer> res = new  ArrayList<>();         if (root!=null ) queue.add(root);         while (!queue.isEmpty()){             int  len = queue.size();             while (len-->0 ){                 TreeNode cur = queue.poll();                 res.add(cur.val);                 if (cur.left!=null ) queue.add(cur.left);                 if (cur.right!=null ) queue.add(cur.right);             }         }         return  res;     } } 
2、双栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class  Solution      public  int  maxDepth (TreeNode root)                    if (root==null ) return  0 ;         List<TreeNode> now_layer=new  ArrayList<TreeNode>();         List<TreeNode> next_layer=new  ArrayList<TreeNode>();         int  res=0 ;         now_layer.add(root);         while (now_layer.size()>0 ){             res+=1 ;             for (TreeNode p:now_layer){                 if (p.left!=null ) next_layer.add(p.left);                 if (p.right!=null ) next_layer.add(p.right);             }             now_layer=next_layer;             next_layer=new  ArrayList<TreeNode>();         }         return  res;     } } 
排序 1、冒泡排序 (稳定、N2,1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 "" " 从左到右不断交换相邻逆序的元素,在一轮的循环之后,可以让未排序的最大元素上浮到右侧。 在一轮循环中,如果没有发生交换,那么说明数组已经是有序的,此时可以直接退出。 " ""     public  void  sort (int [] nums)          boolean  issorted=false ;          int  len=nums.length;         for (int  i=len-1 ;i>0 &&(issorted==false );i--){             issorted=true ;             for (int  j=0 ;j<i;j++){                 if (nums[j]>nums[j+1 ]){                     issorted=false ;                     swap(nums,j,j+1 );                 }             }         }     } 
2、归并排序(稳定、NlogN,N(merge时辅助数组))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public  void  sort (int [] nums)     mergeandsort(nums,0 ,nums.length-1 ); } public  void  mergeandsort (int [] nums,int  l,int  h)     if (l<h){         int  m=(l+h)/2 ;         mergeandsort(nums,l,m);         mergeandsort(nums,m+1 ,h);         merge(nums,l,m,h);     }     else  return ; } public  void  merge (int [] nums,int  l,int  m,int  h)     int  i=l,j=m+1 ;     int [] temp=nums.clone();     for (int  k=l;k<=h;k++){         if (i>m) nums[k]=temp[j++];         else  if (j>h) nums[k]=temp[i++];         else  if (temp[i]>temp[j]) nums[k]=temp[j++];         else  nums[k]=temp[i++];     } } 
3、快速排序 (使用之前可以先随机打乱,不稳定,NlogN,logN(栈))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public  void  sort (int [] nums)         quicksort(nums,0 ,nums.length-1 );     }     public  void  quicksort (int [] nums,int  l,int  h)          if (l<h){             int  m=partition(nums,l,h);             quicksort(nums,l,m-1 );             quicksort(nums,m+1 ,h);         }     }     public  int  partition (int [] nums,int  l,int  h)          int  pivot=nums[l];         int  i=l+1 ,j=h;         while (true ){             while (i<=h&&nums[i]<=pivot) i++;             while  (j>=0 &&nums[j]>pivot) j--;             if (i>j) break ;             swap(nums,i,j);         }         swap(nums,l,j);         return  j;     }     public  void  swap (int [] nums,int  i,int  j)          int  temp=nums[i];         nums[i]=nums[j];         nums[j]=temp;     } 
单调栈 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 "" " 单调栈 " "" class  Solution      public  int  largestRectangleArea (int [] heights)                    int [] tmp = new  int [heights.length + 2 ];         System.arraycopy(heights, 0 , tmp, 1 , heights.length);                   Deque<Integer> stack = new  ArrayDeque<>();         int  area = 0 ;         for  (int  i = 0 ; i < heights.length+2 ; i++) {                                                    while  (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {                 int  h = tmp[stack.pop()];                 area = Math.max(area, (i - stack.peek() - 1 ) * h);                }             stack.push(i);         }         return  area;     } } 
8、Floyd判环算法  龟兔赛跑
参考博客:https://blog.csdn.net/u012534831/article/details/74231581 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import  java.util.*;public  class  Solution      public  ListNode EntryNodeOfLoop (ListNode pHead)           if (pHead==null  ||pHead.next==null ) return  null ;         ListNode fast = pHead;         ListNode slow = pHead;         do {             fast = fast.next.next;             slow = slow.next;         }while (fast!=null  && fast.next!=null  && fast!=slow);         if (fast==null  ||fast.next==null ) return  null ;                  fast = pHead;         while (fast!=slow){             fast = fast.next;             slow = slow.next;         }         return  slow;     } } "" " 弗洛伊德(Floyd )使用了两个指针,一个慢指针(龟)每次前进一步,快指针(兔)指针每次前进两步(两步或多步效果是等价的,只要一个比另一个快就行。但是如果移动步数增加,算法的复杂度可能增加)。 如果两者在链表头以外(不包含开始情况)的某一点相遇(即相等)了,那么说明链表有环,否则,如果(快指针)到达了链表的结尾(如果存在结尾,肯定无环),那么说明没环。 环的起点:将慢指针(或快指针)移到链表起点,然后两者同时移动,每次移动一步,那么两者相遇的地方就是环的起点。 环的长度:当两者相遇之后,固定一个指针,让另一个指针行走一圈,使用count计数,如果两个指针相等(即相遇),则count即为环的长度。 " "" 
9、堆
剑指 Offer 40 最小的k个数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 "" " 1、大堆   我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中,随后从第 k+1 个数开始遍历,如果当前遍历到的数比大根堆的堆顶的数要小,就把堆顶的数弹出,再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。 " "" public  ArrayList<Integer> GetLeastNumbers_Solution (int [] nums, int  k)      if  (k > nums.length || k <= 0 )         return  new  ArrayList<>();     PriorityQueue<Integer> maxHeap = new  PriorityQueue<>((o1, o2) -> o2 - o1);     for  (int  num : nums) {         maxHeap.add(num);         if  (maxHeap.size() > k)             maxHeap.poll();     }     return  new  ArrayList<>(maxHeap); } "" " 2、快排 " "" class  Solution      public  int [] getLeastNumbers(int [] arr, int  k) {         if (k==0  || arr.length==0 ){             return  new  int [0 ];         }         else              return  quicksort(arr,0 ,arr.length-1 ,k-1 );     }               private  int [] quicksort(int [] nums,int  lo,int  hi,int  k){         int  pivot=partition(nums,lo,hi);         if (pivot==k){             return  Arrays.copyOf(nums,k+1 );         }         else {             return  pivot>k?quicksort(nums,lo,pivot-1 ,k):quicksort(nums,pivot+1 ,hi,k);         }     }               private  int  partition (int [] nums,int  lo,int  hi)          int  pivot_value=nums[lo];         int  i=lo,j=hi+1 ;         while (true ){             while (++i<=hi && nums[i]<pivot_value);             while  (--j>=lo && nums[j]>pivot_value);             if (i>=j){                 break ;             }             int  temp=nums[i];             nums[i]=nums[j];             nums[j]=temp;         }         nums[lo]=nums[j];         nums[j]=pivot_value;         return  j;     } } "" " 3、二叉搜索树--TreeMap 我们遍历数组中的数字,维护一个数字总个数为 K 的 TreeMap: 1.若目前 map 中数字个数小于 K,则将 map 中当前数字对应的个数 +1; 2.否则,判断当前数字与 map 中最大的数字的大小关系:若当前数字大于等于 map 中的最大数字,就直接跳过该数字;若当前数字小于 map 中的最大数字,则将 map 中当前数字对应的个数 +1,并将 map 中最大数字对应的个数减 1。 " "" class  Solution      public  int [] getLeastNumbers(int [] arr, int  k) {         if  (k == 0  || arr.length == 0 ) {             return  new  int [0 ];         }                           TreeMap<Integer, Integer> map = new  TreeMap<>();         int  cnt = 0 ;         for  (int  num: arr) {                          if  (cnt < k) {                 map.put(num, map.getOrDefault(num, 0 ) + 1 );                 cnt++;                 continue ;             }                                                                               Map.Entry<Integer, Integer> entry = map.lastEntry();             if  (entry.getKey() > num) {                 map.put(num, map.getOrDefault(num, 0 ) + 1 );                 if  (entry.getValue() == 1 ) {                     map.pollLastEntry();                   } else  {                     map.put(entry.getKey(), entry.getValue() - 1 );                   }             }         }                  int [] res = new  int [k];         int  idx = 0 ;         for  (Map.Entry<Integer, Integer> entry: map.entrySet()) {             int  freq = entry.getValue();             while  (freq-- > 0 ) {                 res[idx++] = entry.getKey();             }         }         return  res;     } } 
10、堆
LRU缓存实现 一、问题描述 
节点用LinkedHashMap存 k,value
get:利用key获得对应节点 并且将该节点删除,在链表末重新加上该节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 import  java.util.*;public  class  Solution           public  int [] LRU (int [][] operators, int  k) {                  Map<Integer, Integer> map = new  LinkedHashMap<>();         List<Integer> list = new  LinkedList<>();         for  (int [] operator : operators) {             int  key = operator[1 ];             switch (operator[0 ]) {                 case  1 :                     int  value = operator[2 ];                     if  (map.size() < k) {                         map.put(key, value);                     } else  {                         Iterator it = map.keySet().iterator();                         map.remove(it.next());                         map.put(key, value);                     }                     break ;                 case  2 :                     if  (map.containsKey(key)) {                         int  val = map.get(key);                         list.add(val);                         map.remove(key);                         map.put(key, val);                     } else  {                         list.add(-1 );                     }                     break ;                 default :             }         }         int [] res = new  int [list.size()];         int  i = 0 ;         for  (int  val : list) {             res[i++] = val;         }         return  res;     } } "" " 使用LinkedHashMap不过关  双向队列也要自己写 " "" public  class  LRUCache      HashMap<Integer, Node> map;      DoubleLinkedList cache;       int  cap;       public  LRUCache (int  capacity)          map   = new  HashMap<>();         cache = new  DoubleLinkedList();         cap   = capacity;     }          public  void  put (int  key, int  val)          Node newNode = new  Node(key, val);                  if (map.containsKey(key)){               cache.delete(map.get(key));             cache.addFirst(newNode);             map.put(key, newNode);         }else {              if (map.size() == cap){                 int  k = cache.deleteLast();                 map.remove(k);             }             cache.addFirst(newNode);             map.put(key, newNode);                      }     }          public  int  get (int  key)          if (!map.containsKey(key))   return  -1 ;                  int  val = map.get(key).val;         put(key, val);                  return  val;     } } class  DoubleLinkedList     Node head;     Node tail;     public  DoubleLinkedList ()          head = new  Node(0 ,0 );         tail = new  Node(0 ,0 );         head.next = tail;         tail.prev = head;     }     public  void  addFirst (Node node)          node.next   = head.next;         node.prev   = head;         head.next.prev = node;         head.next      = node;     }     public  int  delete (Node n)          int  key = n.key;         n.next.prev = n.prev;         n.prev.next = n.next;                  return  key;     }     public  int  deleteLast ()          if (head.next == tail)   return  -1 ;         return  delete(tail.prev);     } } class  Node     public  int  key;     public  int  val;     public  Node prev;     public  Node next;     public  Node (int  key, int  val)          this .key = key;         this .val = val;     } } 
最小编辑距离 dp 一、问题描述 
对“dp[i-1][j-1] 表示替换操作,dp[i-1][j] 表示删除操作,dp[i][j-1] 表示插入操作。”的补充理解:
(1) dp[i-1][j-1],即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro,然后将第五个字符 word1[4](因为下标基数以 0 开始) 由 e 替换为 s(即替换为 word2 的第三个字符,word2[2])
(2) dp[i][j-1],即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro,然后在末尾补充一个 s,即插入操作
(3) dp[i-1][j],即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros,然后删除 word1 的第 5 个字符
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class  Solution  public :    int  minEditCost (string str1, string str2, int  ic, int  dc, int  rc)           if (str1=="" &&str2=="" ) return  0 ;         int  len1 = str1.size();         int  len2 = str2.size();                  int  dp[len1+1 ][len2+1 ];         for (int  i=0 ;i<=len1;i++){             dp[i][0 ] = i*dc;         }         for (int  j=0 ;j<=len2;j++){             dp[0 ][j] = j*ic;         }         for (int  i=1 ;i<=len1;i++){             for (int  j=1 ;j<=len2;j++){                 if (str1[i-1 ]==str2[j-1 ]) dp[i][j] = dp[i-1 ][j-1 ];                 else {                                                                                    int  choice1 = dp[i-1 ][j-1 ] + rc;                                                                                                         int  choice2 = dp[i][j-1 ]+ic;                                                                                                         int  choice3 = dp[i-1 ][j]+dc;                     dp[i][j] = min(choice1,min(choice2,choice3));                 }             }         }         return  dp[len1][len2];     } }; 
图 无向图的遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 "" " dfs 判断连通图个数 " "" class  Solution      public  int  findCircleNum (int [][] isConnected)           int  res=0 ;         int  num=isConnected.length;         boolean [] visited=new  boolean [num];         for (int  i=0 ;i<num;i++){             if (visited[i]==false ){                 dfs(visited,i,isConnected);                 res+=1 ;             }         }         return  res;     }     public  void  dfs (boolean [] visited,int  cur,int [][]isConnected)          for (int  j=0 ;j<visited.length;j++){             if (isConnected[cur][j]==1 &&visited[j]==false ){                  visited[j]=true ;                 dfs(visited,j,isConnected);             }         }     } } "" " 2、bfs 对于每个城市,如果该城市尚未被访问过,则从该城市开始广度优先搜索,直到同一个连通分量中的所有城市都被访问到,即可得到一个省份。 " "" class  Solution      public  int  findCircleNum (int [][] isConnected)           int  res = 0 ;         int  num = isConnected.length;         boolean [] visited = new  boolean [num];         Queue<Integer> queue=new  LinkedList<>();         for (int  i=0 ;i<num;i++){             if (visited[i]==false ){                 queue.add(i);                 res+=1 ;                 while  (!queue.isEmpty()){                       int  j=queue.poll();                     for (int  k=0 ;k<num;k++){                         if (isConnected[j][k]==1 &&visited[k]==false ){                             queue.add(k);                             visited[k]=true ;                         }                     }                 }             }         }         return  res;     } } 
有序–二分
不会:34
剑指 Offer 04. 二维数组中的查找 
剑指 Offer 07. 重建二叉树 
剑指 Offer 08. 二叉树的下一个结点 
剑指 Offer 09. 用两个栈实现队列 
剑指 Offer 10-1 求斐波那契数列 
剑指 Offer 10-2 青蛙跳台阶问题 
剑指 Offer 10-3 矩形覆盖 
剑指 Offer 10-4 变态跳台阶 
剑指 Offer 11 旋转数组的最小数字 
剑指 Offer 12 矩阵中的路径 
剑指 Offer 13 机器人的运动范围 
剑指 Offer 14 剪绳子 
剑指 Offer 15 二进制中1的个数 
剑指 Offer 16 数值的整数次方 
剑指 Offer 18-2 删除链表中重复的结点  
剑指 Offer 19 正则表达式匹配 
剑指 Offer 21 调整数组顺序使奇数位于偶数前面 
剑指 Offer 22 链表中倒数第k个节点 
剑指 Offer 23 链表中环的入口结点 
剑指 Offer 24 反转链表 
剑指 Offer 25 合并两个排序的链表 
剑指 Offer 26 树的子结构 
剑指 Offer 29 顺时针打印矩阵 
剑指 Offer 30 包含min函数的栈 )
剑指 Offer 31 栈的压入、弹出序列 
剑指 Offer 33 二叉搜索树的后序遍历序列 
剑指 Offer 34 二叉树中和为某一值的路径 
剑指 Offer 35 复制链表的复制 
剑指 Offer 36 二叉搜索树与双向链表 
剑指 Offer 37 序列化二叉树 
剑指 Offer 38 字符串的全排列 
剑指 Offer 39 数组中出现次数超过一半的数字 
剑指 Offer 40 最小的k个数 
剑指 Offer 42 连续子数组的最大和 
剑指 Offer 41 数据流中的中位数 
剑指 Offer 43 1~n整数中1出现的次数 
剑指 Offer 44 数字序列中某一位的数字 
剑指 Offer 45 把数组排成最小的数 
剑指 Offer 46 把数字翻译成字符串 
剑指 Offer 47 礼物的最大价值 
剑指 Offer 48 最长不含重复字符的子字符串 
剑指 Offer 49 丑数 
剑指 Offer 50 第一个只出现一次的字符 
剑指 Offer 51 数组中的逆序对 
剑指 Offer 52 两个链表的第一个公共节点 
剑指 Offer 53_1 在排序数组中查找数字 
剑指 Offer 53_2 0~n-1中缺失的数字 
剑指 Offer 54 二叉搜索树的第k大节点 
剑指 Offer 55 二叉树的深度 
剑指 Offer 55-1 平衡二叉树 
剑指 Offer 56-1 数组中数字出现的次数 
剑指 Offer 56-2 数组中数字出现的次数2 
剑指 Offer 57 和为s的两个数字 
剑指 Offer 57_2 和为s的两个数字 
剑指 Offer 58_1 和为s的两个数字 
剑指 Offer 58_2 左旋转字符串 
剑指 Offer 59_1 滑动窗口的最大值 
剑指 Offer 59_2 队列的最大值 
剑指 Offer 60 n个骰子的点数 
剑指 Offer 61 扑克牌中的顺子 
剑指 Offer 62 圆圈中最后剩下的数字 
剑指 Offer 63 股票的最大利润 
剑指 Offer 64 求1+2+…+n 
剑指 Offer 65 不用加减乘除做加法 
剑指 Offer 66 构建乘积数组 
剑指 Offer 67 把字符串转换为整数 
剑指 Offer 68_1 二叉搜索树的最近公共祖先 
大数的和 
接雨水 
剑指 Offer 04. 二维数组中的查找 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 '' ' 有序就要想到二分  从数组右上角出发 其实是二叉搜索树 ' '' class  Solution      public  boolean  findNumberIn2DArray (int [][] matrix, int  target)           if (matrix.length<1 ||matrix[0 ].length<1 ) return  false ;         int  i=0 ,j=matrix[0 ].length-1 ;         while (i<matrix.length&&j>=0 ){             if (matrix[i][j]>target) j--;             else  if (matrix[i][j]<target) i++;             else  return  true ;         }         return  false ;     } } 
剑指 Offer 07. 重建二叉树 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 '' ' 前序遍历性质: 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。 中序遍历性质: 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。 利用map 存中序遍历的值与其对应的下标,这样方便查找根节点在中序遍历数组的下标 ' '' class  Solution      int [] preorder;     HashMap<Integer,Integer> map=new  HashMap<>();     public  TreeNode buildTree (int [] preorder, int [] inorder)           for (int  i=0 ;i<inorder.length;i++){             map.put(inorder[i],i);         }         this .preorder=preorder;         return   recur(0 ,0 ,inorder.length-1 );     }                    public  TreeNode recur (int  root,int  left,int  right)          if (left>right) return  null ;         TreeNode node=new  TreeNode(preorder[root]);         int  idx=map.get(node.val);         node.left=recur(root+1 ,left,idx-1 );         node.right=recur(root+1 +idx-left,idx+1 ,right);         return   node;     } } 
剑指 Offer 08. 二叉树的下一个结点 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 '' ' 中序遍历某个节点的下一个节点 要么是该节点右子树的最左边的数,要么是其父节点(该节点是父节点的左子节点) 或者是父节点的父节点.... ' '' public  TreeLinkNode GetNext (TreeLinkNode pNode)      if  (pNode.right != null ) {         TreeLinkNode node = pNode.right;         while  (node.left != null )             node = node.left;         return  node;     } else  {         while  (pNode.next != null ) {             TreeLinkNode parent = pNode.next;             if  (parent.left == pNode)                 return  parent;             pNode = pNode.next;         }     }     return  null ; } 
剑指 Offer 09. 用两个栈实现队列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 '' ' 用两个栈 实现队列 队列入操作:直接入左边的栈 队列出操作:假如右边的栈不为空,则直接输出右边栈顶;假如右边栈为空,则将左边的数都弹出压到右边,再输出右边栈顶 ' '' class  CQueue      Stack<Integer> s1;     Stack<Integer> s2;     public  CQueue ()           s1=new  Stack<>();         s2=new  Stack<>();     }     public  void  appendTail (int  value)           s1.push(value);     }     public  int  deleteHead ()           if (!s2.empty()) return  s2.pop();         else  if (!s1.empty()){             while  (!s1.empty()){                 s2.push(s1.pop());             }             return  s2.pop();         }         else  return  -1 ;     } } # Your CQueue object will be instantiated and called as such: # obj = CQueue() # obj.appendTail(value) # param_2 = obj.deleteHead() 
剑指 Offer 10-1 求斐波那契数列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 '' ' 由于只跟前两个数有关,于是用两个变量存前两个数 ' '' class  Solution      public  int  fib (int  n)            int  f0=0 ,f1=1 ;          if (n<2 ) return  n;          int  i=1 ;          while (i<n){              int  temp=f1;              f1=(f0+f1)%1000000007 ;              f0=temp;              i+=1 ;          }          return  f1;     } } 
剑指 Offer 10-2 青蛙跳台阶问题 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 '' ' 跟10-1一样 也是动态规划问题  F(N)=F(N-1)+F(N-2)) 区别在于F(0)=1 因为跳台阶          等于最后剩两步 一次跳两步;         最后剩一步 一次跳一步,         全部情况等于上述两种情况的和 ' '' class  Solution      public  int  numWays (int  n)           if (n<2 ) return  1 ;         int  dp0=1 ,dp1=1 ,i=2 ;         while (i<=n){             int  temp=dp1;             dp1=(dp0+dp1)%1000000007 ;             dp0=temp;             i+=1 ;         }         return  dp1;     } } 
剑指 Offer 10-3 矩形覆盖 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 public  int  rectCover (int  n)      if  (n <= 2 )         return  n;     int  pre2 = 1 , pre1 = 2 ;     int  result = 0 ;     for  (int  i = 3 ; i <= n; i++) {         result = pre2 + pre1;         pre2 = pre1;         pre1 = result;     }     return  result; } 
剑指 Offer 10-4 变态跳台阶 一、问题描述 
二、具体代码 1 2 3 public  int  JumpFloorII (int  target)      return  (int ) Math.pow(2 , target - 1 ); } 
剑指 Offer 11 旋转数组的最小数字 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 "" " 1、找到波谷 " "" class  Solution      public  int  minArray (int [] numbers)           int  i=1 ;         while (i<numbers.length&&numbers[i-1 ]<=numbers[i]) i+=1 ;         if (i==numbers.length) return  numbers[0 ];         else  return  numbers[i];     } } "" " 2、因为递增 有序就要想到二分 数组最后一个数一定小于等于数组第一个数 " "" class  Solution      public  int  minArray (int [] numbers)           int  l=0 ,h=numbers.length-1 ;         while (l<h){             int  m=l+(h-l)/2 ;               if (numbers[m]<numbers[h]) h=m;              else  if (numbers[m]>numbers[h]) l=m+1 ;              else  h--;          }         return  numbers[h];     } } 
剑指 Offer 12 矩阵中的路径 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 '' ' 回溯 ' '' class  Solution      public  boolean  exist (char [][] board, String word)           if (board.length<1 ||board[0 ].length<1 ||word.length()<1 ) return  false ;         int  w=board[0 ].length,h=board.length;         boolean [][] visited=new  boolean [h][w];         char [] words=word.toCharArray();         for (int  i=0 ;i<h;i++) {             for  (int  j=0 ;j<w;j++){                 if (words[0 ]==board[i][j]){                      if (dfs(board,i,j,visited,words,0 )) return  true ;                 }             }         }         return  false ;     }          public  boolean  dfs (char [][] board,int  i,int  j,boolean [][] visited,char [] words,int  idx)                   if (words.length==idx) return  true ;                  if (i<0 ||j<0 ||i==board.length||j==board[0 ].length||visited[i][j]||board[i][j]!=words[idx]){             return  false ;         }                  visited[i][j]=true ;         idx+=1 ;         if (dfs(board,i-1 ,j,visited,words,idx)||dfs(board,i+1 ,j,visited,words,idx)||dfs(board,i,j-1 ,visited,words,idx)||dfs(board,i,j+1 ,visited,words,idx)){             return  true ;         }                  visited[i][j]=false ;         idx-=1 ;         return  false ;     } } 
剑指 Offer 13 机器人的运动范围 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 '' ' 题目就是从[0,0]出发,能够达到哪些地方,只能往上下左右移动,且下标数位和小于k,其实也只需计算往右下移动的 因为左上都是回到已访问过的节点 注意 这道题选择后不能撤销 因为算的是全部能访问到的节点  访问后不可撤销 递归 ' '' class  Solution      public  int  movingCount (int  m, int  n, int  k)           boolean [][] visited=new  boolean [m][n];         return  dfs(visited,0 ,0 ,k);              }     public  int  dfs (boolean [][] visited,int  i,int  j,int  k)          if (isvalid(i,j,k,visited)){             visited[i][j]=true ;                          return  dfs(visited,i+1 ,j,k)+dfs(visited,i,j+1 ,k)+1 ;         }         else  return  0 ;     }          public  boolean  isvalid (int  i,int  j,int  k,boolean [][] visited)          int  temp=0 ;         if (i<0 ||j<0 ||i==visited.length||j==visited[0 ].length||visited[i][j]) return  false ;         while (i>0 ){             temp+=i%10 ;             i/=10 ;         }         while  (j>0 ){             temp+=j%10 ;             j/=10 ;         }         if (temp>k) return  false ;         return  true ;     } } 
剑指 Offer 14 剪绳子 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 '' ' 当每段都为3时,乘积最大 若最后为4,因为2*2大于1*3,所以乘4 其余情况就每段取3 再乘以小于3的 ' '' class  Solution      public  int  cuttingRope (int  n)           int  res=1 ;         if (n<4 ) return  n-1 ;         while (n>4 ){             res*=3 ;             n-=3 ;         }         return  res*n;     } }          
剑指 Offer 15 二进制中1的个数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 '' ' 最右一位和1与 若最右一位为1 则结果为1 否则为0 判断完后 将数往右移一位 ' '' public  class  Solution           public  int  hammingWeight (int  n)           int  count=0 ;         int  help=1 ;         while (n!=0 ){             if ((help&n)!=0 ) count+=1 ;             n=n>>>1 ;          }         return  count;     } }          
剑指 Offer 16 数值的整数次方 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 '' ' 快速幂法(二分法角度) ' '' class  Solution      public  double  myPow (double  x, int  n)           if (n==0 ) return  1.0 ;                  long  b=n;          double  res=1.0 ;         if (n<0 ){             x=1 /x;             b=-b;         }         while (b>0 ){             if ((b&1 )!=0 ) res*=x;              x*=x;             b=b>>1 ;         }         return  res;     } }          
剑指 Offer 18-2 删除链表中重复的结点 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 '' ' 伪造头结点来统一节点为空的情况 ' '' public  class  Solution      public  ListNode deleteDuplication (ListNode pHead)           ListNode preHead = new  ListNode(-1 );           ListNode pre = preHead;         ListNode now = pHead;           ListNode nextNode;           while (now != null ){             nextNode = now.next;             if (nextNode!=null  && now.val==nextNode.val){                   while (now!=null  && now.next!=null  && now.val==nextNode.val){                     now = nextNode;                     nextNode = nextNode.next;                 }                  now = nextNode;               }else {                 pre.next = now;                 pre = now;                 now = nextNode;             }         }         pre.next = now;          return  preHead.next;     } }          
剑指 Offer 19 正则表达式匹配 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ''' ''' class  Solution :    def  isMatch (self, s, p ):         m,n = len(s),len(p)         dp = [[False  for  _ in  range(n+1 )] for  _ in  range(m+1 )]         dp[0 ][0 ] = True           for  i in  range(0 ,m+1 ):             for  j in  range(1 ,n+1 ):                 if  p[j-1 ]!='*' :                       if  i>0  and  (p[j-1 ]==s[i-1 ] or  p[j-1 ]=='.' ):                         dp[i][j]=dp[i-1 ][j-1 ]                 else :                     if  j>=2  and  dp[i][j-2 ]==True :                           dp[i][j]=True                      if  i>=1  and  j>=2  and  (s[i-1 ]==p[j-2 ] or  p[j-2 ]=='.' ) and  dp[i-1 ][j]==True :                           dp[i][j]=True          return  dp[m][n]          
剑指 Offer 21 调整数组顺序使奇数位于偶数前面 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 '' ' 双指针法 i指向偶数 j指向奇数 若i<j则交换 这种可以用于 不要求稳定性的情况 ' '' class  Solution      public  int [] exchange(int [] nums) {         int  l=0 ,h=nums.length-1 ;         while (l<h){             while (l<nums.length&&(nums[l]&1 )==1 )l++;             while (h>0 &&(nums[h]&1 )==0 )h--;             if (l>=h) return  nums;              int  temp=nums[h];             nums[h]=nums[l];             nums[l]=temp;         }         return  nums;     } }          
剑指 Offer 22 链表中倒数第k个节点 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 '' ' 双指针法 helper先走k步 随后helper和res同时走,当helper到达末尾时,res也就到达了倒数第k个数 若如果该链表长度小于k,请返回一个长度为 0 的链表。 ' '' public  ListNode FindKthToTail  (ListNode pHead, int  k)           ListNode res = pHead;     ListNode p = pHead;     while (p!=null  && k>0 ){         p = p.next;         k--;     }     if (k>0 ) return  null ;     while (p!=null ){         res=res.next;         p=p.next;     }     return  res; }          
剑指 Offer 23 链表中环的入口结点 一、问题描述 一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。https://blog.csdn.net/u012534831/article/details/74231581 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 '' ' 快慢指针 ' '' import  java.util.*;public  class  Solution      public  ListNode EntryNodeOfLoop (ListNode pHead)           if (pHead==null  ||pHead.next==null ) return  null ;         ListNode fast = pHead;         ListNode slow = pHead;         do {             fast = fast.next.next;             slow = slow.next;         }while (fast!=null  && fast.next!=null  && fast!=slow);         if (fast==null  ||fast.next==null ) return  null ;                 fast = pHead;         while (fast!=slow){             fast = fast.next;             slow = slow.next;         }         return  slow;     } } 
剑指 Offer 24 反转链表 一、问题描述 二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 "" " pre p tmp 转p.next=pre 然后pre p后移一位 " "" class  Solution      public  ListNode reverseList (ListNode head)           ListNode pre=null ;         ListNode p=head;         while (p!=null ){             ListNode tmp=p.next;             p.next=pre;             pre=p;             p=tmp;         }         return  pre;     } } 
剑指 Offer 25 合并两个排序的链表 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 '' ' 双指针法 i指向链表1待比较节点  j指向链表2待比较节点 ' '' public  class  Solution      public  ListNode Merge (ListNode list1,ListNode list2)           ListNode pre = new  ListNode(-1 );         ListNode now = pre;         while (list1 != null  && list2 != null ){             if (list1.val < list2.val){                 now.next = list1;                 list1 = list1.next;             }else {                 now.next = list2;                 list2 = list2.next;             }             now = now.next;         }         if (list2 == null ) now.next = list1;         if (list1 == null ) now.next = list2;         return  pre.next;     } }     '' '      同样思路 大佬的写法     ' ''     class  Solution       public  ListNode mergeTwoLists (ListNode l1, ListNode l2)           ListNode dum=new  ListNode(0 );         ListNode head=dum;         while (l1!=null &&l2!=null ){             if (l1.val>l2.val) {                 dum.next=l2;                 l2=l2.next;             }             else  {                 dum.next=l1;                 l1=l1.next;             }             dum=dum.next;         }         dum.next=(l1!=null )?l1:l2;         return  head.next;     } } 
剑指 Offer 26 树的子结构 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 '' ' 递归 ' '' class  Solution      public  boolean  isSubStructure (TreeNode A, TreeNode B)           if (A==null ||B==null ) return  false ;         if (issame(A,B)) return  true ;         else  return  isSubStructure(A.left,B)||isSubStructure(A.right,B);     }     public  boolean  issame (TreeNode A,TreeNode B)          if (B==null ) return  true ;          else  if (A==null ) return  false ;         if (A.val!=B.val) return  false ;         else  return  issame(A.left,B.left)&&issame(A.right,B.right);     } } '' ' 二叉树的镜像(翻转左右子树) ' '' class  Solution      public  TreeNode mirrorTree (TreeNode root)           if (root==null ||(root.left==null &&root.right==null )) return  root;         mirrorTree(root.left);         mirrorTree(root.right);         TreeNode tmp=root.right;         root.right=root.left;         root.left=tmp;         return  root;     } } '' ' 判断是否左右对称  ' '' class  Solution      public  boolean  isSymmetric (TreeNode root)           if (root==null ) return  true ;         return  issame(root.left,root.right);     }     public  boolean  issame (TreeNode A,TreeNode B)          if (A==null &&B==null ) return  true ;         if (A==null ||B==null ) return  false ;         return  A.val==B.val&&issame(A.left,B.right)&&issame(A.right,B.left);      } } 
剑指 Offer 29 顺时针打印矩阵 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 "" " 模拟打印  用二维数组存方向和对应的i,j边界变量增量 简化代码 " "" class  Solution      public  int [] spiralOrder(int [][] matrix) {         if (matrix.length<1 ||matrix[0 ].length<0 ) return  new  int [0 ];         int [][] directions={{0 ,1 },{1 ,0 },{0 ,-1 },{-1 ,0 }};         int  m=matrix.length,n=matrix[0 ].length;         boolean [][] visited=new  boolean [m][n];         int [] res=new  int [m*n];         res[0 ]=matrix[0 ][0 ];         visited[0 ][0 ]=true ;         int  i=0 ,j=0 ,idx=1 ,direct_idx=0 ;         while  (idx<res.length){             int  di=directions[direct_idx][0 ];             int  dj=directions[direct_idx][1 ];             while (i+di<m&&i+di>=0 &&j+dj<n&&j+dj>=0 && !visited[i + di][j + dj]){                 i+=di;                 j+=dj;                 res[idx]=matrix[i][j];                 visited[i][j]=true ;                 idx+=1 ;             }             direct_idx=(direct_idx+1 )%4 ;          }         return  res;     } } 
剑指 Offer 30 包含min函数的栈 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 "" " 辅助栈  " "" class  MinStack      Stack<Integer> stack,minstack;          public  MinStack ()           stack=new  Stack<>();         minstack=new  Stack<>();     }     public  void  push (int  x)          stack.push(x);        if (minstack.isEmpty()||minstack.peek()>=x){             minstack.push(x);        }     }     public  void  pop ()           int  tmp=stack.pop();         if (minstack.peek().equals(tmp)) minstack.pop();     }     public  int  top ()           return  stack.peek();     }     public  int  min ()           return  minstack.peek();     } } 
剑指 Offer 31 栈的压入、弹出序列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31     "" "      辅助栈模拟弹入弹出过程中的栈     根据弹出序列         1、若该待弹出元素还没入栈 即在弹入序列中,则将弹入序列中排在该元素前的元素都压入栈中         2、若该待弹出元素在栈中,则一定是栈顶元素 不然就False     " "" class  Solution      public  boolean  validateStackSequences (int [] pushed, int [] popped)           Stack<Integer> stack= new  Stack<>();         int  push_idx=0 ,i=0 ;         while  (i<popped.length){             if (stack.isEmpty()||stack.peek()!=popped[i]){                 while (push_idx<pushed.length&&pushed[push_idx]!=popped[i]){                     stack.add(pushed[push_idx]);                     push_idx+=1 ;                 }                 if (push_idx<pushed.length) {                     i+=1 ;                     push_idx+=1 ;                     continue ;                 }                 return  false ;             }             else  {                  stack.pop();                 i+=1 ;             }         }         return  true ;     } } 
剑指 Offer 32_1 从上到下打印二叉树 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 "" " 层序遍历 " "" class  Solution      public  int [] levelOrder(TreeNode root) {         if (root == null ) return  new  int [0 ];         Queue<TreeNode> queue = new  LinkedList<>(){{ add(root); }};         ArrayList<Integer> ans = new  ArrayList<>();         while (!queue.isEmpty()) {             TreeNode node = queue.poll();             ans.add(node.val);             if (node.left != null ) queue.add(node.left);             if (node.right != null ) queue.add(node.right);         }         int [] res = new  int [ans.size()];         for (int  i = 0 ; i < ans.size(); i++)             res[i] = ans.get(i);         return  res;     } } "" " 2、分层 二维矩阵输出 " "" class  Solution      public  List<List<Integer>> levelOrder(TreeNode root) {         if (root==null ) return  new  LinkedList<>();         Queue<TreeNode> queue=new  LinkedList<>();         queue.add(root);         int  len;         List<List<Integer>> res=new  LinkedList<>();         while (!queue.isEmpty()){             List<Integer> tmplayer= new  LinkedList<>();             len=queue.size();             while (len>0 ){                 TreeNode tmp=queue.poll();                 len-=1 ;                 tmplayer.add(tmp.val);                 if (tmp.left!=null ) queue.add(tmp.left);                 if (tmp.right!=null ) queue.add(tmp.right);             }             res.add(tmplayer);         }         return  res;     } } "" "  3、分层 隔层逆序输出 加个flag就可 " "" class  Solution      public  List<List<Integer>> levelOrder(TreeNode root) {         if (root==null ) return  new  LinkedList<>();         Queue<TreeNode> queue=new  LinkedList<>();         queue.add(root);         int  len;         List<List<Integer>> res=new  LinkedList<>();         boolean  flag=false ;         while (!queue.isEmpty()){             List<Integer> tmplayer= new  LinkedList<>();             len=queue.size();             while (len>0 ){                 TreeNode tmp=queue.poll();                 len-=1 ;                 if (flag){                     tmplayer.add(0 ,tmp.val);                 }                 else                  {tmplayer.add(tmp.val);}                 if (tmp.left!=null ) queue.add(tmp.left);                 if (tmp.right!=null ) queue.add(tmp.right);             }             flag=!flag;             res.add(tmplayer);         }         return  res;     } } 
剑指 Offer 33 二叉搜索树的后序遍历序列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "" " 二叉搜索树的后序遍历有个特点: 根节点是最后一个数  并且可以将序列按顺序切割  前一截小于根节点的为左子树,后一截大于根节点的为右子树。 l,m-1为左子树 m,h-1为右子树 " "" class  Solution      public  boolean  verifyPostorder (int [] postorder)           return  recur(postorder,0 ,postorder.length-1 );     }     public  boolean  recur (int [] postorder,int  l,int  h)          if (l>=h) return  true ;         int  m,p=l;         int  root=postorder[h];         while (postorder[p]<root) p++;         m=p;         while (postorder[p]>root) p++;         return  p==h&&recur(postorder,l,m-1 )&&recur(postorder,m,h-1 );      } } 
剑指 Offer 34 二叉树中和为某一值的路径 一、问题描述 
二、具体代码 回溯+dfs  先序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public  class  Solution      private  ArrayList<ArrayList<Integer>> res = new  ArrayList<>();     private  ArrayList<Integer> path = new  ArrayList<>();     public  ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int  target) {         backtrace(root, target);         return  res;     }     private  void  backtrace (TreeNode root, int  target)          if (root == null ) return ;         path.add(root.val);          if (root.left==null  && root.right==null  && root.val==target){             res.add(new  ArrayList<>(path));         }else {             backtrace(root.left, target-root.val);             backtrace(root.right, target-root.val);         }         path.remove(path.size()-1 );      } } 
剑指 Offer 35 复杂链表的复制 一、问题描述 
二、具体代码 具体分为3步:
1、在每个原节点后面新增一个节点 值与原节点一致 temp=Node(cur.val,cur.next)
2、复制原节点的randan指针  新节点的randan指向原节点randan的后一个节点  copycur.random=cur.random.next
3、拆分链表  要注意两个链表的末尾的next都为None1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class  Solution      public  Node copyRandomList (Node head)           if (head == null ) return  null ;         Node cur = head;                  while (cur != null ) {             Node tmp = new  Node(cur.val);             tmp.next = cur.next;             cur.next = tmp;             cur = tmp.next;         }                  cur = head;         while (cur != null ) {             if (cur.random != null )                 cur.next.random = cur.random.next;             cur = cur.next.next;         }                  cur = head.next;         Node pre = head, res = head.next;         while (cur.next != null ) {             pre.next = pre.next.next;             cur.next = cur.next.next;             pre = pre.next;             cur = cur.next;         }         pre.next = null ;          return  res;           } } 
剑指 Offer 36 二叉搜索树与双向链表 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 利用二叉搜索树中序遍历是递增的这一特性   递归中序遍历 另外新增两个指针节点 head和pre " "" public  class  Solution      private  TreeNode pre;     private  TreeNode head;     public  TreeNode Convert (TreeNode pRootOfTree)           inOrder(pRootOfTree);         return  head;     }     private  void  inOrder (TreeNode root)          if (root == null ) return ;         inOrder(root.left);         root.left = pre;         if (pre!=null ) pre.right = root;         if (head == null ) head = root;         pre = root;         inOrder(root.right);     } } 
剑指 Offer 37 序列化二叉树 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 "" " 序列化的字符串实际上是二叉树的 “层序遍历”(BFS)结果 队列模仿层序遍历  string->int  Integer.parseInt(string) int ->string   string.valueof(int) string截断  .substring() " "" public  class  Codec      public  String serialize (TreeNode root)           if (root==null ) return  "[]" ;         StringBuilder res=new  StringBuilder("[" );         Queue<TreeNode> queue=new  LinkedList<>();         queue.add(root);         while (!queue.isEmpty()){             TreeNode temp=queue.poll();             if (temp!=null ){                 res.append(temp.val+"," );                 queue.add(temp.left);                 queue.add(temp.right);             }             else  res.append("null," );         }         res.delete(res.length()-1 ,res.length()-1 );         res.append("]" );         return  res.toString();     }     public  TreeNode deserialize (String data)           if (data.equals("[]" )) return  null ;         String[] nums=data.substring(1 ,data.length()-1 ).split("," );         Queue<TreeNode> queue=new  LinkedList<>();         TreeNode root=new  TreeNode(Integer.parseInt(nums[0 ]));         queue.add(root);         int  i=1 ;         while  (!queue.isEmpty()){             TreeNode temp=queue.poll();             if (temp!=null ){                 if (!nums[i].equals("null" )){                     temp.left=new  TreeNode(Integer.parseInt(nums[i]));                     queue.add(temp.left);                 }                 i+=1 ;                 if (!nums[i].equals("null" )){                     temp.right=new  TreeNode(Integer.parseInt(nums[i]));                     queue.add(temp.right);                 }                 i+=1 ;             }         }         return  root;     } } 
剑指 Offer 38 字符串的全排列 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 "" " 回溯+剪枝 " "" import  java.util.*;public  class  Solution      public  String[] permutation(String s) {         int  len = s.length();         if  (len == 0 ) {             return  new  String[0 ];         }                  char [] charArr = s.toCharArray();                  Arrays.sort(charArr);                  StringBuilder path = new  StringBuilder();         boolean [] used = new  boolean [len];                  List<String> res = new  ArrayList<>();         dfs(charArr, len, 0 , used, path, res);                  return  res.toArray(new  String[0 ]);     }          private  void  dfs (char [] charArr,                       int  len,                      int  depth,                      boolean [] used,                      StringBuilder path,                      List<String> res)          if  (depth == len) {                          res.add(path.toString());             return ;         }         for  (int  i = 0 ; i < len; i++) {             if  (!used[i]) {                 if  (i > 0  && charArr[i] == charArr[i - 1 ] && !used[i - 1 ]) {                     continue ;                 }                 used[i] = true ;                 path.append(charArr[i]);                 dfs(charArr, len, depth + 1 , used, path, res);                                  path.deleteCharAt(path.length() - 1 );                 used[i] = false ;             }         }     } } 
剑指 Offer 39 数组中出现次数超过一半的数字 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 "" " 摩尔投票法: 设输入数组 nums 的众数为 x ,数组长度为 n 。 推论一: 若记 众数 的票数为 +1 ,非众数 的票数为 −1 ,则一定有所有数字的 票数和 > 0。                                   推论二: 若数组的前 a 个数字的 票数和 =0 ,则 数组剩余 (n-a)个数字的 票数和一定仍 >0 ,即后(n−a) 个数字的 众数仍为x 。 算法流程: 初始化: 票数统计 votes = 0 , 众数 x; 循环: 遍历数组 nums 中的每个数字 num ; 当 票数 votes 等于 0 ,则假设当前数字 num 是众数; 当 num = x 时,票数 votes 自增 1 ;当 num != x 时,票数 votes 自减 1 ; 返回值: 返回 x 即可; " "" class  Solution      public  int  majorityElement (int [] nums)           int  num=nums[0 ];         if (nums.length<3 ){             return  nums[0 ];         }         int  count=0 ;         for (int  i:nums){             if (i==num){                 count+=1 ;             }             else  if (count>1 ){                 count-=1 ;             }             else {                 num=i;                 count=1 ;             }         }         return  num;     } } "" " 若找出投票超过1/3的候选人 " "" class  Solution      public  List<Integer> majorityElement (int [] nums)                    List<Integer> res = new  ArrayList<>();         if  (nums == null  || nums.length == 0 ) return  res;                  int  cand1 = nums[0 ], count1 = 0 ;         int  cand2 = nums[0 ], count2 = 0 ;                           for  (int  num : nums) {                          if  (cand1 == num) {                 count1++;                 continue ;             }             if  (cand2 == num) {                 count2++;                 continue ;             }                          if  (count1 == 0 ) {                 cand1 = num;                 count1++;                 continue ;             }                          if  (count2 == 0 ) {                 cand2 = num;                 count2++;                 continue ;             }             count1--;             count2--;         }                           count1 = 0 ;         count2 = 0 ;         for  (int  num : nums) {             if  (cand1 == num) count1++;             else  if  (cand2 == num) count2++;         }         if  (count1 > nums.length / 3 ) res.add(cand1);         if  (count2 > nums.length / 3 ) res.add(cand2);         return  res;     } } 作者:wotxdx 链接:https: 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 
剑指 Offer 40 最小的k个数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 "" " 1、大堆   我们用一个大根堆实时维护数组的前 k 小值。每次大根堆中数字的个数超过k后,将最大的弹出,这样每次留下来的都是最小的k个数 " "" public  ArrayList<Integer> GetLeastNumbers_Solution (int [] nums, int  k)      if  (k > nums.length || k <= 0 )         return  new  ArrayList<>();     PriorityQueue<Integer> maxHeap = new  PriorityQueue<>((o1, o2) -> o2 - o1);     for  (int  num : nums) {         maxHeap.add(num);         if  (maxHeap.size() > k)             maxHeap.poll();     }     return  new  ArrayList<>(maxHeap); } "" " 2、快排 " "" class  Solution      public  int [] getLeastNumbers(int [] arr, int  k) {         if (k==0  || arr.length==0 ){             return  new  int [0 ];         }         else              return  quicksort(arr,0 ,arr.length-1 ,k-1 );     }               private  int [] quicksort(int [] nums,int  lo,int  hi,int  k){         int  pivot=partition(nums,lo,hi);         if (pivot==k){             return  Arrays.copyOf(nums,k+1 );         }         else {             return  pivot>k?quicksort(nums,lo,pivot-1 ,k):quicksort(nums,pivot+1 ,hi,k);         }     }               private  int  partition (int [] nums,int  lo,int  hi)          int  pivot_value=nums[lo];         int  i=lo,j=hi+1 ;         while (true ){             while (++i<=hi && nums[i]<pivot_value);             while  (--j>=lo && nums[j]>pivot_value);             if (i>=j){                 break ;             }             int  temp=nums[i];             nums[i]=nums[j];             nums[j]=temp;         }         nums[lo]=nums[j];         nums[j]=pivot_value;         return  j;     } } "" " 3、二叉搜索树--TreeMap 我们遍历数组中的数字,维护一个数字总个数为 K 的 TreeMap: 1.若目前 map 中数字个数小于 K,则将 map 中当前数字对应的个数 +1; 2.否则,判断当前数字与 map 中最大的数字的大小关系:若当前数字大于等于 map 中的最大数字,就直接跳过该数字;若当前数字小于 map 中的最大数字,则将 map 中当前数字对应的个数 +1,并将 map 中最大数字对应的个数减 1。 " "" class  Solution      public  int [] getLeastNumbers(int [] arr, int  k) {         if  (k == 0  || arr.length == 0 ) {             return  new  int [0 ];         }                           TreeMap<Integer, Integer> map = new  TreeMap<>();         int  cnt = 0 ;         for  (int  num: arr) {                          if  (cnt < k) {                 map.put(num, map.getOrDefault(num, 0 ) + 1 );                 cnt++;                 continue ;             }                                                                               Map.Entry<Integer, Integer> entry = map.lastEntry();             if  (entry.getKey() > num) {                 map.put(num, map.getOrDefault(num, 0 ) + 1 );                 if  (entry.getValue() == 1 ) {                     map.pollLastEntry();                   } else  {                     map.put(entry.getKey(), entry.getValue() - 1 );                   }             }         }                  int [] res = new  int [k];         int  idx = 0 ;         for  (Map.Entry<Integer, Integer> entry: map.entrySet()) {             int  freq = entry.getValue();             while  (freq-- > 0 ) {                 res[idx++] = entry.getKey();             }         }         return  res;     } } 
剑指 Offer 42 连续子数组的最大和 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 动态规划 dp 以当前节点为结尾的数组和的最大值 若前一个节点的最大值为正 直接加上即可 不然就不加 随时更新全局最大值 " "" class  Solution      public  int  maxSubArray (int [] nums)           if (nums.length<2 ){             return  nums[0 ];         }         int  pre_dp=nums[0 ];         int  now_dp;         int  res=pre_dp;         for (int  i=1 ;i<nums.length;i++){             now_dp=nums[i];             if  (pre_dp>0 ){                 now_dp+=pre_dp;                 }             pre_dp=now_dp;             res=res>now_dp?res:now_dp;          }         return  res;     } } 
剑指 Offer 41 数据流中的中位数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 "" " 左右均分用大小堆存  注意返回要为double,所以最后/2.0 " "" class  MedianFinder      Queue<Integer> left,right;           public  MedianFinder ()           left=new  PriorityQueue<>((x,y)->(y-x));         right=new  PriorityQueue<>();     }          public  void  addNum (int  num)           if (left.size()==right.size()){             right.add(num);             left.add(right.poll());         }         else  {             left.add(num);             right.add(left.poll());         }     }     public  double  findMedian ()           if (left.size()==right.size()){             return  (left.peek()+right.peek())/2.0 ;         }         else  return  left.peek();     } } 
剑指 Offer 43 1~n整数中1出现的次数 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class  Solution      public  int  countDigitOne (int  n)           int  digit=1 ,low=0 ,high=n/10 ;         int  cur=n%10 ,res=0 ;         while (cur!=0 ||high!=0 ){             if (cur==0 ) res+=high*digit;               else  if (cur==1 ) res+=high*digit+low+1 ;             else  res+=(high+1 )*digit;             low+=cur*digit;             digit*=10 ;             cur=high%10 ;             high/=10 ;         }         return  res;     } } 
剑指 Offer 44 数字序列中某一位的数字 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class  Solution      public  int  findNthDigit (int  n)           int  digit = 1 ;            long  start = 1 ;           long  count = 9 ;           while (n>count){             n-=count;             digit+=1 ;             start*=10 ;             count=digit*start*9 ;          }                  long  num=start+(n-1 )/digit;         int  res=(n-1 )%digit;           return  Long.toString(num).charAt(res)-'0' ;     } } 
剑指 Offer 45 把数组排成最小的数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class  Solution      public  String minNumber (int [] nums)           String[] strs=new  String[nums.length];         for (int  i=0 ;i<nums.length;i++){             strs[i]=String.valueOf(nums[i]);           }                             Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));                  StringBuilder res=new  StringBuilder();           for (String temp:strs){             res.append(temp);         }         return  res.toString();     } } 
剑指 Offer 46 把数字翻译成字符串 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 "" " 递归  也可以dp " "" class  Solution      public  int  translateNum (int  num)           if (num<10 ){               return  1 ;         }         int  yushu=num%100 ;         if (yushu<10  || yushu>25 )              {return  translateNum(num/10 );}         else {             return  translateNum(num/10 )+translateNum(num/100 );          }     } } 
剑指 Offer 47 礼物的最大价值 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 "" " dp " "" class  Solution      public  int  maxValue (int [][] grid)           int [][] dp=new  int [grid.length][grid[0 ].length];         dp[0 ][0 ]=grid[0 ][0 ];         for (int  i=0 ;i<grid.length;i++){             for (int  j=0 ;j<grid[0 ].length;j++){                 int  left=j>0 ?dp[i][j-1 ]:0 ;                   int  top=i>0 ?dp[i-1 ][j]:0 ;                    dp[i][j]=Math.max(left,top)+grid[i][j];               }         }         return  dp[grid.length-1 ][grid[0 ].length-1 ];     } } 
剑指 Offer 48 最长不含重复字符的子字符串 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class  Solution      public  int  lengthOfLongestSubstring (String s)           if  (s.length()==0 ) return  0 ;         HashMap<Character, Integer> map = new  HashMap<Character, Integer>();         int  max = 0 ;         int  left = 0 ;         for (int  i = 0 ; i < s.length(); i ++){             if (map.containsKey(s.charAt(i))){                 left = Math.max(left,map.get(s.charAt(i))+1 );             }             map.put(s.charAt(i),i);             max = Math.max(max,i-left+1 );         }         return  max;        } } 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 "" " 动态规划  " "" class  Solution      public  int  lengthOfLongestSubstring (String s)           int  res=0 ;         int  temp=0 ;          Map<Character,Integer> map=new  HashMap<>();         for (int  j=0 ;j<s.length();j++) {             int  i = map.getOrDefault(s.charAt(j),-1 );                map.put(s.charAt(j),j);              temp=temp<j-i?temp+1 :j-i;              res=Math.max(temp,res);          }         return  res;     } } 
剑指 Offer 49 丑数 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 "" " 三指针法  所有丑数的排列,必定就是ABC3个数组的合并结果然后去重得到的,就转换成了三个有序数组的无重复元素合并的问题 " "" class  Solution      public  int  nthUglyNumber (int  n)           if (n==0 ){             return  0 ;         }         int [] ugly = new  int [n];         ugly[0 ]=1 ;         int  i=0 ,j=0 ,k=0 ;         for (int  idx=1 ;idx<n;idx++){             int  temp=Math.min(ugly[i]*2 ,Math.min(ugly[j]*3 ,ugly[k]*5 ));             if (temp==ugly[i]*2 )i++;             if (temp==ugly[j]*3 )j++;             if (temp==ugly[k]*5 )k++;             ugly[idx]=temp;         }         return  ugly[n-1 ];     } } 
剑指 Offer 50 第一个只出现一次的字符 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 "" " 数组存出现次数 再遍历一次找第一个出现次数为一次的字符返回即可 " "" class  Solution      public  char  firstUniqChar (String s)           int [] count=new  int [26 ];         for (char  c:s.toCharArray()){             count[c-'a' ]+=1 ;         }         for (char  c:s.toCharArray()){             if (count[c-'a' ]==1 ){                 return  c;             }         }         return  ' ' ;     } } "" " 维持一个队列,其中队首永远是目前只出现一次的数 也就是每次insert的时候,都去检测队首,若队首出现不止一次,则删除,直到队首只出现一次为止 由于是字符,ASCII码只有128个字符,所以可以用128长的数组来记录出现次数 " "" import  java.util.*;public  class  Solution           int [] cnt = new  int [128 ];     Queue<Character> queue = new  LinkedList<>();     public  void  Insert (char  ch)       {        cnt[ch]++;         queue.add(ch);         while (!queue.isEmpty() && cnt[queue.peek()]>1 ){             queue.poll();         }              }        public  char  FirstAppearingOnce ()       {        return  queue.isEmpty()?'#' :queue.peek();     } } 
剑指 Offer 51 数组中的逆序对 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 "" " 归并排序 在于「归并」当中「并」的过程:在左右两个有序数组合并的过程中计算逆序对 " "" public  class  Solution      public  int  reversePairs (int [] nums)           int  len = nums.length;         if  (len < 2 ) {             return  0 ;         }         int [] copy = new  int [len];         for  (int  i = 0 ; i < len; i++) {             copy[i] = nums[i];         }         int [] temp = new  int [len];         return  reversePairs(copy, 0 , len - 1 , temp);     }          private  int  reversePairs (int [] nums, int  left, int  right, int [] temp)           if  (left == right) {             return  0 ;         }         int  mid = left + (right - left) / 2 ;         int  leftPairs = reversePairs(nums, left, mid, temp);         int  rightPairs = reversePairs(nums, mid + 1 , right, temp);         if  (nums[mid] <= nums[mid + 1 ]) {             return  leftPairs + rightPairs;         }         int  crossPairs = mergeAndCount(nums, left, mid, right, temp);         return  leftPairs + rightPairs + crossPairs;     }          private  int  mergeAndCount (int [] nums, int  left, int  mid, int  right, int [] temp)           for  (int  i = left; i <= right; i++) {             temp[i] = nums[i];         }         int  i = left;         int  j = mid + 1 ;         int  count = 0 ;         for  (int  k = left; k <= right; k++) {             if  (i == mid + 1 ) {                 nums[k] = temp[j];                 j++;             } else  if  (j == right + 1 ) {                  nums[k] = temp[i];                 i++;             } else  if  (temp[i] <= temp[j]) {                 nums[k] = temp[i];                 i++;             } else  {                  nums[k] = temp[j];                 j++;                 count += (mid - i + 1 );              }         }         return  count;     } } 
剑指 Offer 52 两个链表的第一个公共节点 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 "" " 求得A,B的长度 由于公共节点,则最后的末节点一定一致 双指针 将两者的长度调为一致后  一起往后移动  遇到第一个相同的节点即为第一个公共节点 " "" public  class  Solution      public  ListNode FindFirstCommonNode (ListNode pHead1, ListNode pHead2)           int  len1 = 0 ;         int  len2 = 0 ;         ListNode p1 = pHead1, p2 = pHead2;                  while (p1!= null ){             len1+=1 ;             p1= p1.next;         }         while (p2 != null ){             len2+=1 ;             p2 = p2.next;         }         if (len1>len2){             int  k = len1-len2;             while (k>0 ){                 pHead1 = pHead1.next;                 k-=1 ;             }         }else {             int  k = len2-len1;             while (k>0 ){                 pHead2 = pHead2.next;                 k-=1 ;             }         }         while (pHead2 != pHead1){             pHead2 = pHead2.next;             pHead1 = pHead1.next;         }         return  pHead2;     } } "" " 设 A 的长度为 a + c,B 的长度为 b + c,其中 c 为尾部公共部分长度,可知 a + c + b = b + c + a。 当访问链表 A 的指针访问到链表尾部时,令它从链表 B 的头部重新开始访问链表 B;同样地,当访问链表 B 的指针访问到链表尾部时,令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。 " "" public  ListNode FindFirstCommonNode (ListNode pHead1, ListNode pHead2)      ListNode l1 = pHead1, l2 = pHead2;     while  (l1 != l2) {         l1 = (l1 == null ) ? pHead2 : l1.next;         l2 = (l2 == null ) ? pHead1 : l2.next;     }     return  l1; } 
剑指 Offer 53_1 在排序数组中查找数字 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 "" " 二分查找+双指针拓展找边界 " "" class  Solution      public  int  search (int [] nums, int  target)                    int  index=bisearch(nums,target);         if (index==-1 ){             return  0 ;         }         int  low=index-1 ,high=index+1 ;                  while (low>=0 &&nums[low]==target)low--;         while  (high<nums.length&&nums[high]==target) high++;         return  high-low-1 ;     }          public  int  bisearch (int [] nums,int  target)          int  low=0 ,high=nums.length-1 ;         while (low<=high){             int  mid=(low+high)/2 ;             if (nums[mid]==target){                 return  mid;             }             else  if (nums[mid]<target){                 low=mid+1 ;             }             else  {                 high=mid-1 ;             }         }         return  -1 ;     } } 
剑指 Offer 53_2 0~n-1中缺失的数字 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 "" " 二分查找 " "" class  Solution      public  int  missingNumber (int [] nums)           int  low=0 ,high=nums.length-1 ;         while (low<=high){             int  mid=(low+high)/2 ;             if (nums[mid]==mid){                 low=mid+1 ;             }             else {                 high=mid-1 ;             }          }         return  low;      } } 
剑指 Offer 54 二叉搜索树的第k大节点 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 "" " 利用二叉搜索树中序遍历递增的规则 右中左遍历 第k个数即为所求结果。 " "" class  Solution      int  res, k;     public  int  kthLargest (TreeNode root, int  k)           this .k = k;         dfs(root);         return  res;     }     void  dfs (TreeNode root)           if (root == null ) return ;         dfs(root.right);         if (k == 0 ) return ;         if (--k == 0 ) res = root.val;         dfs(root.left);     } } "" " 递归 但时间复杂度高  若k=1 则重复计算右子树个数 " ""     public  int  kthLargest (TreeNode root, int  k)           int  right=treenum(root.right);         if (right<k){             if (right==k-1 ){                 return  root.val;             }             else  {                 return  kthLargest(root.left,k-right-1 );             }         }         else  {             return  kthLargest(root.right,k);         }     }     public  int  treenum (TreeNode root)          if (root==null ){             return  0 ;         }         return  treenum(root.left)+treenum(root.right)+1 ;     } 
剑指 Offer 55 二叉树的深度 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 "" " 层序遍历 " "" class  Solution      public  int  maxDepth (TreeNode root)                    if (root==null ) return  0 ;         List<TreeNode> now_layer=new  ArrayList<TreeNode>();         List<TreeNode> next_layer=new  ArrayList<TreeNode>();         int  res=0 ;         now_layer.add(root);         while (now_layer.size()>0 ){             res+=1 ;             for (TreeNode p:now_layer){                 if (p.left!=null ) next_layer.add(p.left);                 if (p.right!=null ) next_layer.add(p.right);             }             now_layer=next_layer;             next_layer=new  ArrayList<TreeNode>();         }         return  res;     } } "" " 深度遍历(递归) " "" class  Solution      public  int  maxDepth (TreeNode root)           if (root == null ) return  0 ;         return  Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 ;     } } 
剑指 Offer 55-1 平衡二叉树 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 "" " 自底向上 剪枝 " "" public  class  code      public  boolean  isBalanced (TreeNode root)           if (root==null ) return  true ;         return  treedepth(root)!=-1 ;     }          public  int  treedepth (TreeNode root)          if (root==null ) return  0 ;          int  left=treedepth(root.left);         if (left==-1 ) return  -1 ;         int  right=treedepth(root.right);         if (right==-1 ) return  -1 ;         return  Math.abs(left-right)<=1 ?Math.max(left,right)+1 :-1 ;      } } "" " 自上而下直接递归算子树高度 判断平衡条件  因为会有重复计算 所以时间复杂度会比较高 " "" class  Solution      public  boolean  isBalanced (TreeNode root)           if (root==null ){             return  true ;         }         if (isBalanced(root.left)&&isBalanced(root.right)){             if (Math.abs(treedepth(root.left)-treedepth(root.right))<=1 ){                 return  true ;             }            }         return  false ;     }     public  int  treedepth (TreeNode root)          if (root==null ){             return  0 ;         }         return  Math.max(treedepth(root.left),treedepth(root.right))+1 ;     } } 
剑指 Offer 56-1 数组中数字出现的次数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 "" " 先对所有数字进行一次异或,得到两个出现一次的数字的异或值。 在异或结果中找到任意为 1 的位(取最低位为1的那位)。 根据这一位对所有的数字进行分组。 在每个组内进行异或操作,得到两个数字。 " "" class  Solution      public  int [] singleNumbers(int [] nums) {         int  res=0 ;         int [] result=new  int [2 ];         for (int  temp:nums){             res^=temp;           }         int  k=1 ;         while ((k&res)==0 ){              k=k<<1 ;         }         int  a=0 ,b=0 ;         for (int  temp:nums){             if ((k&temp)==0 ){                 a^=temp;               }             else {                 b^=temp;               }         }         result[0 ]=a;         result[1 ]=b;         return  result;     } } 
剑指 Offer 56-2 数组中数字出现的次数2 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 "" " 如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1; 同样适用于某位数字出现一次 其余数字出现奇数次的情况 若其余数字出现偶数次 则可以直接用异或 " "" public  class  Solution56_2  	     public  int  singleNumber (int [] nums)           if (nums.length==0 ) return  -1 ;         int [] bitSum = new  int [32 ];         int  res=0 ;         for (int  num:nums){             int  bitMask=1 ;             for (int  i=31 ;i>=0 ;i--){             	             	                 if ((num&bitMask)!=0 ) bitSum[i]++;                 bitMask=bitMask<<1 ;             }         }         for (int  i=0 ;i<32 ;i++){             res=res<<1 ;             res+=bitSum[i]%3 ;         }         return  res;     } } 
剑指 Offer 57 和为s的两个数字 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 "" " 递增所以可以用双指针法 不然直接用Hashmap遍历 " "" import  java.util.ArrayList;import  java.util.*;public  class  Solution      public  ArrayList<Integer> FindNumbersWithSum (int  [] array,int  sum)           int  left = 0 ;         int  right = array.length-1 ;         while (left<right){             int  now_sum = array[left]+array[right];             if (now_sum==sum){                 return  new  ArrayList<>(Arrays.asList(array[left],array[right]));             }else  if (now_sum<sum){                 left++;             }else {                 right--;             }         }         return  new  ArrayList<>();     } } 
剑指 Offer 57_2 和为 S 的连续正数序列 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 "" " 用双指针法 " "" import  java.util.ArrayList;public  class  Solution      public  ArrayList<ArrayList<Integer> > FindContinuousSequence(int  sum) {        int  left = 1 , right = 2 , curSum = 3 ;         ArrayList<ArrayList<Integer>> res = new  ArrayList<>();         while (right<sum){             if (curSum<sum){                   right++;                 curSum+=right;             }else  if (curSum>sum){                   curSum-=left;                 left++;             }else {                 ArrayList list = new  ArrayList<>();                 for (int  i = left; i<=right; i++){                     list.add(i);                 }                 res.add(list);                                                   curSum-=left;                 left+=1 ;                 right+=1 ;                 curSum+=right;             }         }         return  res;     } } 
剑指 Offer 58_1 翻转单词顺序列 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 "" " 用双指针法 public String trim()     返回一个字符串,其值为此字符串,删除了所有前导和尾随空格 " "" class  Solution      public  String reverseWords (String s)           s = s.trim();          int  j = s.length() - 1 , i = j;         StringBuilder res = new  StringBuilder();         while (i >= 0 ) {             while (i >= 0  && s.charAt(i) != ' ' ) i--;              res.append(s.substring(i + 1 , j + 1 ) + " " );              while (i >= 0  && s.charAt(i) == ' ' ) i--;              j = i;          }         return  res.toString().trim();      } } "" " 用java内置函数split public String[] split(String regex)     将此字符串拆分为给定regular expression的匹配项 。     结尾的空字符串不包含在结果数组中。 " "" class  Solution      public  String reverseWords (String s)           String[] strs = s.trim().split(" " );          StringBuilder res = new  StringBuilder();         for (int  i = strs.length - 1 ; i >= 0 ; i--) {              if (strs[i].equals("" )) continue ;              res.append(strs[i] + " " );          }         return  res.toString().trim();      } } 
剑指 Offer 58_2 左旋转字符串 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 "" " 左旋 右旋 然后一起旋 " "" public  String LeftRotateString (String str, int  n)      if  (n >= str.length())         return  str;     char [] chars = str.toCharArray();     reverse(chars, 0 , n - 1 );     reverse(chars, n, chars.length - 1 );     reverse(chars, 0 , chars.length - 1 );     return  new  String(chars); } private  void  reverse (char [] chars, int  i, int  j)      while  (i < j)         swap(chars, i++, j--); } private  void  swap (char [] chars, int  i, int  j)      char  t = chars[i];     chars[i] = chars[j];     chars[j] = t; } "" " 内置substring函数 " "" class  Solution      public  String reverseLeftWords (String s, int  n)           return  s.substring(n)+s.substring(0 ,n);     } } "" " stringbuilder  .charAt()  .append()  .toString " "" class  Solution      public  String reverseLeftWords (String s, int  n)           StringBuilder res = new  StringBuilder();         for (int  i = n; i < s.length(); i++)             res.append(s.charAt(i));         for (int  i = 0 ; i < n; i++)             res.append(s.charAt(i));         return  res.toString();     } } "" " string函数 .charAt() " "" class  Solution      public  String reverseLeftWords (String s, int  n)           String res = "" ;         for (int  i = n; i < s.length(); i++)             res += s.charAt(i);         for (int  i = 0 ; i < n; i++)             res += s.charAt(i);         return  res;     } } 
剑指 Offer 59_1 滑动窗口的最大值 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 "" " 用双端队列来维护窗口内的单调栈(单调递减 " "" import  java.util.*;public  class  Solution      public  ArrayList<Integer> maxInWindows (int  [] num, int  size)           if (num.length<0  || size>num.length || size<1 ){             return  new  ArrayList<>();         }         Deque<Integer> deque = new  LinkedList<>();         ArrayList<Integer> res = new  ArrayList<>();         for (int  i=0 ;i<size;i++){              while (!deque.isEmpty() && deque.peekLast()<num[i]){                 deque.removeLast();             }             deque.addLast(num[i]);         }         for (int  i = size;i<num.length;i++){              res.add(deque.peekFirst());                          if (num[i-size]==deque.peekFirst()){                  deque.removeFirst();             }                          while (!deque.isEmpty() && deque.peekLast()<num[i]){                  deque.removeLast();             }             deque.addLast(num[i]);         }         res.add(deque.peekFirst());         return  res;     } } 
剑指 Offer 59_2 队列的最大值 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 "" " 用双端队列来维护队列内的单调栈(单调递减 " "" class  MaxQueue      Queue<Integer> q;     Deque<Integer> d;     public  MaxQueue ()           q = new  LinkedList<Integer>();         d = new  LinkedList<Integer>();     }          public  int  max_value ()           if  (d.isEmpty()) {             return  -1 ;         }         return  d.peekFirst();     }          public  void  push_back (int  value)           while  (!d.isEmpty() && d.peekLast() < value) {             d.removeLast();         }         d.addLast(value);         q.add(value);     }          public  int  pop_front ()           if  (q.isEmpty()) {             return  -1 ;         }         int  ans = q.remove();         if  (ans == d.peekFirst()) {             d.removeFirst();         }         return  ans;     } } 
剑指 Offer 60 n个骰子的点数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 "" " 动态规划 n个筛子能投的点数k的次数等于n-1个筛子能投的点数(k-6,k-5,k-4,k-3,k-2,k-1)的个数和 for (第n枚骰子的点数 i = 1; i <= 6; i ++) {     dp[n][j] += dp[n-1][j - i] } " "" class  Solution      public  double [] dicesProbability(int  n) {         int [] counts=new  int [n*6 +1 ];           double [] res=new  double [n*5 +1 ];         for (int  i=1 ;i<=6 ;i++) {             counts[i]=1 ;           }         for (int  i=2 ;i<=n;i++){             for (int  j=6 *i;j>=i;j--){                  int  count=6 ;                  counts[j]=0 ;                   while (count>0 ){                     if (j-count+1 >=i){                         counts[j]+=counts[j-count];                      }                     count-=1 ;                 }             }         }         for (int  i=n;i<=6 *n;i++){             res[i-n]=counts[i]/Math.pow(6 ,n);         }         return  res;     } } 
剑指 Offer 61 扑克牌中的顺子 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 "" " 先找到最小的牌 然后向后遍历5个数 若没有 就用大小王代替 没有大小王就报错 若有则跳过 " "" class  Solution      public  boolean  isStraight (int [] nums)           int [] count=new  int [14 ];         for (int  i=0 ;i<5 ;i++){             count[nums[i]]+=1 ;         }         int  magic=count[0 ];          int  i=1 ;         while (count[i]==0 ) i+=1           for (int  idx=1 ;idx<5 ;idx++){             if (i+idx<14 &&count[i+idx]>0 ) continue ;              else {                 if (magic>0 ){                      magic-=1 ;                 }                 else  return  false ;              }         }         return  true ;     } } 
剑指 Offer 62 圆圈中最后剩下的数字 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 "" " 模拟过程 " "" class  Solution      public  int  lastRemaining (int  n, int  m)           int  idx=0 ,len=n;         List<Integer> nums=new  ArrayList<>();         for (int  j=0 ;j<n;j++){              nums.add(j);         }         while (len>1 ){             idx=(idx+m-1 )%len;             nums.remove(idx);             len-=1 ;         }         return  nums.get(0 );     } } 
剑指 Offer 63 股票的最大利润 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 "" " 动态规划 第i天的最大利润=max(第i-1天的最大利润,第i天卖出(第i天的价格-前i-1天的最低价格) " "" class  Solution      public  int  maxProfit (int [] prices)           int  cost = Integer.MAX_VALUE, profit = 0 ;         for (int  price : prices) {             cost = Math.min(cost, price);               profit = Math.max(profit, price - cost);         }         return  profit;     } } 
剑指 Offer 63-1 股票的最大利润 可买卖多次 二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 "" " 爬坡两端卖出 降坡不卖 " "" class  Solution      public  int  maxProfit (int [] prices)           int  i =0 , j=1 ;         int  minIdx = 0 ;         int  res = 0 ;         while (j<prices.length){             minIdx = i;             if (prices[i]<prices[j]){                 while (j<prices.length&&prices[i]<prices[j]){                     i++;                     j++;                 }                 res+=prices[i] - prices[minIdx];             }else {                 while (j<prices.length&&prices[i]>=prices[j]){                     i++;                     j++;                 }             }         }         return  res;     } } 
剑指 Offer 64 求1+2+…+n 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 "" " 利用&&实现递归判断 以逻辑运算符 && 为例,对于 A && B 这个表达式,如果 A 表达式返回 False ,那么 A && B 已经确定False ,此时不会去执行表达式 B 将判断是否为递归的出口看作 A && B 表达式中的 A 部分,递归的主体函数看作 B 部分。如果不是递归出口,则返回True,并继续执行表达式 B 的部分,否则递归结束。 " "" class  Solution      public  int  sumNums (int  n)           Boolean x=n>0 &&((n+=sumNums(n-1 ))>0 );         return  n;     } } 
剑指 Offer 65 不用加减乘除做加法 一、问题描述 
二、具体代码 
1 2 3 4 5 6 7 8 9 10 11 "" " 利用位运算实现加法 a^b 等于a与b不考虑进位的加法结果 a&b 等于a与b加法的进位结果 " "" class  Solution      public  int  add (int  a, int  b)           if (b==0 ) return  a;         return  add(a^b,(a&b)<<1 );     } } 
剑指 Offer 66 构建乘积数组 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 "" " 可以将B[i] 拆分为两部分:     A[0]×A[1]×…×A[i-1]     A[i+1]×…×A[n-1] " "" class  Solution      public  int [] constructArr(int [] a) {         int  n=a.length;         int [] B=new  int [n];         for (int  i=0 ,product=1 ;i<n;product*=a[i],i++){              B[i]=product;         }         for (int  i=n-1 ,product=1 ;i>=0 ;product*=a[i],i--){              B[i]*=product;         }         return  B;     } } 
剑指 Offer 67 把字符串转换为整数 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 "" " 可以将B[i] 拆分为两部分:     A[0]×A[1]×…×A[i-1]     A[i+1]×…×A[n-1] " "" class  Solution      public  int  strToInt (String str)           char [] s=str.toCharArray();         int  i=0 ,flag=1 ;         long   res=0 ;         if (s.length==0 ) return  0 ;          while (i<s.length&&s[i]==' ' ){              i++;         }         if (i<s.length&&(s[i]=='-' ||s[i]=='+' )){              if (s[i]=='-' ) flag=-1 ;             i+=1 ;         }                 if (i>=s.length ||!((s[i]>='0' &&s[i]<='9' )||s[i]=='-' ||s[i]=='+' )){             return  0 ;         }         while (i<s.length&&s[i]>='0' &&s[i]<='9' ){             res=res*10 +(s[i]-'0' );             if (res>Integer.MAX_VALUE) return  flag>0 ?Integer.MAX_VALUE:Integer.MIN_VALUE;             i++;         }         return  flag*(int )res;     } } 
剑指 Offer 68_1 二叉搜索树的最近公共祖先 一、问题描述 
二、具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 "" " 利用二叉搜索树 左<中<右这个规律 " "" "" " 1、递归 " "" public  TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q)      if  (root == null )         return  root;     if  (root.val > p.val && root.val > q.val)         return  lowestCommonAncestor(root.left, p, q);     if  (root.val < p.val && root.val < q.val)         return  lowestCommonAncestor(root.right, p, q);     return  root; } "" " 2、迭代     循环搜索: 当节点 root为空时跳出;         当 p, q都在 root 的 右子树 中,则遍历至 root.right;         否则,当 p, q 都在 root 的 左子树 中,则遍历至 root.left;         否则,说明找到了 最近公共祖先 ,跳出。     返回值: 最近公共祖先 root 。 " "" class  Solution      public  TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q)           while (root != null ) {             if (root.val < p.val && root.val < q.val)                  root = root.right;              else  if (root.val > p.val && root.val > q.val)                  root = root.left;              else  break ;         }         return  root;     } } "" " 若为普通二叉树 " "" class  Solution      public  TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q)           if (root == null  || root == p || root == q) return  root;                   TreeNode left = lowestCommonAncestor(root.left, p, q);         TreeNode right = lowestCommonAncestor(root.right, p, q);         if (left == null ) return  right;         if (right == null ) return  left;         return  root;     } } 
大数的和 1 2 3 4 5 6 7 8 9 10 11 12 public  String solve (String s, String t)      StringBuilder stringBuilder = new  StringBuilder();     int  i = s.length() - 1 , j = t.length() - 1 , carry = 0 ;     while  (i >= 0  || j >= 0  || carry != 0 ) {         int  x = i < 0  ? 0  : s.charAt(i--) - '0' ;         int  y = j < 0  ? 0  : t.charAt(j--) - '0' ;         int  sum = x + y + carry;         stringBuilder.append(sum % 10 );         carry = sum / 10 ;     }     return  stringBuilder.reverse().toString(); } 
42接雨水 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class  Solution      public  int  trap (int [] height)           int  n = height.length;         if  (n == 0 ) {             return  0 ;         }         int [] leftMax = new  int [n];         leftMax[0 ] = height[0 ];         for  (int  i = 1 ; i < n; ++i) {             leftMax[i] = Math.max(leftMax[i - 1 ], height[i]);         }         int [] rightMax = new  int [n];         rightMax[n - 1 ] = height[n - 1 ];         for  (int  i = n - 2 ; i >= 0 ; --i) {             rightMax[i] = Math.max(rightMax[i + 1 ], height[i]);         }         int  ans = 0 ;         for  (int  i = 0 ; i < n; ++i) {             ans += Math.min(leftMax[i], rightMax[i]) - height[i];         }         return  ans;     } } "" " 对于下标 i,下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值,下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去height[i]。 如果 height[left]<height[right],则必有 leftMax<rightMax,下标left 处能接的雨水量等于 leftMax−height[left],将下标left 处能接的雨水量加到能接的雨水总量,然后将 left 加 1(即向右移动一位); " "" class  Solution      public  int  trap (int [] height)           int  ans = 0 ;         int  left = 0 , right = height.length - 1 ;         int  leftMax = 0 , rightMax = 0 ;         while  (left < right) {             leftMax = Math.max(leftMax, height[left]);             rightMax = Math.max(rightMax, height[right]);             if  (leftMax < rightMax) {                 ans += leftMax - height[left];                 ++left;             } else  {                 ans += rightMax - height[right];                 --right;             }         }         return  ans;     } }