Test.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-8-23-[1646.获取生成数组中的最大值](https://leetcode-cn.com/problems/get-maximum-in-generated-array/description/)\n",
    "- T1646.获取生成数组中的最大值\n",
    "- [获取生成数组中的最大值](https://leetcode-cn.com/problems/get-maximum-in-generated-array/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[None, None, None, None, None, None, None, None]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [None]*8\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "获取列表末尾元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [0, 1, 2, 3, 4, 5, 6]\n",
    "max(lst[-1], lst[-2]  )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "测试实例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 1, 2, 1, 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def getMaximumGenerated( n: int) -> int:\n",
    "    nums = [0]*(n+1)\n",
    "    nums[1] = 1\n",
    "    i = 2\n",
    "    while i < n+1:\n",
    "        if i%2 == 0:\n",
    "            nums[i] = nums[i//2]\n",
    "        else:\n",
    "            nums[i] = nums[i//2] + nums[i//2 + 1]\n",
    "        i += 1\n",
    "    print(nums)\n",
    "    return max(nums[-1], nums[-2], nums[-3])\n",
    "\n",
    "getMaximumGenerated(5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 三目运算符\n",
    "max_n = 2 if 2>1 else 1\n",
    "max_n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "转变成了一个求函数最大值的问题  \n",
    "最大值应该出现在倒数第1或第二个奇数索引处  \n",
    "貌似随着数组大小增大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-8-24-[787.K 站中转内最便宜的航班](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/description/)\n",
    "- [787-K 站中转内最便宜的航班](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/description/)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[inf, inf, inf, inf, inf, inf],\n",
       " [inf, inf, inf, inf, inf, inf],\n",
       " [inf, inf, inf, inf, inf, inf],\n",
       " [inf, inf, inf, inf, inf, inf]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 6\n",
    "k = 2\n",
    "f = [[float(\"inf\")] * n for _ in range(k + 2)]\n",
    "f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, inf, inf], [inf, 100, inf], [inf, inf, inf]]\n",
      "[[0, inf, inf], [inf, 100, inf], [inf, inf, inf]]\n",
      "[[0, inf, inf], [inf, 100, 500], [inf, inf, inf]]\n",
      "[[0, inf, inf], [inf, 100, 500], [inf, inf, inf]]\n",
      "[[0, inf, inf], [inf, 100, 500], [inf, inf, 200]]\n",
      "[[0, inf, inf], [inf, 100, 500], [inf, inf, 200]]\n",
      "[[0, inf, inf], [inf, 100, 500], [inf, inf, 200]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "200"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCheapestPrice(n, flights, src, dst, k: int) -> int:\n",
    "    f = [[float(\"inf\")] * n for _ in range(k + 2)]\n",
    "    f[0][src] = 0\n",
    "    for t in range(1, k + 2):\n",
    "        for j, i, cost in flights:\n",
    "            f[t][i] = min(f[t][i], f[t - 1][j] + cost)\n",
    "            print(f)\n",
    "    \n",
    "    ans = min(f[t][dst] for t in range(1, k + 2))\n",
    "    print(f)\n",
    "    return -1 if ans == float(\"inf\") else ans\n",
    "    \n",
    "n = 3\n",
    "flights = [[0,1,100],[1,2,100],[0,2,500]]\n",
    "src = 0\n",
    "dst = 2\n",
    "k = 1\n",
    "findCheapestPrice(n, flights, src, dst, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[inf, 100, 500]\n",
      "[inf, inf, 200]\n",
      "[inf, inf, 200]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "200"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCheapestPrice(n, flights, src, dst, k: int) -> int:\n",
    "    f = [float(\"inf\")] * n\n",
    "    f[src] = 0\n",
    "    ans = float(\"inf\")\n",
    "    for t in range(1, k + 2):\n",
    "        g = [float(\"inf\")] * n\n",
    "        for j, i, cost in flights:\n",
    "            g[i] = min(g[i], f[j] + cost)\n",
    "        f = g\n",
    "        print(f)\n",
    "        ans = min(ans, f[dst])\n",
    "    \n",
    "    print(f)\n",
    "    return -1 if ans == float(\"inf\") else ans\n",
    "\n",
    "n = 3\n",
    "flights = [[0,1,100],[1,2,100],[0,2,500]]\n",
    "src = 0\n",
    "dst = 2\n",
    "k = 1\n",
    "findCheapestPrice(n, flights, src, dst, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "# 2021-8-25-[797.所有可能的路径](https://leetcode-cn.com/problems/all-paths-from-source-to-target/description/)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试代码框架\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        return\n",
    "\n",
    "solution  = Solution()\n",
    "graph = [[1,2],[3],[3],[]]\n",
    "solution.allPathsSourceTarget(graph)\n",
    "\n",
    "# 示例输出: [0, 1, 3], [0, 2, 3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3]\n",
      "[0, 2, 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[0], [0]]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 尝试深度优先搜索\n",
    "def allPathsSourceTarget(graph):\n",
    "    ans = list()\n",
    "    stk = list()\n",
    "\n",
    "    def dfs(x: int):\n",
    "        if x == len(graph) - 1:\n",
    "            print(stk)\n",
    "            ans.append(stk)\n",
    "            return\n",
    "        \n",
    "        for y in graph[x]:\n",
    "            stk.append(y)\n",
    "            dfs(y)\n",
    "            stk.pop()\n",
    "    \n",
    "    stk.append(0)\n",
    "    dfs(0)\n",
    "    return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "graph = [[1,2],[3],[3],[]]\n",
    "allPathsSourceTarget(graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, [1, 2, 3]]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [1, 2, 3]\n",
    "lst[::-1]\n",
    "\n",
    "len(lst)\n",
    "\n",
    "# for t in range(len(lst) -1, -1, -1):\n",
    "#     print(t)\n",
    "\n",
    "lst[-1]\n",
    "\n",
    "lst[:]\n",
    "lst\n",
    "# lst.pop()\n",
    "lst.append(lst[:])\n",
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 1], [2, 3, 4]]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst1 = [[0, 1]]\n",
    "lst2 = [2, 3, 4]\n",
    "lst1.append(lst2[:])\n",
    "lst1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-8-26-[881.救生艇](https://leetcode-cn.com/problems/boats-to-save-people/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 尽可能多的让更多人坐两艘船\n",
    "def numRescueBoats(people, limit: int) -> int:\n",
    "    people.sort()\n",
    "    ans = 0\n",
    "    front = 0\n",
    "    back = len(people) - 1\n",
    "\n",
    "    while front <= back:\n",
    "        if people[front] + people[back] <= limit:\n",
    "            ans += 1\n",
    "            front += 1\n",
    "            back -= 1\n",
    "        else:\n",
    "            ans += 1\n",
    "            back -= 1\n",
    "\n",
    "    return ans\n",
    "\n",
    "people = [3,5,3,4]\n",
    "limit = 5\n",
    "numRescueBoats(people, limit)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-8-27-[295 数据流的中位数](https://leetcode-cn.com/problems/find-median-from-data-stream/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        return\n",
    "    \n",
    "    def addNum(self, num: int) -> None:\n",
    "        return\n",
    "\n",
    "    def findMedian(self) -> float:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.lst = list()\n",
    "\n",
    "    def addNum(self, num: int) -> None:\n",
    "        self.lst.append(num)\n",
    "        return\n",
    "\n",
    "\n",
    "    def findMedian(self) -> float:\n",
    "        lst = self.lst\n",
    "        lst.sort()\n",
    "        length = len(lst)\n",
    "        return  (lst[length//2] + lst[length//2-1]) / 2  if length % 2 == 0 \\\n",
    "            else lst[length//2]\n",
    "\n",
    "\n",
    "obj = MedianFinder()\n",
    "obj.addNum(1)\n",
    "obj.addNum(2)\n",
    "print(obj.findMedian())\n",
    "obj.addNum(3) \n",
    "print(obj.findMedian())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "from heapq import heappop, heappush\n",
    "\n",
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.queMin = list()\n",
    "        self.queMax = list()\n",
    "    \n",
    "    def addNum(self, num: int) -> None:\n",
    "        queMin_ = self.queMin\n",
    "        queMax_ = self.queMax\n",
    "\n",
    "        if not queMin_ or num <= -queMin_[0]:\n",
    "            heappush(queMin_, -num)\n",
    "            if len(queMax_) + 1 < len(queMin_):\n",
    "                heappush(queMax_, -heappop(queMin_))\n",
    "        else:\n",
    "            heappush(queMax_, num)\n",
    "            if len(queMax_) > len(queMin_):\n",
    "                heappush(queMin_, -heappop(queMax_))\n",
    "\n",
    "    def findMedian(self) -> float:\n",
    "        queMin_ = self.queMin\n",
    "        queMax_ = self.queMax\n",
    "\n",
    "        if len(queMin_) > len(queMax_):\n",
    "            return - queMin_[0]\n",
    "        else:\n",
    "            return (-queMin_[0] + queMax_[0]) / 2\n",
    "\n",
    "\n",
    "obj = MedianFinder()\n",
    "obj.addNum(1)\n",
    "obj.addNum(2)\n",
    "print(obj.findMedian())\n",
    "obj.addNum(3) \n",
    "print(obj.findMedian())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.5\n",
      "2.0\n"
     ]
    }
   ],
   "source": [
    "# 有序集合 + 双指针\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.nums = SortedList()\n",
    "        self.row = self.column = None\n",
    "        self.row_value = self.column_value = None\n",
    "\n",
    "    def addNum(self, num: int) -> None:\n",
    "        nums_ = self.nums\n",
    "\n",
    "        n = len(nums_)\n",
    "        nums_.add(num)\n",
    "\n",
    "        if n == 0:\n",
    "            self.row = self.column = 0\n",
    "        else:\n",
    "            # 模拟双指针，当 num 小于 self.row 或 self.column 指向的元素时，num 的加入会导致对应指针向右移动一个位置\n",
    "            if num < self.row_value:\n",
    "                self.row += 1\n",
    "            if num < self.column_value:\n",
    "                self.column += 1\n",
    "\n",
    "            if n & 1:\n",
    "                if num < self.row_value:\n",
    "                    self.row -= 1\n",
    "                else:\n",
    "                    self.column += 1\n",
    "            else:\n",
    "                if self.row_value < num < self.column_value:\n",
    "                    self.row += 1\n",
    "                    self.column -= 1\n",
    "                elif num >= self.column_value:\n",
    "                    self.row += 1\n",
    "                else:\n",
    "                    self.column -= 1\n",
    "                    self.row = self.column\n",
    "        \n",
    "        self.row_value = nums_[self.row]\n",
    "        self.column_value = nums_[self.column]\n",
    "\n",
    "    def findMedian(self) -> float:\n",
    "        return (self.row_value + self.column_value) / 2\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/shu-ju-liu-de-zhong-wei-shu-by-leetcode-ktkst/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "obj = MedianFinder()\n",
    "obj.addNum(1)\n",
    "obj.addNum(2)\n",
    "print(obj.findMedian())\n",
    "obj.addNum(3) \n",
    "print(obj.findMedian())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 & 4\n",
    "10 & 100\n",
    "0 & 1\n",
    "2 & 1\n",
    "4 & 1\n",
    "6 & 1\n",
    "8 & 1\n",
    "# 偶数 & 1 = 0\n",
    "# 奇数 & 1 = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.nums = SortedList()\n",
    "        self.row = self.column = None\n",
    "        self.row_value = self.column_value = None\n",
    "    \n",
    "    def addNum(self, num: int) -> None:\n",
    "        nums_ = self.nums\n",
    "\n",
    "        n = len(nums_)\n",
    "        nums_.add(num)\n",
    "\n",
    "        if n == 0:\n",
    "            self.row = self.column = 0\n",
    "        else:\n",
    "            if num < self.row_value:\n",
    "                self.row += 1\n",
    "            if num < self.column_value:\n",
    "                self.column += 1\n",
    "\n",
    "            if n & 1:\n",
    "                if num < self.row_value:\n",
    "                    self.row -= 1\n",
    "                else:\n",
    "                    self.column += 1\n",
    "                    \n",
    "\n",
    "\n",
    "    def findMedian(self) -> float:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "from sortedcontainers import SortedList\n",
    "\n",
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.nums = SortedList()\n",
    "    \n",
    "    def addNum(self, num: int) -> None:\n",
    "        nums_ = self.nums\n",
    "        nums_.add(num)\n",
    "\n",
    "    def findMedian(self) -> float:\n",
    "        nums_ = self.nums\n",
    "        n  = len(nums_)\n",
    "        return  nums_[n//2]  if n & 1 \\\n",
    "            else (nums_[n//2] + nums_[n//2-1]) / 2\n",
    "\n",
    "\n",
    "obj = MedianFinder()\n",
    "obj.addNum(1)\n",
    "obj.addNum(2)\n",
    "print(obj.findMedian())\n",
    "obj.addNum(3) \n",
    "print(obj.findMedian())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-8-28-[1480.一维数组的动态和](https://leetcode-cn.com/problems/running-sum-of-1d-array/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 6, 10]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 简单迭代\n",
    "def runningSum(nums):\n",
    "    ans = [nums[0]]\n",
    "    slider = nums[0]\n",
    "    for i in range(1, len(nums)):\n",
    "        slider += nums[i]\n",
    "        ans.append(slider)\n",
    "    return ans\n",
    "\n",
    "nums = [1,2,3,4]\n",
    "runningSum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 6, 10]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def runningSum(nums):\n",
    "    ans = [nums[0]]\n",
    "    slider = nums[0]\n",
    "    i = 1\n",
    "    while i < len(nums):\n",
    "        slider += nums[i]\n",
    "        ans.append(slider)\n",
    "        i += 1\n",
    "    return ans\n",
    "\n",
    "nums = [1,2,3,4]\n",
    "runningSum(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-8-29 [所有奇数长度子数组的和](https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/description/)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "for i in range(1, 2, 2):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [1, 2, 3]\n",
    "sum(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-8-30-[528.按权重随机选择](https://leetcode-cn.com/problems/random-pick-with-weight/description/)\n",
    "\n",
    "|  Category  |   Difficulty    | Likes | Dislikes |\n",
    "| :--------: | :-------------: | :---: | :------: |\n",
    "| algorithms | Medium (46.92%) |  116  |    -     |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试初始框\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self, w):\n",
    "        return\n",
    "\n",
    "    def pickIndex(self) -> int:\n",
    "        return\n",
    "\n",
    "solution  = Solution([1])\n",
    "solution.pickIndex()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试用例\n",
    "\n",
    "# 示例 2\n",
    "solution  = Solution([1, 3])\n",
    "solution.pickIndex()\n",
    "solution.pickIndex()\n",
    "solution.pickIndex()\n",
    "solution.pickIndex()\n",
    "solution.pickIndex()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "# 暴力解法\n",
    "# from random import random\n",
    "# class Solution:\n",
    "\n",
    "#     def __init__(self, w):\n",
    "#         self.w = w\n",
    "\n",
    "#     def pickIndex(self) -> int:\n",
    "#         w = self.w\n",
    "#         rand = random()\n",
    "#         gross = sum(w)\n",
    "#         subSum = 0\n",
    "#         if len(w) != 1:\n",
    "#             for i in range(len(w)-1):\n",
    "#                 if w[i+1]/gross + subSum > rand:\n",
    "#                     return i\n",
    "#                 else:\n",
    "#                     subSum += w[i]/gross\n",
    "#         else:\n",
    "#             return 0\n",
    "# 浮点运算用得太多了(\n",
    "\n",
    "solution  = Solution([1])\n",
    "print(solution.pickIndex())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.07442545428267267"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from random import random\n",
    "random()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<itertools.accumulate object at 0x0000026AA5F63700>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 3, 6, 10, 15]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import accumulate\n",
    "w = [1, 2, 3, 4, 5]\n",
    "pre = list(accumulate(w))\n",
    "pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import accumulate\n",
    "from bisect import bisect_row\n",
    "from random import randint\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self, w):\n",
    "        self.pre = list(accumulate(w))\n",
    "        self.total = sum(w)\n",
    "\n",
    "    def pickIndex(self) -> int:\n",
    "        x = randint(1, self.total)\n",
    "        return bisect_row(self.pre, x)\n",
    "\n",
    "solution  = Solution([1])\n",
    "solution.pickIndex()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-8-31-[1109.航班预订统计](https://leetcode-cn.com/problems/corporate-flight-bookings/description/)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试代码框架\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings, n: int):\n",
    "        return\n",
    "\n",
    "solution  = Solution()\n",
    "bookings = [[1,2,10],[2,3,20],[2,5,25]]\n",
    "n = 5\n",
    "solution.corpFlightBookings(bookings, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试数据集\n",
    "\n",
    "# 示例 1\n",
    "bookings = [[1,2,10],[2,3,20],[2,5,25]]\n",
    "n = 5\n",
    "#输出：[10,55,45,25,25]\n",
    "\n",
    "# 示例 2\n",
    "bookings = [[1,2,10],[2,2,15]]\n",
    "n = 2\n",
    "#输出：[10,25]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 55, 45, 25, 25]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 超时了\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings, n: int):\n",
    "        ans = [0] * n\n",
    "        for i, j, seats in bookings:\n",
    "            for k in range(i, j+1):\n",
    "                ans[k-1] += seats\n",
    "        return ans\n",
    "\n",
    "\n",
    "solution  = Solution()\n",
    "bookings = [[1,2,10],[2,3,20],[2,5,25]]\n",
    "n = 5\n",
    "solution.corpFlightBookings(bookings, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 55, 45, 25, 25]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 差分数组\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings, n: int):\n",
    "        ans = [0] * n\n",
    "        for i, j, seats in bookings:\n",
    "            ans[i-1] += seats\n",
    "            if j < n:\n",
    "                ans[j] -= seats \n",
    "        for i in range(1, n):\n",
    "            ans[i] += ans[i-1]\n",
    "        return ans\n",
    "\n",
    "\n",
    "solution  = Solution()\n",
    "bookings = [[1,2,10],[2,3,20],[2,5,25]]\n",
    "n = 5\n",
    "solution.corpFlightBookings(bookings, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 55, 45, 25, 25]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 库函数求累加和\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings, n: int):\n",
    "        ans = [0] * n\n",
    "        for i, j, seats in bookings:\n",
    "            ans[i-1] += seats\n",
    "            if j < n:\n",
    "                ans[j] -= seats \n",
    "        ans = list(accumulate(ans))\n",
    "        return ans\n",
    "\n",
    "\n",
    "solution  = Solution()\n",
    "bookings = [[1,2,10],[2,3,20],[2,5,25]]\n",
    "n = 5\n",
    "solution.corpFlightBookings(bookings, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [704.二分查找](https://leetcode-cn.com/problems/binary-search/description/)\n",
    "\n",
    "|  Category  |  Difficulty   | Likes | Dislikes |\n",
    "| :--------: | :-----------: | :---: | :------: |\n",
    "| algorithms | Easy (55.49%) |  336  |    -     |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        return\n",
    "\n",
    "solution  = Solution()\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 9\n",
    "print(solution.search(nums, target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 示例 1\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 9\n",
    "# 输出: 4\n",
    "# 解释: 9 出现在 nums 中并且下标为 4\n",
    "\n",
    "# 示例 2\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 2\n",
    "# 输出: -1\n",
    "# 解释: 2 不存在 nums 中因此返回 -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当前值为12\n",
      "12 > 2\n",
      "0 5\n",
      "当前值为3\n",
      "3 > 2\n",
      "0 2\n",
      "当前值为0\n",
      "0 < 2\n",
      "1 2\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        if nums[0] > target or nums[-1] < target:\n",
    "            return -1\n",
    "        if nums[0] == target:\n",
    "            return 0\n",
    "\n",
    "        row, column = 0, len(nums) - 1\n",
    "        ans = column\n",
    "        while nums[ans] != target and row < column - 1:\n",
    "            print(\"当前值为{0}\".format(nums[ans]))\n",
    "            if nums[ans] > target:\n",
    "                print(\"{0} > {1}\".format(nums[ans], target))\n",
    "                column = ans\n",
    "                ans = (row + column) // 2\n",
    "                print(row, column)\n",
    "            else:\n",
    "                print(\"{0} < {1}\".format(nums[ans], target))\n",
    "                row = ans\n",
    "                ans = (row + column) // 2\n",
    "                print(row, column)\n",
    "        return ans if nums[ans] == target else -1\n",
    "\n",
    "solution  = Solution()\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 2\n",
    "print(solution.search(nums, target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 删去输出语句\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        if nums[0] > target or nums[-1] < target:\n",
    "            return -1\n",
    "        if nums[0] == target:\n",
    "            return 0\n",
    "\n",
    "        row, column = 0, len(nums) - 1\n",
    "        ans = column\n",
    "        while nums[ans] != target and row < column - 1:\n",
    "            if nums[ans] > target:\n",
    "                column = ans\n",
    "                ans = (row + column) // 2\n",
    "            else:\n",
    "                row = ans\n",
    "                ans = (row + column) // 2\n",
    "        return ans if nums[ans] == target else -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Accepted  \n",
    "46/46 cases passed (32 ms)  \n",
    "Your runtime beats 94.75 % of python3 submissions  \n",
    "Your memory usage beats 5.06 % of python3 submissions (16.1 MB)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 官方写法\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        row, column = 0, len(nums) - 1\n",
    "        while row <= column:\n",
    "            pivot = row + (column - row) // 2\n",
    "            if nums[pivot] == target:\n",
    "                return pivot\n",
    "            if target < nums[pivot]:\n",
    "                column = pivot - 1\n",
    "            else: \n",
    "                row = pivot + 1\n",
    "        return -1\n",
    "\n",
    "# 作者：LeetCode\n",
    "# 链接：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Accepted   \n",
    "46/46 cases passed (36 ms)  \n",
    "Your runtime beats 83.59 % of python3 submissions  \n",
    "Your memory usage beats 60.25 % of python3 submissions (15.8 MB)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "# 2021-9-1-[165.比较版本号](https://leetcode-cn.com/problems/compare-version-numbers/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试代码\n",
    "class Solution:\n",
    "    def compareVersion(self, version1: str, version2: str) -> int:\n",
    "        return\n",
    "\n",
    "solution  = Solution()\n",
    "version1 = \"1.01\"\n",
    "version2 = \"1.001\"\n",
    "solution.compareVersion(version1, version2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试用例\n",
    "\n",
    "# 示例 1\n",
    "version1 = \"1.01\"\n",
    "version2 = \"1.001\"\n",
    "# 输出：0\n",
    "# 解释：忽略前导零，\"01\" 和 \"001\" 都表示相同的整数 \"1\"\n",
    "\n",
    "# 示例 2\n",
    "version1 = \"1.0\"\n",
    "version2 = \"1.0.0\"\n",
    "# 输出：0\n",
    "# 解释：version1 没有指定下标为 2 的修订号，即视为 \"0\"\n",
    "\n",
    "# 示例 3\n",
    "version1 = \"0.1\"\n",
    "version2 = \"1.1\"\n",
    "# 输出：-1\n",
    "# 解释：version1 中下标为 0 的修订号是 \"0\"，\n",
    "#       version2 中下标为 0 的修订号是 \"1\" 。0 < 1，\n",
    "#       所以 version1 < version2\n",
    "\n",
    "# 示例 4\n",
    "version1 = \"1.0.1\"\n",
    "version2 = \"1\"\n",
    "# 输出：1\n",
    "\n",
    "# 示例 5\n",
    "version1 = \"7.5.2.4\"\n",
    "version2 = \"7.5.3\"\n",
    "# 输出：-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 官方题解(字符串分割)\n",
    "from itertools import zip_longest\n",
    "class Solution:\n",
    "    def compareVersion(self, version1: str, version2: str) -> int:\n",
    "        for v1, v2 in zip_longest(version1.split('.'), version2.split('.'), fillvalue=0):\n",
    "            x, y = int(v1), int(v2)\n",
    "            if x != y:\n",
    "                return 1 if x > y else -1\n",
    "        return 0\n",
    "\n",
    "\n",
    "solution  = Solution()\n",
    "version1 = \"1.0.1\"\n",
    "version2 = \"1\"\n",
    "solution.compareVersion(version1, version2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Accepted  \n",
    "81/81 cases passed (24 ms)  \n",
    "Your runtime beats 97.69 % of python3 submissions  \n",
    "Your memory usage beats 98.3 % of python3 submissions (14.7 MB)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 失败\n",
    "class Solution:\n",
    "    def compareVersion(self, version1: str, version2: str) -> int:\n",
    "        lst1 = version1.split(\".\")\n",
    "        lst2 = version2.split(\".\")\n",
    "        lenLst2 = len(lst2)\n",
    "        lenLst1 = len(lst1)\n",
    "        if lenLst1 <= lenLst2:\n",
    "            addNum = lenLst2 - lenLst1\n",
    "            extendLst = [0] * addNum\n",
    "            lst1.extend(extendLst)\n",
    "        for i in range(lenLst2):\n",
    "            if int(lst1[i]) < int(lst2[i]):\n",
    "                return -1\n",
    "            elif int(lst1[i]) > int(lst2[i]):\n",
    "                return 1\n",
    "        return 0\n",
    "\n",
    "\n",
    "solution  = Solution()\n",
    "version1 = \"1.0.1\"\n",
    "version2 = \"1\"\n",
    "solution.compareVersion(version1, version2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '01']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "version1 = \"1.01\"\n",
    "version1.split(\".\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1, 2]\n",
    "b = [3, 4]\n",
    "\n",
    "a.extend(b)\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int('001')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-9-2-[剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'val: 4, next: ListNode {val: 5, next: None}'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class ListNode():\n",
    "    def __init__(self, val):\n",
    "        if isinstance(val,int):\n",
    "            self.val = val\n",
    "            self.next = None\n",
    "            \n",
    "        elif isinstance(val,list):\n",
    "            self.val = val[0]\n",
    "            self.next = None\n",
    "            cur = self\n",
    "            for i in val[1:]:\n",
    "                cur.next = ListNode(i)\n",
    "                cur = cur.next\n",
    "    \n",
    "    def gatherAttrs(self):\n",
    "        return \", \".join(\"{}: {}\".format(k, getattr(self, k)) for k in self.__dict__.keys())\n",
    "\n",
    "    def __str__(self):\n",
    "            return self.__class__.__name__+\" {\"+\"{}\".format(self.gatherAttrs())+\"}\"\n",
    "\n",
    "# 作者：娃哈哈店长\n",
    "# 链接：https://leetcode-cn.com/circle/article/s3RcOW/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:\n",
    "        node, n = head, 0  \n",
    "        while node:\n",
    "            node = node.next\n",
    "            n += 1\n",
    "\n",
    "        node = head\n",
    "        for _ in range(n-k):\n",
    "            node = node.next\n",
    "        \n",
    "        return node\n",
    "\n",
    "solution = Solution()\n",
    "head = ListNode([1,2,3,4,5])\n",
    "k = 2\n",
    "ans = solution.getKthFromEnd(head, k)\n",
    "ans.gatherAttrs()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "#### 2021-9-3-[面试题 17.14. 最小K个数](https://leetcode-cn.com/problems/smallest-k-lcci/)\n",
    "\n",
    "\n",
    "\n",
    "设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        return\n",
    "\n",
    "solution = Solution()\n",
    "arr =  [1,3,5,7,2,4,6,8]\n",
    "k = 4\n",
    "solution.smallestK(arr, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 排序\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        return arr[:k]\n",
    "\n",
    "solution = Solution()\n",
    "arr =  [1,3,5,7,2,4,6,8]\n",
    "k = 4\n",
    "solution.smallestK(arr, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 3, 1, 2]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 维护大根堆\n",
    "from typing import List\n",
    "from heapq import heappop, heappush, heapify\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return list()\n",
    "        \n",
    "        frontK = [-x for x in arr[:k]]\n",
    "        heapify(frontK)\n",
    "        for y in arr[k:]:\n",
    "            if -frontK[0] > y:\n",
    "                heappop(frontK)\n",
    "                heappush(frontK, -y)\n",
    "        ans = [-x for x in frontK]\n",
    "        return ans\n",
    "\n",
    "solution = Solution()\n",
    "arr =  [1,3,5,7,2,4,6,8]\n",
    "k = 4\n",
    "solution.smallestK(arr, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [1, 2, 3]\n",
    "lst[1:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-9-4-[剑指 Offer 10- I. 斐波那契数列](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 测试框架\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        ans = int()\n",
    "        return ans\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "n = 5\n",
    "solution.fib(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "front:0, back:1,ans:1\n",
      "front:1, back:1,ans:2\n",
      "front:1, back:2,ans:3\n",
      "front:2, back:3,ans:5\n",
      "front:3, back:5,ans:8\n",
      "front:5, back:8,ans:13\n",
      "front:8, back:13,ans:21\n",
      "front:13, back:21,ans:34\n",
      "front:21, back:34,ans:55\n",
      "front:34, back:55,ans:89\n",
      "front:55, back:89,ans:144\n",
      "front:89, back:144,ans:233\n",
      "front:144, back:233,ans:377\n",
      "front:233, back:377,ans:610\n",
      "front:377, back:610,ans:987\n",
      "front:610, back:987,ans:1597\n",
      "front:987, back:1597,ans:2584\n",
      "front:1597, back:2584,ans:4181\n",
      "front:2584, back:4181,ans:6765\n",
      "front:4181, back:6765,ans:10946\n",
      "front:6765, back:10946,ans:17711\n",
      "front:10946, back:17711,ans:28657\n",
      "front:17711, back:28657,ans:46368\n",
      "front:28657, back:46368,ans:75025\n",
      "front:46368, back:75025,ans:121393\n",
      "front:75025, back:121393,ans:196418\n",
      "front:121393, back:196418,ans:317811\n",
      "front:196418, back:317811,ans:514229\n",
      "front:317811, back:514229,ans:832040\n",
      "front:514229, back:832040,ans:1346269\n",
      "front:832040, back:1346269,ans:2178309\n",
      "front:1346269, back:2178309,ans:3524578\n",
      "front:2178309, back:3524578,ans:5702887\n",
      "front:3524578, back:5702887,ans:9227465\n",
      "front:5702887, back:9227465,ans:14930352\n",
      "front:9227465, back:14930352,ans:24157817\n",
      "front:14930352, back:24157817,ans:39088169\n",
      "front:24157817, back:39088169,ans:63245986\n",
      "front:39088169, back:63245986,ans:102334155\n",
      "front:63245986, back:102334155,ans:165580141\n",
      "front:102334155, back:165580141,ans:267914296\n",
      "front:165580141, back:267914296,ans:433494437\n",
      "front:267914296, back:433494437,ans:701408733\n",
      "front:433494437, back:701408733,ans:1134903170\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "134903163"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 迭代\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        front, back, ans = 0, 1, int()\n",
    "        for _ in range(n-1):\n",
    "            ans = front + back\n",
    "            print(\"front:{0}, back:{1},ans:{2}\".format(front, back, ans))\n",
    "            front = back\n",
    "            back = ans\n",
    "        \n",
    "        return ans % 1000000007\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "n = 45\n",
    "solution.fib(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "134903163"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 迭代过程中取模, 当计算当变得很大时, 不取模的话就要一直做两个大数加法运算了\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        front, back, ans, MOD = 0, 1, int(), 10 ** 9 + 7\n",
    "        for _ in range(n-1):\n",
    "            ans = (front + back) % MOD\n",
    "            front = back\n",
    "            back = ans\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "n = 45\n",
    "solution.fib(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-9-5-[470.用 Rand7() 实现 Rand10()](https://leetcode-cn.com/problems/implement-rand10-using-rand7/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return \n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "solution.rand10()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 拒绝采样\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            ans = (rand7() - 1) * 7 + rand7()\n",
    "            if ans <= 40:\n",
    "                return ans % 10 + 1\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "solution.rand10()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 进阶, 利用拒绝值优化调用次数\n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "            idx = (a - 1) * 7 + b\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "            a = idx - 40\n",
    "            b = rand7()\n",
    "            # get uniform dist from 1 - 63\n",
    "            idx = (a - 1) * 7 + b\n",
    "            if idx <= 60:\n",
    "                return 1 + (idx - 1) % 10\n",
    "            a = idx - 60\n",
    "            b = rand7()\n",
    "            # get uniform dist from 1 - 21\n",
    "            idx = (a - 1) * 7 + b\n",
    "            if idx <= 20:\n",
    "                return 1 + (idx - 1) % 10\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/yong-rand7-shi-xian-rand10-by-leetcode-s-qbmd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 2021-9-6-[704.二分查找](https://leetcode-cn.com/problems/binary-search/description/)\n",
    "\n",
    "> 这道题 8.31 做过了("
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        return\n",
    "\n",
    "solution  = Solution()\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 9\n",
    "print(solution.search(nums, target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 示例 1\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 9\n",
    "# 输出: 4\n",
    "# 解释: 9 出现在 nums 中并且下标为 4\n",
    "\n",
    "# 示例 2\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 2\n",
    "# 输出: -1\n",
    "# 解释: 2 不存在 nums 中因此返回 -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n"
     ]
    }
   ],
   "source": [
    "# 测试框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        row, column = 0, len(nums) - 1\n",
    "        while row <= column:\n",
    "            pivot = row + (column - row) // 2\n",
    "            if nums[pivot] == target:\n",
    "                return pivot\n",
    "            if target < nums[pivot]:\n",
    "                column = pivot - 1\n",
    "            else:\n",
    "                row = pivot + 1\n",
    "        return -1\n",
    "\n",
    "solution  = Solution()\n",
    "nums = [-1,0,3,5,9,12]\n",
    "target = 11\n",
    "print(solution.search(nums, target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [278.第一个错误的版本](https://leetcode-cn.com/problems/first-bad-version/description/)\n",
    "- 调用了自定义函数, 就不写测试了("
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [35.搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return\n",
    "\n",
    "solution  = Solution()\n",
    "nums = [1, 3, 5, 6]\n",
    "target = 5\n",
    "solution.searchInsert(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 二分查找\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        row, column = 0, len(nums) - 1\n",
    "        while row <= column:\n",
    "            p = row + ((column - row) >> 1)\n",
    "            if nums[p] < target:\n",
    "                row = p + 1\n",
    "            else:\n",
    "                column = p - 1\n",
    "        return row\n",
    "\n",
    "solution  = Solution()\n",
    "nums = [1, 3, 5, 6]\n",
    "target = 5\n",
    "solution.searchInsert(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "# 2021-9-7-[1221.分割平衡字符串](https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "class Solution:\n",
    "    def balancedStringSplit(self, s: str) -> int:\n",
    "        return\n",
    "\n",
    "solution  = Solution()\n",
    "s = \"RLRRRLLRLL\"\n",
    "solution.balancedStringSplit(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 贪心\n",
    "class Solution:\n",
    "    def balancedStringSplit(self, s: str) -> int:\n",
    "        ans, length, numR, numL = 0, len(s), 0, 0\n",
    "        for i in range(length):\n",
    "            if s[i] == 'R':\n",
    "                numR += 1\n",
    "            else:\n",
    "                numL += 1\n",
    "            if numR == numL:\n",
    "                ans += 1\n",
    "                numR, numL = 0, 0\n",
    "        return ans\n",
    "\n",
    "solution  = Solution()\n",
    "s = \"RLRRRLLRLL\"\n",
    "solution.balancedStringSplit(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 优化变量数目\n",
    "class Solution:\n",
    "    def balancedStringSplit(self, s: str) -> int:\n",
    "        ans, sp = 0, 0\n",
    "        for ch in s:\n",
    "            if ch == 'R':\n",
    "                sp += 1\n",
    "            else:\n",
    "                sp -= 1\n",
    "            if sp == 0:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "solution  = Solution()\n",
    "s = \"RLRRRLLRLL\"\n",
    "solution.balancedStringSplit(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "s = \"LLLLRRRR\"\n",
    "# start = time.time()\n",
    "# for ch in s:\n",
    "#     print(ch)\n",
    "# end = time.time()\n",
    "# print(\"运行时间\", end - start)\n",
    "# start1 = time.time()\n",
    "# # length = len(s)\n",
    "# for i in range(len(s)):\n",
    "#     print(s[i])\n",
    "# end1 = time.time()\n",
    "# print(\"运行时间\", end1 - start1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-9-8-[502.IPO](https://leetcode-cn.com/problems/ipo/description/)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        return\n",
    "\n",
    "\n",
    "k = 2\n",
    "w = 0\n",
    "profits = [1,2,3]\n",
    "capital = [0,1,1]\n",
    "solution = Solution()\n",
    "solution.findMaximizedCapital(k, w, profits, capital)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 官方题解:利用堆的贪心算法\n",
    "from typing import List\n",
    "import pandas\n",
    "from heapq import heappop, heappush, heapify\n",
    "\n",
    "class Solution:\n",
    "    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n",
    "        if w >= max(capital):\n",
    "            return w + sum(nlargest(k, profits))\n",
    "\n",
    "        n = len(profits)\n",
    "        curr = 0\n",
    "        arr = [(capital[i], profits[i]) for i in range(n)]\n",
    "        arr.sort(key = lambda x : x[0])\n",
    "        \n",
    "        pq = []\n",
    "        for _ in range(k):\n",
    "            while curr < n and arr[curr][0] <= w:\n",
    "                heappush(pq, -arr[curr][1])\n",
    "                curr += 1\n",
    "\n",
    "            if pq:\n",
    "                w -= heappop(pq)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return w\n",
    "\n",
    "\n",
    "k = 2\n",
    "w = 0\n",
    "profits = [1,2,3]\n",
    "capital = [0,1,1]\n",
    "solution = Solution()\n",
    "solution.findMaximizedCapital(k, w, profits, capital)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-9-9-[68.文本左右对齐](https://leetcode-cn.com/problems/text-justification/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        return\n",
    "\n",
    "\n",
    "words = [\"I\", \"Am\", \"Iron\", \"Man\"]\n",
    "maxWidth = 20\n",
    "solution = Solution()\n",
    "solution.fullJustify(words, maxWidth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['I Am Iron Man       ']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 官方题解\n",
    "from typing import List\n",
    "\n",
    "# blank 返回长度为 n 的由空格组成的字符串\n",
    "def blank(n: int) -> str:\n",
    "    return ' ' * n\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        ans = []\n",
    "        column, n = 0, len(words)\n",
    "        while True:\n",
    "            row = column  # 当前行的第一个单词在 words 的位置\n",
    "            sumLen = 0  # 统计这一行单词长度之和\n",
    "            # 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格\n",
    "            while column < n and sumLen + len(words[column]) + column - row <= maxWidth:\n",
    "                sumLen += len(words[column])\n",
    "                column += 1\n",
    "\n",
    "            # 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格\n",
    "            if column == n:\n",
    "                s = \" \".join(words[row:])\n",
    "                ans.append(s + blank(maxWidth - len(s)))\n",
    "                break\n",
    "\n",
    "            numWords = column - row\n",
    "            numSpaces = maxWidth - sumLen\n",
    "\n",
    "            # 当前行只有一个单词：该单词左对齐，在行末填充空格\n",
    "            if numWords == 1:\n",
    "                ans.append(words[row] + blank(numSpaces))\n",
    "                continue\n",
    "\n",
    "            # 当前行不只一个单词\n",
    "            avgSpaces = numSpaces // (numWords - 1)\n",
    "            extraSpaces = numSpaces % (numWords - 1)\n",
    "            s1 = blank(avgSpaces + 1).join(words[row:row + extraSpaces + 1])  # 拼接额外加一个空格的单词\n",
    "            s2 = blank(avgSpaces).join(words[row + extraSpaces + 1:column])  # 拼接其余单词\n",
    "            ans.append(s1 + blank(avgSpaces) + s2)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "words = [\"I\", \"Am\", \"Iron\", \"Man\"]\n",
    "maxWidth = 20\n",
    "solution = Solution()\n",
    "solution.fullJustify(words, maxWidth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-9-10-[1894.找到需要补充粉笔的学生编号](https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        return\n",
    "\n",
    "chalk = [3,4,1,2]\n",
    "k = 25\n",
    "solution = Solution()\n",
    "solution.chalkReplacer(chalk, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 模拟\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        ans, perResume = 0, sum(chalk)\n",
    "        chalk_row = k % perResume if k >= perResume else k\n",
    "        while chalk_row >= chalk[ans]:\n",
    "            chalk_row -= chalk[ans]\n",
    "            ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "chalk = [3,4,1,2]\n",
    "k = 25\n",
    "solution = Solution()\n",
    "solution.chalkReplacer(chalk, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试用例\n",
    "\n",
    "# 示例 1\n",
    "chalk = [5,1,5]\n",
    "k = 22\n",
    "# 输出：0\n",
    "\n",
    "# 示例 2\n",
    "chalk = [3,4,1,2]\n",
    "k = 25\n",
    "# 输出：1\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-9-11-[600.不含连续1的非负整数](https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 动态规划\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        dp = [0] * 31\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, 31):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(29, -1, -1):\n",
    "            val = (1 << i)\n",
    "            if n & val:\n",
    "                res += dp[i + 1]\n",
    "                if pre == 1:\n",
    "                    break\n",
    "                pre = 1\n",
    "            else:\n",
    "                pre = 0\n",
    "\n",
    "            if i == 0:\n",
    "                res += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/solution/bu-han-lian-xu-1de-fei-fu-zheng-shu-by-l-9l86/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-9-12-[678.有效的括号字符串](https://leetcode-cn.com/problems/valid-parenthesis-string/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试框架\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        return\n",
    "\n",
    "str = \"()\"\n",
    "solution = Solution()\n",
    "solution.checkValidString(str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 测试用例\n",
    "\n",
    "# 示例 1\n",
    "str = \"()\"\n",
    "# 输出: True\n",
    "\n",
    "# 示例 2\n",
    "str = \"(*)\"\n",
    "# 输出: True\n",
    "\n",
    "# 示例 3\n",
    "str = \"(*))\"\n",
    "# 输出: True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 贪心\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        maxCount, minCount = 0, 0\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                maxCount += 1\n",
    "                minCount += 1\n",
    "            elif ch == ')':\n",
    "                maxCount -= 1\n",
    "                if maxCount < 0:\n",
    "                    return False\n",
    "                minCount = 0 if minCount - 1 < 0 else minCount - 1\n",
    "            else:\n",
    "                maxCount += 1\n",
    "                minCount = 0 if minCount - 1 < 0 else minCount - 1\n",
    "        return minCount == 0\n",
    "\n",
    "s = \"()\"\n",
    "solution = Solution()\n",
    "solution.checkValidString(str)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-18-剑指 Offer 09. 用两个栈实现队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CQueue:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.lst = list()\n",
    "\n",
    "    def appendTail(self, value: int) -> None:\n",
    "        self.lst.append(value)\n",
    " \n",
    "    def deleteHead(self) -> int:\n",
    "        return self.lst.pop(0) if len(self.lst) > 0 else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Your CQueue object will be instantiated and called as such:\n",
    "# obj = CQueue()\n",
    "# obj.appendTail(value)\n",
    "# param_2 = obj.deleteHead()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# list.pop\n",
    "lst = [1, 2, 3]\n",
    "print(lst.pop(1))\n",
    "print(lst.pop(-1))\n",
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CQueue:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.lst = list()\n",
    "\n",
    "    def appendTail(self, value: int) -> None:\n",
    "        self.lst.append(value)\n",
    " \n",
    "    def deleteHead(self) -> int:\n",
    "        try:\n",
    "            return self.lst.pop(0)\n",
    "        except:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-18-剑指 Offer 30. 包含min函数的栈\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "class MinStack:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        initialize your data structure here.\n",
    "        \"\"\"\n",
    "        return\n",
    "\n",
    "    def push(self, x: int) -> None:\n",
    "        return\n",
    "\n",
    "    def pop(self) -> None:\n",
    "        return\n",
    "\n",
    "    def top(self) -> int:\n",
    "        return\n",
    "\n",
    "    def min(self) -> int:\n",
    "        return\n",
    "\n",
    "\n",
    "# Your MinStack object will be instantiated and called as such:\n",
    "# obj = MinStack()\n",
    "# obj.push(x)\n",
    "# obj.pop()\n",
    "# param_3 = obj.top()\n",
    "# param_4 = obj.min()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MinStack:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.lst = list()\n",
    "        self.min__lst = list()\n",
    "\n",
    "\n",
    "    def push(self, x: int) -> None:\n",
    "        self.lst.append(x)\n",
    "        if not self.min__lst or x <= self.min__lst[-1]:\n",
    "            self.min__lst.append(x)\n",
    "\n",
    "    def pop(self) -> None:\n",
    "        if self.min__lst[-1] == self.lst.pop(-1):\n",
    "            self.min__lst.pop(-1)\n",
    "\n",
    "    def top(self) -> int:\n",
    "        return self.lst[-1]\n",
    "\n",
    "    def min(self) -> int:\n",
    "        return self.min__lst[-1]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-18-剑指 Offer 06. 从尾到头打印链表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reversePrint(self, head: ListNode) -> List[int]:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 1]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 题中的 head 是 ListNode 不是 python list\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def reversePrint(self, head: List) -> List[int]:\n",
    "        return head[::-1]\n",
    "\n",
    "head = [1, 3, 2]\n",
    "solution = Solution()\n",
    "solution.reversePrint(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 1]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from typing import List\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "    def append(self, x:ListNode):\n",
    "        while self.next != None:\n",
    "            self = self.next\n",
    "        self.next = x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePrint(self, head: ListNode) -> List[int]:\n",
    "        lst = list()\n",
    "        while head != None:\n",
    "            lst.append(head.val)\n",
    "            head = head.next\n",
    "        return lst[::-1]\n",
    "\n",
    "head = ListNode(1)\n",
    "node1 = ListNode(3)\n",
    "node2 = ListNode(2)\n",
    "head.append(node1)\n",
    "head.append(node2)\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "solution.reversePrint(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 1]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 递归写法\n",
    "from typing import List\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "    def append(self, x:ListNode):\n",
    "        while self.next != None:\n",
    "            self = self.next\n",
    "        self.next = x\n",
    "\n",
    "class Solution:\n",
    "    def reversePrint(self, head: ListNode) -> List[int]:\n",
    "        if head == None:\n",
    "            return []\n",
    "        else:\n",
    "            lst = list(self.reversePrint(head.next))\n",
    "            if head != None:\n",
    "                lst.append(head.val)\n",
    "            return lst\n",
    "\n",
    "head = ListNode(1)\n",
    "node1 = ListNode(3)\n",
    "node2 = ListNode(2)\n",
    "head.append(node1)\n",
    "head.append(node2)\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "solution.reversePrint(head)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-19-[211. 添加与搜索单词 - 数据结构设计](https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "class WordDictionary:\n",
    "\n",
    "    def __init__(self):\n",
    "        return \n",
    "\n",
    "    def addWord(self, word: str) -> None:\n",
    "        return\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        return\n",
    "\n",
    "\n",
    "# Your WordDictionary object will be instantiated and called as such:\n",
    "# obj = WordDictionary()\n",
    "# obj.addWord(word)\n",
    "# param_2 = obj.search(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-19-[208. 实现 Trie (前缀树)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```C++\n",
    "#include<vector>\n",
    "#include<iostream>\n",
    "using namespace std;\n",
    "\n",
    "class Trie {\n",
    "private:\n",
    "    vector<Trie*> children;\n",
    "    bool isEnd;\n",
    "\n",
    "    /*从当前节点查找 prefix, 如果不能完整的查出则返回空指针, \n",
    "        否则返回最后一个字符所在的结点地址*/ \n",
    "    Trie* searchPrefix(string prefix) {\n",
    "        Trie* node = this;\n",
    "        for (char ch : prefix) {\n",
    "            ch -= 'a';\n",
    "            if (node->children[ch] == nullptr) {\n",
    "                return nullptr;\n",
    "            }\n",
    "            node = node->children[ch];\n",
    "        }\n",
    "        return node;\n",
    "    }\n",
    "\n",
    "public:\n",
    "    Trie() : children(26), isEnd(false) {}\n",
    "\n",
    "    /*从当前节点插入一个 word*/\n",
    "    void insert(string word) {\n",
    "        Trie* node = this;\n",
    "        for (char ch : word) {\n",
    "            ch -= 'a';\n",
    "            if (node->children[ch] == nullptr) node->children[ch] = new Trie();\n",
    "            node = node->children[ch];\n",
    "        }\n",
    "        node->isEnd = true;\n",
    "    }\n",
    "\n",
    "    /* 判断 word 是否在树种*/\n",
    "    bool search(string word) {\n",
    "        Trie* node = this->searchPrefix(word);\n",
    "        return node != nullptr && node->isEnd;\n",
    "    }\n",
    "\n",
    "    /*判断树中是否有以prefix为前缀的word*/\n",
    "    bool startsWith(string prefix) {\n",
    "        return this->searchPrefix(prefix) != nullptr;\n",
    "    }\n",
    "};\n",
    "\n",
    "\n",
    "\n",
    "int main() {\n",
    "    Trie tree = Trie();\n",
    "    tree.insert(\"apple\");\n",
    "    tree.search(\"apple\");\n",
    "    tree.search(\"app\");\n",
    "    tree.startsWith(\"app\");\n",
    "    tree.insert(\"app\");\n",
    "    tree.search(\"app\");\n",
    "    return 0;\n",
    "}\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-19-[剑指 Offer 12. 矩阵中的路径](https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/)\n",
    "\n",
    "注意：本题与[主站 79 题](https://leetcode-cn.com/problems/word-search/)相同：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        h, w = len(board), len(board[0])\n",
    "        visited = set()\n",
    "\n",
    "        def check(i: int, j: int, k: int) -> bool:\n",
    "            \"\"\"从 board[i, j] 出发寻找 word[k:]\n",
    "            \"\"\"\n",
    "            if board[i][j] != word[k]:\n",
    "                return False\n",
    "            if k == len(word) - 1:\n",
    "                return True\n",
    "            \n",
    "            visited.add((i, j))\n",
    "            result = False\n",
    "            for di, dj in directions:\n",
    "                newi, newj = i + di, j + dj\n",
    "                if 0 <= newi < len(board) and 0 <= newj < len(board[0]):\n",
    "                    if (newi, newj) not in visited:\n",
    "                        if check(newi, newj, k + 1):\n",
    "                            result = True\n",
    "                            break\n",
    "            \n",
    "            visited.remove((i, j))\n",
    "            return result\n",
    "\n",
    "\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if check(i, j, 0):\n",
    "                    return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "solution = Solution()\n",
    "board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\n",
    "word = \"ABCCED\"\n",
    "solution.exist(board, word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['a', 'b'], ['c', 'd']]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# DFS + 剪枝\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        def dfs(i, j, k):\n",
    "            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False\n",
    "            if k == len(word) - 1: return True\n",
    "            board[i][j] = ''\n",
    "            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)\n",
    "            board[i][j] = word[k]\n",
    "            return res\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if dfs(i, j, 0): return True\n",
    "\n",
    "        return False\n",
    "\n",
    "solution = Solution()\n",
    "board = [[\"a\",\"b\"],[\"c\",\"d\"]]\n",
    "word = \"abcd\"\n",
    "solution.exist(board, word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({'b', 'n', 'o', 'r', 'u'}, {'e', 'g', 'l', 'o'})"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = set('runoob')\n",
    "y = set('google')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-21-[剑指 Offer 35. 复杂链表的复制](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x20950154430>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# [哈希表](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-/)\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        cur = head\n",
    "        dic = dict()\n",
    "        while cur:\n",
    "            dic[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            dic[cur].next = dic.get(cur.next)\n",
    "            dic[cur].random = dic.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return dic[head]\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "node3 = Node(3)\n",
    "node2 = Node(3, node3, 0)\n",
    "head = Node(3, node2)\n",
    "solution.copyRandomList(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-22-[剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "class Solution:\n",
    "    def replaceSpace(self, s: str) -> str:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'We%20are%20happy.'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Solution:\n",
    "    def replaceSpace(self, s: str) -> str:\n",
    "        return s.replace(\" \", \"%20\")\n",
    "\n",
    "s = \"We are happy.\"\n",
    "solution = Solution()\n",
    "solution.replaceSpace(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-22-[剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "class Solution:\n",
    "    def reverserowWords(self, s: str, n: int) -> str:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cdefgab'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 字符串拼接\n",
    "class Solution:\n",
    "    def reverserowWords(self, s: str, n: int) -> str:\n",
    "        return s[n:] + s[:n]\n",
    "\n",
    "s = \"abcdefg\"\n",
    "k = 2\n",
    "solution = Solution()\n",
    "solution.reverserowWords(s, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-22-[剑指 Offer 03. 数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findRepeatNumber(self, nums: List[int]) -> int:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 字典查询\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findRepeatNumber(self, nums: List[int]) -> int:\n",
    "        dic = dict()\n",
    "        for i in nums:\n",
    "            if dic.get(i):  return i\n",
    "            dic[i] = 1\n",
    "\n",
    "nums = [2, 3, 1, 0, 2, 5, 3]\n",
    "solution = Solution()\n",
    "solution.findRepeatNumber(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 解法2 原地交换(让索引与值一一对应)(https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-yua/)\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findRepeatNumber(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if nums[i] == i: \n",
    "                i += 1\n",
    "                continue\n",
    "            if nums[nums[i]] == nums[i]:  return nums[i]\n",
    "            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]\n",
    "        return -1\n",
    "\n",
    "nums = [2, 3, 1, 0, 2, 5, 3]\n",
    "solution = Solution()\n",
    "solution.findRepeatNumber(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-23-[剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 二分查找 + 边界判断\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        length = len(nums)\n",
    "        row, column = 0, length - 1\n",
    "        while row <= column:\n",
    "            middle = (row + column) >> 1\n",
    "            if nums[middle] <= target:  row = middle + 1\n",
    "            else:  column = middle - 1\n",
    "        if row == 0:  return 0\n",
    "        if row == length and nums[length-1] != target:  return 0\n",
    "        row -= 1\n",
    "        num = 0\n",
    "        while row >= 0 and nums[row] == target:\n",
    "            num += 1\n",
    "            row -= 1\n",
    "        return num\n",
    "\n",
    "# nums = [5,7,7,8,8,10]\n",
    "# target = 8\n",
    "\n",
    "# nums = [5,7,7,8,8,10]\n",
    "# target = 6\n",
    "\n",
    "nums = [1]\n",
    "target = 1\n",
    "\n",
    "solution = Solution()\n",
    "solution.search(nums, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 3\n",
    "a >> 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 两次二分查找(https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/)\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        def binSearch(tar):\n",
    "            i, j = 0, len(nums) - 1\n",
    "            while i <= j:\n",
    "                m = (i + j) >> 1\n",
    "                if nums[m] <= tar: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return i\n",
    "        return binSearch(target) - binSearch(target - 1)\n",
    "\n",
    "nums = [5,7,7,8,8,10]\n",
    "target = 8\n",
    "\n",
    "# nums = [5,7,7,8,8,10]\n",
    "# target = 6\n",
    "\n",
    "# nums = [1]\n",
    "# target = 1\n",
    "\n",
    "solution = Solution()\n",
    "solution.search(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 两次二分查找(https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/)\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        def binSearch(tar):\n",
    "            i, j = 0, len(nums) - 1\n",
    "            while i <= j:\n",
    "                m = (i + j) >> 1\n",
    "                if nums[m] <= tar: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return i\n",
    "        a = binSearch(target)\n",
    "        b = binSearch(target - 1)\n",
    "        print(a, b)\n",
    "        return a-b\n",
    "\n",
    "nums = [5,6,6,8,8,10]\n",
    "target = 8\n",
    "\n",
    "# nums = [5,7,7,8,8,10]\n",
    "# target = 6\n",
    "\n",
    "# nums = [1]\n",
    "# target = 1\n",
    "\n",
    "solution = Solution()\n",
    "solution.search(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-23-[剑指 Offer 53 - II. 0～n-1中缺失的数字](https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return\n",
    "\n",
    "solution = Solution()\n",
    "nums1 = [0,1,3]\n",
    "nums2 = [0,1,2,3,4,5,6,7,9]\n",
    "solution.missingNumber(nums1)\n",
    "solution.missingNumber(nums2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 遍历列表建立访问表, 遍历访问表返回未访问到的索引\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        length = len(nums) + 1\n",
    "        visit = [0]*length\n",
    "        for i in nums:\n",
    "            visit[i] = 1\n",
    "        for i in range(length):\n",
    "            if not visit[i]:  return i\n",
    "\n",
    "solution = Solution()\n",
    "nums1 = [0,1,3]\n",
    "nums2 = [0,1,2,3,4,5,6,7,9]\n",
    "nums3 = [0]\n",
    "solution.missingNumber(nums1)\n",
    "solution.missingNumber(nums2)\n",
    "solution.missingNumber(nums3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 由于列表是有序的且没有重复值, 所以第一个索引和值对不上的就是不存在的数据\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            if nums[i] != i:\n",
    "                return i\n",
    "        return length\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "nums1 = [0,1,3]\n",
    "nums2 = [0,1,2,3,4,5,6,7,9]\n",
    "nums3 = [0]\n",
    "# solution.missingNumber(nums1)\n",
    "# solution.missingNumber(nums2)\n",
    "solution.missingNumber(nums3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 二分查找\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        row, column = 0, len(nums) - 1\n",
    "        while row <= column:\n",
    "            middle = (row + column) >> 1\n",
    "            if nums[middle] == middle:  row = middle + 1\n",
    "            else:  column = middle - 1\n",
    "        return row\n",
    "\n",
    "solution = Solution()\n",
    "nums1 = [0,1,3]\n",
    "nums2 = [0,1,2,3,4,5,6,7,9]\n",
    "nums3 = [0]\n",
    "# solution.missingNumber(nums1)\n",
    "solution.missingNumber(nums2)\n",
    "# solution.missingNumber(nums3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 二分法(https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/)\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if nums[m] == m: i = m + 1\n",
    "            else: j = m - 1\n",
    "        return i\n",
    "\n",
    "solution = Solution()\n",
    "nums1 = [0,1,3]\n",
    "nums2 = [0,1,2,3,4,5,6,7,9]\n",
    "nums3 = [0]\n",
    "solution.missingNumber(nums1)\n",
    "solution.missingNumber(nums2)\n",
    "solution.missingNumber(nums3)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2021-10-24-[中等-剑指 Offer 04. 二维数组中的查找](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 答题框架\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        return\n",
    "\n",
    "solution = Solution()\n",
    "matrix = [\n",
    "  [1,   4,  7, 11, 15],\n",
    "  [2,   5,  8, 12, 19],\n",
    "  [3,   6,  9, 16, 22],\n",
    "  [10, 13, 14, 17, 24],\n",
    "  [18, 21, 23, 26, 30]\n",
    "]\n",
    "target1 = 5\n",
    "target2 = 20\n",
    "solution.findNumberIn2DArray(matrix, target1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "横纵两个方向进行二分查找\n",
    "\n",
    "得, 方向错了步步错, 这玩意儿就没法二分, 问题在于不见得对角线递增速度比横纵方向快\n",
    "\n",
    "所以这题直接横纵方向遍历就行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2][2]\n",
      "[3][3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:  return False\n",
    "        if not matrix[0]: return False\n",
    "        row_len, column_len = len(matrix), len(matrix[0])\n",
    "        row_front, column_front = 0, 0\n",
    "        row_back, column_back = row_len-1, column_len-1\n",
    "        while row_front < row_back and column_front < column_back:\n",
    "            for i in range(row_front, row_len):\n",
    "                if matrix[i][column_front] == target:  return True\n",
    "            for i in range(column_front, column_len):\n",
    "                if matrix[row_front][i] == target:  return True\n",
    "            row_middle = (row_front+row_back) >> 1\n",
    "            column_middle = (column_front+column_back) >> 1\n",
    "            print(\"[{0}][{1}]\".format(row_middle, column_middle))\n",
    "            if matrix[row_middle][column_middle] < target:\n",
    "                for i in range(row_middle+1, row_len):\n",
    "                    if matrix[i][column_middle] == target:\n",
    "                        return True\n",
    "                for i in range(column_middle+1, column_len):\n",
    "                    if matrix[row_middle][i] == target:\n",
    "                        return True\n",
    "                row_front, column_front = row_middle+1, column_middle+1\n",
    "            elif matrix[row_middle][column_middle] == target:\n",
    "                return True\n",
    "            else:\n",
    "                row_back = row_middle\n",
    "                column_back = column_middle\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "matrix1 = [\n",
    "  [1,   4,  7, 11, 15],\n",
    "  [2,   5,  8, 12, 19],\n",
    "  [3,   6,  9, 16, 22],\n",
    "  [10, 13, 14, 17, 24],\n",
    "  [18, 21, 23, 26, 30]\n",
    "]\n",
    "target1 = 5\n",
    "target2 = 20\n",
    "target3 = 15\n",
    "target4 = 12\n",
    "\n",
    "matrix2 = []\n",
    "target21 = 0\n",
    "\n",
    "matrix3 = [[]]\n",
    "target31 = 1\n",
    "\n",
    "matrix4 = [[-5]]\n",
    "target41 = -2\n",
    "\n",
    "matrix5 = [[1, 3, 5]]\n",
    "target51 = 1\n",
    "\n",
    "# solution.findNumberIn2DArray(matrix1, target1)\n",
    "# solution.findNumberIn2DArray(matrix1, target2)\n",
    "# solution.findNumberIn2DArray(matrix2, target21)\n",
    "# solution.findNumberIn2DArray(matrix3, target31)\n",
    "# solution.findNumberIn2DArray(matrix4, target41)\n",
    "# solution.findNumberIn2DArray(matrix5, target51)\n",
    "solution.findNumberIn2DArray(matrix1, target4)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:  return False\n",
    "        if not matrix[0]: return False\n",
    "        row_len, column_len = len(matrix), len(matrix[0])\n",
    "        row_front, column_front = 0, 0\n",
    "        row_back, column_back = row_len-1, column_len-1\n",
    "        while row_front <= row_back and column_front <= column_back:\n",
    "            row_middle = (row_front+row_back) >> 1\n",
    "            column_middle = (column_front+column_back) >> 1\n",
    "            if matrix[row_middle][column_middle] < target:\n",
    "                for i in range(row_middle+1, row_len):\n",
    "                    if matrix[i][column_middle] == target:\n",
    "                        return True\n",
    "                for i in range(column_middle+1, column_len):\n",
    "                    if matrix[row_middle][i] == target:\n",
    "                        return True\n",
    "                row_front, column_front = row_middle+1, column_middle + 1\n",
    "            elif matrix[row_middle][column_middle] == target:\n",
    "                return True\n",
    "            else:\n",
    "                if row_middle != 0:\n",
    "                    row_back= row_middle - 1\n",
    "                if column_middle != 0:\n",
    "                    column_back = column_middle - 1\n",
    "                if row_middle  == 0 and column_middle == 0:\n",
    "                    print(\"get\")\n",
    "                    for i in range(1, row_len):\n",
    "                        if matrix[i][0] == target:\n",
    "                            return True\n",
    "                    for i in range(1, column_len):\n",
    "                        if matrix[0][i] == target:\n",
    "                            return True\n",
    "                    return False\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "matrix1 = [\n",
    "  [1,   4,  7, 11, 15],\n",
    "  [2,   5,  8, 12, 19],\n",
    "  [3,   6,  9, 16, 22],\n",
    "  [10, 13, 14, 17, 24],\n",
    "  [18, 21, 23, 26, 30]\n",
    "]\n",
    "target1 = 5\n",
    "target2 = 20\n",
    "target3 = 15\n",
    "\n",
    "matrix2 = []\n",
    "target21 = 0\n",
    "\n",
    "matrix3 = [[]]\n",
    "target31 = 1\n",
    "\n",
    "matrix4 = [[-5]]\n",
    "target41 = -2\n",
    "\n",
    "matrix5 = [[1, 3, 5]]\n",
    "target51 = 1\n",
    "\n",
    "# solution.findNumberIn2DArray(matrix1, target1)\n",
    "# solution.findNumberIn2DArray(matrix1, target2)\n",
    "# solution.findNumberIn2DArray(matrix2, target21)\n",
    "# solution.findNumberIn2DArray(matrix3, target31)\n",
    "# solution.findNumberIn2DArray(matrix4, target41)\n",
    "# solution.findNumberIn2DArray(matrix5, target51)\n",
    "solution.findNumberIn2DArray(matrix1, target3)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[\"二叉搜索树\"](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/)\n",
    "\n",
    "将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树 ，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target 。\n",
    "\n",
    "![Picture1.png](http://cdn.ayusummer233.top/img/202110241023219.png)\n",
    "\n",
    "- 时间复杂度 $O(M+N)$ ：其中，NN 和 MM 分别为矩阵行数和列数，此算法最多循环 M+NM+N 次。\n",
    "- 空间复杂度 $O(1)$ : i, j 指针使用常数大小额外空间。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 二叉搜索树(https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/)\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i, j = len(matrix) - 1, 0\n",
    "        while i >= 0 and j < len(matrix[0]):\n",
    "            if matrix[i][j] > target: i -= 1\n",
    "            elif matrix[i][j] < target: j += 1\n",
    "            else: return True\n",
    "        return False\n",
    "\n",
    "solution = Solution()\n",
    "matrix1 = [\n",
    "  [1,   4,  7, 11, 15],\n",
    "  [2,   5,  8, 12, 19],\n",
    "  [3,   6,  9, 16, 22],\n",
    "  [10, 13, 14, 17, 24],\n",
    "  [18, 21, 23, 26, 30]\n",
    "]\n",
    "target1 = 5\n",
    "target2 = 20\n",
    "target3 = 15\n",
    "target4 = 12\n",
    "\n",
    "\n",
    "# solution.findNumberIn2DArray(matrix1, target1)\n",
    "# solution.findNumberIn2DArray(matrix1, target2)\n",
    "solution.findNumberIn2DArray(matrix1, target4)\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "be333bfaf4b40d9f2128eb06ccf81a284655b9f6c456fc22510d92c5f9e0d280"
  },
  "kernelspec": {
   "display_name": "Python 3.8.5 64-bit ('base': conda)",
   "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.8.5"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}