Leetcode-100.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3026dbb6",
   "metadata": {},
   "source": [
    "# 快速排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "144590f8",
   "metadata": {},
   "outputs": [],
   "source": [
    ">>> sort() 就地排序\n",
    ">>> x=[8,9,0,7,4,5,1,2,3,6]\n",
    ">>> x.sort(reverse=Fasle)\n",
    "\n",
    ">>> sorted 另外开一个数组\n",
    ">>> x=[8,9,0,7,4,5,1,2,3,6]\n",
    ">>> y=sorted(x)\n",
    ">>> print(y) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "c3c9b47f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 66]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 快速排序\n",
    "def quick_sort(array, left, right):\n",
    "    if left >= right:\n",
    "        return\n",
    "    \n",
    "    low = left\n",
    "    high = right\n",
    "    key = array[low]\n",
    "    \n",
    "    while left < right:\n",
    "        while left < right and array[right] > key:\n",
    "            right -= 1\n",
    "        array[left] = array[right]\n",
    "        while left < right and array[left] < key:\n",
    "            left += 1\n",
    "        array[right] = array[left]\n",
    "        \n",
    "    array[right] = key\n",
    "    quick_sort(array, low, left - 1)\n",
    "    quick_sort(array, left + 1, high)\n",
    "    \n",
    "def quicksort(arr,left,right):\n",
    "    if left>=right:\n",
    "        return\n",
    "    \n",
    "    low = left\n",
    "    high = right\n",
    "    key = arr[left]\n",
    "    \n",
    "    while left<right:\n",
    "        while left<right and arr[right]>key:\n",
    "            right-=1\n",
    "        arr[left]=arr[right]\n",
    "        while left<right and arr[left]<key:\n",
    "            left+=1\n",
    "        arr[right]=arr[left]\n",
    "    \n",
    "    arr[right]=key\n",
    "    quicksort(arr,low,left-1)\n",
    "    quicksort(arr,left+1,high)\n",
    "        \n",
    "\n",
    "\n",
    "x=[8,9,0,7,4,5,1,66,2,3,6]\n",
    "quicksort(x,0,11-1)\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6224e005",
   "metadata": {},
   "source": [
    "# 自定义类实例排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "44937d20",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "百年孤独           \t59        \n",
      "云边有个小卖部        \t49        \n",
      "高等数学           \t19.9      \n",
      "\n",
      "=====\n",
      "高等数学           \t19.9      \n",
      "云边有个小卖部        \t49        \n",
      "百年孤独           \t59        \n",
      "\n",
      "=====\n"
     ]
    }
   ],
   "source": [
    "class Book(object):\n",
    "    def __init__(self, book_name, book_price):\n",
    "        self.book_name = book_name\n",
    "        self.book_price = book_price\n",
    "    \n",
    "    # 只是为了输出来展示结果，可写可不写\n",
    "    def __str__(self):\n",
    "        return \"{name:<15}\\t{price:<10}\".format(name=self.book_name, price=self.book_price)\n",
    "\n",
    "def show_book_list(book_list):\n",
    "    for book in book_list:\n",
    "        print(book)\n",
    "    print(\"\\n=====\")\n",
    "    \n",
    "b1 = Book(\"百年孤独\", 59)\n",
    "b2 = Book(\"云边有个小卖部\", 49)\n",
    "b3 = Book(\"高等数学\", 19.9)\n",
    "\n",
    "book_list = [b1, b2, b3]\n",
    "show_book_list(book_list)\n",
    "\n",
    "book_list_sort = sorted(book_list, key=lambda x:x.book_price, reverse=False)\n",
    "show_book_list(book_list_sort)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5674b0ac",
   "metadata": {},
   "source": [
    "# 拓扑排序，判断是否是有向无环图"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81a29a97",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在初始化时，维护一个入度列表，维护一个0入度节点的后缀邻接链表\n",
    "# 先做一个初始化，取出最初的0入度节点入队\n",
    "# 只要队列还有元素，就把他pop出来，同时修改其对应的后缀节点的入度，如果修改后的后缀节点变成0了，那么继续入队"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efdccb47",
   "metadata": {},
   "source": [
    "# 二分法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91d6365d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(array,n):\n",
    "    array.sort()#对数组进行排序\n",
    "    low = 0#开始下标\n",
    "    h = len(array) - 1#结束下标\n",
    "    while low <= h:\n",
    "        k = (low + h)//2\n",
    "        if array[k] < n:\n",
    "            low = k + 1\n",
    "        elif array[k] > n:\n",
    "            h = k -1\n",
    "        else:\n",
    "            return k#找到返回对应下标\n",
    "    return -1#找不到返回-1\n",
    "\n",
    "array = [i for i in range(1,1001,5)]#本身就是有序的数组\n",
    "print(search(array,816))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d9d160b",
   "metadata": {},
   "source": [
    "# Trick"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "120d2be3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# XOR\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            ans ^= nums[i]\n",
    "        return ans\n",
    "\n",
    "# bin调用\n",
    ">>>bin(10)\n",
    "'0b1010'\n",
    ">>> bin(20)\n",
    "'0b10100'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07af9eeb",
   "metadata": {},
   "source": [
    "# 滑动窗口"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d09a72a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:return 0\n",
    "        left = 0\n",
    "        lookup = set()\n",
    "        n = len(s)\n",
    "        max_len = 0\n",
    "        cur_len = 0\n",
    "        for i in range(n):\n",
    "            cur_len += 1\n",
    "            while s[i] in lookup:\n",
    "                lookup.remove(s[left])\n",
    "                left += 1\n",
    "                cur_len -= 1\n",
    "            if cur_len > max_len:max_len = cur_len\n",
    "            lookup.add(s[i])\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5aa6f71",
   "metadata": {},
   "source": [
    "# 双指针"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c68fb5a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 把数组所有的0移动到右边\n",
    "class Solution(object):\n",
    "    def moveZeroes(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: None Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        # 第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]\n",
    "        j = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]:\n",
    "                nums[j] = nums[i]\n",
    "                j += 1\n",
    "        # 非0元素统计完了，剩下的都是0了\n",
    "        # 所以第二次遍历把末尾的元素都赋为0即可\n",
    "        for i in xrange(j,len(nums)):\n",
    "            nums[i] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b55be8d",
   "metadata": {},
   "source": [
    "# 并查集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6bac1f3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "N=100\n",
    "Tree = [-1 for i in range(N)]\n",
    "\n",
    "def findRoot(x:int):\n",
    "    if(Tree[x]==-1):\n",
    "        return x\n",
    "    else:\n",
    "        tmp = findRoot(Tree[x])\n",
    "        Tree[x]=tmp\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3b61c6c",
   "metadata": {},
   "source": [
    "# hash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70281b72",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for each in nums:\n",
    "            if each in dic:\n",
    "                dic[each]+=1\n",
    "            else:\n",
    "                dic[each]=1\n",
    "        \n",
    "        for key in dic:\n",
    "            if dic[key]==1:\n",
    "                return key\n",
    "\n",
    "# for k,v in dict_1.items():\n",
    "#     print(k,\">>\",v)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50428a5f",
   "metadata": {},
   "source": [
    "# 栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75b7519f",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        lis = []\n",
    "        for each in s:\n",
    "            if each in {'(','[','{'}:\n",
    "                lis.append(each)\n",
    "                # print(lis)\n",
    "            else:\n",
    "                if lis != [] and each==')' and lis[-1]=='(':\n",
    "                    lis.pop()\n",
    "                    continue\n",
    "                elif lis != [] and each==']' and lis[-1]=='[':\n",
    "                    lis.pop()\n",
    "                    continue \n",
    "                elif lis != [] and each=='}' and lis[-1]=='{':\n",
    "                    lis.pop()\n",
    "                    continue\n",
    "                else:\n",
    "                    lis.append(each)\n",
    "                    break\n",
    "            \n",
    "        if lis==[]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "402a462a",
   "metadata": {},
   "source": [
    "# 堆"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "cb6a8974",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37\n"
     ]
    }
   ],
   "source": [
    "import heapq\n",
    "heap = [1,3,4,2,6,8,9]\n",
    "heapq.heapify(heap)\n",
    "# heap = [1,2,4,3,6,8,9]\n",
    "\n",
    "heap = [1,3,4,2,6,8,9]\n",
    "heapq.heappush(heap, 2)\n",
    "# heap = [1,3,4,2,6,8,9,2]\n",
    "\n",
    "heap = [1,3,4,2,6,8,9]\n",
    "# print(heap)\n",
    "heapq.heappop(heap)\n",
    "# print(heap)\n",
    "# heap = [3,2,4,9,6,8] #删除堆顶后将堆尾放到堆顶，然后下沉\n",
    "\n",
    "heap = [1,3,4,2,6,8,9]\n",
    "heapq.heapreplace(heap, 4)\n",
    "# heap = [3,2,4,4,6,8,9]#删除堆顶后将新元素放到堆顶，然后下沉\n",
    "\n",
    "heap = [1,3,4,2,6,8,9]\n",
    "result = heapq.nlargest (2, heap)\n",
    "heap = [1,3,4,2,6,8,9]\n",
    "result = heapq.nsmallest (2, heap)\n",
    "# result = [1,2]\n",
    "\n",
    "\n",
    "# 引申练习： 哈夫曼树\n",
    "\n",
    "# step 1: 建树\n",
    "# 忽略\n",
    "# step 2: 计算哈夫曼路径和\n",
    "\n",
    "Q=[1,2,2,5,9]\n",
    "heapq.heapify(Q)\n",
    "\n",
    "ans = 0\n",
    "while(len(Q)>1):\n",
    "    [a,b]=heapq.nsmallest(2,Q)\n",
    "    heapq.heappop(Q)\n",
    "    heapq.heappop(Q)\n",
    "    tmp = a+b\n",
    "    ans += tmp\n",
    "    heapq.heappush(Q,tmp)\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "917e1175",
   "metadata": {},
   "source": [
    "# 队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e170b215",
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([0, 1, 2, 3, 4])\n",
      "5\n",
      "False\n",
      "False\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "deque([])\n",
      "LIFO栈\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n",
      "get data = [1, 'HaiCoder']\n",
      "get data = [3, 'Python']\n",
      "get data = [40, 1024]\n"
     ]
    }
   ],
   "source": [
    "import queue\n",
    "\n",
    "#TODO: 普通FIFO队列\n",
    "Q = queue.Queue(maxsize=10)  \n",
    "#maxsize指定队列长度，默认为0。但值小于等于0时，表示队列大小无上限。\n",
    "\n",
    "for i in range(5):\n",
    "    Q.put(i)\n",
    "\n",
    "print(Q.queue)  #查看队列中所有元素\n",
    "print(Q.qsize())    #返回队列的大小\n",
    "print(Q.empty())    #判断队空\n",
    "print(Q.full())     #判断队满\n",
    "\n",
    "\n",
    "while not Q.empty():\n",
    "    print(Q.get())\n",
    "\n",
    "print(Q.queue)  #查看队列中所有元素\n",
    "\n",
    "#TODO: LIFO队列\n",
    "print(\"LIFO栈\")\n",
    "q = queue.LifoQueue()\n",
    " \n",
    "for i in range(5):\n",
    "    q.put(i)\n",
    " \n",
    "while not q.empty():\n",
    "    print(q.get())\n",
    "\n",
    "# 优先队列\n",
    "import queue\n",
    "q = queue.PriorityQueue()\n",
    "q.put([1, 'HaiCoder'])   # 1是级别最高的\n",
    "q.put([40, 1024])\n",
    "q.put([3, 'Python'])\n",
    "\n",
    "while not q.empty():  # 不为空时候执行\n",
    "    print(\"get data =\", q.get())\n",
    "    \n",
    "# deque\n",
    "# coding=utf-8\n",
    "import collections\n",
    " \n",
    " \n",
    "queue = collections.deque()\n",
    "queue.append('a')\n",
    "queue.append('b')\n",
    "queue.append('c')\n",
    "print(queue)\n",
    "queue.appendleft('A')\n",
    "queue.appendleft('B')\n",
    "print(queue)\n",
    "\n",
    "print(queue.pop())\n",
    "print(queue.popleft())\n",
    "print(queue)\n",
    "\n",
    "queue.insert(3, 'T')\n",
    "print(queue)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a4eddfc",
   "metadata": {},
   "source": [
    "# 链表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5de3796b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "        # 5. 标记val\n",
    "        while head:\n",
    "            # s = getattr(head, 's', None)  # 获取s属性\n",
    "            # if s:  # 判断s属性\n",
    "            if head.val == '1':\n",
    "                return True\n",
    "            # head.s = 1  # 添加s属性\n",
    "            head.val = '1'\n",
    "            head = head.next\n",
    "        return False\n",
    "    \n",
    "# 合并有序链表\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        start = ListNode(0)\n",
    "        pre = start\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                pre.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                pre.next = l2\n",
    "                l2 = l2.next\n",
    "            pre = pre.next\n",
    "        \n",
    "        if l1 is not None:\n",
    "            pre.next = l1\n",
    "        else:\n",
    "            pre.next = l2\n",
    "        \n",
    "        return start.next\n",
    "    \n",
    "# 找出链表相交节点\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        nodeA = headA\n",
    "        nodeB = headB\n",
    "        while(nodeA !=nodeB):\n",
    "            nodeA = nodeA.next if nodeA else headB\n",
    "            nodeB = nodeB.next if nodeB else headA\n",
    "        return nodeA\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "222c9227",
   "metadata": {},
   "source": [
    "# 图算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64ceec80",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Floyd最短路\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        for k in range(n):\n",
    "            if(ans[i][k]==-1 or ans[k][j]==-1) continue\n",
    "            if(ans[i][j]==-1 or ans[i][k]+ans[k][j]<ans[i][j]):\n",
    "                ans[i][j]=ans[i][k]+ans[k][j]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c780df8",
   "metadata": {},
   "source": [
    "# 树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6534fced",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        def in_order(r):\n",
    "            if r:\n",
    "                in_order(r.left)\n",
    "                res.append(r.val)\n",
    "                in_order(r.right)\n",
    "        in_order(root)\n",
    "        return res\n",
    "    \n",
    "# 子树交换\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        # 递归终止条件\n",
    "        if root == None:\n",
    "            return None\n",
    "        \n",
    "        # 将当前节点的左右子树交换\n",
    "        root.left, root.right = root.right, root.left\n",
    "        \n",
    "        # 递归左子树\n",
    "        self.invertTree(root.left)\n",
    "        # 递归右子树\n",
    "        self.invertTree(root.right)\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c785177",
   "metadata": {},
   "source": [
    "# 最小生成树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5de455e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# kruskal算法可以用并查集去解决\n",
    "# 思路：首先对边长进行排序，然后从最小边开始遍历，分析两端节点是否属于一个祖先，如果是一个祖先，则跳过这条边，否则加上这条边，同时修改祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f248969f",
   "metadata": {},
   "source": [
    "# 动态规划&贪心法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "745218df",
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'List' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Input \u001b[1;32mIn [30]\u001b[0m, in \u001b[0;36m<cell line: 13>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     10\u001b[0m         \u001b[38;5;28;01mreturn\u001b[39;00m s[n]\n\u001b[0;32m     12\u001b[0m \u001b[38;5;66;03m# 买卖股票\u001b[39;00m\n\u001b[1;32m---> 13\u001b[0m \u001b[38;5;28;01mclass\u001b[39;00m \u001b[38;5;21;01mSolution\u001b[39;00m:\n\u001b[0;32m     14\u001b[0m     \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mmaxProfit\u001b[39m(\u001b[38;5;28mself\u001b[39m, prices: List[\u001b[38;5;28mint\u001b[39m]) \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m>\u001b[39m \u001b[38;5;28mint\u001b[39m:\n\u001b[0;32m     15\u001b[0m         inf \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mint\u001b[39m(\u001b[38;5;241m1e9\u001b[39m)\n",
      "Input \u001b[1;32mIn [30]\u001b[0m, in \u001b[0;36mSolution\u001b[1;34m()\u001b[0m\n\u001b[0;32m     13\u001b[0m \u001b[38;5;28;01mclass\u001b[39;00m \u001b[38;5;21;01mSolution\u001b[39;00m:\n\u001b[1;32m---> 14\u001b[0m     \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mmaxProfit\u001b[39m(\u001b[38;5;28mself\u001b[39m, prices: \u001b[43mList\u001b[49m[\u001b[38;5;28mint\u001b[39m]) \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m>\u001b[39m \u001b[38;5;28mint\u001b[39m:\n\u001b[0;32m     15\u001b[0m         inf \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mint\u001b[39m(\u001b[38;5;241m1e9\u001b[39m)\n\u001b[0;32m     16\u001b[0m         minprice \u001b[38;5;241m=\u001b[39m inf\n",
      "\u001b[1;31mNameError\u001b[0m: name 'List' is not defined"
     ]
    }
   ],
   "source": [
    "# 爬梯子\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        s = [0 for i in range(n+1)]\n",
    "        if n==1 or n==2:\n",
    "            return n\n",
    "        s[1],s[2]=1,2\n",
    "        for i in range(3,n+1):\n",
    "            s[i]=s[i-1]+s[i-2]\n",
    "        return s[n]\n",
    "    \n",
    "# 买卖股票\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        inf = int(1e9)\n",
    "        minprice = inf\n",
    "        maxprofit = 0\n",
    "        for price in prices:\n",
    "            maxprofit = max(price - minprice, maxprofit)\n",
    "            minprice = min(price, minprice)\n",
    "        return maxprofit\n",
    "\n",
    "# 二进制bit位数\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        res = [0] * (num + 1)\n",
    "        for i in range(1, num + 1):\n",
    "            res[i] = res[i >> 1] + (i & 1)\n",
    "        return res\n",
    "\n",
    "    \n",
    "# 最长公共子序列\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "        m,n = len(text1),len(text2)\n",
    "        \n",
    "        total = []\n",
    "        for i in range(m+1):\n",
    "            total.append([0 for i in range(n+1)])\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,1+n):\n",
    "                if(text1[i-1]==text2[j-1]):\n",
    "                    total[i][j]=total[i-1][j-1]+1\n",
    "                else:\n",
    "                    total[i][j] = max(total[i-1][j],total[i][j-1])\n",
    "        \n",
    "        return total[m][n]\n",
    "    \n",
    "#最大连续子数组和\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        \n",
    "        dp = [nums[i] for i in range(n)]\n",
    "\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dp[i]=max(nums[i],nums[i]+dp[i-1])\n",
    "        \n",
    "        return max(dp)\n",
    "\n",
    "# 三角形的最小路径和\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        import copy\n",
    "        dp = copy.deepcopy(triangle)\n",
    "\n",
    "        lines = len(triangle)\n",
    "\n",
    "        for i in range(1,lines):\n",
    "            cols = len(triangle[i])\n",
    "            for j in range(cols):\n",
    "                if j==0:\n",
    "                    dp[i][j]+=dp[i-1][j]\n",
    "                elif j==cols-1:\n",
    "                    dp[i][j]+=dp[i-1][j-1]\n",
    "                else:\n",
    "                    # print(f\"i:{i} and j:{j}\")\n",
    "                    dp[i][j]+=min(dp[i-1][j-1],dp[i-1][j])\n",
    "        \n",
    "        # print(dp[lines-1])\n",
    "        return min(dp[lines-1])\n",
    "    \n",
    "# 最长上升子序列\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = []\n",
    "        for i in range(len(nums)):\n",
    "            dp.append(1)\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return max(dp)\n",
    "\n",
    "# 0-1背包，完全背包，多重背包\n",
    "\n",
    "# 0-1背包：物品n种，背包容量s，物品信息为list[i].w & list[i].v，每个东西只能被选择一次\n",
    "\n",
    "dp = [0 for i in range(s+1)]\n",
    "\n",
    "for i in range(1,n+1):\n",
    "    for j in range(s,list[i].w,-1):\n",
    "        dp[j]=max(dp[j],dp[j-list[i].w]+list[i].v)\n",
    "        \n",
    "# 完全背包：数量不限制，每种东西可以被多次选取\n",
    "for i in range(1,n+1):\n",
    "    for j in range(list[i].w, s+1):\n",
    "        dp[j]=max(dp[j],dp[j-list[i].w]+list[i].v)\n",
    "\n",
    "# 多重背包可以转化为0-1背包，每个东西的数量有限，并且这个数量可以用2进制优化来减少空间"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9538a74",
   "metadata": {},
   "source": [
    "# 搜索 DFS 深度优先搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a650981",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 二叉树最大深度\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        if root is None: \n",
    "            return 0 \n",
    "        else: \n",
    "            left_height = self.maxDepth(root.left) \n",
    "            right_height = self.maxDepth(root.right) \n",
    "            return max(left_height, right_height) + 1\n",
    "        \n",
    "# 两棵树是否相同\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        elif not p or not q:\n",
    "            return False\n",
    "        elif p.val != q.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "\n",
    "        \n",
    "# 树的最大直径100/104\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        if root is None: \n",
    "            return 0 \n",
    "        else: \n",
    "            left_height = self.maxDepth(root.left) \n",
    "            right_height = self.maxDepth(root.right) \n",
    "            return max(left_height, right_height) + 1 \n",
    "\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        import heapq\n",
    "        heap = []\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            left_depth = self.maxDepth(root.left)\n",
    "            right_depth = self.maxDepth(root.right)\n",
    "            if left_depth!=0 and right_depth!=0:\n",
    "                heap.append(-(left_depth+right_depth))    \n",
    "            heap.append(-(left_depth+right_depth))\n",
    "        heapq.heapify(heap)\n",
    "        return -heapq.heappop(heap)\n",
    "    \n",
    "#平衡二叉树\n",
    "class Solution:\n",
    "    def dfs(self,root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            left_height = self.dfs(root.left)+1\n",
    "            right_height = self.dfs(root.right)+1\n",
    "\n",
    "            ans = abs(left_height-right_height)\n",
    "            if ans>self.maxdiv:\n",
    "                self.maxdiv=ans\n",
    "\n",
    "            return max(left_height,right_height)\n",
    "\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.maxdiv = 0\n",
    "        self.dfs(root)\n",
    "        if self.maxdiv>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "# 合并二叉树\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:\n",
    "        if not t1:\n",
    "            return t2\n",
    "        if not t2:\n",
    "            return t1\n",
    "        \n",
    "        merged = TreeNode(t1.val + t2.val)\n",
    "        merged.left = self.mergeTrees(t1.left, t2.left)\n",
    "        merged.right = self.mergeTrees(t1.right, t2.right)\n",
    "        return merged\n",
    "    \n",
    "\n",
    "# 根据前序和中序得出后序，根据后续和中序得到前序亦然\n",
    "def ToPostOrder(Pre,InOrder):\n",
    "    length = len(Pre)\n",
    "    if length == 0:\n",
    "        return 0\n",
    "    root = Pre[0]　　#前序遍历的根节点\n",
    "    for i in range(length):　#循环找到中序遍历中根节点的位置\n",
    "        if root == InOrder[i]:\n",
    "            break\n",
    "    ToPostOrder(Pre[1:i+1],InOrder[0:i])　#递归，传入左子树的前序遍历序列和左子树的中序遍历序列\n",
    "    ToPostOrder(Pre[i+1:length],InOrder[i+1:length]) #递归，传入右子树的前序遍历序列和右子树的中旭遍历序列\n",
    "    print(root,end=\"\")　#输出根节点数据，在递归中，为左右子树的根\n",
    "    \n",
    "ToPostOrder(\"126745\",\"627154\")\n",
    "print(\"\\n\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8702af02",
   "metadata": {},
   "source": [
    "# 搜索 BFS 广度优先搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7430ea4",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            # 获取当前队列的长度，这个长度相当于 当前这一层的节点个数\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "            # 将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中\n",
    "            # 如果节点的左/右子树不为空，也放入队列中\n",
    "            for _ in range(size):\n",
    "                r = queue.pop(0)\n",
    "                tmp.append(r.val)\n",
    "                if r.left:\n",
    "                    queue.append(r.left)\n",
    "                if r.right:\n",
    "                    queue.append(r.right)\n",
    "            # 将临时list加入最终返回结果中\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}