# Week2：链表和抽象数据类型

AI悦创原创大约 37 分钟...约 11095 字

• 链表2
• 抽象数据结构
• 栈结构

# -*- coding: utf-8 -*-
# @Time    : 2023/12/7 17:04
# @Author  : AI悦创
# @Software: PyCharm
# @Blog    ：https://bornforthis.cn/
# Created by Bornforthis.
class IntNode(object):
def __init__(self, item, next):
self.item = item
self.next = next

class SLList(object):
def __init__(self, x):
self.__first = IntNode(x, None)
self.__length = 1

self.__first = IntNode(x, self.__first)
self.__length += 1

def get_first(self):
return self.__first.item

p = self.__first
while p.next is not None:
p = p.next
p.next = IntNode(x, None)
self.__length += 1

def __size(self, p):
"""
循环获取链表长度
"""
if p.next is None:
return 1
else:
return 1 + self.__size(p.next)

def size(self):
return self.__length

if __name__ == '__main__':
l = SLList(15)
print(l.get_first())
print(l.size())


## 1. 尾部添加数据优化

Sample Code
# -*- coding: utf-8 -*-
# @Time    : 2023/12/7 17:19
# @Author  : AI悦创
# @Software: PyCharm
# @Blog    ：https://bornforthis.cn/
# Created by Bornforthis.
#---snip---
class SLList(object):
def __init__(self, x):
self.__first = IntNode(x, None)
self.__length = 1
self.__last = self.__first  # 新增属性，指向链表的最后一个节点

#---snip---

new_node = IntNode(x, None)
self.__last.next = new_node  # 在链表末尾添加新节点
self.__last = new_node  # 更新__last引用
self.__length += 1

#---snip---


## 2. 创建一个空链表

### 2.1 缘由

lst = []
lst.append(5)
lst.append(10)
lst.append(15)
lst.append(20)


### 2.2 设置默认值

Sample Code
class SLList(object):
def __init__(self, x=None):
if x is None:
self.__first = None
self.__length = 0
else:
self.__first = IntNode(x, None)
self.__length = 1


### 2.3 测试

if __name__ == '__main__':
l = SLList()
print(l.get_first())
print(l.size())


if __name__ == '__main__':
l = SLList()
print(l.get_first())
print(l.size())

Traceback (most recent call last):
File "/Users/huangjiabao/GitHub/iMac/Pycharm/StudentCoder/数据结构/Week1/Linked6.py", line 52, in <module>
while p.next is not None:
AttributeError: 'NoneType' object has no attribute 'next'


### 2.4 改进

def add_last(self, x):
p = self.__first
while p.next is not None:
p = p.next
p.next = IntNode(x, None)
self.__length += 1


#### 2.4.1 一种解决方案

def add_last(self, x):
p = self.__first
if p is None:
self.__first = IntNode(x, None)
self.__length += 1
return
while p.next is not None:
p = p.next
p.next = IntNode(x, None)
self.__length += 1


#### 2.4.2 更优雅的方法

——加一个哨兵在最前面

class SLList(object):
def __init__(self, x=None):
self.__sentinel = IntNode(49, None)
if x is None:
# self.__first = None
self.__length = 0
else:
# self.__first = IntNode(x, None)
self.__sentinel.next = IntNode(x, None)
self.__length = 1

original_first = self.__sentinel.next
new_first = IntNode(x, original_first)
self.__sentinel.next = new_first
self.__length += 1

def get_first(self):
# return self.__first.item
return self.__sentinel.next.item


def add_last(self, x):
p = self.__sentinel
# if p is None:
#     self.__first = IntNode(x, None)
#     self.__length += 1
#     return

while p.next is not None:
p = p.next
p.next = IntNode(x, None)
self.__length += 1


## 3. SLList 的一点问题

### 3.1 发现问题

——使用一个变量实时跟踪就可以。

——你可以想想数据量大的时候，比如 20万个链表数据的时候，岂不是至少要遍历 20万次。我们现在所做的，要预料到遥远的未来。

SampleCode
# ---snip---
class SLList(object):
def __init__(self, x=None):
self.__sentinel = IntNode(49, None)
self.__end = self.__sentinel  # 尾部指针初始化为哨兵节点
if x is not None:
# self.__end.next = IntNode(x, None)
self.__sentinel.next = IntNode(x, None)  # 和上面等价
self.__end = self.__end.next
# self.__end = self.__sentinel.next  # 和上面等价
self.__length = 1
else:
self.__length = 0

original_first = self.__sentinel.next
new_first = IntNode(x, original_first)
self.__sentinel.next = new_first
if self.__end == self.__sentinel:  # 如果链表为空，则更新尾部指针
self.__end = new_first
self.__length += 1

def get_first(self):
if self.__sentinel.next is not None:
return self.__sentinel.next.item
return None

new_end = IntNode(x, None)
self.__end.next = new_end
self.__end = new_end
self.__length += 1

def size(self):
return self.__length

# ---snip---


### 3.2 另一问题

• add_last()
• get_last()
• remove_last()

why？因为移除最后一个后，我们还得找到最新的最后一个，也就是我们删除的上一个。

## 4. 双向链表

### 4.1 初探双向链表实现

# -*- coding: utf-8 -*-
# @Time    : 2023/12/20 21:29
# @Author  : AI悦创
# @FileName: demo2.py
# @Software: PyCharm
# @Blog    ：https://bornforthis.cn/
# Created by Bornforthis.
class IntNode(object):
def __init__(self, item, next=None, prev=None):
self.item = item
self.next = next
self.prev = prev

class DLList(object):
def __init__(self, x=None):
self.__sentinel = IntNode(49)
self.__end = self.__sentinel  # 尾部指针初始化为哨兵节点
if x is not None:
self.__sentinel.next = IntNode(item=x, next=None, prev=self.__sentinel)
self.__end = self.__sentinel.next
self.__length = 1
else:
self.__length = 0

original_first = self.__sentinel.next
new_first = IntNode(item=x, next=original_first, prev=self.__sentinel)
self.__sentinel.next = new_first
if original_first is not None:  # 如果原本的不是空节点，则需要把原本的第一节车厢的 prev 指向新添加的
original_first.prev = new_first
else:  # 如果原来链表是空的
self.__end = new_first
self.__length += 1

def get_first(self):
if self.__sentinel.next is not None:
return self.__sentinel.next.item
return None

new_end = IntNode(x, None, self.__end)
self.__end.next = new_end
self.__end = new_end
self.__length += 1

def size(self):
return self.__length

if __name__ == '__main__':
l = DLList(15)
print(l.get_first())  # 应该输出5
print(l.size())  # 应该输出4


    def get_end(self):
return self.__end.item


### 4.2 目前所存在的问题

——怎么办呢？也就是 last 出现这种特例的情况。

1. 链表为空时，last「self.__end」 指向哨兵节点：当链表中没有任何数据节点时（即链表为空），尾部指针 __end 指向哨兵节点。哨兵节点不包含有效的数据，它的存在主要是为了在链表为空时提供一个稳定的指向，从而避免额外的空值检查。在我们上面的实现中，这是通过初始化 self.__end = self.__sentinel 实现的。

2. 链表不为空时，last「self.__end」 指向最后一个真实的数据节点：一旦链表中添加了数据节点，尾部指针 __end 应该更新为指向链表中最后一个实际的数据节点。这意味着 __end 总是指向链表的最后一个元素，而不是哨兵节点。

3. 可能的特殊情况和调整：由于 __end 的行为根据链表是否为空而变化，所以在进行某些操作时可能需要特别注意这一点。

例如，在添加或删除元素时，特别是在链表的头部或尾部进行操作时，可能需要特殊处理以确保 __end 正确地指向最后一个数据节点或回到哨兵节点（如果链表变为空）。这就是为什么在 add_first 方法中有对链表是否为空的检查，以及为什么在 add_last 方法中始终更新 __end

1. 添加元素到空链表：当链表为空时，添加元素需要特别处理，因为既需要更新哨兵节点的 next 指针，也需要确保 __end 指针指向新添加的元素。
2. 从链表中删除唯一的元素：如果链表中只有一个元素，删除这个元素后，链表将变为空。在这种情况下，需要重置 __end 指针回到哨兵节点。
3. 在链表头部添加元素：在双向链表的头部添加元素需要更新新节点的 nextprev 指针，以及原来第一个节点的 prev 指针。
demo
class DLList(object):
# ...（其余代码与之前相同）

original_first = self.__sentinel.next
new_first = IntNode(x, original_first, self.__sentinel)
self.__sentinel.next = new_first

if original_first is not None:
original_first.prev = new_first
else:  # 如果原来链表是空的
self.__end = new_first

self.__length += 1

def remove_first(self):
if self.__sentinel.next is not None:
removed_item = self.__sentinel.next.item  # 存储移除的值
self.__sentinel.next = self.__sentinel.next.next

if self.__sentinel.next is not None:
self.__sentinel.next.prev = self.__sentinel
else:
self.__end = self.__sentinel  # 链表变为空时，重置 __end

self.__length -= 1
return removed_item
return None

# 示例代码
l = DLList()
print("After adding to empty list:", l.size())

l.remove_first()  # 删除唯一的元素，使链表变为空
print("After removing the only element:", l.size())


1. 初始链表大小（应为 0）: 0
2. 添加元素后的首个元素（应为 20）: 20
3. 添加元素后的末尾元素（应为 30）: 30
4. 添加元素后的链表大小（应为 3）: 3
5. 删除首个元素后被移除的元素（应为 20）: 20
6. 删除首个元素后的新首个元素（应为 10）: 10
7. 删除元素后的链表大小（应为 2）: 2
8. 移除所有元素后的链表大小（应为 0）: 0
9. 在链表为空时尝试获取末尾元素（应为 None）: None

——头尾哨兵合成一个，形成环转链表。

### 4.3 尾部添加哨兵节点「把 self.__end 改变成哨兵节点」

class IntNode(object):
def __init__(self, item, next=None, prev=None):
self.item = item
self.next = next
self.prev = prev

class DLList(object):
def __init__(self, x=None):
self.__sentinel_front = IntNode(None)  # 头部哨兵
self.__sentinel_end = IntNode(None)  # 尾部哨兵
self.__sentinel_front.next = self.__sentinel_end  # 初始化时哨兵节点相连
self.__sentinel_end.prev = self.__sentinel_front
self.__length = 0

if x is not None:

new_first = IntNode(item=x, next=self.__sentinel_front.next, prev=self.__sentinel_front)
self.__sentinel_front.next.prev = new_first
self.__sentinel_front.next = new_first
self.__length += 1

def get_first(self):
if self.__sentinel_front.next != self.__sentinel_end:
return self.__sentinel_front.next.item
return None

new_end = IntNode(item=x, next=self.__sentinel_end, prev=self.__sentinel_end.prev)
# new_end = IntNode(item=x, next=self.__sentinel_end, prev=self.__sentinel_front)  # 目前和上面等价，但是推荐上面的写法。这个写法在链表不为空的时候，会出现节点错误
self.__sentinel_end.prev.next = new_end
# self.__sentinel_front.next = new_end  # 目前和上面等价，但是推荐上面的写法。这个写法在链表不为空的时候，会出现节点错误
self.__sentinel_end.prev = new_end
self.__length += 1
# 更好理解的方法
# original_node = self.__sentinel_end.prev
# new_end = IntNode(item=x, next=self.__sentinel_end, prev=original_node)
# original_node.next = new_end
# self.__sentinel_end.prev = new_end

def size(self):
return self.__length

if __name__ == '__main__':
l = DLList(15)
print(l.get_first())  # 应该输出5
print(l.size())  # 应该输出4


### 4.4 实现 remove_last()

1. 检查链表是否为空。如果链表为空（即头部哨兵的 next 指向尾部哨兵），则没有元素可以移除。
2. 找到最后一个元素，这是尾部哨兵的 prev 指向的元素。
3. 调整最后一个元素前一个元素的 next 指针，使其指向尾部哨兵。
4. 调整尾部哨兵的 prev 指针，使其指向新的最后一个元素（即原最后一个元素的前一个元素）。
5. 减少链表的长度计数。

class DLList(object):
# ... [之前的代码保持不变]

def remove_last(self):
if self.__sentinel_front.next == self.__sentinel_end:  # 检查链表是否为空
return None

last_item = self.__sentinel_end.prev.item  # 获取最后一个元素的值
self.__sentinel_end.prev = self.__sentinel_end.prev.prev  # 更新尾部哨兵的 prev 指针
self.__sentinel_end.prev.next = self.__sentinel_end  # 更新新的最后一个元素的 next 指针
self.__length -= 1  # 减少长度计数
return last_item  # 返回被删除的元素的值

def remove_last2(self):
if self.__sentinel_front.next == self.__sentinel_end:  # 检查链表是否为空
return None

last_node = self.__sentinel_end.prev  # 获取最后一个节点
if last_node.prev == self.__sentinel_front:  # 如果链表只有一个元素
self.__sentinel_front.next = self.__sentinel_end  # 更新头部哨兵的 next 指针
else:
last_node.prev.next = self.__sentinel_end  # 更新倒数第二个节点的 next 指针hhhh

self.__sentinel_end.prev = last_node.prev  # 更新尾部哨兵的 prev 指针
self.__length -= 1  # 减少长度计数
return last_node.item  # 返回被删除的元素的值

# 测试代码
if __name__ == '__main__':
l = DLList(15)
print(l.remove_last())  # 应该输出20
print(l.size())  # 应该输出3


### 4.5 remove_at(index) 移除特定位置数据

1. 检查索引是否有效（即是否在链表的长度范围内）。
2. 遍历链表，找到指定索引位置的节点。
3. 调整该节点前后节点的 nextprev 指针，以从链表中移除该节点。
4. 减少链表的长度计数。
5. 返回被删除节点的值。

class DLList(object):
# ... [之前的代码保持不变]

def remove_at(self, index):
if index < 0 or index >= self.__length:
raise IndexError("Index out of bounds")

current = self.__sentinel_front.next
for i in range(index):
current = current.next

current.prev.next = current.next
current.next.prev = current.prev
self.__length -= 1

return current.item

# 测试代码
if __name__ == '__main__':
l = DLList(15)
print(l.remove_at(1))  # 应该输出10（移除第二个元素）
print(l.size())  # 应该输出3


### 4.7 形成一个环状链表

• 形成一个回环
• 哨兵节点的下一个元素是第一个「号」元素
• 哨兵节点的前一个元素是最后一号元素
1
DLList
# -*- coding: utf-8 -*-
# @Time    : 2024/1/1 13:35
# @Author  : AI悦创
# @FileName: DLList.py
# @Software: PyCharm
# @Blog    ：https://bornforthis.cn/
# Created by Bornforthis.
class IntNode(49, None, None):
def __init__(self, item, next=None, prev=None):
self.item = item
self.next = next
self.prev = prev

class DLList(object):
def __init__(self, x=None):
self.__sentinel = IntNode(49, None, None)
self.__sentinel.next = self.__sentinel
self.__sentinel.prev = self.__sentinel
self.__last = self.__sentinel.prev
if x is None:
self.__length = 0
else:
self.__sentinel.next = IntNode(item=x, next=self.__sentinel, prev=self.__sentinel)
self.__sentinel.prev = self.__sentinel.next
self.__length = 1

1
Code1
# -*- coding: utf-8 -*-
# @Time    : 2024/1/1 13:35
# @Author  : AI悦创
# @FileName: DLList.py
# @Software: PyCharm
# @Blog    ：https://bornforthis.cn/
# Created by Bornforthis.
class IntNode(49, None, None):
def __init__(self, item, next=None, prev=None):
self.item = item
self.next = next
self.prev = prev

class DLList(object):
def __init__(self, x=None):
self.__sentinel = IntNode(49, None, None)
self.__sentinel.next = self.__sentinel
self.__sentinel.prev = self.__sentinel
self.__last = self.__sentinel.prev
if x is None:
self.__length = 0
else:
self.__sentinel.next = IntNode(item=x, next=self.__sentinel, prev=self.__sentinel)
self.__sentinel.prev = self.__sentinel.next
self.__length = 1

# self.__sentinel.next = IntNode(item=item, next=self.__sentinel.next, prev=self.__sentinel)
# self.__sentinel.next.next.prev = self.__sentinel.next

original_first = self.__sentinel.next
news_first = IntNode(item, next=None, prev=None)
news_first.next = original_first
news_first.prev = self.__sentinel
self.__sentinel.next = news_first
original_first.prev = news_first

self.__length += 1

"""在链表的尾部添加数据"""
pass

def remove_at(self, index):
"""移除特定位置的节点"""
pass

def get_value(self, index):
"""获取链表特定位置节点的值"""
pass


## 5. 抽象数据类型「Abstract Data Types & ADT」

img 0

• add_first()
• add_last()
• is_empty()
• size()
• print_deque()
• remove_first()
• remove_last()
• get(index)

## 6. 栈结构「Stack」

• push(x): 将 x 放在栈的顶端
• pop(): 将栈最上面的元素拿走并取出来得到它的值

### 6.1 用 Python 的列表来实现一个栈结构

class Stack(object):
def __init__(self):
self.__data = []

def push(self, x):
self.__data.append(x)

def pop(self):
return self.__data.pop()

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())


4
3
2
1


### 6.2 使上面的 Stack 更全面

Python 中的栈（Stack）可以用多种方式实现。最简单和最常见的方法是使用列表（List）作为栈的底层结构。栈是一种后进先出（Last In, First Out，LIFO）的数据结构，这意味着最后添加进栈的元素会最先被移除。

1. 初始化栈：创建一个空列表来表示栈。
2. 压栈（Push）操作：使用列表的 append() 方法在栈的顶部添加元素。
3. 弹栈（Pop）操作：使用列表的 pop() 方法移除并返回栈顶元素。
4. 查看栈顶元素：可以使用索引 [-1] 来访问栈顶元素，而不移除它。
5. 检查栈是否为空：可以通过检查列表的长度来确定栈是否为空。
6. 获取栈的大小：使用 len() 方法来获取栈中元素的数量。

1. 初始化一个空栈。
2. 通过 push 方法添加了三个元素（"apple", "banana", "cherry"）到栈中。
3. 使用 peek 方法查看了栈顶元素，此时为 "cherry"。
4. 使用 size 方法获取了栈的大小，此时为 3。
5. 使用 is_empty 方法检查了栈是否为空，返回值为 False，表示栈中有元素。

class Stack:
def __init__(self):
self.items = []

def is_empty(self):
return len(self.items) == 0

def push(self, item):
self.items.append(item)

def pop(self):
if not self.is_empty():
return self.items.pop()
return None

def peek(self):
if not self.is_empty():
return self.items[-1]
return None

def size(self):
return len(self.items)

# 示例：创建一个栈并进行一些操作
stack = Stack()
stack.push("apple")
stack.push("banana")
stack.push("cherry")

# 查看栈的状态
(stack.peek(), stack.size(), stack.is_empty())


### 6.3 用链表实现 Stack

# -*- coding: utf-8 -*-
# @Time    : 2024/1/1 13:35
# @Author  : AI悦创
# @FileName: DLList.py
# @Software: PyCharm
# @Blog    ：https://bornforthis.cn/
# Created by Bornforthis.
class IntNode(49, None, None):
def __init__(self, item, next=None, prev=None):
self.item = item
self.next = next
self.prev = prev

class DLList(object):
def __init__(self, x=None):
self.__sentinel = IntNode(49, None, None)
self.__sentinel.next = self.__sentinel
self.__sentinel.prev = self.__sentinel
self.__last = self.__sentinel.prev
if x is None:
self.__length = 0
else:
self.__sentinel.next = IntNode(item=x, next=self.__sentinel, prev=self.__sentinel)
self.__sentinel.prev = self.__sentinel.next
self.__length = 1

# self.__sentinel.next = IntNode(item=item, next=self.__sentinel.next, prev=self.__sentinel)
# self.__sentinel.next.next.prev = self.__sentinel.next

original_first = self.__sentinel.next
news_first = IntNode(item, next=None, prev=None)
news_first.next = original_first
news_first.prev = self.__sentinel
self.__sentinel.next = news_first
original_first.prev = news_first

self.__length += 1

"""在链表的尾部添加数据"""
new_last = IntNode(item, next=self.__sentinel, prev=self.__last)
self.__last.next = new_last
self.__last = new_last
self.__sentinel.prev = new_last
self.__length += 1

def remove_at(self, index):
"""移除特定位置的节点"""
if index >= self.__length:
raise IndexError("Index out of bounds")
current = self.__sentinel.next
for _ in range(index):
current = current.next
current.prev.next = current.next
current.next.prev = current.prev
self.__length -= 1

def get_value(self, index):
"""获取链表特定位置节点的值"""
if index >= self.__length:
raise IndexError("Index out of bounds")
current = self.__sentinel.next
for _ in range(index):
current = current.next
return current.item


### 6.4 有效的括号

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

1. 输入: "()"，输出: True
2. 输入: "()[]{}"，输出: True
3. 输入: "(]"，输出: False
4. 输入: "([)]"，输出: False
5. 输入: "{[]}"，输出: True

• 如果是开放括号（(, {, [），则将其推入栈中。
• 如果是闭合括号（), }, ]），则检查栈是否为空，以及栈顶元素是否与当前闭合括号匹配。如果匹配，则从栈中弹出栈顶元素；否则，字符串无效。
• 完成遍历后，如果栈为空，则字符串有效；否则，无效。
def is_valid_parentheses(s):
# 使用字典来存储括号的配对关系
brackets = {')': '(', '}': '{', ']': '['}
stack = []

for char in s:
if char in brackets:
top_element = stack.pop() if stack else '#'
if brackets[char] != top_element:
return False
else:
stack.append(char)

return not stack

# 测试提供的示例
test_cases = ["()", "()[]{}", "(]", "([)]", "{[]}"]
test_results = [is_valid_parentheses(s) for s in test_cases]
test_results


1. 输入: "()"，输出: True
2. 输入: "()[]{}"，输出: True
3. 输入: "(]"，输出: False
4. 输入: "([)]"，输出: False
5. 输入: "{[]}"，输出: True

• 遍历给定的字符串，对每个字符进行检查。
• 如果字符是闭合括号，检查它是否与栈顶的开放括号匹配。如果匹配，从栈中弹出该括号；如果不匹配或栈为空，返回 False
• 如果字符是开放括号，将其压入栈中。
• 遍历完成后，如果栈为空，则所有括号都已正确匹配，返回 True；如果栈非空，表示有未匹配的括号，返回 False

### 6.2 使用 Python 的列表来实现一个集合结构

class Set(object):
def __init__(self, data=[]):
self.__data = []
for item in data:
if item not in self.__data:
self.__data.append(item)

if x not in self.__data:
self.__data.append(x)

def get_all(self):
return self.__data

our_set = Set([1, 2, 3, 1, 2])
print(our_set.get_all())


## 7. 作业

### 7.1 链表插入

#### 7.1.3 输出

1 2 3 4
0 1


1->1->2->3->4


3 4 5 6 7 8
2 10


3->4->5->10->6->7->8


#### Solution

class IntNode(object):
"""docstring for IntNode"""

def __init__(self, i, n, p):
self.item = i
self.next = n
self.prev = p

class DLList(object):
"""docstring for SLList"""

def __init__(self, x=None):
self.__sentinel = IntNode(49, None, None)
self.__sentinel.next = self.__sentinel
self.__sentinel.prev = self.__sentinel
self.__last = self.__sentinel.prev
if x is None:
self.__size = 0
else:
self.__sentinel.next = IntNode(x, self.__sentinel, self.__sentinel)
self.__sentinel.prev = self.__sentinel.next
self.__size = 1

self.__sentinel.next = IntNode(x, self.__sentinel.next, self.__sentinel)
self.__sentinel.next.next.prev = self.__sentinel.next
self.__size += 1

def get_first(self):
return self.__sentinel.next.item

self.__size += 1
self.__sentinel.prev = IntNode(x, self.__sentinel, self.__sentinel.prev)
self.__sentinel.prev.prev.next = self.__sentinel.prev

def insert(self, num, x):
self.__size += 1
p = self.__sentinel.next
count = 0
while count < num:
p = p.next
count += 1

new_node = IntNode(x, p.next, p)
p.next.prev = new_node
p.next = new_node

def size(self):
return self.__size

def output(self):
s = ''
p = self.__sentinel.next
count = 0
while count < self.__size - 1:
s += p.item + '->'
p = p.next
count += 1
s += p.item
print(s)

s1 = input()
s2 = input()

s_list = s1.split(' ')
l = DLList()
for item in s_list:

s2 = s2.split(' ')
num = int(s2[0])
item = s2[1]

l.insert(num, item)
l.output()


### 7.2 单身狗配对

#### 7.2.1 描述

B公司组织了一场七夕配对活动，单身的男女生可以来参加活动。

1. 所有参加活动的人都只排成一列，来参加活动的女生只会和排在队伍最后的男生配对。

2. 如果女生来到现场没有可以配对的男生则活动失败。

3. 如果最后有没有被领走的男生则活动也失败。

#### 7.2.3 输出

True 或者 False 表示活动能否成功举办。

mfmfmf


True


mfmmfffm


False


#### Solution

s = input()

stack = []
can_match = True
for item in s:
if item == 'm':
stack.append('m')
else:
if len(stack) == 0:
can_match = False
break
else:
stack.pop()
if len(stack) > 0:
can_match = False
print(can_match)


### 7.3 单身狗配对2

#### 7.3.1 描述

C 公司模仿 B 公司组织了一场七夕配对活动，单身的男女生可以来参加活动。

#### 7.3.3 输出

True 或者 False 表示活动能否成功举办。

m1 m2 m3 f3 f2 f1


True


m2 m3 m3 f1 f2 f3


False


#### Solution

s = input()

s_list = s.split(' ')
stack = []
can_match = True
for item in s_list:
if item[0] == 'm':
stack.append(item)
else:
if len(stack) == 0:
can_match = False
break
else:
if stack[-1][1] == item[1]:
stack.pop()
if len(stack) > 0:
can_match = False
print(can_match)


### 7.4 身高排序

#### 7.4.1 描述

A 公司举办七夕活动，活动结束大家准备拍照，由于场地限制的原因，每次可能只能让其中一部分人一起拍照。

A 公司纪律严谨，每次拍照必须按照身高从大到小排列。

#### 7.4.3 输出

5
2


[5, 4]
[5, 3]
[5, 2]
[5, 1]
[4, 3]
[4, 2]
[4, 1]
[3, 2]
[3, 1]
[2, 1]


4
3


[4, 3, 2]
[4, 3, 1]
[4, 2, 1]
[3, 2, 1]


#### Solution

combination = []

def permutation(arr, index, count):
global combination
if count == 1:
for i in range(index + 1, 0, -1):
combination.append(i)
print(combination)
combination.pop()
elif index > 0:
combination.append(arr[index])
permutation(arr, index - 1, count - 1)
combination.pop()
permutation(arr, index - 1, count)

n = int(input())
m = int(input())
permutation([i for i in range(1, n + 1)], n - 1, m)


AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

• 0
• 0
• 0
• 0
• 0
• 0

• 按正序
• 按倒序
• 按热度