前言 学长发话了，找实习之前把hot100和剑指offer刷了就行了
先刷烧鸡100
中言 tmd我的hexo代码高亮一直没用，试了100种方法，没用就没用吧，拉倒了
简单题部分 首先就是暴力法，很垃圾
public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> ans; for(int i=0;i<nums.size()-1;i++) { for(int j=i+1;j<nums.size();j++) { if(nums[i]+nums[j]==target) { ans.push_back(i); ans.push_back(j); return ans; } } } return ans; }
然后，好方法是什么，看答案
public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int>hashtable; for(int i=0;i<nums.size();i++) { auto it=hashtable.find(target-nums[i]); if(it!=hashtable.end()) { return {it->second,i}; } hashtable[nums[i]]=i; } return {}; }
用哈希表就能把查找target-x的复杂度降到O（1），这样一次遍历就行
为了熟悉go语言，也用go语言实现一下
func twoSum(nums []int, target int) []int { hash:=map[int]int{} for i,x:=range nums{ if p,ok:=hash[target-x];ok{ return []int {p,i} } hash[x]=i; } return nil }
为了熟悉go语言，也用go语言实现一下
func isValid(s string) bool { n:len(s) if n%2==1{ return false; } pairs:=map[byte]byte{ ')':'(', '[':']', '{':'}', } stack:=[]byte{} for i:=0;i<n;i++{ if pairs[s[i]]>0{ if len(stack)==0||stack[len(stack)-1]!=pairs[s[i]]{ return false; } stack=stack[:len(stack)-1] }else{ stack=append(stack,s[i]); } } return len(stack)==0 }
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* ans=new ListNode(); ListNode* p=list1; ListNode* q=list2; ListNode* curr=ans; while(p!=NULL&&q!=NULL) { if(p->val>=q->val) { curr->next=q; q=q->next; } else { curr->next=p; p=p->next; } curr=curr->next; } if(p!=NULL) { curr->next=p; } if(q!=NULL) { curr->next=q; } return ans->next; } };
class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x^y); } }
知识点：异或、bitCount()
class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if(t1==null) { return t2; } if(t2==null) { return t1; } TreeNode merged=new TreeNode(t1.val+t2.val); merged.left=mergeTrees(t1.left,t2.left); merged.right=mergeTrees(t1.right,t2.right); return merged; } }
我的没注意的地方：t1,t2为null时，应该是return 另一个
我最先想到了递归，但是超时了
public int climbStairs(int n) { if(n==1)return 1; if(n==2)return 2; return climbStairs(n-1)+climbStairs(n-2); }
于是经典动态规划
public int climbStairs(int n) { int p=0,q=0,r=1; for(int i=0;i<n;i++) { p=q; q=r; r=p+q; } return r; }
中等 public int maxArea(int[] height) { int i=0,j=height.length-1; int max=0; while(i<j) { int di=j-i; int gao=Math.min(height[i],height[j]); int area=di*gao; max=Math.max(area,max); if(height[i]<height[j]) { i++; }else { j--; } } return max; }
只要更新矮的那一边即可
public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); int len=nums.length; List<List<Integer>> res=new ArrayList<>(); for(int i=0;i<len-2;i++) { if(nums[i]>0) break; if(i>0&&nums[i]==nums[i-1]) continue; int j=i+1,k=len-1; int sum; while(j<k) { sum=nums[i]+nums[j]+nums[k]; if(sum>0) { while(j<k&&nums[k]==nums[--k]); }else if(sum<0) { while(j<k&&nums[j]==nums[++j]); }else { res.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[k]))); while(j<k&&nums[k]==nums[--k]); while(j<k&&nums[j]==nums[++j]); } } } return res; }
有一说一有点难度，主要是这个去重没想到
class Solution { public int[] searchRange(int[] nums, int target) { int res[]={0,0}; res[0]=btsL(nums,target); res[1]=btsR(nums,target); return res; } public int btsL(int []nums,int k) { int l=0,r=nums.length-1; while(l<=r) { int mid=(l+r)/2; if(nums[mid]<k) { l=mid+1; }else if (nums[mid]>k) { r=mid-1; }else { r=mid-1; } } if(l>=nums.length||nums[l]!=k)//如果是l>nums.length，那么后面数组越界了 return -1; return l; } public int btsR(int []nums,int k) { int l=0,r=nums.length-1; while(l<=r) { int mid=(l+r)/2; if(nums[mid]<k) { l=mid+1; }else if (nums[mid]>k) { r=mid-1; }else { l=mid+1; } } if(r<0||nums[r]!=k)//如果是r<=0,那么当[1]这种情况，直接返回-1了 return -1; return r; } }
二分查找找左右边界问题，注意注释里的
哈希部分 public int longestConsecutive(int[] nums) { Set<Integer> set=new HashSet<>(); for(int num:nums) { set.add(num); } int ans=0; for(int num:set) { int cur=num; if(!set.contains(cur-1)) { while(set.contains(cur+1)) { cur++; } } ans=Math.max(ans,cur-num+1); } return ans; }
脑筋急转弯：cur-1开始的序列肯定比cur开始的长
滑动窗口 public List<Integer> findAnagrams(String s, String p) { int slen=s.length(),plen=p.length(); if(slen<plen) { return new ArrayList<Integer>(); } List<Integer> ans=new ArrayList<Integer>(); int []scount=new int[26]; int []pcount=new int[26]; for(int i=0;i<plen;i++) { ++scount[s.charAt(i)-'a'];//初始化 ++pcount[p.charAt(i)-'a'];//p里面的字母各个的数量，用来比较 } if (Arrays.equals(scount, pcount)) { ans.add(0);//先比较0处 } for(int i=0;i<slen-plen;i++) { --scount[s.charAt(i)-'a'];//滑动一次，最左边的花出去了 ++scount[s.charAt(i+plen)-'a'];//新来的加上 if(Arrays.equals(scount,pcount)){ ans.add(i+1);//为什么是i+1,注意第二个循环是从i=0开始的，但是i=0已经在第一次循环被花出去了 } } return ans; }
我一开始：写一个isyiwei()，然后循环判断，超时
子串问题 public int subarraySum(int[] nums, int k) { int count=0; for(int start=0;start<nums.length;start++) { int sum=0; for(int end=start;end>=0;--end) { sum+=nums[end]; if(sum==k) { count++; } } } return count; }
public int[] maxSlidingWindow(int[] nums, int k) { int[]res=new int[nums.length-k+1]; LinkedList<Integer>queue=new LinkedList<>(); for(int right=0;right<nums.length;right++) { while(!queue.isEmpty()&&nums[right]>=nums[queue.peekLast()]){ queue.removeLast(); } queue.addLast(right); int left=right-k+1; if(queue.peekFirst()<left) { queue.removeFirst(); } if(right+1>=k) { res[left]=nums[queue.peekFirst()]; } } return res; }
脑筋急转弯部分：1.双端队列，这个我就没想到 2.当queue的队首表示的下标小于窗口下标时，队首就可以出了，我还想用queue大小来判断来着
普通数组 public int maxSubArray(int[] nums) { int len=nums.length; int []dp=new int[len]; dp[0]=nums[0]; for(int i=1;i<len;i++) { if(dp[i-1]>0) { dp[i]=dp[i-1]+nums[i]; }else { dp[i]=nums[i]; } } int res=dp[0]; for(int i=1;i<len;i++) { res=Math.max(res,dp[i]); } return res; }
经典动态规划题目，一开始还没想起来，后来想起来是动态规划，还是比较简单的
此题很吊
public int[][] merge(int[][] intervals) { Arrays.sort(intervals,(a,b)->a[0]-b[0]); List<int []>ans=new ArrayList<>(); ans.add(intervals[0]); for(int i=1;i<intervals.length;i++) { int s=intervals[i][0],e=intervals[i][1];//s左断电，e右断电 if(ans.get(ans.size()-1)[1]<s)//ans最右边的那个数组，其右端点如果小于正在比较的那个的左端点 { ans.add(intervals[i]);//说明不重合，直接add }else { ans.get(ans.size()-1)[1]=Math.max(ans.get(ans.size()-1)[1],e);//否则，覆盖，就是把把右边更新为大的哪一个 } } return ans.toArray(new int[ans.size()][]); }
注意点：1.先按左边界排序，不然你比较勾八？2.List<int[]>的用法，见java算法常用
public void rotate(int[] nums, int k) { while(k>0) { int j=nums[nums.length-1]; for(int i=nums.length-1;i>0;i--) { nums[i]=nums[i-1]; } nums[0]=j; k--; } }
首先想到暴力，但是超时了！
用翻转法：
public void rotate(int[] nums, int k) { k%=nums.length; reverse(nums,0, nums.length-1); reverse(nums,0,k-1); reverse(nums,k,nums.length-1); } public void reverse(int []nums,int s,int e) { while(s<e){ int t=nums[s]; nums[s]=nums[e]; nums[e]=t; s+=1; e-=1; } }
全翻转->分别翻转两部分
PS:这题目南软考过
public int firstMissingPositive(int[] nums) { int n=nums.length; for(int i=0;i<n;i++) { while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){//为什么是while?因为你换到nums[i]上的那个数可能还是不符合条件 int t=nums[nums[i]-1]; nums[nums[i]-1]=nums[i]; nums[i]=t; } } for(int i=0;i<n;i++) { if(nums[i]!=i+1) { return i+1; } } return n+1; }
我是呆子
矩阵 public void setZeroes(int[][] matrix) { int m=matrix.length,n=matrix[0].length; boolean[]row=new boolean[m]; boolean[]col=new boolean[n]; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(matrix[i][j]==0) { row[i]=col[j]=true; } } } for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(row[i]||col[j]) { matrix[i][j]=0; } } } }
疑似暴力，对有0的行和列做标记
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean flagCol0 = false, flagRow0 = false; for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { flagCol0 = true; } } for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { flagRow0 = true; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = matrix[0][j] = 0;//为什么可以修改第一行和第一列呢，因为反正如果出现0了，那么这一个位置也是要被置为0的 } } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (flagCol0) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } if (flagRow0) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } } }
缩减空间复杂度：用第一行和第一列记录是否有0 ，先保存第一行和第一列有没有0，然后用于记录
my assessment:有什么大病
官方题解：my assessment：烂
public List<Integer> spiralOrder(int[][] matrix) { List<Integer> order=new ArrayList<Integer>(); if(matrix==null||matrix.length==0||matrix[0].length==0) { return order; } int rows=matrix.length,cols=matrix[0].length; boolean is[][]=new boolean[rows][cols]; int total=rows*cols; int row=0,col=0; int[][]dir={{0,1},{1,0},{0,-1},{-1,0}}; int direIndex=0; for(int i=0;i<total;i++) { order.add(matrix[row][col]); is[row][col]=true; int nextrow=row+dir[direIndex][0],nexcol=col+dir[direIndex][1]; if(nextrow<0||nextrow>=rows||nexcol<0||nexcol>=cols||is[nextrow][nexcol]){ direIndex=(direIndex+1)%4; } row+=dir[direIndex][0]; col+=dir[direIndex][1]; } return order; }
神中神做法：
public List<Integer> spiralOrder(int[][] matrix) { if(matrix.length==0) return new ArrayList<Integer>(); int l=0,r=matrix[0].length-1,t=0,b=matrix.length-1,x=0; Integer[]res=new Integer[(r+1)*(b+1)]; while(true) { for(int i=l;i<=r;i++) res[x++]=matrix[t][i]; if(++t>b)break; for(int i=t;i<=b;i++)res[x++]=matrix[i][r]; if(--r<l)break; for(int i=r;i>=l;i--)res[x++]=matrix[b][i]; if(--b<t)break; for(int i=b;i>=t;i--)res[x++]=matrix[i][l]; if(++l>r)break; } return Arrays.asList(res); }
神级思路，设立四个边界，然后按边界走，同时收缩边界
弱智方法：就是找个t，先复制一下，然后按规律改
public void rotate(int[][] matrix) { int n=matrix.length; int [][]tmp=new int[n][n]; for(int i=0;i<n;i++) { tmp[i]=matrix[i].clone(); } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { matrix[j][n-1-i]=tmp[i][j]; } } }
神方法：知识点->遇到有覆盖问题，则什么，设置temp
public void rotate(int[][] matrix) { int n=matrix.length; for(int i=0;i<n/2;i++) { for(int j=0;j<(n+1)/2;j++) { int t=matrix[i][j]; matrix[i][j]=matrix[n-1-j][i]; matrix[n-1-j][i]=matrix[n-1-i][n-1-j]; matrix[n-1-i][n-1-j]=matrix[j][n-1-i]; matrix[j][n-1-i]=t; } } }
一：暴力
二：每一行二分
三：妙方法
public boolean searchMatrix(int[][] array, int target) { int i=0,j=array[0].length-1; while(i<array.length&&j>=0) { if(target>array[i][j]) { i++; } else if(target<array[i][j]) { j--; } else { return true; } } return false; }
从最左下角开始
你行从小到大，那么如果这个值大于target，那么这一行右边是不是都可以取消了，同理，你列从小到大，那么这个值小于target，这一列都不用看了
链表部分 方法一：妙啊，用set，虽然笨但是我都没想到，我是傻逼
public ListNode detectCycle(ListNode head) { ListNode pos = head; Set<ListNode> visited = new HashSet<ListNode>(); while (pos != null) { if (visited.contains(pos)) { return pos; } else { visited.add(pos); } pos = pos.next; } return null; }
方法二：双指针，我想到了但是不会做，我草
public ListNode detectCycle(ListNode head) { ListNode fast=head,slow=head; while(true) { if(fast==null||fast.next==null)return null; fast=fast.next.next; slow=slow.next; if(fast==slow)break; } fast=head; while(slow!=fast) { slow=slow.next; fast=fast.next; } return fast; }
严格的数学推导，见解答
我的想法：用栈啊，很好，超过100%时间复杂度
public ListNode swapPairs(ListNode head) { if(head==null||head.next==null) { return head; } Stack<ListNode> stack=new Stack<>(); ListNode senty=new ListNode(-1); ListNode s=senty; ListNode next=null; while(head!=null&&head.next!=null) { for(int i=0;i<2;i++) { next=head.next; head.next=null; stack.push(head); head=next; } s.next=stack.pop(); s.next.next=stack.pop(); s=s.next.next; } if(head!=null) { s.next=head;//如果是奇数个还剩一个 } return senty.next; }
更多人用的：递归
public ListNode swapPairs(ListNode head) { if(head==null||head.next==null) { return head; } ListNode next=head.next; head.next=swapPairs(next.next); next.next=head; return next; }
递归法你只需要关注什么
三个：
返回值：swap后的链表，此处是next，为什么，因为next被交换到前面了
过程：交换两个
什么时候停止：没了，或者下一个没了
public ListNode reverseKGroup(ListNode head, int k) { Deque<ListNode> stack = new ArrayDeque<ListNode>(); ListNode dummy = new ListNode(0); ListNode p = dummy; while (true) { int count = 0; ListNode tmp = head; while (tmp != null && count < k) { stack.add(tmp); tmp = tmp.next; count++; } if (count != k) { p.next = head;//直接连就行了 break; } /* 一开始我还写成了while...pollfirst，根本没必要，因为本来就是连着的 */ while (!stack.isEmpty()){ p.next = stack.pollLast(); p = p.next; } head=tmp;//head肯定要更新的，每次都得是没进去的第一个 } return dummy.next; }
依旧是栈，注意事项在注释里
此题作为归并排序的板子，记住！！！！！！
public ListNode sortList(ListNode head) { if(head==null||head.next==null) { return head; } ListNode fast=head.next,slow=head; while(fast!=null&&fast.next!=null) { slow=slow.next; fast=fast.next.next; } ListNode tmp=slow.next; slow.next=null; ListNode left=sortList(head); ListNode right=sortList(tmp); ListNode h=new ListNode(0); ListNode res=h; while(left!=null&&right!=null) { if(left.val<right.val){ h.next=left; left=left.next; }else{ h.next=right; right=right.next; } h=h.next; } h.next=left!=null?left:right; return res.next; }
class Solution { public ListNode mergeKLists(ListNode []lists) { return mergeKLists(lists,0,lists.length); } public ListNode mergeKLists(ListNode[] lists,int i,int j) { ListNode p=new ListNode(0); int m=j-i; if(m==0)return null; if(m==1)return lists[i]; ListNode left=mergeKLists(lists,i,i+m/2); ListNode right=mergeKLists(lists,i+m/2,j); return mergeTwo(left,right); } public ListNode mergeTwo(ListNode l1,ListNode l2) { ListNode dummy=new ListNode(); ListNode p=dummy; while(l1!=null&&l2!=null) { if(l1.val<l2.val) { p.next=l1; l1=l1.next; }else { p.next=l2; l2=l2.next; } p=p.next; } p.next=l1!=null?l1:l2; return dummy.next; } }
递归法，此题很重要，思想，很重要
二叉树 long pre=Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if(root==null)return true; if(!isValidBST(root.left))return false; if(root.val<=pre)return false; pre=root.val; return isValidBST(root.right); }
对于二叉搜索树，无脑中序遍历就完事了
class Solution { int res,k; void dfs(TreeNode root) { if(root==null)return; dfs(root.left); if(k==0)return ; if(--k==0)res=root.val; dfs(root.right); } public int kthSmallest(TreeNode root, int k) { this.k=k; dfs(root); return res; } }
仍然无脑中序遍历。还有一个知识点：对于递归可以新建一个函数
我的想法：层序遍历，每一层最后一个即为能看见的
List<Integer>res=new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { if(root!=null) { Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); int size; TreeNode node; while(!queue.isEmpty()) { size=queue.size(); while(size-->0) { node=queue.poll(); if(node.left!=null)queue.offer(node.left); if(node.right!=null)queue.offer(node.right); if(size==0)res.add(node.val); } } } return res; }
此题南软经典问题
class Solution { private Map<Integer, Integer> indexMap; public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null; } // 前序遍历中的第一个节点就是根节点 int preorder_root = preorder_left; // 在中序遍历中定位根节点 int inorder_root = indexMap.get(preorder[preorder_root]); // 先把根节点建立出来 TreeNode root = new TreeNode(preorder[preorder_root]); // 得到左子树中的节点数目 int size_left_subtree = inorder_root - inorder_left; // 递归地构造左子树，并连接到根节点 // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1); // 递归地构造右子树，并连接到根节点 // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 构造哈希映射，帮助我们快速定位根节点 indexMap = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { indexMap.put(inorder[i], i); } return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); } }
注意点：1.用哈希降低复杂度2.注意边界
方法一：深度优先搜索，也相当于暴力，这个得回
class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) { return 0; } int ret = rootSum(root, targetSum); ret += pathSum(root.left, targetSum); ret += pathSum(root.right, targetSum); return ret; } public int rootSum(TreeNode root, int targetSum) { int ret = 0; if (root == null) { return 0; } int val = root.val; if (val == targetSum) { ret++; } ret += rootSum(root.left, targetSum - val); ret += rootSum(root.right, targetSum - val); return ret; } }
递归，分类讨论法
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&&right!=null)return root; return left!=null?left:right; }
注意点：自己也是自己的祖先，这是root==p,root==q可以return的前提
图 经典dfs
我没想明白的：如何去重？答：改变值作为标记
如何处理越界？答：你先赋值，然后再判断是否越界，越界了就return即可
class Solution { public int numIslands(char[][] grid) { int count=0; for(int i=0;i<grid.length;i++) { for(int j=0;j<grid[0].length;j++) { if(grid[i][j]=='1') { dfs(grid,i,j); count++; } } } return count; } private void dfs(char[][]grid,int i,int j){ if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]=='0')//越界了，退出 return; grid[i][j]='0'; dfs(grid,i+1,j); dfs(grid,i,j+1); dfs(grid,i-1,j); dfs(grid,i,j-1); } }
经典BFS，为什么是BFS他要求轮数，肯定是bfS
BFS相当于什么，层序遍历
知道这两个，鉴定为易
class Solution { public int orangesRotting(int[][] grid) { int M=grid.length; int N=grid[0].length; Queue<int[]>queue=new LinkedList<>(); int count=0; for(int i=0;i<M;i++){ for(int j=0;j<N;j++) { if(grid[i][j]==1) { count++; }else if(grid[i][j]==2) { queue.add(new int[]{i,j}); } } } int round=0; while(count>0&&!queue.isEmpty()){ round++; int n=queue.size(); for(int i=0;i<n;i++) { int []orange=queue.poll(); int r=orange[0]; int c=orange[1]; if(r-1>=0&&grid[r-1][c]==1) { grid[r-1][c]=2; count--; queue.add(new int[]{r-1,c}); } if(r+1<M&&grid[r+1][c]==1) { grid[r+1][c]=2; count--; queue.add(new int[]{r+1,c}); } if(c+1<N&&grid[r][c+1]==1) { grid[r][c+1]=2; count--; queue.add(new int[]{r,c+1}); } if(c-1>=0&&grid[r][c-1]==1) { grid[r][c-1]=2; count--; queue.add(new int[]{r,c-1}); } } } if(count>0)return -1; return round; } }
经典拓扑排序，我做的时候只想到了环，没发现这是拓扑排序，鉴定为考研全忘了
但是此解还是用看有没有环写的
如何判断有没有环？dfs看是否遍历到已经遍历过的节点
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>>adj=new ArrayList<>(); for(int i=0;i<numCourses;i++) adj.add(new ArrayList<>()); int []flags=new int[numCourses]; for(int []cp:prerequisites) { adj.get(cp[1]).add(cp[0]); } for(int i=0;i<numCourses;i++) { if(!dfs(adj,flags,i))return false; } return true; } private boolean dfs(List<List<Integer>> adj,int[]flags,int i) { if(flags[i]==1)return false;//访问到自己之前访问过的了，说明有环，不行 if(flags[i]==-1)return true;//-1表示是别人访问过的，那就不访问了，直接return flags[i]=1;//第一次访问，置为1 for(Integer j:adj.get(i)) { if(!dfs(adj,flags,j))return false; } flags[i]=-1;//访问完后，回头置为-1 return true; } }
注意事项：要区分自己dfs和别人dfs的
注意事项：isEnd标志，表示是否结束了
class Trie { private Trie[]children; private boolean isEnd; public Trie() { children=new Trie[26]; isEnd=false; } public void insert(String word) { Trie node=this; for(int i=0;i<word.length();i++) { char ch=word.charAt(i); int index=ch-'a'; if(node.children[index]==null) { node.children[index]=new Trie(); } node=node.children[index]; } node.isEnd=true; } public boolean search(String word) { Trie node=serchaprefix(word); return node!=null&&node.isEnd; } public boolean startsWith(String prefix) { return serchaprefix(prefix)!=null; } public Trie serchaprefix(String prefix) { Trie node=this; for(int i=0;i<prefix.length();i++){ char c=prefix.charAt(i); int index=c-'a'; if(node.children[index]==null) { return null; } node=node.children[index]; } return node; } }
二分查找部分 此思路神中神
public int findMin(int[] nums) { int n=nums.length; int l=0,r=n-1; while(l<r) { int mid=l+r+1>>1; if(nums[mid]>=nums[0]) { l=mid; }else { r=mid-1; } } return r+1<n?nums[r+1]:nums[0]; }
考虑到：旋转点左侧>=nums[0],右侧<=nums[0]，所以先找到旋转点，再返回其右边的即可
此题和上体一个道理，对于旋转数组，先找旋转点，然后再按其性质写
class Solution { public int search(int[] nums, int target) { int n=nums.length; int idx=0; for(int i=0;i<n-1;i++){ if(nums[i]>nums[i+1])//旋转点的特点：左侧和右侧都是升序 { idx=i; break;//找到旋转点了 } } int ans=find(nums,0,idx,target); if(ans!=-1)return ans; if(idx+1<n)ans=find(nums,idx+1,n-1,target); return ans; } int find(int []nums,int l,int r,int target) { while(l<r) { int mid=l+r>>1; if(nums[mid]>=target) { r=mid; }else { l=mid+1; } } return nums[l]==target?l:-1; } }
这个题目我这方法无敌
其实他就是什么，行升序，列升序的矩阵
那我们从右上角开始找
public boolean searchMatrix(int[][] matrix, int target) { int i=0,j=matrix[0].length-1; while(i<matrix.length&&j>=0)//从右上角开始 { if(matrix[i][j]<target)//比目标小，那么说明这一行往左都比目标小，直接跳下一行 { i++; }else if(matrix[i][j]>target)//比目标大，说明这一列往下都比他大 { j--; } else { return true; } } return false; }
回溯法部分 反正我从来不会，妈的
总的来说模板如下
横向遍历，纵向遍历，横向控制开始是哪个元素，纵向控制他后面的
遇到回溯问题，先抽象成树
oid backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } } 来源：批码随想录
class Solution { List<List<Integer>> result=new ArrayList<>(); LinkedList<Integer> path=new LinkedList<>(); boolean []used; public List<List<Integer>> permute(int[] nums) { if(nums.length==0) return result; used=new boolean[nums.length]; permuteHelper(nums); return result; } public void permuteHelper(int []nums) { if(path.size()==nums.length) { result.add(new ArrayList<>(path)); return; } for(int i=0;i<nums.length;i++) { if(used[i]) { continue; }used[i]=true; path.add(nums[i]); permuteHelper(nums); path.removeLast(); used[i]=false; } } }
回溯算法进店题目了
子集和全排列的区别，全排列是全部得排，所以必须path满了之后才能add
而子集不用
但是子集如何避免重复呢？用startindex即可，这个是全排列里没有的
class Solution { List<List<Integer>> res=new ArrayList<>(); LinkedList<Integer>path=new LinkedList<>(); public List<List<Integer>> subsets(int[] nums) { subhelp(nums,0); return res; } public void subhelp(int []nums,int start) { res.add(new ArrayList<>(path)); if(start>=nums.length) { return; } for(int i=start;i<nums.length;i++)//i从start开始，避免重复了 { path.add(nums[i]); subhelp(nums,i+1); path.removeLast(); } } }
这个问题在于什么
1.映射数字和字母
2.如何讲n个for循环改成回溯
class Solution { List<String>res=new ArrayList<>(); public List<String> letterCombinations(String digits) { if(digits==null||digits.length()==0)return res; String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; backtracking(digits,numString,0); return res; } StringBuilder temp = new StringBuilder(); public void backtracking(String digits,String[]numString,int index) { if(index==digits.length()) { res.add(temp.toString()); return; } String str=numString[digits.charAt(index)-'0']; for(int i=0;i<str.length();i++) { temp.append(str.charAt(i)); backtracking(digits,numString,index+1); temp.deleteCharAt(temp.length()-1); } } }
注意此处的index，他不是子集问题中，控制不重复的startindex，而是你遍历到了第几个数字，
而每一个数字对应的字符串都是从开头开始遍历，因为2对应的和3对应的不一样，没重复的
此问题很吊，自己画出树形图就行了
class Solution { List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { char[][] chessboard = new char[n][n]; for (char[] c : chessboard) { Arrays.fill(c, '.'); } backTrack(n, 0, chessboard); return res; } public void backTrack(int n, int row, char[][] chessboard) { if (row == n) { res.add(Array2List(chessboard)); return; } for (int col = 0;col < n; ++col) { if (isValid (row, col, n, chessboard)) { chessboard[row][col] = 'Q'; backTrack(n, row+1, chessboard); chessboard[row][col] = '.'; } } } public List Array2List(char[][] chessboard) { List<String> list = new ArrayList<>(); for (char[] c : chessboard) { list.add(String.copyValueOf(c)); } return list; } public boolean isValid(int row, int col, int n, char[][] chessboard) { // 检查列 for (int i=0; i<row; ++i) { // 相当于剪枝 if (chessboard[i][col] == 'Q') { return false; } } // 检查45度对角线 for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) { if (chessboard[i][j] == 'Q') { return false; } } // 检查135度对角线 for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) { if (chessboard[i][j] == 'Q') { return false; } } return true; } }
栈 这题比较简单，值得注意的是用map提到效率，省的写一大堆ifelse判断是否成双成对
class Solution { public boolean isValid(String s) { int n=s.length(); if(n%2==1) { return false; } Deque<Character>stk=new LinkedList<>(); Map<Character,Character>pairs=new HashMap<>(); pairs.put(')','(');//注意先写 pairs.put(']','['); pairs.put('}','{'); for(int i=0;i<s.length();i++) { char ch=s.charAt(i); if(pairs.containsKey(ch)) { if(stk.isEmpty()||stk.peek()!=pairs.get(ch)) { return false; } stk.pop(); }else { stk.push(ch); } } return stk.isEmpty(); } }
双栈解法，一个是存放数值，另一个存放每一个数值进入时，栈内的最小值，getmin返回Minstack中的peek即可
class MinStack { Deque<Integer>xStack; Deque<Integer>minStack; public MinStack() { xStack=new LinkedList<Integer>(); minStack=new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { xStack.push(val); minStack.push(Math.min(val,minStack.peek())); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } }
这一题，关键在于如何解决[]的嵌套问题
解决方法：遇到”[“入栈，遇到’]’出栈，看注解
public static String decodeString(String s) { s = s.trim(); if(s.length()==0 || s==null) return s; StringBuilder res = new StringBuilder();//用Stringbuilder，可以append Stack<Integer> nums = new Stack<>(); Stack<String> strs = new Stack<>(); int num = 0; for(int i=0; i<s.length(); i++) { if(s.charAt(i)>='0' && s.charAt(i)<='9') {//如果 是数字，那么先暂存 num = num*10 + s.charAt(i)-'0';//为什么*10？考虑123[abc]这种情况，123是三位数 }else if(s.charAt(i)>='a' && s.charAt(i)<='z' || s.charAt(i)>='A' && s.charAt(i)<='Z') { res.append(s.charAt(i));//如果还没遇到[，先存着 }else if(s.charAt(i)=='[') {//遇到[了，准备入栈 nums.push(num);//[前面的数字，入栈 strs.push(res.toString());//'['前面的字符串，入栈 res = new StringBuilder();//入完了 啊，又得进行新的一轮暂存了 num = 0;//num也是 }else {//遇到']'了，准备出栈 int time = nums.pop();//前面对应‘【’的前面的数字是多少，就是多少倍 String tmp = strs.pop();//先前存着的‘【’前面的一串字符 for(int j=0; j<time; j++) { tmp += res.toString();//加多少个到后面 } res = new StringBuilder(tmp);//更新res } } return res.toString(); }
额首先是暴力法，但是最后一个测试用例超时了，经典9999999999999999999
public int[] dailyTemperatures(int[] temperatures) { int len=temperatures.length; int[]ans=new int[len]; for(int i=0;i<len-1;i++) { int num=1; for(int j=i+1;j<len;j++) { if(temperatures[j]>temperatures[i]) { ans[i]=num; break; }else { num++; } } } return ans; }
然后是单调站，我想到了，但是遇到问题
栈存储值，如何在ans[]中将多少天存到对应的位置呢？
答案是栈存储下标
public int[] dailyTemperatures(int[] temperatures) { //思路：维持递减栈，那么遇到的比栈头大的就一定是第一个比栈头大的元素 int len=temperatures.length; int []ans=new int[len]; Deque<Integer>stk=new LinkedList<>(); for(int i=0;i<len;i++) { int temperature=temperatures[i]; while(!stk.isEmpty()&&temperature>temperatures[stk.peek()])//注意这里栈直接存储下标就行了 {//如果栈头一直比当前元素大，那么就一直pop int preindex=stk.pop();//拿出栈头元素的下标 ans[preindex]=i-preindex;//减，则是距离 } stk.push(i);//没有更大的了，是递减了，push } return ans; }
堆问题 首先我们要了解compare，这个去java算法常用里去看，虽然我还没写
额，写完这句发现这题我好像就卡在这
class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer,Integer>map=new HashMap<>(); for(int num:nums) { map.put(num,map.getOrDefault(num,0)+1);//经典 } PriorityQueue<Integer>pq=new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a,Integer b) { return map.get(a)-map.get(b);//重写比较的规则，那么这个堆将成为小顶堆，并按此规则自己调整 } }); for(Integer key:map.keySet()) { if(pq.size()<k) { pq.add(key); }else if(map.get(key)>map.get(pq.peek()))//已经有k个了，但是有频率比目前堆中最少的更高的，那么把最少的去掉，新的加入 { pq.remove(); pq.add(key); } } List<Integer> res=new ArrayList<>(); while(!pq.isEmpty()) { res.add(pq.remove()); } return res; } }
有了上一题的理解，这一题就鉴定为易了
不就是小顶堆么
public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer>pq=new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a ,Integer b) { return a-b; } }); for(int num:nums) { if(pq.size()<k) { pq.add(num); }else if(pq.peek()<num) { pq.remove(); pq.add(num); } } return pq.peek(); }