day5
25-k个一组翻转链表
题目：
答案：
迭代法：
public ListNode reverseKGroup(ListNode head, int k) {
ListNode node = new ListNode(0);
ListNode pre=node;
node.next=head;
while (head!=null){
ListNode tail=head;
for (int i = 0; i < k - 1; i++) {
tail=tail.next;
if (tail==null){
return node.next;
}
}
ListNode[] reserve = reserve(head, tail);
head=reserve[0];
tail=reserve[1];
pre.next=head;
pre=tail;
head=tail.next;
}
return node.next;
}
public ListNode[] reserve(ListNode head,ListNode tail){
ListNode p=head;
ListNode prev=tail.next;
while (prev!=tail){
ListNode temp=p.next ;
p.next=prev;
prev=p;
p=temp;
}
return new ListNode[]{tail,head};
}
就是因为是k个一组嘛，每次遍历k个元素，然后调用外部的方法进行反转，反转之后再进行拼接，所以要提前记录反转头部的前一个节点，又因为，头节点没有前一个节点，所以要使用虚拟头节点；使用虚拟头节点进行连接；
递归：
ListNode curNode =head;
int count=0;
while (curNode !=null){
curNode = curNode.next;
count++;
}
if (count<k){
return head;
}
ListNode pre=head;
ListNode cur=head.next;
for (int i = 0; i < k - 1; i++) {
ListNode temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
head.next=reverseKGroup(cur,k);
return pre;
先判断剩下的节点能不能构成一组，如果不能构成一组那么就直接返回，如果能，就先进行反转，然后head也就是反转之后的队列尾的下一个节点，进行递归，最后返回反转后的头节点pre；
138-随机链表的复制
题目：
答案：
public Node copyRandomList(Node head) {
if (head==null){
return null;
}
HashMap<Node, Node> map = new HashMap<>();
Node cur=head;
while (cur!=null){
Node node=new Node(cur.val);
map.put(cur,node);
cur=cur.next;
}
cur=head;
while (cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
就是两次遍历链表，第一次创建所以节点的副本添加到map中，同时保持与原链表的对应关系，这样就能在第二次遍历中，找到对应关系，第二次遍历就是直接给新的节点的属性赋值；
148-排序列表
题目
答案：
public ListNode sortList(ListNode head) {
if (head==null||head.next==null){
return head;
}
ListNode fast=head;
ListNode slow=head;
while (fast.next!=null||fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
fast=slow.next;
slow.next=null;
slow=fast;
ListNode left=sortList(head);
ListNode right=sortList(slow);
ListNode newHead = new ListNode(-1);
ListNode cur=newHead;
while (left!=null&&right!=null){
if (left.val<= right.val){
cur.next=left;
left=left.next;
}else {
cur.next=right;
right=right.next;
}
cur=cur.next;
}
cur.next=left!=null?left:right;
return newHead.next;
}
这里使用了归并排序的思想，先通过快慢指针，快指针每次移动两个节点，慢指针每次移动一个节点，当快指针指到链表的尾部时，那么慢指针就指向了链表的中间位置，然后将其断开，然后接着递归分开，直到只剩下一个节点再去合并。
23-合并k个有序链表
题目：
1：就是依次两个两个链表合并，用一个变量保存结果：
ListNode cur=lists[0];
for (int i = 1; i < lists.length; i++) {
ListNode merge = merge(cur, lists[i]);
cur=merge;
}
return cur;
public ListNode merge2List(ListNode left ,ListNode right){
ListNode head = new ListNode(-1);
ListNode cur=head;
while (left!=null&&right!=null){
if (left.val<=right.val){
cur.next=left;
left=left.next;
}else {
cur.next=right;
right=right.next;
}
cur=cur.next;
}
if (left!=null){
cur.next=left;
}
if (right!=null){
cur.next=right;
}
return head.next;
}
2：使用分治合并的思想，比如集合有四个链表，2个2个合并了只需要合并两次；如果是第一种方法要合并3次；
if (lists.length==0){
return null;
}
return merge(lists,0,lists.length-1);
public ListNode merge(ListNode[]list,int l,int r){
if (l==r){
return list[l];
}
int mid=(l+r)/2;
ListNode left=merge(list,l,mid);
ListNode right=merge(list,mid+1,r);
return merge2List(left,right);
}
public ListNode merge2List(ListNode left ,ListNode right){
ListNode head = new ListNode(-1);
ListNode cur=head;
while (left!=null&&right!=null){
if (left.val<=right.val){
cur.next=left;
left=left.next;
}else {
cur.next=right;
right=right.next;
}
cur=cur.next;
}
if (left!=null){
cur.next=left;
}
if (right!=null){
cur.next=right;
}
return head.next;
}
3：使用优先级队列，放入队列就是按照从小到达排序的，又因为每个链表都是有序的，所以我们只需要每个链表加入一个元素，然后放入优先级队列就自动比较，每个链表的唯一元素谁是最小的，取出最小的，然后往对应链表向后遍历，加入下一个元素，依次比较就行：
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node!=null){
queue.offer(node);
}
}
ListNode newHead = new ListNode(-1);
ListNode cur=newHead;
while (!queue.isEmpty())
{
ListNode s = queue.poll();
cur.next=s;
s=s.next;
if (s!=null){
queue.offer(s);
}
}
return newHead.next;
146-LRU缓存
题目：
答案：
class LRUCache {
class DLinkedNode {
public DLinkedNode prev;
public DLinkedNode next;
public Integer key;
public Integer value;
public DLinkedNode(Integer key, Integer value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> map = new HashMap<>();
private int capacity;
private int size;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head=new DLinkedNode(0,0);
tail=new DLinkedNode(0,0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = map.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = map.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode(key, value);
map.put(key,newNode);
addHead(newNode);
size++;
if (size>capacity){
DLinkedNode remove= removeTail();
map.remove(remove.key);
size--;
}
}else {
node.value=value;
moveToHead(node);
}
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(tail.prev);
return res;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addHead(node);
}
private void addHead(DLinkedNode node) {
node.next = head.next;
head.next = node;
node.next.prev = node;
node.prev = head;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
题目的意思是设计一个数据结构，像map一样存储键值对，但是其中的get方法，和put方法有不同，因为put方法中要求，如果添加元素之后缓存的大小大于原本设置的大小就要去除掉最长时间没被使用的元素，这里的使用可以指的是通过get方法使用，也可以1指的是put重复的元素。所以需要当元素被使用时需要进行更新。所以我们在设计数据结构时，不仅需要map充当主要的数据结构，还需要一个数据结构去存储每个元素的使用情况。可以使用一个双向链表来存储。当使用元素时就将元素放置到双向链表的首部，添加元素时也将元素放入到首部；
为了使添加和删除元素方便，我们使用虚拟头节点，和虚拟尾节点。然后map的val也是双向链表的节点，这是为了更改链表信息方便。然后在get方法中，先获取，判断是否为空，如果为空就返回-1，如果不为空就将其移至头部，因为是移至头部，所以需要先删除节点，再将节点添加到头部。然后返回节点的value；
put方法也是首先获取如果没有那么就是新的节点，需要创建一个双向链表的节点，然后将节点放入map，再将这个节点放入双向链表头部。之后size++，再判断size是否大于缓存的容量如果大于就要删除双向链表的尾部的节点，同时将对应的缓存也删除，然后将size–；
如果不是新的节点，那么只需要更新节点的value值，然后重新加入双向链表的头部；
94-二叉树中序遍历
题目：
第一种递归：
List<Integer>list=new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
travel(root);
return list;
}
public void travel(TreeNode root){
if (root==null){
return ;
}
travel(root.left);
list.add(root.val);
travel(root.right);
}
第二种是迭代：使用栈，因为中序遍历的顺序是左中右，要一致向左遍历直到为空，所以我们也是一直向左遍历，并且将节点加入栈中，因为先入栈后出，和中序遍历的顺序一样，然后直到为空开始出栈，那个位置就是最左边，然后出栈，之后将出栈节点的右节点加入。一直循环就行；
List<Integer>list=new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
travel(root);
return list;
}
public void travel(TreeNode root){
TreeNode cur=root;
Stack<TreeNode> stack = new Stack<>();
while (cur!=null||!stack.isEmpty()){
if (cur!=null){
stack.push(cur);
cur=cur.left;
}else {
cur= stack.pop();
list.add(cur.val);
cur=cur.right;
}
}
}
104-二叉树的最大深度
题目：
第一种办法：层序遍历，每遍历一层加1，最大层数就是最大深度；层序遍历使用队列实现；
public int maxDepth(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
int res=0;
if (root==null)return res;
queue.offer(root);
while (!queue.isEmpty()){
int len=queue.size();
while (len>0){
TreeNode poll = queue.poll();
if (poll.left!=null)queue.offer(poll.left);
if (poll.right!=null)queue.offer(poll.right);
len--;
}
res++;
}
return res;
}
第二种办法：递归遍历；一直遍历直到为空然后向上返回，每返回一次深度就加一；
public int maxDepth(TreeNode root) {
if (root==null){
return 0;
}else {
int left=maxDepth(root.left);
int right=maxDepth(root.right);
return Math.max(left,right)+1;
}
}
226-翻转二叉树
题目：
第一种方法递归：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
invertTree(root.left);
invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right=temp;
return root;
}
第二种方法：层序遍历：
public TreeNode invertTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
if (root==null)return root;
while (!queue.isEmpty()){
int len=queue.size();
while (len>0){
TreeNode poll = queue.poll();
if (poll.left!=null)queue.offer(poll.left);
if (poll.right!=null)queue.offer(poll.right);
TreeNode temp=poll.left;
poll.left=poll.right;
poll.right=temp;
len--;
}
}
return root;
}
101-对称二叉树
题目：
第一种方式：
public boolean isSymmetric(TreeNode root) {
return compare(root.left,root.right);
}
public boolean compare(TreeNode left , TreeNode right){
if (left==null&&right!=null){
return false;
}
if (left!=null&&right==null){
return false;
}
if (left==null&&right==null){
return true;
}
if (left.val!=right.val){
return false;
}
boolean compare = compare(left.left, right.right);
boolean compare1 = compare(left.right, right.left);
return compare && compare1;
}
递归，递归的参数是左子树的根节点和右指针的根节点；
判断两个树是否对称看的其实是左子树的左节点和右子树的右节点是否相等，并且，左子树的右节点是否和右子树的左节点相等；
递归停止条件是：左子节点为空，右子节点不为空；
右子节点为空，左子节点不为空；
左右节点不相等；
第二种：也算是层序遍历把，先把根节点的左右节点加入队列里，然后取出，判断左右节点是否相同，如果都为空就继续，如果有一个为空或者值不相同就返回false；如果都相同的话就将左节点的左节点，右右，左右，右左依次加入，进行下一轮判断；如果都满足，最后返回true；
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left==null&&right==null){
continue;
}
if (left==null||right==null||left.val!=right.val){
return false;
}
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
543-二叉树的直径
题目：
答案：
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
treeMax(root);
return ans - 1;
}
public int treeMax(TreeNode root) {
if (root == null) {
return 0;
}
int left = treeMax(root.left);
int right = treeMax(root.right);
ans = Math.max(ans, left + right + 1);
return Math.max(left, right) + 1;
}
使用ans记录每个节点的左右节点的深度和+1，就是从当前节点出发能经过的最大节点数，然后每个节点都记录，比较出最大值赋值给ans，最后返回ans-1，最大路径就是经过的最大节点数+1；
108-将有序数组转为二叉搜索树
题目：
答案：
public TreeNode sortedArrayToBST(int[] nums) {
if (nums.length==0){
return null;
}
int mid=nums.length/2;
TreeNode root=new TreeNode(nums[mid]);
root.left=sortedArrayToBST(Arrays.copyOfRange(nums,0,mid));
root.right=sortedArrayToBST(Arrays.copyOfRange(nums,mid+1,nums.length));
return root;
}
通过递归来拼接，因为是二叉搜索树而且是平衡的，我们要使用中间的节点作为根节点，然后在递归根节点左边的数组和右边的数组，获取的结果就是根节点的左子节点和右子节点；
98-验证二叉搜索树
题目：
答案：
public boolean isValidBST(TreeNode root) {
if (root==null)return true;
boolean validBST = isValidBST(root.left);
if (root.val>along){
along=root.val;
}else return false;
boolean validBST1 = isValidBST(root.right);
return validBST1&&validBST;
}
因为二叉搜索树是经过排序的，也就是说二叉树中序遍历的结果是一个递增的序列；我们依照这一点进行中序遍历，存储之前遍历的最大值，如果在中序遍历的过程中发现有比最大值要小的说，说明这个序列不是递增的，也就不是二叉搜索树；
230-二叉搜索树第k小的节点
题目：
答案：
这里求的是二叉搜索树第k小的节点就很简单了，因为二叉搜索树中序遍历后就是递增的序列，递增的序列求第k个最小元素不就是第k个元素吗。所以我们使用中序遍历，然后计数。当遍历到第k个元素时就返回就行；
- 使用迭代的中序遍历
public int kthSmallest(TreeNode root, int k) {
/*travelList(root,k);
return list.get(k-1);*/
int ans = -1;
int count = 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (count == k) {
break;
}
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
TreeNode pop = stack.pop();
ans = pop.val;
cur = pop.right;
count++;
}
}
return ans;
}
第二种：递归法：
int count = 0;
int ans = -1;
public int kthSmallest(TreeNode root, int k) {
travelList(root, k);
return ans;
}
public void travelList(TreeNode root, int k) {
if (root == null || count==k) {
return;
}
travelList(root.left, k);
if (count < k) {
ans = root.val;
count++;
}
travelList(root.right, k);
}
114-二叉树展开为链表
题目：
这里要求展开成链表之后是先序遍历，我们知道先序遍历是中左右的顺序，所以右子树是最后的，而我们要将右子树拼接到左子树上，也就是拼接到前驱节点，前驱节点是左子树中先序遍历最后一个访问的节点，一般就是左子树第一个节点，如果第一个节点有右子节点，就是右子节点，一直向右直到为空；所以我们就要找到前驱节点，然后将右子树拼接到前驱节点就行，这样我们遍历每个节点获取前驱节点，然后通过调换位置就能得到答案了；
public void flatten(TreeNode root) {
TreeNode cur=root;
while (cur!=null){
if (cur.left!=null){
TreeNode next=cur.left;
TreeNode pre=next;
while (pre.right!=null){
pre=pre.right;
}
pre.right=cur.right;
cur.left=null;
cur.right=next;
}
cur=cur.right;
}
}
第二种解法是通过前序遍历：
List<TreeNode> list = new ArrayList<>();
public void flatten(TreeNode root) {
travel(root);
for (int i = 1; i < list.size(); i++) {
TreeNode pre=list.get(i-1);
TreeNode cur=list.get(i);
pre.left=null;
pre.right=cur;
}
}
public void travel(TreeNode root) {
if (root != null) {
list.add(root);
travel(root.left);
travel(root.right);
}
}
TreeNode next=cur.left;
TreeNode pre=next;
while (pre.right!=null){
pre=pre.right;
}
pre.right=cur.right;
cur.left=null;
cur.right=next;
}
cur=cur.right;
}
}
第二种解法是通过前序遍历：
```java
List<TreeNode> list = new ArrayList<>();
public void flatten(TreeNode root) {
travel(root);
for (int i = 1; i < list.size(); i++) {
TreeNode pre=list.get(i-1);
TreeNode cur=list.get(i);
pre.left=null;
pre.right=cur;
}
}
public void travel(TreeNode root) {
if (root != null) {
list.add(root);
travel(root.left);
travel(root.right);
}
}