高频算法题（一）

 

目录

k个一组反转链表

121. 买卖股票的最佳时机

15. 三数之和

155. 最小栈

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

199. 二叉树的右视图

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

88. 合并两个有序数组

108. 将有序数组转换为二叉搜索树

110. 平衡二叉树

236. 二叉树的最近公共祖先

33. 搜索旋转排序数组

322. 零钱兑换

518. 零钱兑换 II

 83. 删除排序链表中的重复元素

206. 反转链表

215. 数组中的第K个最大元素

56. 合并区间

146. LRU缓存机制

102. 二叉树的层序遍历

剑指 Offer 09. 用两个栈实现队列

54. 螺旋矩阵

1299. 将每个元素替换为右侧最大元素

42. 接雨水

105. 从前序与中序遍历序列构造二叉树

160. 相交链表

139. 单词拆分

67. 二进制求和

230. 二叉搜索树中第K小的元素

70. 爬楼梯

剑指 Offer 61. 扑克牌中的顺子

543. 二叉树的直径

112. 路径总和

23. 合并K个排序链表

1143. 最长公共子序列

2. 两数相加

141. 环形链表

---

主要总结了高频的算法题，题目来自于字节跳动按岗位汇总算法高频题 

k个一组反转链表

尾插法，先找到k个一组的尾节点，然后将pre的下一个节点插到尾部，直到pre.next=tail

public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy=new ListNode(0); dummy.next=head; ListNode pre=dummy; ListNode tail=dummy; while (true){ for(int i=0;i<k;i++){ if(tail==null)break; tail=tail.next; } if(tail==null)break; ListNode phead=pre.next; while (pre.next!=tail){ ListNode ne = pre.next; pre.next=ne.next; ne.next = tail.next; tail.next = ne; } pre=phead; tail=phead; } return dummy.next; }

121. 买卖股票的最佳时机

维护一个当前的最小值

public int maxProfit(int[] prices) { int min=Integer.MAX_VALUE; int ans=0; for(int i=0;i<prices.length;i++){ min=Math.min(prices[i],min); ans=Math.max(prices[i]-min,ans); } return ans; }

15. 三数之和

对数组排序之后，先确定第一个数，然后双指针找到和

public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans=new ArrayList<>(); Arrays.sort(nums); for(int i=0;i<nums.length;i++){ if(nums[i]>0)break; if(i>0&&nums[i]==nums[i-1])continue; int num=-nums[i]; int l=i+1;int r=nums.length-1; while (l<r){ if(nums[l]+nums[r]==num){ ans.add(Arrays.asList(nums[i],nums[l],nums[r])); while (l<r&&nums[l]==nums[l+1])l++; while (l<r&&nums[r]==nums[r-1])r--; l++; r--; } else if(nums[l]+nums[r]<num){ l++; }else { r--; } } } return ans; }

155. 最小栈

两个栈，最小栈存储的是比栈顶小或者相等的值

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

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

public int res=Integer.MIN_VALUE; public int getMax(TreeNode root){ if(root==null)return 0; int l=Math.max(0,getMax(root.left)); int r=Math.max(0,getMax(root.right)); res=Math.max(res,root.val+l+r); return Math.max(l,r)+root.val; } public int maxPathSum(TreeNode root) { getMax(root); return res; }

199. 二叉树的右视图

基础的层序遍历方法是O（nlog(n))的，可以再用一个队列记录当前深度，用一个map一直更新当前层的元素。最后根据深度读取值。

public List<Integer> rightSideView(TreeNode root) { Map<Integer,Integer>map=new HashMap<>(); List<Integer> list=new ArrayList<>(); Queue<TreeNode> que=new LinkedList<>(); Queue<Integer> depth=new LinkedList<>(); que.add(root); depth.add(0); int maxdepth=-1; while (!que.isEmpty()){ TreeNode cur=que.poll(); int dep=depth.poll(); if(cur!=null){ maxdepth=Math.max(maxdepth,dep); map.put(dep,cur.val); que.add(cur.left); que.add(cur.right); depth.add(dep+1); depth.add(dep+1); } } for(int i=0;i<=maxdepth;i++){ list.add(map.get(i)); } return list; }

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

用一个set来表示滑动窗口，如果当前元素在set中包含的话，左指针右移。否则右指针右移

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

88. 合并两个有序数组

从大到小进行排序

public void merge(int[] nums1, int m, int[] nums2, int n) { int r1=m-1; int r2=n-1; int num=m+n-1; while (r2>=0&&r1>=0){ if(nums1[r1]>nums2[r2]){ nums1[num--]=nums1[r1--]; }else nums1[num--]=nums2[r2--]; } if(r1<0){ for(int i=r2;i>=0;i--){ nums1[num--]=nums2[i]; } } }

108. 将有序数组转换为二叉搜索树

二分

public TreeNode BST(int[] nums,int l,int r){ if(l<=r) { int mid = (l + r) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = BST(nums, l, mid - 1); root.right = BST(nums, mid + 1, r); return root; } return null; } public TreeNode sortedArrayToBST(int[] nums) { return BST(nums,0,nums.length-1); }

110. 平衡二叉树

easy

public int height(TreeNode root){ if(root==null)return 0; int l=height(root.left); int r=height(root.right); return Math.max(l,r)+1; } public boolean isBalanced(TreeNode root) { if(root==null)return true; return Math.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right); }

236. 二叉树的最近公共祖先

递归

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

33. 搜索旋转排序数组

其中一侧是排好序的，另一侧是没有排序的。

public int search(int[] arr, int target) { int l=0; int r=arr.length-1; if(arr.length==0)return -1; while (l<=r){ int mid=(l+r)/2; if(arr[mid]==target)return mid; else if(arr[l]<=arr[mid]){ if(arr[l]<=target&&target<arr[mid]){ r=mid-1; }else { l=mid+1; } } else { if(target>arr[mid]&&target<=arr[r]){ l=mid+1; }else { r=mid-1; } } } return -1; }

322. 零钱兑换

public int coinChange(int[] coins, int amount) { int[] dp=new int[amount+1]; Arrays.fill(dp,amount+1); dp[0]=0; for(int i=0;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?-1:dp[amount]; }

518. 零钱兑换 II

public int change(int amount, int[] coins) { int[] dp=new int[amount+1]; dp[0]=1; for(int i=0;i<coins.length;i++){ for(int j=0;j+coins[i]<=amount;j++){ dp[j+coins[i]]+=dp[j]; } } return dp[amount]; }

 83. 删除排序链表中的重复元素

easy题目

public ListNode deleteDuplicates(ListNode head) { ListNode dummy=new ListNode(0); dummy.next=head; ListNode pre=dummy; while (head!=null){ while (head!=null&&head.next!=null&&head.val==head.next.val){ head=head.next; } pre.next=head; pre=pre.next; if(head!=null){ head=head.next; } } return dummy.next; }

206. 反转链表

public ListNode reverseList(ListNode head) { ListNode cur=null; while (head!=null){ ListNode ne=head.next; head.next=cur; cur=head; head=ne; } return cur; }

215. 数组中的第K个最大元素

快排的思想。

public void swap(int[] nums,int l,int r){ int tmp=nums[l]; nums[l]=nums[r]; nums[r]=tmp; } public int Qsort(int[] nums,int l,int r,int k){ if(l>=r)return nums[l]; int start=l; int end=r; swap(nums,start,r); while (true) { while (start < end && nums[start] >= nums[r]) start++; while (start < end && nums[end] <= nums[r]) end--; if(start>=end)break; swap(nums,start,end); } swap(nums,start,r); if(start==k-1)return nums[start]; else if(start<k-1){ return Qsort(nums,start+1,r,k); }else return Qsort(nums,l,start-1,k); } public int findKthLargest(int[] nums, int k) { return Qsort(nums,0,nums.length-1,k); }

56. 合并区间

按照第一个序号从左到右排序，比较右边界最大的。

public int[][] merge(int[][] intervals) { Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0]-o2[0]; } }); int n=intervals.length; List<int[]> list=new ArrayList<>(); for(int i=0;i<n;i++){ int left=intervals[i][0]; int right=intervals[i][1]; while (i<n-1&&right>=intervals[i+1][0]){ right=Math.max(right,intervals[i+1][1]); i++; } list.add(new int[]{left,right}); } return list.toArray(new int[list.size()][2]); }

146. LRU缓存机制

双向链表+hash

class LRUCache { private Map<Integer,Integer> map=new LinkedHashMap<>(); private int cap; public LRUCache(int capacity) { this.cap=capacity; } public int get(int key) { if(map.containsKey(key)){ int value=map.get(key); map.remove(key); map.put(key,value); return value; } else return -1; } public void put(int key, int value) { if(map.containsKey(key)){ map.remove(key); }else if(map.size()==cap){ Iterator<Integer> iterator=map.keySet().iterator(); int k=iterator.next(); map.remove(k); } map.put(key,value); } }

102. 二叉树的层序遍历

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> lists=new ArrayList<>(); if(root==null)return lists; Queue<TreeNode> que=new LinkedList<>(); que.add(root); while (!que.isEmpty()){ int size=que.size(); List<Integer> tmp=new ArrayList<>(); for(int i=0;i<size;i++){ TreeNode cur=que.poll(); tmp.add(cur.val); if(cur.left!=null)que.add(cur.left); if(cur.right!=null)que.add(cur.right); } lists.add(new ArrayList<>(tmp)); } return lists; }

剑指 Offer 09. 用两个栈实现队列

用两个栈，第一个栈存放的是队列尾部，当第二个栈是空的时候，将第一个栈的元素全部弹入到第二个栈中，否则的话直接弹出第二个栈的元素即可。

class CQueue { Stack<Integer> stack=new Stack<>(); Stack<Integer> fuzhu=new Stack<>(); public CQueue() { } public void appendTail(int value) { stack.add(value); } public int deleteHead() { if(fuzhu.isEmpty()){ if(stack.isEmpty())return -1; while (!stack.isEmpty()){ fuzhu.add(stack.pop()); } return fuzhu.pop(); } return fuzhu.pop(); } }

54. 螺旋矩阵

public List<Integer> spiralOrder(int[][] matrix) { List<Integer> list=new ArrayList<>(); if(matrix.length==0)return list; int left=0; int right=matrix[0].length-1; int top=0; int bottom=matrix.length-1; while (left<=right&&top<=bottom){ for(int i=left;i<=right;i++){ list.add(matrix[top][i]); } for(int i=top+1;i<=bottom;i++){ list.add(matrix[i][right]); } if(left<right&&top<bottom){ for(int i=right-1;i>=left;i--){ list.add(matrix[bottom][i]); } for(int i=bottom-1;i>top;i--){ list.add(matrix[i][left]); } } left++;right--;top++;bottom--; } return list; }

1299. 将每个元素替换为右侧最大元素

public int[] replaceElements(int[] arr) { int val=-1; for(int i=arr.length-1;i>=0;i--){ int tmp=arr[i]; arr[i]=val; val=Math.max(val,tmp); } return arr; }

42. 接雨水

public int trap(int[] height) { int ans=0; int left=0,right=height.length-1; int leftMax=0,rightMax=0; while (left<right){ if(height[left]<height[right]){ if(height[left]>leftMax){ leftMax=height[left]; }else { ans+=leftMax-height[left]; } left++; }else { if(height[right]>rightMax){ rightMax=height[right]; }else { ans+=rightMax-height[right]; } right--; } } return ans; }

105. 从前序与中序遍历序列构造二叉树

public TreeNode build(int[] preorder,int ps,int pe,int[] inorder,int is,int ie){ if(ps>pe||is>ie)return null; int i; for(i=is;i<=ie;i++){ if(inorder[i]==preorder[ps]){ break; } } TreeNode root=new TreeNode(preorder[ps]); root.left=build(preorder,ps+1,ps+i-is,inorder,is,i-1); root.right=build(preorder,ps+i-is+1,pe,inorder,i+1,ie); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1); }

160. 相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode l1=headA; ListNode l2=headB; while (l1!=l2){ l1=l1==null?headB:l1.next; l2=l2==null?headA:l2.next; } return l1; }

139. 单词拆分

public boolean wordBreak(String s, List<String> wordDict) { int start=0; if(s.length()==0)return true; boolean[] dp=new boolean[s.length()+1]; dp[0]=true; for(int i=1;i<=s.length();i++){ for(int j=0;j<i;j++) { if (dp[j]&&wordDict.contains(s.substring(j, i))) { dp[i]=true; } } } return dp[s.length()]; }

67. 二进制求和

public String addBinary(String a, String b) { int m=a.length()-1; int n=b.length()-1; int carry=0; StringBuilder sb=new StringBuilder(); while (m>=0||n>=0){ int l1=m>=0?a.charAt(m--)-'0':0; int l2=n>=0?b.charAt(n--)-'0':0; sb.append(l1^l2^carry); carry=(l1&l2)|(l1&carry)|(l2&carry); } if(carry>0)sb.append(carry); return sb.reverse().toString(); }

230. 二叉搜索树中第K小的元素

public int kthSmallest(TreeNode root, int k) { Stack<TreeNode> stack=new Stack<>(); int cnt=0; while (!stack.isEmpty()||root!=null){ while (root!=null){ stack.push(root); root=root.left; } root=stack.peek(); stack.pop(); cnt++; if(cnt==k)return root.val; root=root.right; } return 0; }

70. 爬楼梯

easy题目

public int climbStairs(int n) { int[] dp=new int[n+1]; if(n<3)return n; dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; }

剑指 Offer 61. 扑克牌中的顺子

public boolean isStraight(int[] nums) { int s=0; int dif=0; Arrays.sort(nums); for(int i=0;i<nums.length-1;i++){ if(nums[i]==0){ s++; }else { if(nums[i]==nums[i+1])return false; if(nums[i]+1!=nums[i+1]){ dif+=(nums[i+1]-nums[i]-1); } } } return s>=dif; }

543. 二叉树的直径

类似二叉树中的最大路径和问题。

public int ans=0; public int heighta(TreeNode root){ if(root==null)return 0; int l=heighta(root.left); int r=heighta(root.right); ans=Math.max(l+r,ans); return Math.max(l,r)+1; } public int diameterOfBinaryTree(TreeNode root) { heighta(root); return ans; }

112. 路径总和

public boolean hasPathSum(TreeNode root, int sum) { if(root==null)return false; if(root.left==null&&root.right==null){ if(sum==root.val)return true; else return false; } return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val); }

23. 合并K个排序链表

public ListNode mergeSort(ListNode l1,ListNode l2){ ListNode d=new ListNode(0); ListNode s=d; d.next=l1; while (l1!=null&&l2!=null){ if(l1.val<l2.val){ d.next=l1; l1=l1.next; }else{ d.next=l2; l2=l2.next; } d=d.next; } if (l1!=null){ d.next=l1; } if(l2!=null){ d.next=l2; } return s.next; } public ListNode merge(ListNode[] lists,int s,int e){ if(s==e)return lists[s]; else if(s<e) { int mid=(s+e)/2; ListNode l1 = merge(lists, s, mid); ListNode l2=merge(lists,mid+1,e); return mergeSort(l1,l2); } else return null; } public ListNode mergeKLists(ListNode[] lists) { int n=lists.length; return merge(lists,0,n-1); }

1143. 最长公共子序列

public int longestCommonSubsequence(String text1, String text2) { int m=text1.length(); int n=text2.length(); int[][] dp=new int[m+1][n+1]; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(text1.charAt(i-1)==text2.charAt(j-1)){ dp[i][j]=dp[i-1][j-1]+1; }else { dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); } } } return dp[m][n]; }

2. 两数相加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode ans=new ListNode(0); ListNode dummy=ans; int carry=0; while (l1!=null||l2!=null||carry!=0){ int x=l1==null?0:l1.val; int y=l2==null?0:l2.val; ans.next=new ListNode((x+y+carry)); carry=(x+y+carry)/10; ans=ans.next; if(l1!=null)l1=l1.next; if(l2!=null)l2=l2.next; } return dummy.next; }

141. 环形链表

public boolean hasCycle(ListNode head) { 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; }