链表 | 笔记整理!
链表 | 笔记整理!
算法竞赛 | 例题:约瑟夫
算法竞赛例题 | 洛谷 P1996 约瑟夫问题
题目
# P1996 约瑟夫问题
求解
数组 | 标记 模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
| m,n=map(int,input().split())
flag=[0]*(m+1)
idx=0
for i in range(m):
j=0
while j<n:
idx+=1
if idx>m:idx=1
if flag[idx]:j-=1
j+=1
print(idx,end=' ')
flag[idx]=1
|
单链表处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| m,n=map(int,input().split())
class LinkNode():
def __init__(self,val=0,next=None) -> None:
self.val=val
self.next=next
node=cur=None
for i in range(1,m+1):
if i==1:
cur=node=LinkNode(i)
else:
cur.next=LinkNode(i)
cur=cur.next
cur.next=node
head=prev=node
for _ in range(m):
for _ in range(1,n):
prev=head
head=head.next
print(head.val,end=' ')
prev.next=head.next
head=prev.next
|
静态链表处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| m,n=map(int,input().split())
node=[0]*(m+1)
for i in range(1,m):
node[i]=i+1
node[m]=1
prev=head=1
for _ in range(m):
for _ in range(1,n):
prev=head
head=node[head]
print(head,end=' ')
node[prev]=node[head]
head=node[prev]
|
力扣刷题 | 部分经典题目
部分总结归纳
dfs做法 | 笔记整理在另一篇
面试题 04.03. 特定深度节点链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
ans=[]
def dfs(root,level):
if not root:return
cur=ListNode(root.val)
if len(ans)==level:
ans.append(cur)
else:
cur.next=ans[level]
ans[level]=cur
dfs(root.right,level+1)
dfs(root.left,level+1)
dfs(tree,0)
return ans
|
模拟加减运算
链表求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
def cal_ans(l1,l2):
flag=0
head=ans=ListNode()
while l1 or l2:
x=l1.val if l1 else 0
y=l2.val if l2 else 0
s=x+y+flag
flag=s//10
cur=ListNode(s%10)
ans.next=cur
ans=ans.next
if l1:l1=l1.next
if l2:l2=l2.next
if flag:
ans.next=ListNode(1)
return head.next
return cal_ans(l1,l2)
|
环路检测 问题
set集合检测 | 环装归纳
环路检测
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast=slow=head
while fast:
slow=slow.next
if fast.next:
fast=fast.next.next
else:
return None
if fast==slow:
while head!=slow:
head=head.next
slow=slow.next
return head
return None
|
链表 + 前缀和
从链表中删去总和值为零的连续节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur=dummpy=ListNode(0,head)
pre=0
d=dict()
while cur:
pre+=cur.val
d[pre]=cur
cur=cur.next
s=0
cur=dummpy
while cur:
s+=cur.val
cur.next=d[s].next
cur=cur.next
return dummpy.next
|
经典递归调用 | 树+链表
此处过于精彩!
二叉树中的链表
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
def helper(head,root):
if not head:return True
if not root:return False
if head.val!=root.val:
return False
return helper(head.next,root.left) or helper(head.next,root.right)
if not root:return False
return helper(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)
|
小结
这部分还是比较重要的，如果单纯考链表就比较容易了！