算法进阶与NOAI初赛备战

# 大 O 表示法：数据量翻倍，耗时怎么变？
import time
def find(lst, x):                 # O(n) 线性查找
    for i, v in enumerate(lst):
        if v == x: return i
    return -1
data = list(range(10_000_000))
t = time.perf_counter()
find(data, -1)                    # 最坏情况：全找一遍
print("O(n) 找 1000 万个数：%.3f 秒" % (time.perf_counter() - t))
print("O(log n) 二分只需 ~24 步，O(1) 直接定位")

def quick_sort(a):
    if len(a) <= 1: return a
    pivot = a[len(a) // 2]              # 选基准
    left  = [x for x in a if x < pivot]
    mid   = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

print(quick_sort([5, 2, 9, 1, 7, 3]))
# 归并排序思路：对半分 → 各自排好 → 合并

# 栈：后进先出，像弹匣
def is_valid(s):
    stack, pair = [], {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != pair[ch]:
            return False
    return not stack

print(is_valid("([()])"))
print(is_valid("([)]"))

class Node:                      # 一节车厢
    def __init__(self, val):
        self.val, self.next = val, None

head = Node("车头")
head.next = Node("车厢A")
head.next.next = Node("车厢B")

# 插入：改两根「挂钩」就行，不用挪其他车厢
new = Node("加急车厢")
new.next, head.next = head.next, new

cur = head
while cur:
    print(cur.val, end=" → ")
    cur = cur.next
print("尾")

class Node:
    def __init__(self, val):
        self.val, self.l, self.r = val, None, None

root = Node("爷爷")
root.l, root.r = Node("大伯"), Node("爸爸")
root.r.l = Node("我")

def preorder(n):            # 前序：根 → 左 → 右
    return [n.val] + preorder(n.l) + preorder(n.r) if n else []

print("前序遍历：", preorder(root))

def hanoi(n, a, b, c):
    """把 n 个盘从 a 借 b 挪到 c"""
    if n == 1:
        return [(n, a, c)]
    return (hanoi(n-1, a, c, b)       # ① 上面 n-1 个挪去 b
            + [(n, a, c)]             # ② 最大盘直接去 c
            + hanoi(n-1, b, a, c))    # ③ 再把 n-1 个从 b 挪到 c

for mv in hanoi(3, "A", "B", "C"):
    print("盘%d：%s → %s" % mv)
print("n 个盘共需 2^n - 1 步")

# 每次走 1 或 2 阶，n 阶有几种走法？
def climb(n):
    if n <= 2: return n
    a, b = 1, 2                    # dp[i-2], dp[i-1]
    for _ in range(3, n + 1):
        a, b = b, a + b            # dp[i] = dp[i-1] + dp[i-2]
    return b

print("3 阶：", climb(3), "种")
print("10 阶：", climb(10), "种")
# 递归 + 记忆化 = 同样的 O(n)，自底向上更省空间

# 贪心：每次都拿「当前最大」面额
coins = [25, 10, 5, 1]
def change(n):
    cnt, plan = 0, []
    for c in coins:
        k = n // c
        if k: plan.append(f"{c}分×{k}")
        cnt += k; n -= k * c
    return cnt, plan

print(change(68))
# 注意：贪心不总是全局最优，如面额 [1,3,4] 凑 6

# 初赛高频概念，一句话分清楚：
concepts = {
    "机器学习": "从数据中学规律，不用人写死规则",
    "深度学习": "用多层神经网络自动提特征",
    "训练集":  "用来学习的题目",
    "验证集":  "用来调参的模拟考",
    "测试集":  "最终大考，只考一次",
    "过拟合":  "死记硬背，新题就不会",
    "欠拟合":  "根本没学会，老题也错",
}
for k in ["过拟合", "欠拟合"]:
    print(k, "：", concepts[k])

# 编程题四步法：读题 → 举例 → 写码 → 边界
# 例：统计每个字符出现次数
s = "noicontest"
from collections import Counter
cnt = Counter(s)
print(cnt.most_common(3))        # 手写就是 dict + 循环
# 手写版：
d = {}
for ch in s:
    d[ch] = d.get(ch, 0) + 1
print(sorted(d.items(), key=lambda x: -x[1])[:3])

# 90 分钟 100 分的典型分配：
plan = [
    ("选择题 2'×15", "25 分钟", "稳拿，概念题不纠结"),
    ("程序填空 3'×10", "30 分钟", "先在脑内跑一遍代码"),
    ("编程题 10'×2~3", "30 分钟", "先写暴力解保底，再优化"),
    ("检查", "5 分钟", "文件名、输出格式、边界"),
]
for part, t, tip in plan:
    print(f"{part:<18} {t:<8} {tip}")