{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# \u7b97\u6cd5\u56fe\u89e3 \u2014 \u57fa\u7840\u7bc7\n", "\n", "\u672c\u7b14\u8bb0\u672c\u662f [grokking_algorithms.html](grokking_algorithms.html) \u4e2d**\u57fa\u7840**\n", "\u548c**\u6570\u636e\u7ed3\u6784**\u4e24\u8282\u7684\u52a8\u624b\u5b9e\u8df5\u7248\u3002\n", "\n", "\u6bcf\u4e2a\u4ee3\u7801\u5355\u5143\u683c\u524d\u9762\u90fd\u6709\u4e00\u6bb5\u7b80\u77ed\u7684 **\ud83d\udc0d \u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027**\n", "\u8bf4\u660e \u2014\u2014 \u5373\u4ee3\u7801\u7528\u5230\u4e86\u54ea\u4e9b Python \u77e5\u8bc6 \u2014\u2014 \u800c\u4ee3\u7801\u6bcf\u4e00\u884c\u90fd\u6709\u6ce8\u91ca\u3002\n", "\u770b\u6ce8\u91ca\u4f60\u5e94\u8be5\u5c31\u80fd\u7406\u89e3\u6574\u4e2a\u5355\u5143\u683c\u3002\n", "\n", "**\u672c\u7b14\u8bb0\u672c\u6db5\u76d6\uff1a**\n", "1. \u5927 O \u8bb0\u53f7\n", "2. \u9012\u5f52\n", "3. \u54c8\u5e0c\u8868\n", "4. \u5806\u4e0e\u4f18\u5148\u961f\u5217\n", "5. \u4e8c\u53c9\u641c\u7d22\u6811\n", "6. \u5e76\u67e5\u96c6" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. \u5927 O \u8bb0\u53f7\n", "\n", "\u5927 O \u8bb0\u53f7\u63cf\u8ff0\u5f53\u8f93\u5165\u53d8\u5927\u65f6\u7b97\u6cd5\u6240\u9700\u7684\u6b65\u6570\u5982\u4f55\u589e\u957f\u3002\u4e0b\u9762\u7684\u5355\u5143\u683c\n", "\u5bf9\"x \u662f\u5426\u5728\u8fd9\u4e2a\u96c6\u5408\u91cc\uff1f\"\u7528\u4e24\u79cd\u65b9\u5f0f\u8ba1\u65f6\uff0c\u96c6\u5408\u4ece 1,000 \u9879\u589e\u957f\u5230\n", "1,000,000 \u9879\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `import time` \u5bfc\u5165 Python \u7684\u8ba1\u65f6\u5de5\u5177\u3002`time.perf_counter()` \u8fd4\u56de\u9ad8\u7cbe\u5ea6\u8ba1\u65f6\u5668\u7684\u5f53\u524d\u503c\uff08\u4ee5\u79d2\u4e3a\u5355\u4f4d\u7684\u6d6e\u70b9\u6570\uff09\u3002\u4e24\u6b21\u8bfb\u6570\u76f8\u51cf\u5c31\u80fd\u5f97\u5230\u7ecf\u8fc7\u7684\u65f6\u95f4\u3002`list(range(n))` \u751f\u6210 `[0, 1, 2, ..., n-1]`\u3002`set(iterable)` \u4ece\u53ef\u8fed\u4ee3\u5bf9\u8c61\u751f\u6210\u96c6\u5408\uff0c`in` \u67e5\u8be2\u5f88\u5feb\u3002`in` \u8fd0\u7b97\u7b26\u5bf9\u5217\u8868\u548c\u96c6\u5408\u90fd\u80fd\u7528\uff0c\u4f46\u5217\u8868\u662f O(n)\uff0c\u96c6\u5408\u5e73\u5747\u662f O(1)\u3002`f\"...\"` \u662f f-string\uff1a`{}` \u91cc\u7684\u8868\u8fbe\u5f0f\u5728\u8fd0\u884c\u65f6\u4f1a\u88ab\u6c42\u503c\u5e76\u66ff\u6362\u8fdb\u5b57\u7b26\u4e32\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time # \u5185\u7f6e\u8ba1\u65f6\u5de5\u5177\n", "\n", "sizes = [1_000, 10_000, 100_000, 1_000_000] # \u4e0b\u5212\u7ebf\u53ea\u4e3a\u597d\u770b\uff1b\u7b49\u540c\u4e8e 1000\u300110000 \u7b49\n", "\n", "for n in sizes:\n", " data_list = list(range(n)) # \u751f\u6210\u5217\u8868 [0, 1, 2, ..., n-1]\n", " data_set = set(data_list) # \u540c\u6837\u7684\u5143\u7d20\u653e\u8fdb\u96c6\u5408\n", " target = n - 1 # \u7ebf\u6027\u67e5\u627e\u7684\u6700\u574f\u60c5\u51b5\uff08\u6700\u540e\u4e00\u4e2a\u5143\u7d20\uff09\n", "\n", " t0 = time.perf_counter() # \u8bb0\u5f55\u5f00\u59cb\u65f6\u95f4\n", " target in data_list # \u5728\u5217\u8868\u91cc\u67e5\u627e \u2014\u2014 O(n)\n", " list_time = time.perf_counter() - t0 # \u7ecf\u8fc7\u7684\u79d2\u6570\n", "\n", " t0 = time.perf_counter()\n", " target in data_set # \u5728\u96c6\u5408\u91cc\u67e5\u627e \u2014\u2014 \u5e73\u5747 O(1)\n", " set_time = time.perf_counter() - t0\n", "\n", " # f-string\uff1a{n:>9,} \u8868\u793a\u53f3\u5bf9\u9f50\u5360 9 \u683c\u3001\u52a0\u5343\u4f4d\u9017\u53f7\n", " print(f\"n = {n:>9,} list: {list_time*1e6:>8.1f} \u00b5s \"\n", " f\"set: {set_time*1e6:>6.1f} \u00b5s\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5\uff1a**\u628a `target = n - 1` \u6539\u6210 `target = 0`\u3002\u7ebf\u6027\u67e5\u627e\u8017\u65f6\n", "\u4f1a\u5927\u5e45\u4e0b\u964d \u2014\u2014 \u56e0\u4e3a\u76ee\u6807\u503c\u73b0\u5728\u5728\u5217\u8868\u6700\u524d\u9762\uff0c\u7acb\u523b\u5c31\u80fd\u627e\u5230\u3002\n", "\u5927 O \u901a\u5e38\u63cf\u8ff0\u7684\u662f*\u6700\u574f\u60c5\u51b5*\uff1b\u8fd9\u4e2a\u5b9e\u9a8c\u8ba9\u4f60\u770b\u5230\u6700\u597d\u60c5\u51b5\u4f5c\u4e3a\u5bf9\u6bd4\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. \u9012\u5f52\n", "\n", "\u4e00\u4e2a\u51fd\u6570\u9488\u5bf9\u540c\u4e00\u95ee\u9898\u7684\u66f4\u5c0f\u7248\u672c\u8c03\u7528\u81ea\u8eab\u3002\u7ecf\u5178\u4f8b\u5b50\u662f**\u9636\u4e58**\uff1a\n", "`4! = 4 \u00d7 3 \u00d7 2 \u00d7 1 = 24`\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `def \u51fd\u6570\u540d(\u53c2\u6570):` \u5b9a\u4e49\u4e00\u4e2a\u51fd\u6570\u3002`if \u6761\u4ef6:` \u53ea\u5728\u6761\u4ef6\u4e3a\u771f\u65f6\u8fd0\u884c\u7f29\u8fdb\u5757\u3002`return \u503c` \u7ed3\u675f\u51fd\u6570\u5e76\u628a\u503c\u4ea4\u8fd8\u7ed9\u8c03\u7528\u8005\u3002\u51fd\u6570\u53ef\u4ee5\u8c03\u7528\u81ea\u8eab \u2014\u2014 \u8fd9\u5c31\u662f\u9012\u5f52\u3002`for i in range(6)` \u4f1a\u5faa\u73af\u904d\u5386 `0, 1, 2, 3, 4, 5`\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def factorial(n):\n", " if n <= 1: # \u57fa\u7840\u60c5\u51b5 \u2014\u2014 \u4ec0\u4e48\u65f6\u5019\u505c\u4e0b\u6765\n", " return 1 # 0! \u548c 1! \u90fd\u5b9a\u4e49\u4e3a 1\n", " return n * factorial(n - 1) # \u9012\u5f52\u60c5\u51b5 \u2014\u2014 n \u00d7 (n-1)!\n", "\n", "for n in range(6):\n", " print(f\"{n}! = {factorial(n)}\") # \u6253\u5370 0 \u5230 5 \u7684\u9636\u4e58" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5\uff1a**\u5199\u4e00\u4e2a\u9012\u5f52\u51fd\u6570 `countdown(n)`\uff0c\u4f9d\u6b21\u6253\u5370 n, n-1, ..., 1\uff0c\n", "\u6700\u540e\u6253\u5370 \"Go!\"\u3002\u518d\u7528\u9012\u5f52\u5199 `sum_to(n)`\uff0c\u8ba1\u7b97 1 + 2 + ... + n \u7684\u548c\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `pass` \u662f\u5360\u4f4d\u7b26\uff0c\u4ec0\u4e48\u90fd\u4e0d\u505a \u2014\u2014 Python \u8981\u6c42\u51fd\u6570\u4f53\u91cc\u5fc5\u987b\u6709\u5185\u5bb9\uff0c\u5728\u4f60\u8fd8\u6ca1\u60f3\u597d\u600e\u4e48\u5199\u65f6 `pass` \u5360\u7740\u4f4d\u7f6e\u3002\u6ce8\u91ca\u4ee5 `#` \u5f00\u5934\uff0cPython \u4f1a\u5ffd\u7565 `#` \u5f00\u5934\u7684\u884c\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# \u8be5\u4f60\u5199\u4e86 \u2014\u2014 \u628a\u4e0b\u9762\u8fd9\u4e9b\u586b\u5b8c\u6574\u3002\n", "\n", "def countdown(n):\n", " # \u57fa\u7840\u60c5\u51b5\uff1a\u4ec0\u4e48\u65f6\u5019\u505c\u4e0b\u6765\uff1f\n", " # \u9012\u5f52\u60c5\u51b5\uff1a\u5148 print(n)\uff0c\u518d\u8c03\u7528 countdown(n-1)\n", " pass # \u5360\u4f4d \u2014\u2014 \u7528\u771f\u6b63\u7684\u4ee3\u7801\u66ff\u6362\u5b83\n", "\n", "def sum_to(n):\n", " # \u57fa\u7840\u60c5\u51b5\uff1asum_to(0) \u5e94\u5f53\u8fd4\u56de 0\n", " # \u9012\u5f52\u60c5\u51b5\uff1an + sum_to(n - 1)\n", " pass # \u5360\u4f4d\n", "\n", "# \u586b\u597d\u4e0a\u9762\u7684\u51fd\u6570\u540e\uff0c\u628a\u4e0b\u9762\u4e24\u884c\u7684 # \u53bb\u6389\u518d\u8fd0\u884c\uff1a\n", "# countdown(5)\n", "# print(sum_to(10)) # \u5e94\u5f53\u6253\u5370 55" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u6ca1\u6709\u57fa\u7840\u60c5\u51b5\u4f1a\u600e\u6837\uff1f**\u5728\u65b0\u5355\u5143\u683c\u91cc\u8bd5\u7740\u8fd0\u884c\u3002Python \u6700\u7ec8\u4f1a\u4ee5\n", "`RecursionError` \u7ed3\u675f \u2014\u2014 \u6bcf\u4e2a\u672a\u5b8c\u6210\u7684\u8c03\u7528\u5360\u636e\u8c03\u7528\u6808\u4e0a\u7684\u4e00\u5757\u7a7a\u95f4\uff0c\n", "\u800c\u8c03\u7528\u6808\u662f\u6709\u9650\u7684\u3002\n", "\n", "```python\n", "def broken(n):\n", " return n * broken(n - 1) # \u6ca1\u6709\u57fa\u7840\u60c5\u51b5\uff01\n", "\n", "# broken(5) # \u5927\u7ea6 1000 \u6b21\u8c03\u7528\u540e\u4f1a\u62a5 RecursionError\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. \u54c8\u5e0c\u8868\n", "\n", "Python \u7684 `dict` *\u5c31\u662f*\u54c8\u5e0c\u8868\u3002\u7ed9\u5b83\u4e00\u4e2a\u952e\uff08key\uff09\uff0c\u7acb\u523b\u5f97\u5230\u4e00\u4e2a\u503c\n", "\uff08value\uff09\u3002\"\u7acb\u523b\"\u7684\u5965\u79d8\u662f\u628a\u952e\u4f20\u5165\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570\uff0c\u8f6c\u6362\u6210\u6570\u7ec4\u7684\u4e0b\u6807\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `{}` \u662f\u7a7a\u5b57\u5178\u3002`d[\u952e] = \u503c` \u6dfb\u52a0\u6216\u66f4\u65b0\u4e00\u9879\u3002`d[\u952e]` \u8bfb\u53d6\u503c\uff08\u5982\u679c\u952e\u4e0d\u5b58\u5728\u4f1a\u629b `KeyError`\uff09\u3002`\u952e in d` \u6d4b\u8bd5\u952e\u662f\u5426\u5728\u5b57\u5178\u91cc\uff0c\u8fd4\u56de `True` \u6216 `False`\u3002`list(d.keys())` \u628a\u5b57\u5178\u952e\u7684\u89c6\u56fe\u8f6c\u6210\u771f\u6b63\u7684\u5217\u8868\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "phone_book = {} # \u7a7a\u5b57\u5178\n", "phone_book[\"alice\"] = \"081-234-5678\" # \u6dfb\u52a0\u4e00\u9879 \u2014\u2014 \u952e\u662f \"alice\"\uff0c\u503c\u662f\u53f7\u7801\n", "phone_book[\"bob\"] = \"082-987-6543\" # \u518d\u6dfb\u52a0\u4e00\u9879\n", "phone_book[\"zoe\"] = \"098-111-2222\" # \u7b2c\u4e09\u9879\n", "\n", "print(phone_book[\"alice\"]) # \u67e5 alice \u7684\u53f7\u7801 \u2014\u2014 \u77ac\u95f4\u5b8c\u6210\uff01\n", "print(\"bob\" in phone_book) # \u68c0\u67e5\u662f\u5426\u5b58\u5728 \u2192 True\n", "print(list(phone_book.keys())) # \u6240\u6709\u952e\uff0c\u8f6c\u6210\u5217\u8868" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \u7528\u54c8\u5e0c\u8868\u505a\u8ba1\u6570\n", "\n", "\u6700\u5e38\u89c1\u7684\u7528\u9014\u4e4b\u4e00\uff1a\u7edf\u8ba1\u67d0\u6837\u4e1c\u897f\u51fa\u73b0\u7684\u6b21\u6570\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `from \u6a21\u5757 import \u540d\u5b57` \u53ea\u4ece\u6a21\u5757\u5bfc\u5165\u4e00\u4e2a\u4e1c\u897f\u3002`Counter` \u662f `dict` \u7684\u5b50\u7c7b\uff0c\u4e13\u95e8\u7528\u6765\u8ba1\u6570\u3002`\u67d0\u5b57\u7b26\u4e32.split()` \u6309\u7a7a\u767d\u628a\u5b57\u7b26\u4e32\u5207\u6210\u5355\u8bcd\u5217\u8868\u3002`counter.most_common(n)` \u8fd4\u56de\u51fa\u73b0\u9891\u6b21\u6700\u9ad8\u7684 n \u9879\uff0c\u5f62\u5f0f\u662f `(\u9879, \u6b21\u6570)` \u5143\u7ec4\u7684\u5217\u8868\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from collections import Counter # Counter \u2014\u2014 \u4e13\u95e8\u7528\u4e8e\u8ba1\u6570\u7684\u5b57\u5178\n", "\n", "sentence = \"the quick brown fox jumps over the lazy dog the fox is quick\"\n", "counts = Counter(sentence.split()) # \u5207\u5206\u5355\u8bcd\u5e76\u7edf\u8ba1\u6bcf\u4e2a\n", "print(counts) # \u5b8c\u6574\u7684\u6bcf\u4e2a\u5355\u8bcd\u7684\u8ba1\u6570\n", "print(\"Most common 3:\", counts.most_common(3)) # \u9891\u6b21\u6700\u9ad8\u7684 3 \u4e2a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \u4ece\u96f6\u5b9e\u73b0\u4e00\u4e2a\u54c8\u5e0c\u8868\n", "\n", "\u8bc1\u660e\u5e76\u4e0d\u795e\u79d8 \u2014\u2014 \u8fd9\u91cc\u662f\u4e00\u4e2a\u6700\u5c0f\u5316\u7684\u54c8\u5e0c\u8868\uff0c\u7528\"\u5206\u79bb\u94fe\u63a5\u6cd5\"\u5904\u7406\u51b2\u7a81\n", "\uff08\u6bcf\u4e2a\u69fd\u91cc\u653e\u4e00\u4e2a (key, value) \u5bf9\u7684\u5c0f\u5217\u8868\uff09\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `class \u7c7b\u540d:` \u5b9a\u4e49\u4e00\u4e2a\u7c7b\u3002`def __init__(self, ...)` \u662f\u6784\u9020\u51fd\u6570\uff0c\u521b\u5efa\u5b9e\u4f8b\u65f6\u81ea\u52a8\u8fd0\u884c\u4e00\u6b21\u3002`self.\u5c5e\u6027` \u628a\u6570\u636e\u5b58\u5728\u5b9e\u4f8b\u4e0a\u3002`[[] for _ in range(size)]` \u662f\u5217\u8868\u63a8\u5bfc\u5f0f\uff0c\u751f\u6210 `size` \u4e2a\u7a7a\u5217\u8868\u3002`hash(x)` \u5bf9\u4efb\u4f55\u53ef\u54c8\u5e0c\u5bf9\u8c61\u8fd4\u56de\u4e00\u4e2a\u6574\u6570\u54c8\u5e0c\u503c\u3002`%` \u662f\u53d6\u6a21\u8fd0\u7b97\u7b26\uff08\u9664\u6cd5\u7684\u4f59\u6570\uff09\u3002`enumerate(seq)` \u5728\u8fed\u4ee3\u65f6\u540c\u65f6\u7ed9\u51fa `(\u4e0b\u6807, \u503c)`\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class HashMap:\n", " def __init__(self, size=8):\n", " self.size = size # \u4e00\u5171\u6709\u591a\u5c11\u4e2a\u69fd\n", " self.buckets = [[] for _ in range(size)] # \u6bcf\u4e2a\u69fd\u653e\u4e00\u4e2a\u7a7a\u5217\u8868\n", "\n", " def put(self, key, value):\n", " idx = hash(key) % self.size # \u8fd9\u4e2a\u952e\u5c5e\u4e8e\u54ea\u4e2a\u69fd\n", " bucket = self.buckets[idx] # \u90a3\u4e2a\u69fd\u91cc\u7684\u5217\u8868\n", " for i, (k, _) in enumerate(bucket): # \u904d\u5386\u8fd9\u6761\u94fe\n", " if k == key:\n", " bucket[i] = (key, value) # \u5df2\u5b58\u5728 \u2192 \u66f4\u65b0\n", " return\n", " bucket.append((key, value)) # \u6ca1\u627e\u5230 \u2192 \u8ffd\u52a0\u65b0\u6761\u76ee\n", "\n", " def get(self, key):\n", " idx = hash(key) % self.size\n", " for k, v in self.buckets[idx]: # \u904d\u5386\u8fd9\u4e2a\u69fd\u7684\u94fe\n", " if k == key:\n", " return v # \u627e\u5230 \u2192 \u8fd4\u56de\u503c\n", " return None # \u952e\u4e0d\u5728\u8868\u91cc\n", "\n", " def show(self):\n", " for i, bucket in enumerate(self.buckets):\n", " print(f\" slot {i}: {bucket}\")\n", "\n", "m = HashMap(size=4) # \u69fd\u6570\u7279\u610f\u8bbe\u5f88\u5c0f\u4ee5\u5236\u9020\u51b2\u7a81\n", "for name in [\"alice\", \"bob\", \"claire\", \"dave\", \"eve\", \"frank\"]:\n", " m.put(name, len(name)) # \u5b58\uff1a\u540d\u5b57 \u2192 \u540d\u5b57\u957f\u5ea6\n", "\n", "print(\"Lookup 'claire':\", m.get(\"claire\"))\n", "print(\"Buckets:\")\n", "m.show() # \u770b\u770b 6 \u4e2a\u540d\u5b57\u600e\u4e48\u5206\u8fdb 4 \u4e2a\u69fd" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5\uff1a**\u7edf\u8ba1\u4e00\u6bb5\u8f83\u957f\u6587\u672c\u4e2d\u7684\u4e0d\u91cd\u590d\u5355\u8bcd\u3002\u4ece\u4e66\u6216\u65b0\u95fb\u91cc\u7c98\u8d34\u4e00\u6bb5\uff0c\n", "\u6309\u7a7a\u683c\u5207\u5206\uff0c\u7136\u540e\u7528 `Counter`\u3002\u6709\u591a\u5c11\u5355\u8bcd\u53ea\u51fa\u73b0\u4e86\u4e00\u6b21\uff1f" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. \u5806\u4e0e\u4f18\u5148\u961f\u5217\n", "\n", "\u5806\u59cb\u7ec8\u628a\u6700\u5c0f\uff08\u6216\u6700\u5927\uff09\u7684\u5143\u7d20\u653e\u5728\u6700\u4e0a\u9762\uff0cpush/pop \u90fd\u662f O(log n)\uff0c\n", "peek \u662f O(1)\u3002Python \u7684 `heapq` \u6a21\u5757\u662f\u7528\u6241\u5e73\u5217\u8868\u5b9e\u73b0\u7684**\u5c0f\u9876\u5806**\n", "\uff08\u6700\u5c0f\u5143\u7d20\u5728\u9876\uff09\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `import heapq` \u5bfc\u5165\u5806\u51fd\u6570\u3002`heapq.heappush(heap, x)` \u63d2\u5165 x \u5e76\u4fdd\u6301\u5806\u7684\u89c4\u5219\u3002`heapq.heappop(heap)` \u53d6\u51fa\u5e76\u8fd4\u56de\u6700\u5c0f\u5143\u7d20\u3002\u5806\u672c\u8eab\u5c31\u662f\u4e00\u4e2a\u666e\u901a Python \u5217\u8868 \u2014\u2014 heapq \u6a21\u5757\u5bf9\u5b83\u539f\u5730\u64cd\u4f5c\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import heapq # \u64cd\u4f5c\u666e\u901a\u5217\u8868\u7684\u5806\u7b97\u6cd5\n", "\n", "heap = [] # \u7a7a\u5217\u8868\u5c31\u662f\u5408\u6cd5\u7684\u7a7a\u5806\n", "for x in [7, 3, 9, 1, 5]:\n", " heapq.heappush(heap, x) # \u628a x \u63a8\u5165\u5806\u5e76\u4fdd\u6301\u5806\u89c4\u5219 \u2014\u2014 O(log n)\n", "\n", "print(\"Heap (array form):\", heap) # \u4e0d\u662f\u6392\u597d\u5e8f\u7684\uff01\u53ea\u662f\u5806\u5e8f\n", "print(\"Smallest:\", heap[0]) # \u5806\u9876\u6c38\u8fdc\u662f\u6700\u5c0f\u5143\u7d20\n", "print(\"Pop:\", heapq.heappop(heap)) # \u53d6\u51fa\u5e76\u8fd4\u56de\u6700\u5c0f\u5143\u7d20\n", "print(\"Pop:\", heapq.heappop(heap)) # \u2026\u518d\u4e0b\u4e00\u4e2a\u6700\u5c0f\u7684\n", "print(\"Heap after two pops:\", heap)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `heapq.heapify(L)` \u628a\u5217\u8868 L \u539f\u5730\u91cd\u6392\u6210\u5408\u6cd5\u7684\u5806 \u2014\u2014 \u8fd9\u4e00\u6b65\u662f O(n)\uff0c\u6bd4\u9010\u4e2a push \u8fdb\u53bb\u8981\u5feb\u3002`[expr for _ in range(n)]` \u8fd9\u79cd\u5217\u8868\u63a8\u5bfc\u5f0f\u7528\u6765\u751f\u6210\u65b0\u5217\u8868\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def heap_sort(items):\n", " h = list(items) # \u590d\u5236\u4e00\u4efd\uff0c\u907f\u514d\u4fee\u6539\u8c03\u7528\u8005\u7684\u5217\u8868\n", " heapq.heapify(h) # \u539f\u5730\u628a h \u53d8\u6210\u5806 \u2014\u2014 O(n)\n", " return [heapq.heappop(h) for _ in range(len(h))] # \u4f9d\u6b21 pop \u51fa\u6240\u6709\u5143\u7d20\n", "\n", "print(heap_sort([7, 3, 9, 1, 5, 2, 8, 4, 6]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \u7528\u5806\u6c42 Top-K\n", "\n", "\u56fa\u5b9a\u5927\u5c0f\u4e3a K \u7684\u5806\u662f\"\u7ed9\u6211\u6570\u636e\u6d41\u4e2d\u6700\u5927\u7684 K \u4e2a\u6570\"\u95ee\u9898\u7684\u6700\u4f73\u7ed3\u6784\u3002\n", "\u6bcf\u4e2a\u5143\u7d20\u90fd push \u8fdb\u53bb\uff1b\u4e00\u65e6\u5806\u8d85\u8fc7 K\uff0c\u5c31\u628a\u6700\u5c0f\u7684 pop \u51fa\u6765\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `random.seed(0)` \u8ba9\u968f\u673a\u7ed3\u679c\u53ef\u91cd\u73b0\u3002`random.randint(a, b)` \u8fd4\u56de `[a, b]` \u533a\u95f4\u5185\uff08\u542b\u4e24\u7aef\uff09\u7684\u968f\u673a\u6574\u6570\u3002`sorted(seq, reverse=True)` \u8fd4\u56de\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\u540e\u7684\u65b0\u5217\u8868\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "def top_k_largest(stream, k):\n", " heap = [] # \u7ef4\u62a4\"\u5f53\u524d top-k\"\u7684\u5c0f\u9876\u5806\n", " for x in stream:\n", " heapq.heappush(heap, x) # \u603b\u662f\u5148 push\n", " if len(heap) > k:\n", " heapq.heappop(heap) # \u8d85\u51fa K \u2192 \u4e22\u6389\u6700\u5c0f\u7684\n", " return sorted(heap, reverse=True) # \u8fd4\u56de\u4ece\u5927\u5230\u5c0f\n", "\n", "random.seed(0) # \u8ba9\u968f\u673a\u6d41\u53ef\u91cd\u73b0\n", "stream = [random.randint(1, 1000) for _ in range(50)]\n", "print(\"Top 5 largest:\", top_k_largest(stream, 5))\n", "print(\"Sanity check:\", sorted(stream, reverse=True)[:5])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5\uff1a**Python \u7684 `heapq` \u53ea\u652f\u6301\u5c0f\u9876\u5806\u3002\u8981\u5f53\u5927\u9876\u5806\u7528\uff0c\u5c31 push\n", "`-x`\uff0cpop \u65f6\u518d\u53d6\u53cd\u3002\u5199\u4e00\u4e2a\u51fd\u6570\u8fd4\u56de\u6570\u636e\u6d41\u4e2d*\u6700\u5c0f*\u7684 K \u4e2a\u6570\uff08\u8fd9\u6b21\n", "\u4f60\u4f1a\u60f3\u8981\u4e00\u4e2a\u5927\u9876\u5806\uff09\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. \u4e8c\u53c9\u641c\u7d22\u6811\n", "\n", "\u6bcf\u4e2a\u8282\u70b9\u90fd\u9075\u5b88\u540c\u4e00\u6761\u89c4\u5219\uff1a\u5de6\u5b50\u6811\u91cc\u90fd\u6bd4\u5b83\u5c0f\uff0c\u53f3\u5b50\u6811\u91cc\u90fd\u6bd4\u5b83\u5927\u3002\n", "\u67e5\u627e\u3001\u63d2\u5165\u3001\u5220\u9664\u90fd\u6cbf\u7740\u6811\u5f80\u4e0b\u8d70\u4e00\u6761\u8def\u5f84 \u2014\u2014 \u6811\u5e73\u8861\u65f6\u662f O(log n)\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `None` \u662f Python \u8868\u793a\u300c\u7a7a\u300d\u6216\u300c\u7f3a\u5931\u300d\u7684\u503c \u2014\u2014 \u6211\u4eec\u7528\u5b83\u8868\u793a\u7a7a\u5b50\u6811\u3002`if root is None` \u5c31\u662f\u68c0\u67e5\u5b83\u3002\u51fd\u6570\u53ef\u4ee5\u8c03\u7528\u81ea\u8eab\uff08\u9012\u5f52\uff09\u6765\u904d\u5386\u6811\u3002\u50cf `out=None` \u8fd9\u6837\u7684\u9ed8\u8ba4\u53c2\u6570\u53ea\u5728\u51fd\u6570*\u5b9a\u4e49*\u65f6\u6c42\u503c\u4e00\u6b21\uff0c\u6240\u4ee5\u53ef\u53d8\u9ed8\u8ba4\u503c\u7684\u5b89\u5168\u5199\u6cd5\u662f\u51fd\u6570\u91cc\u5199 `if out is None: out = []`\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Node:\n", " def __init__(self, key):\n", " self.key = key # \u8282\u70b9\u4e0a\u4fdd\u5b58\u7684\u503c\n", " self.left = None # \u5de6\u5b50\u6811\uff08None \u8868\u793a\u7a7a\uff09\n", " self.right = None # \u53f3\u5b50\u6811\n", "\n", "def insert(root, key):\n", " if root is None:\n", " return Node(key) # \u7a7a\u4f4d \u2014\u2014 \u5728\u8fd9\u91cc\u5efa\u8282\u70b9\n", " if key < root.key:\n", " root.left = insert(root.left, key) # \u6bd4\u5f53\u524d\u5c0f \u2192 \u5f80\u5de6\n", " elif key > root.key:\n", " root.right = insert(root.right, key) # \u6bd4\u5f53\u524d\u5927 \u2192 \u5f80\u53f3\n", " return root # \u76f8\u7b49 \u2192 \u6811\u91cc\u5df2\u7ecf\u6709\u4e86\n", "\n", "def search(root, key):\n", " if root is None or root.key == key:\n", " return root # \u6ca1\u627e\u5230\uff08None\uff09\u6216\u627e\u5230\u4e86\uff08\u8282\u70b9\u672c\u8eab\uff09\n", " if key < root.key:\n", " return search(root.left, key) # \u5c0f \u2192 \u5f80\u5de6\u9012\u5f52\n", " return search(root.right, key) # \u5927 \u2192 \u5f80\u53f3\u9012\u5f52\n", "\n", "def inorder(root, out=None):\n", " # \u4e2d\u5e8f\u904d\u5386\uff1a\u5148\u8bbf\u95ee\u5de6\u5b50\u6811\u3001\u518d\u8bbf\u95ee\u672c\u8282\u70b9\u3001\u6700\u540e\u8bbf\u95ee\u53f3\u5b50\u6811\u3002\n", " # \u5bf9 BST \u6765\u8bf4\uff0c\u8fd9\u6837\u8bbf\u95ee\u5230\u7684\u952e\u662f\u6709\u5e8f\u7684\u3002\n", " if out is None:\n", " out = [] # \u53ef\u53d8\u9ed8\u8ba4\u53c2\u6570\u7684\u5b89\u5168\u5199\u6cd5\n", " if root:\n", " inorder(root.left, out)\n", " out.append(root.key)\n", " inorder(root.right, out)\n", " return out\n", "\n", "root = None # \u4e00\u5f00\u59cb\u6811\u662f\u7a7a\u7684\n", "for k in [8, 3, 10, 1, 6, 14]:\n", " root = insert(root, k) # \u4f9d\u6b21\u63d2\u5165\u6bcf\u4e2a\u952e\n", "\n", "print(\"Search 6:\", search(root, 6) is not None) # True\n", "print(\"Search 7:\", search(root, 7) is not None) # False\n", "print(\"Inorder (should be sorted):\", inorder(root))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5\uff1a**\u628a `1, 2, 3, 4, 5, 6` *\u6309\u8fd9\u4e2a\u987a\u5e8f*\u63d2\u5165\u7a7a BST\uff0c\u7136\u540e\u8c03\u7528\n", "`inorder()`\u3002\u8f93\u51fa\u4f9d\u7136\u6709\u5e8f \u2014\u2014 \u4f46\u6811\u672c\u8eab\u9000\u5316\u6210\u4e86\u4e00\u6839\"\u68cd\u5b50\"\uff08\u6bcf\u4e2a\u8282\u70b9\n", "\u53ea\u6709\u53f3\u5b50\u8282\u70b9\uff09\u3002\u67e5\u627e\u53d8\u6210 O(n)\u3002\u8fd9\u5c31\u662f\u751f\u4ea7\u7cfb\u7edf\u4f7f\u7528\u81ea\u5e73\u8861\u53d8\u79cd\u7684\u539f\u56e0\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u7528\u7684\u662f\u4e0a\u9762\u5b9a\u4e49\u7684 `insert()` \u548c `inorder()`\u3002\u672c\u5355\u5143\u683c\u65b0\u4e1c\u897f\uff1a`while node:` \u53ea\u8981 `node` \u4e3a\u771f\u503c\uff08\u5373\u975e `None`\uff09\u5c31\u4e00\u76f4\u5faa\u73af\u3002`node.right` \u6cbf\u7740\u53f3\u6307\u9488\u8d70\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# \u6545\u610f\u6784\u9020\u7684\u63d2\u5165\u987a\u5e8f \u2014\u2014 \u6811\u9000\u5316\u6210\u94fe\u8868\u3002\n", "bad_root = None\n", "for k in [1, 2, 3, 4, 5, 6]:\n", " bad_root = insert(bad_root, k)\n", "\n", "# \u53ea\u6cbf\u7740\u53f3\u94fe\u8d70\u4e00\u904d\uff0c\u91cf\u4e00\u4e0b\u6df1\u5ea6\u3002\n", "depth = 0\n", "node = bad_root\n", "while node: # \u53ea\u8981\u6709\u8282\u70b9\u5c31\u7ee7\u7eed\n", " depth += 1\n", " node = node.right # \u6cbf\u53f3\u6307\u9488\u8d70\n", "print(f\"Tree depth: {depth} (6 \u4e2a\u8282\u70b9\u5e73\u8861\u65f6\u6df1\u5ea6\u7ea6 3)\")\n", "print(\"Inorder still works:\", inorder(bad_root))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 6. \u5e76\u67e5\u96c6\n", "\n", "\u7ef4\u62a4\u4e00\u5806\"\u5206\u7ec4\"\u3002`find(x)` \u544a\u8bc9\u4f60 x \u5728\u54ea\u4e2a\u7ec4\uff1b`union(x, y)` \u628a x \u7684\n", "\u7ec4\u548c y \u7684\u7ec4\u5408\u5e76\u3002\u52a0\u4e0a\u8def\u5f84\u538b\u7f29\u548c\u6309\u79e9\u5408\u5e76\uff0c\u6bcf\u4e2a\u64cd\u4f5c\u5728\u5b9e\u8df5\u4e2d\u57fa\u672c\u662f O(1)\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u8fd9\u91cc\u7684 `list(range(n))` \u751f\u6210 `[0, 1, 2, ..., n-1]` \u2014\u2014 \u6bcf\u4e2a\u5143\u7d20\u4e00\u5f00\u59cb\u90fd\u662f\u81ea\u5df1\u7684\u7236\u8282\u70b9\u3002`[0] * n` \u751f\u6210 n \u4e2a 0 \u7ec4\u6210\u7684\u5217\u8868\u3002`a, b = b, a` \u4e00\u884c\u5c31\u80fd\u4ea4\u6362\u4e24\u4e2a\u53d8\u91cf\u3002\u65b9\u6cd5\u4e4b\u95f4\u53ef\u4ee5\u901a\u8fc7 `self.\u65b9\u6cd5\u540d(...)` \u4e92\u76f8\u8c03\u7528\u3002\u51fd\u6570\u53ef\u4ee5\u8fd4\u56de `True` \u6216 `False` \u6765\u62a5\u544a\u6210\u529f\u4e0e\u5426\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class UnionFind:\n", " def __init__(self, n):\n", " self.parent = list(range(n)) # \u4e00\u5f00\u59cb\u6bcf\u4e2a\u5143\u7d20\u90fd\u662f\u81ea\u5df1\u7684\u6839\n", " self.rank = [0] * n # \u6811\u9ad8\u7684\u4e0a\u754c\n", "\n", " def find(self, x):\n", " # \u4e00\u8def\u5411\u4e0a\u627e\u5230\u6839\uff0c\u56de\u6765\u65f6\u628a\u8def\u5f84\u4e0a\u7684\u6240\u6709\u8282\u70b9\u76f4\u63a5\u8fde\u5230\u6839\uff08\u538b\u7f29\uff09\u3002\n", " if self.parent[x] != x:\n", " self.parent[x] = self.find(self.parent[x]) # \u8def\u5f84\u538b\u7f29\n", " return self.parent[x]\n", "\n", " def union(self, x, y):\n", " rx, ry = self.find(x), self.find(y)\n", " if rx == ry:\n", " return False # \u5df2\u7ecf\u5728\u540c\u4e00\u7ec4\u91cc\n", " # \u6309\u79e9\u5408\u5e76\uff1a\u8ba9\u77ee\u6811\u63a5\u5230\u9ad8\u6811\u4e0b\u9762\n", " if self.rank[rx] < self.rank[ry]:\n", " rx, ry = ry, rx # \u8ba9 rx \u6210\u4e3a\u66f4\u9ad8\uff08\u6216\u540c\u9ad8\uff09\u7684\u6839\n", " self.parent[ry] = rx # \u628a ry \u6302\u5230 rx \u4e0b\n", " if self.rank[rx] == self.rank[ry]:\n", " self.rank[rx] += 1 # \u4e24\u68f5\u540c\u9ad8 \u2192 \u5408\u5e76\u540e\u9ad8\u5ea6\u52a0 1\n", " return True\n", "\n", "uf = UnionFind(5) # 5 \u4e2a\u5143\u7d20\uff0c\u5168\u90e8\u5b64\u7acb\n", "uf.union(0, 1)\n", "uf.union(2, 3)\n", "uf.union(1, 2) # \u73b0\u5728 0,1,2,3 \u90fd\u5728\u540c\u4e00\u7ec4\n", "\n", "print(\"0 and 3 connected?\", uf.find(0) == uf.find(3)) # True\n", "print(\"0 and 4 connected?\", uf.find(0) == uf.find(4)) # False\n", "print(\"parent array:\", uf.parent) # \u770b\u770b\u538b\u7f29\u540e\u7684\u6811\u7ed3\u6784" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5 \u2014\u2014 \u7edf\u8ba1\u7ec4\u6570\u3002**\u7528\u5e76\u67e5\u96c6\u7edf\u8ba1\uff1a\u7ed9\u5b9a\u4e00\u7ec4\u597d\u53cb\u5173\u7cfb\uff0c\n", "\u6709\u591a\u5c11\u4e2a\u4e92\u76f8\u72ec\u7acb\u7684\u670b\u53cb\u5708\uff1f" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `{\u8868\u8fbe\u5f0f for x in \u53ef\u8fed\u4ee3\u5bf9\u8c61}` \u662f\u96c6\u5408\u63a8\u5bfc\u5f0f \u2014\u2014 \u8ddf\u5217\u8868\u63a8\u5bfc\u5f0f\u5f88\u50cf\uff0c\u4f46\u751f\u6210\u96c6\u5408\uff08\u65e0\u91cd\u590d\uff09\u3002\u6211\u4eec\u7528\u5b83\u6765\u6536\u96c6\u6240\u6709\u4e0d\u540c\u7684\u7ec4\u6839\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def count_groups(num_people, friendships):\n", " uf = UnionFind(num_people)\n", " for a, b in friendships: # \u6bcf\u5bf9\u597d\u53cb\u662f\u4e00\u4e2a (\u4eba a, \u4eba b)\n", " uf.union(a, b) # \u628a\u4e24\u4eba\u7684\u7ec4\u5408\u5e76\n", " roots = {uf.find(i) for i in range(num_people)} # \u4e0d\u540c\u6839\u7684\u96c6\u5408\n", " return len(roots)\n", "\n", "# 6 \u4e2a\u4eba\uff08\u7f16\u53f7 0..5\uff09\uff0c\u597d\u53cb\u5173\u7cfb\n", "friendships = [(0, 1), (1, 2), (3, 4)]\n", "# \u5206\u7ec4\uff1a{0,1,2}, {3,4}, {5} \u2192 3 \u4e2a\u72ec\u7acb\u7684\u7ec4\n", "print(f\"{count_groups(6, friendships)} separate groups\")" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }