Hot100刷题笔记
我直接就是一个刷刷刷！！！
链表
24. 两两交换链表节点
交换时需要考虑的问题：
1、是否满足有两个节点（node1、node2）来交换
2、交换时必须要前一个节点辅助交换
3、交换前必须记录node2的下一个节点
解题思路：
1.要一个哨兵节点辅助交换（问题2）
2.每次只用关注node2是否为空即可（问题1）
3.交换节点之前记录下一个节点（问题3）
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null) return head;
ListNode dumpy = new ListNode(0,head);
ListNode prev=dumpy,node1=head,node2=head.next;
//dumpu->1->2->3->4->null
while(node1!=null&&node2!=null){
ListNode nxt = node2.next;
// 交换
node1.next=nxt;
prev.next=node2;
node2.next=node1;
if(nxt==null){
break;
}
// 重新命名
prev = node1;
node1 = nxt;
node2 = nxt.next;
}
return dumpy.next;
}25. K 个一组翻转链表
思路：本质就是链表翻转。重点在于如何确定翻转的范围：
1、用长度数字进行遍历，记录这段起始点curr_head，到长度k后，翻转curr_head到curr这段链表。
2、翻转后如何拼接链表：此时翻转后变成三段（前，curr，后），需要用哨兵节点记录上一段的最后一个节点拼接前和curr段；翻转前记录后的第一个节点。反转后拼接上curr+后。
3、注意：(i + 1) % k == 0来判断。
public ListNode reverseKGroup(ListNode head, int k) {
int len = 0;
ListNode senti = new ListNode(0, head), curr = head;
while (curr != null) {
curr = curr.next;
len++;
}
ListNode curr_head = head, nxt = null, h_senti = senti;
curr = head;
for (int i = 0; i < len; i++) {
if ((i + 1) % k == 0) {
nxt = curr.next;
curr.next = null;
// 翻转后变成前，curr，后三段链表。
// curr_head反转后从第一个变成最后一个:需要链接到后面的组，并让senti=curr_head
// 拼接-->前+curr
h_senti.next = reverse(curr_head);
// 拼接-->curr+后
curr_head.next = nxt;
h_senti = curr_head;
// 重新定义各个节点
curr_head = nxt;
curr = nxt;
} else {
curr = curr.next;
}
}
return senti.next;
}138. 随机链表的复制
思路：一模一样的复制，若没有random节点，直接遍历复制val即可。有random节点，必须知道在原链表中的节点的random指向哪个节点。做一个交错的复制链表，通过遍历时取next就能取到。但是要注意random为null的情况。
在每个原节点后插入复制节点形成交错链表，这样原节点的复制节点就是它的next，原节点的random指向的节点的复制节点就是random.next。通过三次遍历完成：第一次交错复制、第二次设置random指针、第三次分离链表。
public Node copyRandomList(Node head) {
Node h =head;
// 1.先一个间隔一个的在原链表插入复制一个
while(h!=null){
Node tmp = new Node(h.val);
tmp.next=h.next;
h.next=tmp;
h=h.next.next;
}
// 2.复制random字段，原链表节点对应的下一个
h=head;
while(h!=null){
Node copy = h.next;
// 注意random可能是null，没有下一个节点
copy.random = h.random==null?null:h.random.next;
h=copy.next;
}
// 3.利用dummy拆出节点
h=head;
Node dummy = new Node(0);
Node tmp_dummy=dummy;
while(h!=null){
Node copy = h.next;
tmp_dummy.next = copy;
tmp_dummy=copy;
h.next = copy.next;
h=h.next;
}
return dummy.next;
}148. 排序链表
思路：链表排序，通过分治思想，把链表切割看成两个链表，然后递归使左右有序，合并有序链表即可
public ListNode sortList(ListNode head) {
if(head==null||head.next==null) return head;
ListNode mid = mid(head);
mid = sortList(mid);
head = sortList(head);
return merge(mid,head);
}23. 合并K个升序链表->1
思路：分治思想，把数组切割看成两个数组，递归合并左右数组，到数组只剩两个时进行合并有序链表
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if(len==0) return null;
return mergeLists(lists,0,len-1);
}
ListNode mergeLists(ListNode[] lists,int l,int r){
if(l==r) return lists[l];
ListNode a = mergeLists(lists,l,(l+r)/2);
ListNode b = mergeLists(lists,(l+r)/2+1,r);
return merge(a,b);
}146. LRU 缓存
思路：借助LinkedHashMap（插入有序，最近最少使用的就在第一个）。注意Hashmap的API，containsKey(),map的iterator()先用keySet()进行获取
二叉树
108. 将有序数组转换为二叉搜索树
思路：有序数组转二叉搜索树，即每次切分数组为两份，分别递归构建成左右子树。小的部分构建左子树，大的部分构建右子树。
注意：停止时机：左右index相等时创建节点返回，右节点小于左节点的时候不满足返回null
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums,0,nums.length-1);
}
TreeNode build(int[] nums,int l,int r){
if(r<l) return null;
if(l==r) return new TreeNode(nums[l]);
int mid = l+(r-l)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = build(nums,l,mid-1);
node.right = build(nums,mid+1,r);
return node;
}114. 二叉树展开为链表
思路：题目要求将二叉树展开为链表，即按照按后序遍历顺序展开，展开后的结构应为所有左子树为空、仅用右指针连接的链表。我们可以利用一个全局变量
prev来记录当前已经构建好的链表的头节点。对原树进行后序遍历（右子树 → 左子树 → 根节点），在遍历过程中依次将节点重新连接。
- 当前节点的右指针指向
prev（已构建的链表头），左指针置空；- 更新
prev为当前节点，使其成为新的链表头。
TreeNode ans = null;
public void flatten(TreeNode root) {
dfs(root);
}
void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.right);
dfs(root.left);
root.right = this.ans;
root.left = null;
this.ans = root;
}105. 从前序与中序遍历序列构造二叉树
思路：根据前序（根节点在最前）和中序（根节点在中间）特点，分割左右两个数组，然后分别递归构建左右子树。
1、先用获取前序（根节点在最前），把中序数组分割为两个子数组
2、用序数组分割的两个子数组的长度，将前序数组分割为左右两个子数组
3、分别将上述两个子数组递归构建左右子树
4、在数组长度为0时返回null
思考：为什么长度为1时进行mid+1取子数组也不会出现out length：因为先取inorder，mid只能为0为，mid+1=1，取（1，length）实际就是空数组了，就结束递归。
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0) return null;
// 前序 第一个 切分 中序左右子树
int mid = find(inorder, preorder[0]);
int[] l_inorder = Arrays.copyOfRange(inorder, 0, mid);
int[] r_inorder = Arrays.copyOfRange(inorder, mid + 1, inorder.length);
// 根据中序的左右子树，切分前序数组
int[] l_pre = Arrays.copyOfRange(preorder, 1, 1 + l_inorder.length);
int[] r_pre = Arrays.copyOfRange(preorder, 1 + l_inorder.length, preorder.length);
TreeNode root = new TreeNode(preorder[0]);
root.left = buildTree(l_pre, l_inorder);
root.right = buildTree(r_pre, r_inorder);
return root;
}
int find(int[] nums,int num){
for(int i=0;i<nums.length;i++){
if(nums[i]==num) return i;
}
return -1;
}437. 路径总和 III
思路：要求路径和是从上到下满足targetsum，其实就是前缀和之差，递归二叉树，用curr记录到了的前缀和，用一个map存前缀个数，然后通过map.get(curr-targetsum)若有则表示有一段是满足和为targetsum的。
注意：
1、要先get后再进行存储个数（特殊情况tree=[1],targetSum=0）
2、当前节点结束后要把这包含这个节点的前缀和从map中取消。
3、map的key要设置为Long
class Solution {
HashMap<Long,Integer> map = new HashMap();
int ans=0;
public int pathSum(TreeNode root, int targetSum) {
map.put(0L,1);
dfs(root,targetSum,0L);
return this.ans;
}
void dfs(TreeNode root,int targetSum,Long curr){
if(root==null) return;
curr+=root.val;
this.ans+=map.getOrDefault(curr-targetSum,0);
map.merge(curr,1,Integer::sum);
dfs(root.left,targetSum,curr);
dfs(root.right,targetSum,curr);
map.merge(curr,-1,Integer::sum);
}
}思路：最次返回当前节点。
1、若当前节点为空返回当前节点，若当前节点与p或q其中一个相等也返回当前节点。
2、递归左右子树：若l，r都不为空返回当前节点。若l，r有一个为空返回不为空的。都为空返回null
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return root;
if(root==p||root==q) return root;
TreeNode l = lowestCommonAncestor(root.left,p,q);
TreeNode r = lowestCommonAncestor(root.right,p,q);
if(l!=null&&r!=null) return root;
if(l!=null) return l;
if(r!=null) return r;
return null;
}思路：最大路径和是一条路径上的和，每一个节点都可能成为路径的 “顶点”（即路径以该节点为中心，向左右子树延伸）。
通过后序递归遍历，返回当前节点的最大有效和 （注意：这个地方返回的最长和是要么左要么右，因为要满足向上回溯的路径连续性，只需要向上返回当前节点下的最优，但如果左右都小于0直接返回0）。且每次每个节点要再计算当前节点作为 “顶点” 时的路径和（根节点值 + 左子树有效贡献 + 右子树有效贡献），并更新全局最大值。
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
int dfs(TreeNode root) {
if (root == null)
return 0;
int l = dfs(root.left);
int r = dfs(root.right);
int curr = root.val;
if (l > r) {
curr += l;
} else {
curr += r;
}
int curr_path = root.val+l+r;
max = Math.max(Math.max(curr_path,curr),max);
return curr < 0 ? 0 : curr;
}
}排序
冒泡排序
void sort(int[] nums){
int len=nums.length;
for(int i=0;i<len;i++){
for(int j=1;j<len-i;j++){
if(nums[j-1]>nums[j]){
int tmp=nums[j-1];
nums[j-1]=nums[j];
nums[j]=tmp;
}
}
}
}快速排序
思路：通过分治的思想，先把数组以pivot分割为左小于，右大于的数组，然后递归的再把左右进行相同操作实现排序。
void quickSort(int[] nums){
if(nums.length<1) return;
sort(nums,0,nums.length-1);
}
void sort(int[] nums,int l,int r){
if(l>=r) return; //不用排序了
int pivot = partition(nums,l,r);
sort(nums,l,pivot-1);
sort(nums,pivot+1,r);
}
int partition(int[] nums,int l,int r){
int pivot = nums[l]; //可随机选取未排序范围内数据进行分割
int left = l,right=r;
while(left<right){
while(left<right&&nums[right]>=pivot){
right--;
}
if (left < right) {
nums[left]=nums[right];
left++;
}
while(left<right&&nums[left]<=pivot){
left++;
}
if(left<right){
nums[right]=nums[left];
right--;
}
}
nums[left]=pivot;
return left;
}