秋招突击——7/29——复习{有塔游戏——关联传递性}——新作{随机链表的复制、合并K个升序链表，二叉树—

文章目录

- 引言
- 复习
- - 有塔游戏——关联传递性实现
  - - 复习实现
    - 参考实现
- 新作
- - 随机链表的复制
  - - 个人实现
    - 参考实现
  - 排序链表
  - - 个人实现
    - 参考实现
  - 二叉树章节
  - 二叉树的中序遍历
  - - 个人实现
  - 二叉树的最大深度
  - - 个人实现
    - 参考实现
  - 反转二叉树
  - - 个人实现
    - 参考实现
- 总结

引言

旅游完回来了，今天继续开始准备秋招了，目前除了继续刷算法，还应该抽出时间继续完善一下项目。除此之外，关于很多java的底层的东西，都是看过了，就忘记了，以后每天得抓紧时间开始背书，不然只会更加难过！
加油！

复习

有塔游戏——关联传递性实现

题目内容

给你一个阈值x，然后给你m个点的坐标，然后计算每一个点彼此之间的距离，如果距离小于等于x，那么这两个点就是相关联的。关联具有传递性，A和B关联，B和C关联，那么A和C关联。
输出所有关联的集合，每一行表示对应序号的点是关联的，使用空格尽心分割，同一行按照从小到大进行排序，不同行之间按照首字母的从小到大进行排序。
第一次做学习
输入样例

2.0
5
1.0 2.0
3.0 2.0 
1.0 3.0
5.0 9.5
8.9 1.0

输出样例

0 1 2
3
4

复习实现

这里使用深度遍历dfs去实现，深度是遍历对应的元素数量，单次遍历的内容是当前元素在邻接矩阵中所在的行。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;class Main{static List<Integer> list = new ArrayList<>();static boolean[] visited;static boolean[][] link;static void dfs(int idx,int count){for(int i = 0;i < count;i ++){if(link[idx][i] && !visited[i]){visited[i] = true;list.add(i);dfs(i,count);}}}public static void main(String args[]){Scanner in = new Scanner(System.in);float edge = (float)Math.pow(in.nextFloat(),2);int count = in.nextInt();float[][] nodes = new float[count][2];for(int i = 0;i < count;i ++){nodes[i][0] = in.nextFloat();nodes[i][1] = in.nextFloat();}// cal the neighbour matrixlink = new boolean[count][count];for(int i = 0;i < count;i ++){for(int j = i + 1;j < count;j ++){float dist = (float)(Math.pow(nodes[i][0] - nodes[j][0],2) +Math.pow(nodes[i][1] - nodes[j][1],2));link[i][j] = edge >= dist;link[j][i] = link[i][j];}}// gene the visited matrix and dfs the resultvisited = new boolean[count];for(int i = 0;i < count;i ++){if(!visited[i]){visited[i] = true;list.add(i);dfs(i,count);Collections.sort(list);System.out.println(list);list.clear();}}}
}

在这里插入图片描述

参考实现

这里看了一下GPT，使用了并查集实现，感觉代码比我写的要简洁，而且时间复杂度更低，没研究过并查集，一会去研究一下！

import java.util.*;public class PointsClusters {// 并查集中的查找操作private static int find(int[] parent, int i) {if (parent[i] != i) {parent[i] = find(parent, parent[parent[i]]);}return parent[i];}// 并查集中的合并操作private static void union(int[] parent, int[] rank, int x, int y) {int rootX = find(parent, x);int rootY = find(parent, y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}// 计算点之间的关联集合public static List<List<Integer>> getConnectedComponents(double[][] points, double threshold) {int n = points.length;int[] parent = new int[n];int[] rank = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;rank[i] = 0;}for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {double dist = Math.sqrt(Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2));if (dist <= threshold) {union(parent, rank, i, j);}}}Map<Integer, List<Integer>> components = new HashMap<>();for (int i = 0; i < n; i++) {int root = find(parent, i);components.computeIfAbsent(root, k -> new ArrayList<>()).add(i);}List<List<Integer>> result = new ArrayList<>();for (List<Integer> component : components.values()) {Collections.sort(component);result.add(component);}result.sort(Comparator.comparingInt(a -> a.get(0)));return result;}// 格式化输出public static String formatOutput(List<List<Integer>> components) {StringBuilder sb = new StringBuilder();for (List<Integer> component : components) {for (int i = 0; i < component.size(); i++) {if (i > 0) sb.append(" ");sb.append(component.get(i));}sb.append("\n");}return sb.toString();}public static void main(String[] args) {double x = 5.0;double[][] points = {{0, 0}, {1, 2}, {3, 4}, {8, 8}, {7, 7}};List<List<Integer>> components = getConnectedComponents(points, x);String output = formatOutput(components);System.out.print(output);}
}

并查集这个，就是合并成最小生成树呀，然后返回对应的最小生成树，这样做确实效率会更高一点，但是这个算法感觉要花比较多的时间重新做！
大概看了一下并查集，这里使用路径压缩，确实效果会更好，暂时先跳过，等到了图论的时候，在进行补充！

新作

随机链表的复制

题目链接

在这里插入图片描述

注意

输入的单纯是一个head头节点，返回也仅仅包含对应复制链表的head头节点
防止新的链表的指针指向旧的链表指针。

个人实现

这题如果没有随机指针，会简单很多，就单纯复制对应的链表以及对应的next指针就行。现在需要复制随机链表，如果每一个节点都需要进行遍历一次，这个时间复杂度太高了，这里如何保存对应的，指向它的指针，然后进行反向遍历！

 /*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {if(head == null) return null;// define the dummy node to sotre the resNode dummy = new Node(-1);Node current = dummy;// define the map to store the pos and pointer of the node Node[] idxToPointer = new Node[1001];Map<Node,Integer> map = new HashMap<>();Node temp = head;for(int i = 0;temp != null;temp = temp.next){map.put(temp,i);current.next = new Node(temp.val);idxToPointer[i] = current.next;current = current.next;i ++;}// traverse the origin list to copy random pointertemp = head;for(int i = 0;temp != null;temp = temp.next,i ++){int randomIdx = map.getOrDefault(temp.random,-1);if(randomIdx != -1){idxToPointer[i].random = idxToPointer[randomIdx];//System.out.println(idxToPointer[i].random.val);}}return dummy.next;}
}

在这里插入图片描述
这里忘记加上对应的i的迭代条件，调了半天没有调整出来，还是gpt给我调整出来，这可不行，如果是手撕的话，我这里写错了，就尴尬了！

参考实现

这里使用回溯实现的，将原来的链表和新创建的链表进行绑定，通过回溯遍历对应的链表，如果不存在对应链表就进行创建。
通过一个map来维系
- 如果没有找到，说明当前的节点没有遍历过，然后创建对应的指针。
- 如果找到了，说明当前节点遍历过，直接返回对应连接就行了。

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {Map<Node,Node> map = new HashMap<>();public Node copyRandomList(Node head) {if(head == null) return null;// recursive the list// 下述是没有遍历过对应的节点，然后创建对应的节点if(!map.containsKey(head)){Node newHead = new Node(head.val);map.put(head,newHead);newHead.next = copyRandomList(head.next);newHead.random = copyRandomList(head.random);}// 遍历过对应的节点，这里是直接返回return map.get(head);}
}

在这里插入图片描述

排序链表

在这里插入图片描述

注意

时间复杂度要在nlogn，说明可以使用快排，然后在直接相连对对应的节点就行了。

个人实现

java中collectionss.sort方法实现是通过timesort，时间复杂度就是O(nlogn),然后我其他两个操作的时间复杂度都是O(n)，所以就是最优的时间复杂度！
直接找到每一个节点，然后进行排序就行了。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {if(head == null)    return head;List<ListNode> list = new ArrayList<>();ListNode temp = head;while(temp != null) {list.add(temp);temp = temp.next;}Collections.sort(list,(ListNode a,ListNode b)->Integer.compare(a.val,b.val));for(int i = 0;i < list.size() - 1;i ++){list.get(i).next = list.get(i + 1);}list.get(list.size() - 1).next = null;;return list.get(0);}
}

在这里插入图片描述

不好意思，我没看到还是需要常数级别的时间复杂度，这里没注意到，有问题！

补充

指定sort排序方式的lambda表达式
这段内容是没写出来，是我问了GPT才知道的，不行呀，如果下次笔试或者手撕这样就尴尬了！

 Collections.sort(list,(ListNode a,ListNode b)->Integer.compare(a.val,b.val));

参考实现

这里使用了归并排序的自底向上版本，能够在O(1)的空间复杂度内，实现O(nlogn)的时间复杂度排序，代码有点复杂，要我写肯定写不出来，放弃了！
但是大概的框架是基本上都知道的！

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {int n = 0;for(ListNode temp = head;temp != null;temp = temp.next)  n++;// traverse the listListNode dummy = new ListNode(-1);dummy.next = head;for(int i = 1;i < n;i *= 2){// 这里是每一次都是二分，所以每一次都往后两倍ListNode cur = dummy;for(int j = 0;j + i <= n;j += i*2){// 这里每一次都是排序0 到2*i的序列ListNode p = cur.next,q = p;// 向后遍历i次，到达第i个位置，也就是下一个序列开始的部分for(int k = 0;k < i;k ++) q = q.next;int x = 0;int y = 0;while(x < i && y < i && p!= null && q != null){if(p.val <= q.val)  {cur.next = p;cur = cur.next;p = p.next;x ++;}else{cur.next = q;cur = cur.next;q = q.next;y ++;}}while(x < i && p != null)   {cur.next = p;cur = cur.next;p = p.next;x ++;}while(y < i && q != null){cur.next = q;cur = cur.next;q = q.next;y ++;}cur.next = q;} }return dummy.next;}
}

在这里插入图片描述

二叉树章节

二叉树在拼多多主管面的时候，被狠狠的说了，说我没怎么做过二叉树的题目，然后就挂了，拼多多主管面只能说自己被别人问的一览无余，底裤都不剩了，确实能力不行！
不过无所谓了，继续加油！

二叉树的中序遍历

题目连接

在这里插入图片描述

注意

节点的数量可能为0，所以需要处理为空的情况

个人实现

前序遍历：左中右，然后进行输出

递归实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> list;public void dfs(TreeNode temp){if(temp.left != null) dfs(temp.left);list.add(temp.val);if(temp.right != null) dfs(temp.right);}public List<Integer> inorderTraversal(TreeNode root) {list = new ArrayList<>();if(root == null)    return list;dfs(root);return list;}
}

在这里插入图片描述
迭代实现

迭代实现，就是使用stack模拟函数调用的堆栈进行实现

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stk = new Stack<>();TreeNode current = root;while (current != null || !stk.isEmpty()) {// 走到最左边的节点while (current != null) {stk.push(current);current = current.left;}// 当前节点为空，弹出栈顶节点并访问它current = stk.pop();list.add(current.val);// 准备访问右子树current = current.right;}return list;}
}

这里没有理出来，这种迭代，实现起来，怪怪的，没整好

问题

java中使用什么来模拟栈
push(x)将元素压入栈顶
pop()弹出栈顶元素
peek()查看栈顶元素，但是不移除
isEmpty()查看是否为空
java中队列的操作
add()元素插入队列，队列满就返回异常
offer(）元素插入队列，队列满就返回false
remove（）移除队头元素，如果队列为空，就抛出异常
poll移除并返回队列元素头部，如果队列为空，就返回null
peek返回队列元素，但是不删除

二叉树的最大深度

题目连接

注意
节点的数量可能为空，特殊处理
二叉树

个人实现

树形结构，完全就是回溯的复刻，所以可以直接使用dfs进行实现
- 高度就是迭代限制
- 单次迭代的范围就是两个节点
按照某种顺序遍历一次就行了

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int maxDept = 0;void dfs(TreeNode root,int idx){if(root == null)    {maxDept = Math.max(idx , maxDept);return;}dfs(root.left,idx + 1);dfs(root.right,idx + 1);}public int maxDepth(TreeNode root) {if(root == null) return 0;dfs(root,0);return maxDept;}
}

参考实现

dfs

这个问题可以拆解，拆解成左右两个子树的最大值，然后加一，就是当前的子树的最高的高度了

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;else{int lDept = maxDepth(root.left);int rDept = maxDepth(root.right);return Math.max(lDept,rDept) + 1;}}
}

在这里插入图片描述

真是简洁！！发现这种问题拆解，始终做的不是很流畅，或者说优点奇怪！做不出来，多练习一下！

反转二叉树

题目连接

在这里插入图片描述

注意

队列可能为空，需要特殊处理

个人实现

这里就是交换两个子节点，中间可能需要要给临时的保存一下
这也是一个问题嵌套的情况，如果要交换当前节点的左右子节点，可以交换左右子树的两个节点

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {if(root == null) return null;else{TreeNode temp = invertTree(root.left);root.left = invertTree(root.right);root.right = temp;return root;}}
}