Skip to content

Commit 11c4cf1

Browse files
CoderDreamCoderDream
committed
chatgpt4o版的跳表
带中文注释 > 2024/05/26 21:20:02 解答成功: 执行耗时:15 ms,击败了91.75% 的Java用户 内存消耗:51.8 MB,击败了55.34% 的Java用户 > 2024/05/26 21:32:17 已提交,请稍等 > 2024/05/26 21:32:18 解答成功: 执行耗时:15 ms,击败了91.75% 的Java用户 内存消耗:51.7 MB,击败了64.32% 的Java用户
1 parent 9ac8095 commit 11c4cf1

File tree

4 files changed

+548
-180
lines changed

4 files changed

+548
-180
lines changed

‎hello-algo/lagou-algo/leetcode-question/src/main/java/com/shuzijun/leetcode/editor/cn/Lc1206DesignSkiplist.java

Lines changed: 97 additions & 180 deletions
Original file line numberDiff line numberDiff line change
@@ -71,214 +71,131 @@ public class Lc1206DesignSkiplist {
7171

7272
public static void main(String[] args) {
7373
Skiplist skiplist = new Lc1206DesignSkiplist().new Skiplist();
74+
75+
// Skiplist skiplist = new Skiplist();
76+
skiplist.add(30);
77+
skiplist.add(40);
78+
skiplist.add(50);
79+
skiplist.add(60);
80+
skiplist.add(70);
81+
skiplist.add(90);
82+
83+
System.out.println(skiplist.search(30)); // true
84+
System.out.println(skiplist.search(45)); // false
85+
skiplist.add(45);
86+
System.out.println(skiplist.search(45)); // true
87+
skiplist.erase(45);
88+
System.out.println(skiplist.search(45)); // false
89+
7490
}
7591

7692
//leetcode submit region begin(Prohibit modification and deletion)
77-
class Skiplist {
7893

79-
final int HEAD_VALUE = -1; // 链表头节点的值
80-
final Node HEAD = new Node(HEAD_VALUE);
94+
class Skiplist {
8195

82-
Node head; // 最左上角的头节点，所有操作在开始位置
83-
int levels; // 当前层级，即 head 节点所在的最高层数
84-
int length; // 链表长度
96+
static final int MAX_LEVEL = 16; // 定义跳表的最大层数
97+
private final Node head = new Node(-1, MAX_LEVEL); // 初始化头节点，值为-1，层数为最大层数
98+
private int level = 0; // 当前跳表的层数
99+
private final Random random = new Random(); // 随机数生成器
85100

86-
public Skiplist() {
87-
head = HEAD;
88-
levels = 1;
89-
length = 1;
90-
}
101+
// Node类表示跳表中的节点
102+
class Node {
103+
int value; // 节点的值
104+
Node[] forward; // 前进指针数组，不同层级的前进指针
91105

92-
public Node get(int target) {
93-
return get(target, head);
106+
Node(int value, int level) {
107+
this.value = value; // 初始化节点值
108+
this.forward = new Node[level + 1]; // 初始化前进指针数组
109+
}
94110
}
95111

96-
public Node get(int target, Node from) {
97-
Node n = from;
98-
while (n != null) {
99-
// 1.在同一层级上向右查找，直到链接结尾，或者找到
100-
while (n.right != null && n.right.val < target) {
101-
n = n.right;
102-
}
103-
// 2.若找到，返回true
104-
Node right = n.right; // 要查找的节点
105-
if (right != null && right.val == target) {
106-
return n; // 返回要查找的节点的前一个
107-
}
108-
// 3.若右侧数据较大，向下一层
109-
n = n.down;
112+
// 生成节点的随机层数
113+
private int randomLevel() {
114+
int lvl = 0;
115+
// 当随机数小于0.5且层数小于最大层数时，增加层数
116+
while (random.nextFloat() < 0.5f && lvl < MAX_LEVEL) {
117+
lvl++;
110118
}
111-
return null;
119+
return lvl; // 返回生成的层数
112120
}
113121

114-
/**
115-
* <pre>
116-
* 从 head 开始，从左到右、从上到下依次查找
117-
* 1.小于，往右
118-
* 2.相同，则返回
119-
* 3.链表结尾，或大于，往下
120-
*
121-
* </pre>
122-
*
123-
* @param target
124-
* @return
125-
*/
122+
// 在跳表中查找目标值
126123
public boolean search(int target) {
127-
// Node n = head;
128-
// while (n != null) {
129-
// // 1.在同一层级向右查找，直到链表的结尾
130-
// while (n.right != null && n.right.val < target) {
131-
// n = n.right; // 向右
132-
// }
133-
// // 2.若找到，返回true
134-
// Node right = n.right; // 要查找的节点
135-
// if(right != null && right.val == target) {
136-
// return true;
137-
// }
138-
//
139-
// // 3.若右侧数据较大，向下一层
140-
// n = n.down; // 往下
141-
// }
142-
//
143-
// return false;
144-
Node node = get(target);
145-
return node != null;
124+
Node current = head; // 从头节点开始
125+
// 从最高层逐层向下查找
126+
for (int i = level; i >= 0; i--) {
127+
// 向前移动直到找到大于或等于目标值的节点
128+
while (current.forward[i] != null && current.forward[i].value < target) {
129+
current = current.forward[i];
130+
}
131+
}
132+
current = current.forward[0]; // 移动到最底层
133+
// 检查当前节点的值是否等于目标值
134+
return current != null && current.value == target;
146135
}
147136

148-
/**
149-
* <pre>
150-
* 插入节点，将节点插入原链表中正确的排序位置
151-
* 1.定位插入位置：原链表中 >= num 的最小节点前
152-
* 2.插入新节点
153-
* 3.根据扔硬币决定（是否）生成索引
154-
* </pre>
155-
*
156-
* @param num
157-
*/
137+
// 向跳表中插入一个值
158138
public void add(int num) {
159-
// 1.定位插入位置：原链表中 >= num 的最小节点前
160-
Node node = head;
161-
Node[] nodes = new Node[levels]; // 层级
162-
int i = 0; // 操作上述数组
163-
while (node != null) { // node == null, 到达原链表（第一层）
164-
while (node.right != null && node.right.val < num) {
165-
node = node.right; // 向右走
139+
Node[] update = new Node[MAX_LEVEL + 1]; // 用于存储需要更新的节点
140+
Node current = head; // 从头节点开始
141+
142+
// 从最高层逐层向下查找
143+
for (int i = level; i >= 0; i--) {
144+
// 向前移动直到找到大于或等于插入值的节点
145+
while (current.forward[i] != null && current.forward[i].value < num) {
146+
current = current.forward[i];
166147
}
167-
168-
nodes[i++] = node;
169-
170-
// 到达原链表（第一层）
171-
// if(node.down == null) {
172-
// break;
173-
// }
174-
175-
// 继续查找下一层的位置
176-
node = node.down;
148+
update[i] = current; // 存储需要更新的节点
177149
}
178150

179-
// 2.插入新节点
180-
node = nodes[--i]; // nodes 中最后一个元素
181-
182-
Node newNode = new Node(num, node.right, null);
183-
node.right = newNode;
184-
length++;
185-
186-
// 3.根据扔硬币决定（是否）生成索引
187-
addIndicesByCoinFlip(newNode, nodes, i);
188-
}
189-
190-
/**
191-
* 抛硬币
192-
*
193-
* @param target
194-
* @param nodes
195-
* @param indices 可以创建的层数
196-
*/
197-
private void addIndicesByCoinFlip(Node target, Node[] nodes, int indices) {
198-
Node downNode = target;
199-
// 1.抛硬币，在现有层级范围内建立索引
200-
Random random = new Random();
201-
int coins = random.nextInt(2); // 0 or 1, 50%概率
202-
while (coins == 1 && levels < length >> 6) { // 除以2的2次方
203-
if (indices > 0) {
204-
Node prev = nodes[--indices]; // 数组的倒数第二个元素，level 2，（循环下一次为 level 3）
205-
Node newIndex = new Node(target.val, prev.right, downNode); // newIndex指向当前节点
206-
prev.right = newIndex; //
207-
//indices--;
208-
downNode = newIndex; // 保存新的向下节点
209-
coins = random.nextInt(2); // 0 or 1, 50%概率
210-
} else {
211-
// 2.抛硬币，决定是否建立一层超出跳表层数的索引层
212-
// 新建索引节点和头节点
213-
Node newIndex = new Node(target.val, null, downNode); // 新层级，右边为null，下为上一次的down节点
214-
Node newHead = new Node(HEAD_VALUE, newIndex, head); // 头节点
215-
head = newHead; // head 指针上移
216-
levels++; // 跳表层数加 1
151+
int lvl = randomLevel(); // 生成新节点的随机层数
152+
if (lvl > level) {
153+
// 如果新节点的层数大于当前层数，更新头节点的前进指针
154+
for (int i = level + 1; i <= lvl; i++) {
155+
update[i] = head;
217156
}
157+
level = lvl; // 更新当前层数
218158
}
219-
}
220159

221-
/**
222-
* <pre>
223-
* 遍历跳表，查找与给定值相同的节点，删除每一层
224-
* 1.获取该指定数据节点的前一个节点
225-
* 2.与当前层链表断开
226-
* 3.下移，删除每一层
227-
* </pre>
228-
*
229-
* @param num
230-
* @return
231-
*/
232-
public boolean erase(int num) {
233-
boolean exist = false;
234-
// Node n = head;
235-
// while (n != null) {
236-
// // 1.获取该指定数据节点的前一个节点
237-
// while (n.right != null && n.right.val < num) {
238-
// n = n.right; // 向右
239-
// }
240-
// // 2.与当前层链表断开
241-
// Node right = n.right; // 要删除的节点
242-
// if(right != null && right.val == num) {
243-
// n.right = right.right; // 前一节点 指向待删除节点的后一节点
244-
// right.right = null; // help GC
245-
// exist = true;
246-
// }
247-
//
248-
// // 3.下移，删除每一层
249-
// // 删除下一层
250-
// n = n.down;
251-
// }
252-
Node node = get(num, head);
253-
while (node != null) {
254-
Node right = node.right; // 要删除的节点
255-
node.right = right.right;
256-
right.right = null; // help GC
257-
exist = true;
258-
259-
node = get(num, node.down);
160+
Node newNode = new Node(num, lvl); // 创建新节点
161+
for (int i = 0; i <= lvl; i++) {
162+
newNode.forward[i] = update[i].forward[i]; // 设置新节点的前进指针
163+
update[i].forward[i] = newNode; // 更新前一个节点的前进指针
260164
}
261-
if (exist) {
262-
length--; // 链表长度减 1
263-
}
264-
265-
return exist;
266165
}
267166

268-
class Node {
269-
270-
int val;
271-
Node right, down;
272-
273-
Node(int val) {
274-
this(val, null, null);
167+
// 从跳表中删除一个值
168+
public boolean erase(int num) {
169+
Node[] update = new Node[MAX_LEVEL + 1]; // 用于存储需要更新的节点
170+
Node current = head; // 从头节点开始
171+
172+
// 从最高层逐层向下查找
173+
for (int i = level; i >= 0; i--) {
174+
// 向前移动直到找到大于或等于删除值的节点
175+
while (current.forward[i] != null && current.forward[i].value < num) {
176+
current = current.forward[i];
177+
}
178+
update[i] = current; // 存储需要更新的节点
275179
}
276180

277-
Node(int val, Node right, Node down) {
278-
this.val = val;
279-
this.right = right;
280-
this.down = down;
181+
current = current.forward[0]; // 移动到最底层
182+
// 检查当前节点的值是否等于删除值
183+
if (current != null && current.value == num) {
184+
// 更新前进指针，跳过当前节点
185+
for (int i = 0; i <= level; i++) {
186+
if (update[i].forward[i] != current) {
187+
break;
188+
}
189+
update[i].forward[i] = current.forward[i];
190+
}
191+
192+
// 如果最高层的节点为空，降低当前层数
193+
while (level > 0 && head.forward[level] == null) {
194+
level--;
195+
}
196+
return true; // 返回true表示删除成功
281197
}
198+
return false; // 返回false表示删除失败
282199
}
283200
}
284201

0 commit comments

Comments
 (0)