汇总中国近百年发生的事件,以时间线形式展示
南京大学ICS2023 PA1记录
本博文记录完成南京大学的ICS2023的PA1过程,包括解决的问题、遇到的坑等,仅供参考
Hexo搭建个人Blog
想在Github上搭建一个简易的个人Blog,Hexo是一个不错的选择。Hexo是一个快速、简洁的博客框架,使用Markdown解析文章,在几秒内就可以生成静态网页,然后就可以部署在Github上生成个人网站。
LeetCode 142 - Linked List Cycle II
问题描述
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
To represent a cycle in the given linked list, we use an integer pos
which represents the position (0-indexed) in the linked list where tail connects to. If pos
is -1
, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
1 | Input: head = [3,2,0,-4], pos = 1 |
![](/2020/05/18/LeetCode-142-Linked-List-Cycle-II/1.png)
Example 2:
1 | Input: head = [1,2], pos = 0 |
![](/2020/05/18/LeetCode-142-Linked-List-Cycle-II/2.png)
Example 3:
1 | Input: head = [1], pos = -1 |
![](/2020/05/18/LeetCode-142-Linked-List-Cycle-II/3.png)
Follow-up:
Can you solve it without using extra space?
Related Topics: Linked List
, Two Pointers
原问题: 142. Linked List Cycle II
中文翻译版: 142. 环形链表 II
解决方案
解决方案1
用一个 Set
保存已访问的节点,此时可以遍历整个链表并返回第一个出现重复的节点。时间复杂度为 O(n)
,空间复杂度为 O(n)
参考解题代码
1 | /** |
解决方案2
方案2是 LeetCode 141 解题思路的进一步改进,算法分为两个阶段:
- 阶段1 : 首先使用快指针
fast
和慢指针slow
遍历链表,如果链表有环,两指针最终会相遇到某个节点 - 阶段2 : 初始化额外的两个指针,
ptr1
指向链表的头节点,ptr2
指向相遇节点。然后,我们每次将它们往前移动一步,直到它们相遇,它们相遇的点就是环的入口,返回这个节点
关于阶段2的实现原理,这里提供一个不错的解答说明:LeetCode: 环形链表 II 官方解答
参考解题代码
1 | /** |
LeetCode 155 - Min Stack
问题描述
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- getMin() – Retrieve the minimum element in the stack.
Example 1:
1 | Input |
Constraints:
- Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks.
Related Topics: Stack
, Design
原问题: 155. Min Stack
中文翻译版: 155. 最小栈
解决方案
可以使用两个栈解决该题,一个栈stack存储push进来的数据,另一个栈min_stack存储现有数据的最小值,两个栈存储同等数量的元素。关键的操作 push
实现如下:
push
: push的数据为x,如果x小于min_stack栈顶的值,说明x比现用元素值都要小,则将x压入min_stack,否则将min_stack栈顶的值压入min_stack
参考解题代码
1 | class MinStack { |
LeetCode 206 - Reverse Linked List
1. 问题描述
Reverse a singly linked list.
Example:
1 | Input: 1->2->3->4->5->NULL |
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Related Topics: Linked List
中文翻译版: 206. 反转链表
2. 解决方案
2.1 非递归
非递归的解决方案是按原始顺序迭代节点,并将它们逐个移动到链表的头部。以下举个例子进行说明
![](/2020/05/16/LeetCode-206-Reverse-Linked-List/no_recur_1.png)
黑色节点23是原始头节点。
首先,我们将黑色节点的下一个节点(即节点6)移动到链表的头部:
然后,我们将黑色节点的下一个节点(即节点15)移动到链表的头部:
黑色结点的下一个结点现在是空。因此,我们停止这一过程并返回新的头结点15
从以上流程可以知道该算法的时间复杂度为 O(N)
,空间复杂度为 O(1)
参考解题代码
1 | /** |
2.2 递归
用递归解此题时,此时递归的函数返回的是反转链表后的新的头节点 new_head
,进行整合时,只需要将头节点 head
添加到反转链表的尾部即可。拿前面例子来说,头节点23后部分都已经反转完毕,此时链表构造为
1 | 23 -> 6 <- 15 |
此时 new_head
指向节点15,head
指向节点23,要将节点23添加到反转链表尾部,执行以下操作即可:
1 | head->next->next = head |
经过以上操作以后,链表构造变为
1 | NULL <- 23 <- 6 <- 15 |
最后返回新的头节点 new_head
即可
参考解题代码
1 | /** |
LeetCode 328 - Odd Even Linked List
问题描述
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example 1:
1 | Input: 1->2->3->4->5->NULL |
Example 2:
1 | Input: 2->1->3->5->6->4->7->NULL |
Note:
- The relative order inside both the even and odd groups should remain as it was in the input.
- The first node is considered odd, the second node even and so on …
Related Topics: Linked List
原问题: 328. Odd Even Linked List
中文翻译版: 328. 奇偶链表
解决方案
解此题主要需要两个指针 odd
以及 even
,odd
指向奇节点,even
指向偶节点。odd
从第一个节点开始遍历,even
从第二节点开始遍历,两个指针每次移动都是移动两个节点,每次移动前,先将 next 字段指向下下个节点,即
1 | odd = odd->next->next; |
这样当两个指针遍历完链表时,链表刚好被分为两部分,odd
指向奇节点链表最后一个节点,此时将这两个链表拼在一起即可。偶节点链表头部是头节点的下一个节点,由于在指针遍历时,会破坏链表结构,因此在遍历前先保存该节点 node
,链表拼接时只需
1 | odd->next = node |
参考解题代码
1 | class Solution { |
LeetCode 203 - Remove Linked List Elements
问题描述
Remove all elements from a linked list of integers that have value val
.
Example:
1 | Input: 1->2->6->3->4->5->6, val = 6 |
Related Topics: Linked List
原问题: 203. Remove Linked List Elements
中文翻译版: 203. 移除链表元素
解决方案
链表删除基本操作的实现,使用三个指针 prev
、curr
以及 next
,prev
指向 curr
前一个节点,curr
指向要删除的节点,next
指向 curr
下一个节点。curr
从头节点开始遍历,按照链表删除元素操作依次删除值为 val
的节点即可
1 | next = curr->next; |
这里要注意的是头节点,如果头节点的值刚好 val
,这个删除操作和上面的代码片段有少许区别
参考解题代码
1 | class Solution { |
LeetCode 367 - Valid Perfect Square
问题描述
Given a positive integer num
, write a function which returns True if num
is a perfect square else False.
Note: Do not use any built-in library function such as sqrt
.
Example 1:
1 | Input: 16 |
Example 2:
1 | Input: 14 |
Related Topics: Math
, Binary Search
原问题: 367. Valid Perfect Square
中文翻译版: 367. 有效的完全平方数
解决方案
本题换种说法就是:求正整数 num
的平方根 x
,且 x
的平方等于 num
,如何求正整数的平方根,可以用二分查找进行求解,这个可以参考LeetCode原题 69. Sqrt(x)(解题报告:LeetCode 69 - Sqrt(x)),二分查找后得到的平方根 x
,只需判断 x
的平方是否等于 num
即可判断 num
是否为完全平方数
参考解题代码
1 | #include <iostream> |
LeetCode 19 - Remove Nth Node From End of List
问题描述
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
1 | Given linked list: 1->2->3->4->5, and n = 2. |
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
Related Topics: Linked List
, Two Pointers
原问题: 19. Remove Nth Node From End of List
中文翻译版: 19. 删除链表的倒数第N个节点
解决方案
这道题可以使用双指针方法解决,设定两个指针 p1
和 p2
,先让指针 p1
遍历 n
个节点,然后指针 p2
开始和指针 p1
同步遍历链表,当指针 p1
遍历完链表后,指针 p2
刚好指向倒数第 n
个节点,此时删除该节点即可。
参考解题代码
1 | class Solution { |