Week2：链表和抽象数据类型

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

注意

本系列，你可以在我网站免费学习，但是切勿 copy 分发。本系列为书稿，我的爬虫系统会全天检索。被我找到，我必维权和告之，不死不休。

你学习本系列有问题，可以评论区和加我微信，拉你进交流群。微信：Jiabcdefh

你好，我是悦创。

今天我们将学习：

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

我们先来看看上节课的代码：

# -*- coding: utf-8 -*-
# @Time    : 2023/12/7 17:04
# @Author  : AI悦创
# @FileName: linked3.py
# @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

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

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

    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

    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)
    l.add_first(10)
    l.add_first(5)
    print(l.get_first())
    l.add_last(20)
    print(l.size())

1. 尾部添加数据优化

提示

有时候在每次重复找最后一个的时候，不妨换一个思路想想，我直接跟踪尾部，在需要添加尾部的时候，直接添加，那不是更快么～

我们可以通过在 SLList 类中跟踪链表的尾部来提高在链表尾部添加元素的效率。

在当前的实现中，每次调用 add_last 方法时，都需要遍历整个链表来找到最后一个节点，这会导致操作的时间复杂度为 $O(n)$ 。通过维护一个指向链表最后一个节点的引用，我们可以直接访问尾部节点，将新节点添加到链表的末尾，从而将 add_last 方法的时间复杂度降低到 $O(1)$ 。

Sample Code

# -*- coding: utf-8 -*-
# @Time    : 2023/12/7 17:19
# @Author  : AI悦创
# @FileName: Linked4.py
# @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---

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

#---snip---

完整代码

# -*- coding: utf-8 -*-
# @Time    : 2023/12/7 17:19
# @Author  : AI悦创
# @FileName: Linked4.py
# @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.__last = self.__first  # 新增属性，指向链表的最后一个节点

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

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

    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
        new_node = IntNode(x, None)
        self.__last.next = new_node  # 在链表末尾添加新节点
        self.__last = new_node  # 更新__last引用
        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)
    l.add_first(10)
    l.add_first(5)
    print(l.get_first())
    l.add_last(20)
    print(l.size())

3. SLList 的一点问题

3.1 发现问题

思考🤔编写

上面开始的时候，我率先带你实现了跟踪末尾，现在到这个部分，开始思考一下怎么实现现有代码的跟踪。思考和编写后，再继续往下学习。

我再来描述一遍问题，我们每次都要循环或者递归来找到最后一个节点，显然是有点浪费时间的。时间复杂度上也是 $O(n)$ 。

举个例子🌰

你是一家公司领导，因做的事物资进出管理的职务，时不时需要及时了解仓库库存数据，公司招收了一个仓库看管员。某一天，你需要了解现在仓库库存数量，就询问这个管理员。

管理员说：领导，我得每次重新清点一下，你得给我 1 天的时间。领导同意了，但是领导转念一想，便问：我每次需要数据，你都要花至少一天从头清点？

管理员：是的，有时候物品多的时候会花更多时间，因为物品数量不确定，有时候需要的时间需要 n 天。

领导：了解，思绪一番后。说：你这样效率很低，如果我天天要，甚至一天要很多次那么你得忙的不得了啊。

管理员：那确实。

你发现上面例子的问题了吗？

每次需要都要从头清点一遍，显然效率很低。为什么，不在每次进出物品的时候，及时变化呢？这样需要的时候，直接可以给出数据。这样所需要的时间，仅仅只需要用一小会，毫不夸张的说：一秒。就能解决这个任务。

好，上面讲了这样的一个例子，我想你明白了。现在回到我的问题：之前实现的 add_last() 要得到结果，需要把所有元素循环一遍，才能在链表的尾部添加一个元素。如此反复，再添加，再一次。（还比上一次需要多一次。）

所以：如何优化 add_last() 呢？

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

提前回复杠精潜质的“你”

老师，我就三个数据，我原本的方法也可以实现呀？

——你可以想想数据量大的时候，比如 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

    def add_first(self, x):
        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

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

    def size(self):
        return self.__length

# ---snip---

AllCode

# -*- coding: utf-8 -*-
# @Time    : 2023/12/19 22:37
# @Author  : AI悦创
# @FileName: Code4-plus1.py
# @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=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

    def add_first(self, x):
        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

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

    def size(self):
        return self.__length


if __name__ == '__main__':
    l = SLList(15)
    l.add_first(10)
    l.add_first(5)
    print(l.get_first())  # 应该输出5
    l.add_last(20)
    print(l.size())  # 应该输出4

3.2 另一问题

如果用缓存的方式，以下哪种或哪几种方法会很慢：

add_last()
get_last()
remove_last()

也就是我们跟踪最后一个节点后，上面的三种方法会很慢？——remove_last() 。

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

有可能会想着缓存，但是我们需要知道：我们不可能把每一个缓存，我们不可能就删一次，我们也不知道具体链表会有多长。不可能每次删除最后一个，都存上一个节点。

那么，我们如何实现，知道上一个是谁呢？「remove_last 很慢的原因：我们不知道上一个是谁？」

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

img 0

img 1

img 2

img 3

我们接下来，就来讲一个稍微抽象一点的概念，它名字也很抽象，就叫做：抽象数据结构。

我们刚刚链表这一套基本的东西我们都讲完了，我们来讲一讲一个跟抽象一点东西，这个叫做抽象数据类型，

何为抽象数据类型呢？这个概念也有点抽象。

所谓的抽象数据类型 Abstract Data Types，一般简称 ADT。

我们抽象数据类型是这么描述的：它仅仅由它的操作来定义，而不是由它的实现来定义的。

我们用苏格拉底的《洞穴寓言》：

在洞喻中，柏拉图描述了一群人，他们一生都被锁链拴在洞穴的墙壁旁，面对着一堵空白的墙壁。这些人观察从他们身后火堆前经过的物体投射在墙上的影子，并为这些影子命名。影子是囚犯们的现实，但并不是真实世界的准确呈现。影子代表我们通常可以凭借感官感知的现实片段，而阳光下的物体则代表我们只能通过理性感知的物体真实形态。存在三个更高的层次：自然科学open in new window，数学open in new window、几何学open in new window与演绎推理open in new window，以及理型论open in new window。

苏格拉底解释说，哲学家就像一个从洞穴中获释的囚犯，逐渐明白墙上的影子其实并不是所见图像的直接来源。哲学家的目标是理解和感知更高层次的现实。然而，其他囚犯甚至不想离开洞穴监狱，因为他们对更好的生活一无所知[1]open in new window。

假如说有一些人就这些人，他一生下来就在这洞穴当中的。那么他永远看到的都是墙上由一些火把照出来的影子。

那么对他来说，他就认为这个是他全部的世界。对于这些用户来说，他所看的就是墙上的这一套东西，但是他不知道这个东西「影子」怎么来的，具体来说是怎么样子去弄出来的。

实际上来说，我们作为一个旁观者，我知道是有这样子的一些人，在后面用火把照的这些东西。对于这些用户来说，他所看到的就是：影子能动，不知道影子是怎么来的，他只知道墙上有东西「影子」在动。

其实，我们可以用火把照着形状的方式在墙壁上显示影子。我们也可以直接挂一个显示器来显示影子。

对于这里面用户来说效果是一样的，他感觉没有太大的区别。他不知道你背后是如何实现的，但是反正他就知道墙上影子会动。这就是他唯一所知道的一切。

就是我们提供一系列的操作函数：

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

但使用者不用关心这些函数具体是如何实现的，使用者只需要知道有这些操作函数即可。

只要有双向数据类型，就应该有这样一套来使用。这就是 ADT ，具体怎么实现的并不是 ADT 所要关心的。

ADT 所关心的就是，有哪些方法可以去用。

所以说，我们所说的双端队列，两端都有。ADT 就是知其然，不用知其所以然。

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())

ADT 不关心你内部是使用什么来实现的，反正有 push、pop 就可以了。

上面的代码运行结果：

6.2 使上面的 Stack 更全面

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

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

这里是栈的一个基本实现，以及对它的一些操作：

初始化一个空栈。
通过 push 方法添加了三个元素（"apple", "banana", "cherry"）到栈中。
使用 peek 方法查看了栈顶元素，此时为 "cherry"。
使用 size 方法获取了栈的大小，此时为 3。
使用 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

linked

# -*- 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

    def add_first(self, item):
        # 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

    def add_last(self, item):
        """在链表的尾部添加数据"""
        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

Stack

class Stack:
    def __init__(self):
        self.dllist = DLList()

    def push(self, item):
        self.dllist.add_first(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        item = self.dllist.get_value(0)
        self.dllist.remove_at(0)
        return item

    def is_empty(self):
        return self.dllist.__length == 0

    def size(self):
        return self.dllist.__length

6.4 有效的括号

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'[' 和 ']' 的字符串，判断字符串是否有效。

有效字符串需满足：

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

注意：

空字符串可被认为是有效字符串。

示例：

输入: "()"，输出: True
输入: "()[]{}"，输出: True
输入: "(]"，输出: False
输入: "([)]"，输出: False
输入: "{[]}"，输出: 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

解决方案的测试结果与题目中的示例相符合。这里是针对每个示例的结果：

输入: "()"，输出: True
输入: "()[]{}"，输出: True
输入: "(]"，输出: False
输入: "([)]"，输出: False
输入: "{[]}"，输出: 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)

    def add(self, x):
        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])
our_set.add(1)
our_set.add(4)
print(our_set.get_all())

思考题：

上面那么写，有什么问题？

7. 作业

7.1 链表插入

7.1.1 描述

给定一个链表和链表中的一个位置m，在这个位置的后面插入一个新的元素x。

7.1.2 输入

一共有两行，第一行是多个数字，以空格隔开，最多 100000 个数字。

第二行是两个个数字，第一个数字是 m，第二个是 x。

数字均在 int 范围内。

7.1.3 输出

一行输出，数字之间用“->”来表示链表方向。比如：1->2->3->4

输入样例 1

1 2 3 4
0 1

输出样例 1

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

输入样例 2

3 4 5 6 7 8
2 10

输出样例 2

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

    def add_first(self, x):
        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

    def add_last(self, x):
        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:
    l.add_last(item)

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

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

7.2 单身狗配对

7.2.1 描述

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

配对规则：

所有参加活动的人都只排成一列，来参加活动的女生只会和排在队伍最后的男生配对。
如果女生来到现场没有可以配对的男生则活动失败。
如果最后有没有被领走的男生则活动也失败。

问题：

给定到场参加活动人士顺序的性别，问活动能不能成功举办。

7.2.2 输入

一行数据，到场人士顺序的性别。

如：mfmfmfmmff

参加人数不超过 100 人。

7.2.3 输出

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

输入样例 1

mfmfmf

输出样例 1

True

输入样例 2

mfmmfffm

输出样例 2

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.2 输入

一行数据，到场人士顺序的性别和性格，数据之间用空格隔开。

如：m1 f1 m2 f2 m3 f3 m3 m3 f4 f4

参加人数不超过 20 万人。

7.3.3 输出

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

输入样例 1

m1 m2 m3 f3 f2 f1

输出样例 1

True

输入样例 2

m2 m3 m3 f1 f2 f3

输出样例 2

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.2 输入

一共两行数据，第一行是一共有多少人，第二行是每次可以有多少人来拍照。假设所有人的身高都正好各不相同。

总人数不超过 20 人，一次拍照最多不超过 6 人。

7.4.3 输出

将所有可能排列的方式输出出来。

每行输出一个列表，列表内的数字为拍照时身高排列的序号，如：[10,9,8,7]。

例如，有 20 个人，那么身高最高的人编号就是 20，最低的就是 1。

输出时列表内的数字需要从大到小排列，列表内最大数更大的要先输出，比如 [5,4] 要比 [4,3] 先输出，最大数相同的则数字之和最大的排列方式要优先输出，比如 [5,4] 要在 [5,3] 之前输出。

输入样例 1

5
2

输出样例 1

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

输入样例 2

4
3

输出样例 2

[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悦创【二维码】

AI悦创·编程一对一

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

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

方法一：QQopen in new window

方法二：微信：Jiabcdefh