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是第二个小括号里面的内容**,
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 字符串的全排列 #### 一、问题描述 ![题目描述](剑指offer/38. png) #### 二、具体代码 ```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、搜索 ### 一、问题描述 ![题目描述](Backtrack/search.png) ### 二、具体代码 ```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溢出 2、有序 二分 3、划分数组 一半一半 想到双指针 4、倒数第k个节点 也是双指针 一个先走k步(快慢指针) 5、求矩形最大面积—单调栈 6、图(建图 bfs求两结点的最短路径) 7、前缀树 新的一种数据结构 用于字符串匹配 8、判断链表是否有环 以及环的起点和长度(Floyd判环算法 龟兔赛跑 9、top-k 用堆或者二叉搜索树 10、LRU缓存实现 hashmap+LinkedList 11、最小编辑距离 12、同样的数出现偶数次 找出奇数次的数(异或 然后以异或为1的最低位分为两组 各自异或可得出现奇数次的数) 同样的数出现奇数次,找出偶数次的数 各位相加 若奇数次和可被其整除,不能整除的则为偶数次的数
树遍历 层序遍历 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 set:若map长度小于缓存大小,则直接存;不然就删除map最前面的那个节点(用迭代器)
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] 表示插入操作。”的补充理解: 以 word1 为 “horse”,word2 为 “ros”,且 dp[5][3] 为例,即要将 word1的前 5 个字符转换为 word2的前 3 个字符,也就是将 horse 转换为 ros,因此有:
(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都为None
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 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; } }