目录
1.UVA101: 木块问题 (The Blocks Problem)
2.UVA11988: 破损的键盘 (Broken Keyboard)
一.顺序表
顺序表是线性表的一种实现方式，它用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表主要分为静态顺序表和动态顺序表两种形式。
1、静态顺序表
-
定义：静态顺序表使用定长数组来创建，数组的长度在创建时就已确定，且在后续使用过程中不可改变。
-
特点：
- 空间分配：在编译时或程序执行前就分配了固定大小的存储空间，这个空间大小在程序运行过程中不会改变。
- 使用场景：适用于确定知道需要存储多少数据的场景。
- 缺点：如果预估的存储空间不足，可能会导致数据溢出；如果预估的存储空间过多，则会造成空间浪费。
2、动态顺序表
-
定义：动态顺序表使用动态开辟的数组来存储数据，即根据实际需要动态地分配和释放存储空间。
-
特点：
- 空间分配：在程序运行过程中，根据需要动态地分配和释放存储空间，避免了空间浪费和数据溢出的风险。
- 扩容机制：当现有存储空间不足以容纳更多数据时，动态顺序表会自动进行扩容，通常是通过重新分配一块更大的连续存储空间，并将原有数据复制到新空间中来实现的。扩容时，新的存储空间大小通常是原空间大小的倍数（如2倍），以确保有足够的空间来存储更多的数据。
- 使用场景：适用于不确定需要存储多少数据的场景，或者数据量可能会发生变化的情况。
3、顺序表的操作
顺序表的基本操作主要包括初始化、插入、删除、查找和遍历等。
-
初始化：创建顺序表，并为其分配初始存储空间（对于动态顺序表而言）。
-
插入：在顺序表的指定位置插入一个新的数据元素，并更新顺序表的长度。
-
删除：从顺序表的指定位置删除一个数据元素，并更新顺序表的长度。
-
查找：在顺序表中查找指定的数据元素，并返回其位置（或未找到时的某种表示）。
-
遍历：按顺序访问顺序表中的每个数据元素，执行某种操作（如打印、求和等）。
总的来说，顺序表是一种在实际中广泛使用的数据结构，它结合了数组的高效访问能力和动态分配空间的灵活性。通过选择适当的顺序表类型（静态或动态）以及合理设计扩容机制，可以有效地满足各种应用场景的需求。
二.单链表、双向链表、循环链表、静态链表
单链表、双向链表、循环链表和静态链表都是常见的数据结构，它们各自具有不同的特点和应用场景。以下是对这四种链表结构的详细介绍：
1、单链表
定义：单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点包含数据元素和指向下一个结点的指针。链表中的元素在内存中不必连续存储，其物理存储位置可以是随机的。
特点：
-
链表中的元素通过指针连接，不需要在内存中连续存储。
-
访问链表中的元素需要从头结点开始逐个访问，即顺序访问。
-
适用于写操作多、读操作少，且需要动态调整数据结构大小的场景。
应用场景：
-
需要频繁进行插入和删除操作的场景。
-
需要动态调整数据结构大小的场景。
2、双向链表
定义：双向链表是链表的一种，它的每个节点不仅包含数据域，还具备两个指针域，分别指向前一个节点和后一个节点。
特点：
-
双向链表中的节点可以通过两个指针向前或向后访问，提高了操作的灵活性。
-
适用于需要频繁进行前后遍历的场景。
应用场景：
-
需要同时访问节点的前驱和后继的场景。
-
双向链表在插入和删除节点时，同样不需要移动其他节点，保持了单链表的高效性。
3、循环链表
定义：循环链表是另一种形式的链式存储结构，其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
特点：
-
循环链表中没有NULL指针，从任一节点出发都可以访问到表中的所有节点。
-
适用于需要循环遍历链表的场景。
应用场景：
- 环形队列、循环缓冲区等需要循环遍历的场景。
4、静态链表
定义：静态链表是使用数组来模拟链表结构的一种数据结构。它与传统链表的区别在于，静态链表使用数组保存节点，每个节点包括数据域和游标（指向下一个节点的位置）。
特点：
-
静态链表分配一整片连续的内存空间来存储节点，节点在内存中是连续的。
-
适用于不支持指针的低级语言或数据元素数量固定不变的场景。
应用场景：
- 操作系统中的文件分配表（FAT）等需要固定长度且不支持动态内存分配的场景。
综上所述，单链表、双向链表、循环链表和静态链表各有其特点和应用场景。在实际应用中，应根据具体需求选择合适的数据结构。
三.UVA101、UVA11988、UVA12657
UVA101、UVA11988、UVA12657是UVa Online Judge（UVa OJ）上的三道编程题目，它们各自具有不同的题目背景和要求。以下是对这三道题目的简要介绍和分析：
1.UVA101: 木块问题 (The Blocks Problem)
题目背景： UVA101是一道经典的木块移动问题。题目中给定一系列木块，每个木块都有一个唯一的编号，并且这些木块初始时都位于自己的位置上（即编号i的木块位于位置i）。然后，题目会给出一系列的操作指令，要求模拟这些指令对木块位置的影响。
操作指令：
-
move a onto b：将木块a和木块b上方的所有木块归位，然后将木块a放到木块b上。 -
move a over b：将木块a上方的所有木块归位，然后将木块a放到包含木块b的木块堆的顶部。 -
pile a onto b：将木块b上方的所有木块归位，然后将木块a及其上方的所有木块整体摞在木块b上。 -
pile a over b：将木块a及其上方的所有木块整体摞在包含木块b的木块堆的顶部。 -
quit：终止操作。
解题思路： 为了解决这个问题，通常需要使用一种数据结构来模拟木块的位置和状态。常见的做法是使用向量（vector）或数组来存储每个位置上的木块堆。然后，根据操作指令，通过一系列的归位和移动操作来更新木块的位置。
代码示例:
def min_blocks(w, h):
dp = [[float('inf')] * (h + 1) for _ in range(w + 1)]
for i in range(w + 1):
for j in range(h + 1):
if i == 0 and j == 0:
dp[i][j] = 0
else:
for k in range(1, min(i, j) + 1):
dp[i][j] = min(dp[i][j], dp[i - k][j] + dp[k][j - k] + 1)
for k in range(1, i + 1):
dp[i][j] = min(dp[i][j], dp[i - k][j] + dp[k][j])
for k in range(1, j + 1):
dp[i][j] = min(dp[i][j], dp[i][j - k] + dp[i][k])
return dp[w][h]
# 示例调用
print(min_blocks(5, 3))
2.UVA11988: 破损的键盘 (Broken Keyboard)
题目背景： UVA11988描述了一个有趣的场景，即你有一个破损的键盘，其中的Home键和End键会自动按下。你不知道这个问题，只是专心地打字，直到打开显示器才发现屏幕上显示的是一段“悲剧文本”。
输入： 输入包含多组数据，每组数据占一行，包含不超过100000个字母、下划线、字符[或]。其中，[表示Home键被按下，]表示End键被按下。输入以文件结束符（EOF）为结束标志。
输出： 对于每组数据，输出一行，即屏幕上显示的“悲剧文本”。
解题思路： 为了解决这个问题，可以使用链表或链表的思想来模拟文本编辑的过程。具体来说，可以引入两个数组分别作为链表的数据域和指针域，然后模拟键盘输入对光标位置的影响，并据此调整文本的顺序。
代码示例:
from collections import deque
def broken_keyboard(commands):
left = deque()
right = deque()
for command in commands:
if command == 'L':
if left:
right.appendleft(left.pop())
elif command == 'R':
if right:
left.append(right.popleft())
elif command == 'D':
if left:
left.pop()
else: # 插入字符
left.append(command)
return ''.join(left) + ''.join(right)
# 示例调用
commands = "abcLdeIefR"
print(broken_keyboard(commands))
3.UVA12657: Boxes in a Line
题目背景： UVA12657描述了一个盒子移动的问题。在一条直线上有n个盒子，每个盒子都有一个唯一的编号。然后，题目会给出一系列的操作指令，要求模拟这些指令对盒子位置的影响。
操作指令：
-
1 X Y：将盒子X向左移动到Y（如果X已经是Y的左侧，则忽略此项）。 -
2 X Y：将盒子X向右移动到Y（如果X已经是Y的右侧，则忽略此项）。 -
4：反转整条线路。
解题思路： 为了解决这个问题，可以使用静态双向链表来模拟盒子的位置。静态双向链表是一种在数组中模拟链表结构的数据结构，它可以在O(1)的时间内完成插入、删除和移动操作。通过维护每个盒子的前驱和后继指针，可以方便地模拟题目中的操作指令。
综上所述，UVA101、UVA11988和UVA12657是三道各具特色的编程题目，它们分别考察了不同方面的编程能力和算法知识。在解决这些问题时，需要根据题目的具体要求选择合适的数据结构和算法策略。
代码示例:
def last_digit(a, b):
if b == 0:
return 1
a = a % 10
cycle = []
# 找到最后一位数字的周期
current = a
while current not in cycle:
cycle.append(current)
current = (current * a) % 10
# 计算有效指数
index = (b - 1) % len(cycle)
return cycle[index]
# 示例调用
print(last_digit(2, 10)) # 输出 4