当前位置:网站首页>Liste des liens (simple)
Liste des liens (simple)
2022-07-05 13:49:00 【Anna et son carnet】
Un doigt d'épée. Offer 06. Imprimer la liste de liens de bout en bout
Un doigt d'épée. Offer 24. Inverser la liste des liens
Un doigt d'épée. Offer 35. Copie de listes complexes
Un doigt d'épée. Offer 06. Imprimer la liste de liens de bout en bout - Boucle de force(LeetCode)
Définition d'un tableau à chaîne unique:
/*Definition for singly-linked list:*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
Un.:Méthode Stack
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack=new Stack<>();
ListNode cur=head;
while(cur!=null){
stack.push(cur);
cur=cur.next;
}
int[] arr=new int[stack.size()];
for(int i=0;i<arr.length;i++){
arr[i]=stack.pop().val;
}
return arr;
}
}
/** Analyse de la complexité: Complexité temporelle O(N) Complexité spatiale O(N) */
class Solution {
public int[] reversePrint(ListNode head) {
LinkedList<Integer> stack = new LinkedList<Integer>();
while(head != null) {
stack.addLast(head.val);//addLast()La méthode est utilisée dansLinkedList Insérer un élément spécifique à la fin de
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i++)
res[i] = stack.removeLast();//removeLast()Méthode utilisée pourLinkedListSupprimer le dernier élément
return res;
}
}
/** Analyse de la complexité: Complexité temporelle O(N): Utilisé à la fois à l'intérieur et à l'extérieur de la pile O(N)Temps. Complexité spatiale O(N):Pile auxiliairestackEt tableauxresCo - utilisationO(N)Espace supplémentaire pour */
2.:Méthode récursive
Processus algorithmique:
- Phase récursive : Chaque fois que ça arrive head.next ,Par head == null( C'est - à - dire passer par le noeud de queue de la liste )Condition de terminaison récursive,Retour direct.
- Phase de rétrosuivi : En remontant les couches , Ajouter la valeur actuelle du noeud à la liste ,C'est - à - dire:tmp.add(head.val).
Final,Liste tmp Convertir en tableau res ,Et revenir.
Analyse de la complexité
- Complexité temporelle O(N): Traverser la liste des liens,Récursion N Une fois.
- Complexité spatiale O(N):La récursion du système nécessite l'utilisation de O(N) L'espace de pile de.
class Solution {
ArrayList<Integer> tmp = new ArrayList<Integer>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[tmp.size()];
for(int i = 0; i < res.length; i++)
res[i] = tmp.get(i);
return res;
}
void recur(ListNode head) {
if(head == null) return;
recur(head.next);
tmp.add(head.val);
}
}
Trois:
class Solution {
// Temps d'exécution : 0 ms, Dans tous les Java Battu dans la soumission 100.00% Utilisateurs de
// Consommation de mémoire : 39.8 MB, Dans tous les Java Battu dans la soumission 100.00% Utilisateurs de
// N'utilisez pas la pile,Pas de récursion, Deux scans de toute façon , Pourquoi allouer plus d'espace ?
public static int[] reversePrint(ListNode head) {
ListNode node = head;
int count = 0;
while (node != null) {
++count;
node = node.next;
}
int[] nums = new int[count];
node = head;
for (int i = count - 1; i >= 0; --i) {
nums[i] = node.val;
node = node.next;
}
return nums;
}
}
Un doigt d'épée. Offer 24. Inverser la liste des liens - Boucle de force(LeetCode)
Un.:Itération
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode pre=null;
ListNode cur=head;
ListNode tmp=null;
while(cur!=null){
tmp=cur.next;// Mettre en scène les noeuds suivants cur.next
cur.next=pre;// Modifier next Les références pointent vers
pre=cur;// pre Provisoire cur
cur=tmp;// cur Accéder au noeud suivant
}
return pre;
}
}
2.:Récursion
class Solution {
public ListNode reverseList(ListNode head) {
return recur(head, null); // Appelle récursive et renvoie
}
private ListNode recur(ListNode cur, ListNode pre) {
if (cur == null){
return pre; // Conditions de résiliation
}
ListNode res = recur(cur.next, cur); // Noeud successeur récursif
cur.next = pre; // Modifier la référence du noeud pour pointer vers
return res; // Renvoie le noeud d'en - tête de la liste inversée
}
}
Un doigt d'épée. Offer 35. Copie de listes complexes - Boucle de force(LeetCode)
Un.:Table de hachage
/* // 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) {
Map<Node, Node> m = new HashMap<>();
Node p = head;
while(head != null) {
Node t = new Node(head.val);
m.put(head, t);
head = head.next;
}
head = p;
// Selon la liste originale , Trouver une table de hachage pour relier une nouvelle liste liée
while(head != null) {
Node n = head.next; // Le noeud suivant du noeud original
Node r = head.random;// Noeud d'origine noeud aléatoire
//Nouveau noeudnext Pointez vers le nouveau noeud suivant
m.get(head).next = m.get(n);
//Définir le nouveau noeudrandomLes noeuds pointent vers
m.get(head).random = m.get(r);
head = head.next;
}
return m.get(p);
}
}
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
Map<Node, Node> map = new HashMap<>();
//Copier les noeuds,Et de créer “Noeud original -> Nouveau noeud” De Map Cartographie
while(cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
//Pour construire une nouvelle liste de liens next Et random Pointage
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
//Renvoie le noeud d'en - tête de la nouvelle liste liée
return map.get(head);
}
}
边栏推荐
- redis6事务和锁机制
- Interviewer soul torture: why does the code specification require SQL statements not to have too many joins?
- 通讯录(链表实现)
- [public class preview]: basis and practice of video quality evaluation
- Datapipeline was selected into the 2022 digital intelligence atlas and database development report of China Academy of communications and communications
- Solution to the prompt of could not close zip file during phpword use
- 锚点导航小demo
- Aikesheng sqle audit tool successfully completed the evaluation of "SQL quality management platform grading ability" of the Academy of communications and communications
- Can graduate students not learn English? As long as the score of postgraduate entrance examination English or CET-6 is high!
- Kotlin collaboration uses coroutinecontext to implement the retry logic after a network request fails
猜你喜欢
:: ffff:192.168.31.101 what address is it?
redis6事务和锁机制
About the problem and solution of 403 error in wampserver
Data Lake (VII): Iceberg concept and review what is a data Lake
MMSeg——Mutli-view时序数据检查与可视化
What happened to the communication industry in the first half of this year?
运筹说 第68期|2022年最新影响因子正式发布 快看管科领域期刊的变化
嵌入式软件架构设计-消息交互
Binder communication process and servicemanager creation process
Ordering system based on wechat applet
随机推荐
Multi person cooperation project to see how many lines of code each person has written
记录一下在深度学习-一些bug处理
web3.eth. Filter related
Kafaka log collection
The development of speech recognition app with uni app is simple and fast.
链表(简单)
How to divide a large 'tar' archive file into multiple files of a specific size
2022司钻(钻井)考试题库及模拟考试
几款分布式数据库的对比
多人合作项目查看每个人写了多少行代码
南理工在线交流群
Laravel框架运行报错:No application encryption key has been specified
Solve the problem of invalid uni app configuration page and tabbar
uplad_ Labs first three levels
How to apply the updated fluent 3.0 to applet development
With 4 years of working experience, you can't tell five ways of communication between multithreads. Dare you believe it?
French scholars: the explicability of counter attack under optimal transmission theory
aspx 简单的用户登录
::ffff:192.168.31.101 是一个什么地址?
Etcd database source code analysis -- rawnode simple package