前言
学长发话了，找实习之前把hot100和剑指offer刷了就行了
先刷烧鸡100
中言
tmd我的hexo代码高亮一直没用，试了100种方法，没用就没用吧，拉倒了
简单题部分
1. 两数之和 - 力扣（LeetCode
首先就是暴力法，很垃圾
c++
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;
}然后，好方法是什么，看答案
c++
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语言实现一下
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
}20. 有效的括号 - 力扣（LeetCode）
为了熟悉go语言，也用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
}21. 合并两个有序链表 - 力扣（LeetCode）
c++
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;
}
};461. 汉明距离 - 力扣（LeetCode）
java
class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x^y);
}
}知识点：异或、bitCount()
617. 合并二叉树 - 力扣（LeetCode）
java
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 另一个
70. 爬楼梯 - 力扣（LeetCode）
我最先想到了递归，但是超时了
java
public int climbStairs(int n) {
if(n==1)return 1;
if(n==2)return 2;
return climbStairs(n-1)+climbStairs(n-2);
}于是经典动态规划
java
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;
}中等
11. 盛最多水的容器 - 力扣（LeetCode）
java
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;
}只要更新矮的那一边即可
15. 三数之和 - 力扣（LeetCode）
java
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;
}有一说一有点难度，主要是这个去重没想到
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
java
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;
}
}二分查找找左右边界问题，注意注释里的
哈希部分
128. 最长连续序列 - 力扣（LeetCode）
java
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开始的长
滑动窗口
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
java
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()，然后循环判断，超时
子串问题
560. 和为 K 的子数组 - 力扣（LeetCode）
java
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;
}239. 滑动窗口最大值 - 力扣（LeetCode）
java
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大小来判断来着
普通数组
53. 最大子数组和 - 力扣（LeetCode）
java
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;
}经典动态规划题目，一开始还没想起来，后来想起来是动态规划，还是比较简单的
56. 合并区间 - 力扣（LeetCode）
此题很吊
java
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算法常用
### 189. 轮转数组 - 力扣（LeetCode）
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--;
}
}首先想到暴力，但是超时了！
用翻转法：
java
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:这题目南软考过
41. 缺失的第一个正数 - 力扣（LeetCode）
java
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;
}我是呆子
矩阵
73. 矩阵置零 - 力扣（LeetCode）
java
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的行和列做标记
java
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:有什么大病
54. 螺旋矩阵 - 力扣（LeetCode）
官方题解：my assessment：烂
java
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;
}神中神做法：
java
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);
}神级思路，设立四个边界，然后按边界走，同时收缩边界
48. 旋转图像 - 力扣（LeetCode）
弱智方法：就是找个t，先复制一下，然后按规律改
java
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
java
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;
}
}
}240. 搜索二维矩阵 II - 力扣（LeetCode）
一：暴力
二：每一行二分
三：妙方法
java
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，这一列都不用看了
链表部分
142. 环形链表 II - 力扣（LeetCode）
方法一：妙啊，用set，虽然笨但是我都没想到，我是傻逼
java
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;
}方法二：双指针，我想到了但是不会做，我草
java
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;
}严格的数学推导，见解答
24. 两两交换链表中的节点 - 力扣（LeetCode）
我的想法：用栈啊，很好，超过100%时间复杂度
java
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;
}更多人用的：递归
java
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被交换到前面了
过程：交换两个
什么时候停止：没了，或者下一个没了
25. K 个一组翻转链表 - 力扣（LeetCode）
java
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;
}依旧是栈，注意事项在注释里
148. 排序链表 - 力扣（LeetCode）
此题作为归并排序的板子，记住！！！！！！
java
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;
}23. 合并 K 个升序链表 - 力扣（LeetCode）
java
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;
}
}递归法，此题很重要，思想，很重要
二叉树
98. 验证二叉搜索树 - 力扣（LeetCode）
java
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);
}对于二叉搜索树，无脑中序遍历就完事了
230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）
java
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;
}
}仍然无脑中序遍历。还有一个知识点：对于递归可以新建一个函数
199. 二叉树的右视图 - 力扣（LeetCode）
我的想法：层序遍历，每一层最后一个即为能看见的
java
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;
}105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
此题南软经典问题
java
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.注意边界
437. 路径总和 III - 力扣（LeetCode）
方法一：深度优先搜索，也相当于暴力，这个得回
java
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;
}
}236. 二叉树的最近公共祖先 - 力扣（LeetCode）
递归，分类讨论法
java
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的前提
图
200. 岛屿数量 - 力扣（LeetCode）
经典dfs
我没想明白的：如何去重？答：改变值作为标记
如何处理越界？答：你先赋值，然后再判断是否越界，越界了就return即可
java
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);
}
}994. 腐烂的橘子 - 力扣（LeetCode）
经典BFS，为什么是BFS他要求轮数，肯定是bfS
BFS相当于什么，层序遍历
知道这两个，鉴定为易
java
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;
}
}207. 课程表 - 力扣（LeetCode）
经典拓扑排序，我做的时候只想到了环，没发现这是拓扑排序，鉴定为考研全忘了
但是此解还是用看有没有环写的
如何判断有没有环？dfs看是否遍历到已经遍历过的节点
java
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的
208. 实现 Trie (前缀树) - 力扣（LeetCode）
注意事项：isEnd标志，表示是否结束了
java
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;
}
}
二分查找部分
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
此思路神中神
java
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]，所以先找到旋转点，再返回其右边的即可
33. 搜索旋转排序数组 - 力扣（LeetCode）
此题和上体一个道理，对于旋转数组，先找旋转点，然后再按其性质写
java
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;
}
}74. 搜索二维矩阵 - 力扣（LeetCode）
这个题目我这方法无敌
其实他就是什么，行升序，列升序的矩阵
那我们从右上角开始找
java
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;
}回溯法部分
反正我从来不会，妈的
总的来说模板如下
横向遍历，纵向遍历，横向控制开始是哪个元素，纵向控制他后面的
遇到回溯问题，先抽象成树
javq
oid backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
来源：批码随想录
46. 全排列 - 力扣（LeetCode）
java
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;
}
}
}回溯算法进店题目了
78. 子集 - 力扣（LeetCode）
子集和全排列的区别，全排列是全部得排，所以必须path满了之后才能add
而子集不用
但是子集如何避免重复呢？用startindex即可，这个是全排列里没有的
java
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();
}
}
}17. 电话号码的字母组合 - 力扣（LeetCode）
这个问题在于什么
1.映射数字和字母
2.如何讲n个for循环改成回溯
java
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对应的不一样，没重复的
51. N 皇后 - 力扣（LeetCode）
此问题很吊，自己画出树形图就行了
java
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;
}
}栈
20. 有效的括号 - 力扣（LeetCode）
这题比较简单，值得注意的是用map提到效率，省的写一大堆ifelse判断是否成双成对
java
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();
}
}155. 最小栈 - 力扣（LeetCode）
双栈解法，一个是存放数值，另一个存放每一个数值进入时，栈内的最小值，getmin返回Minstack中的peek即可
java
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();
}
}394. 字符串解码 - 力扣（LeetCode）
这一题，关键在于如何解决[]的嵌套问题
解决方法：遇到”[“入栈，遇到’]’出栈，看注解
java
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();
}739. 每日温度 - 力扣（LeetCode）
额首先是暴力法，但是最后一个测试用例超时了，经典9999999999999999999
java
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[]中将多少天存到对应的位置呢？
答案是栈存储下标
java
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;
}堆问题
347. 前 K 个高频元素 - 力扣（LeetCode）
首先我们要了解compare，这个去java算法常用里去看，虽然我还没写
额，写完这句发现这题我好像就卡在这
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;
}
}215. 数组中的第K个最大元素 - 力扣（LeetCode）
有了上一题的理解，这一题就鉴定为易了
不就是小顶堆么
java
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();
}
