​ 第三篇偏向于进阶算法，

基础

算法的时间复杂度

时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

求解算法时间复杂度的方法

1.找到算法中执行次数最多的语句

​ 算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

2.计算基本语句的执行次数的数量级；

​ 只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

3.用大Ο记号表示算法的时间性能。

​ 将基本语句执行次数的数量级放入大Ο记号中。

常见算法时间复杂度的大小：***\Ο(1)＜Ο(log*2n*)＜Ο(n)＜Ο(nlog\2n)＜Ο(*n*2)＜Ο(\n\3)＜…＜Ο(\2\n)＜Ο(n!)****

算法的空间复杂度

​ 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

​ 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

​ 当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量

空间换时间 时间换空间

常见复杂度

遍历二叉树节点的复杂度：O(N)

编程语言

js

遍历对象使用charAt方法

var s = new String('abc');

s.charAt(1) // "b"
s.charAt(s.length - 1) // "c"

js遍历数组时，一般不使用forEach语法，一般会希望符合某种条件时，就中断遍历，要使用for循环。

for (var i = 0; i < arr.length; i++) {
  if (arr[i] === 2) break;
  console.log(arr[i]);
}
//1

动态规划

动态规划经典问题：0-1背包问题

问题描述：

给你一个可装载重量为W的背包和N个物品，每个物品都有重量和价值两个属性，其中第i个物品的重量为wt(i),价值为val(i),现在用背包装物品，最多能装的价值是多少

举例：可装载重量为4，有3个物品，重量分别为2，1，3，价值分别为4，2，3，则可获得最大价值为6

动态规划经典问题：子集背包问题

动态规划经典问题：完全背包问题

动态规划经典问题：高楼扔鸡蛋问题887. 鸡蛋掉落

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

例：输入：k = 1, n = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 如果它没碎，那么肯定能得出 f = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [0] * (k + 1)
        m = 0
        while dp[k] < n:
            m += 1
            for i in range(k, 0, -1):
                # print(m, k)
                dp[i] = dp[i - 1] + dp[i] + 1
        return m

练习：凑硬币问题

不同路径62

给出一个m*n的地图，一个机器人位于左上角，想到达右下角，只能走右边或者下边，有多少种方式

class Solution:
   def uniquePaths(self,m:int,n:int)->int:
       dp = [[0]*n for _ in range(m)]
       for i in range(m)
           dp[i][0] = 1
       for i in range(n)
           dp[0][i] = 1
       for i in range(1,m)
           for j in range(1,n)
               dp[i][j] = dp[i][j-1] + dp[i-1][j]
       return dp[m-1][n-1]

不同路径63

最小路径和64

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

输出：7 路径为1->3->1->1->1，总和最小

输入：grid = [[1,2,3],[4,5,6]]

输出：12 路径为1-2-3-6

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dp = [[0] * len(grid[0])] * len(grid)
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i > 0 and j > 0:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
                elif i > 0:
                    dp[i][j] = dp[i - 1][j] + grid[i][j]
                elif j > 0:
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                else:
                    dp[i][j] = grid[i][j]
        return dp[-1][-1]

分割回文串132

给定字符串s，将s分割为子串，每个子串都是回文序列，返回最少的分割次数

例：输入：“aab”

输出：1

class Solution:
   def minCut(self,s:str)->int:
       if s == s[::-1]:
          return 0
       
       for i in range(1,len(s)+1);
           if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]
              return 1
       
       dp[i-1 for i in range(len(s)+1)]
       for i in range(1,len(s)+1):
           for j in range(i)
               if s[j:i] == s[i:j][::-1]
                  dp[i] = min(dp[i],dp[j]+1)
       return dp[-1]

三角形最小路径和(120)

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)#三角形行数
        if n==1: return triangle[0][0]
        dp = [[0]*n for i in range(n)]
        
        for i in range(n-1,-1,-1):
            for j in range(len(triangle[i])):
                if i==n-1:
                    dp[i][j]=triangle[i][j]
                else:
                    dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]#(i,j)到达最后一行的最小路径 = min((i+1,j), (i+1,j+1))+triangle[i][j]
        return dp[0][0]

零钱兑换(322)

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

例：输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3 输出：-1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
      	res = [0 for _ in range(amount + 1)]
        
        for i in range(1, amount + 1):
            cost = float('inf')
            for c in coins:
                if i - c >= 0:
                    cost = min(cost, res[i - c] + 1)
            res[i] = cost
        
        if res[amount] == float('inf'):
            return -1
        else:
            return res[amount]

打家劫舍198

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

例：输入：[1,2,3,4]

输出：4,偷窃1号房和3号房

设f为当前的收益，一个房间抢不抢取决于相邻的值：如果抢，则f[i]=nums[i]+f[i-2];如果不抢，则f[i]=f[i-1]

dp[i] = max(dp[i-1], dp[i-2] + nums[i]);

最后是边界处理，dp[0],dp[1] dp[0]为nums[0]。 dp[1]为max(nums[1], nums[0])

class Solution:
    def rob(self, nums: List[int]) -> int:
        n=len(nums)
        if n==0:return 0
        if n==1:return nums[0]
        if n==2:return max(nums[0],nums[1])
        
        dp=[0]*n
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        
        for i in range(2,n):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        
        return dp[-1]

打家劫舍2 213

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

class Solution:
    def rob(self, nums: List[int]) -> int:
      if (n := len(nums)) == 0:
        return 0
      if n == 1:
        return nums[0]
      result1 = self.robRange(nums, 0, n - 2)
      result2 = self.robRange(nums, 1, n - 1)
      return max(result1 , result2)

    def robRange(self, nums: List[int], start: int, end: int) -> int:
      if end == start: return nums[start]
      dp = [0] * len(nums)
      dp[start] = nums[start]
      dp[start + 1] = max(nums[start], nums[start + 1])
      for i in range(start + 2, end + 1):
        dp[i] = max(dp[i -2] + nums[i], dp[i - 1])
      return dp[end]

打家劫舍3 337

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

例：输入: [3,2,3,null,3,null,1]

输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

class Solution:
    def rob(self, root: TreeNode) -> int:
        if root is None:
            return 0
        if root.left is None and root.right  is None:
            return root.val
        # 偷父节点
        val1 = root.val
        if root.left:
            val1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val1 += self.rob(root.right.left) + self.rob(root.right.right)
        # 不偷父节点
        val2 = self.rob(root.left) + self.rob(root.right)
        return max(val1, val2)

最长公共前缀14

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

如输入：strs = ["flower","flow","flight"]

输出：["fl"]

横向扫描：默认将第一个字符串当成默认的prefix，扫描后面的字符串，不过不匹配就减少字符，再进行匹配

全部匹配完，返回空或者prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # If null return ""
        if len(strs) == 0:
            return ""

        prefix = strs[0]

        for i in range(1, len(strs)):
            while(strs[i].find(prefix) != 0):
                prefix = prefix[:-1]
                if len(prefix) == 0:
                    return ""

        return prefix

也可以纵向扫描，对比strs[0][i]

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
				if len(strs) == 0:
            return ""

        for i in range(len(strs[0])):
            for j in range(1, len(strs)):
                if i == len(strs[j]) or strs[0][i] != strs[j][i]: # i==len must be put at the front
                    return strs[0][:i]

        return strs[0]

最长公共子序列1143

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

例：输入：text1="abcde",text2="ace"

输出：3

dp动态规划。一维数组

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1, n2 = len(text1), len(text2)
        pre = [0 for _ in range(n2 + 1)]
        dp = [0 for _ in range(n2 + 1)]
        for i in range(n1):
            for j in range(1, n2 + 1):
                if text1[i] == text2[j-1]:
                    dp[j] = pre[j-1] + 1
                else:
                    dp[j] = max(pre[j], dp[j-1])
                pre[j-1] = dp[j-1]
            pre[j] = dp[j]
        return dp[-1]

匹配子序列的单词数792

给定字符串S和单词字典words，求words[i]中是子序列单词数的个数

例：输入：S="abcde" words=["a","bb","acd","ace"]

输出：3，有3个单词是S的子序列“a”,"acd","ace"

二分查找

class Solution:
   def numMatchingSubseq(self,s:str,words:List)

整数拆分343

编辑距离74

给两个单词word1和word2，计算出将word1转换成word2的最少操作次数

可以进行的操作如下：

插入一个字符；删除一个字符；替换一个字符

例：输入：word1= "horse",word2="rose"

输出：3

Horse -> rorse

rorse -> rose

Rose -> ros(删除e)

1、状态定义：

dp[i][j]表示word1的前i个字母转换成word2的前j个字母所使用的最少操作。

2、状态转移：

i指向word1，j指向word2

若当前字母相同，则dp[i][j] = dp[i - 1][j - 1];

否则取增删替三个操作的最小值 + 1， 即:

dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for j in range(len(dp[0])):
            dp[0][j] = j
        for i in range(len(dp)):
            dp[i][0] = i
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(1 + dp[i][j-1], 1 + dp[i-1][j], 1 + dp[i-1][j-1])
        return dp[-1][-1]

三个数的最大乘积(628)

给你一个整型数组nums，在数组中找出由三个数组成的最大乘积，并输出这个乘积

输入：nums = [1,2,3]

输出：6

输入：nums = [1,2,3,4]

输出：24

class Solution:
    def maximumProduct(self,nums:List[int])->int:
        nums.sort()
        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

最大整除数集(368)

给你一个由无重复的正整数组成的集合nums，请你找出并返回其最大的整除子集answer，子集中每一个元素对answer

如果存在多个有效解子集，返回其中任何一个均可

例：输入：nums=[1,2,3]

输出：[1,2]或者[1,3]

class Solution:
    def largestDivisibleSubset(self,nums:List[int])->List[int]:
        if not nums: return nums
        if len(nums) == 1: return nums
        l = len(nums)
        nums.sort()
        
        dp = [[i] for i in nums]
        
        for i in range(1,l):
            for j in range(i-1,-1,-1):
                if nums[i]%nums[j] == 0:
                   dp[i] = max(dp[j] + nums[i],dp[i],key = len)
                    
        return max(dp,key=len)

https://zhuanlan.zhihu.com/p/92815357

贪心算法

贪心算法是只

经典问题：盛水最多的容器11

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

class Solution:
    def maxArea(self, height: List[int]) -> int:
      """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        right = len(height) - 1
        maxArea = 0
        while left < right:
            b = right - left
            if height[left] < height[right]:
                h = height[left]
                left += 1
            else:
                h = height[right]
                right -= 1
            area = b*h
            if maxArea < area:
                maxArea = area
        return maxArea

递归与回溯

如果在函数中存在着调用函数本身的情况，这种现象就叫递归。

通常来说，为了描述问题的某一状态，必须用到该状态的上一个状态；而如果要描述上一个状态，又必须用到上一个状态的上一个状态…… 这样用自己来定义自己的方法就是递归。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

形象化递归算法

f(6)
//递
=>6*f(5)
=>6*(5*f(4))
=>6*(5*(4*f(3)))
=>6*(5*(4*(3*f(2))))
=>6*(5*(4*(3*(2*f(1)))))
//归
=>6*(5*(4*(3*(2*1))))
=>6*(5*(4*(3*2)))
=>6*(5*(4*6))
=>6*(5*24)
=>6*120
=>720

上面将f(6)逐渐分解到f(1)的过程称为递，求解出f(1)后在在求解出f(6)的过程称为归。

所以递归的本质是能把问题拆分成具有相同解决思路的子问题，。。。直到最后被拆解的子问题再也不能拆分，解决了最小粒度可求解的子问题后，在「归」的过程中自然顺其自然地解决了最开始的问题。

递归的关键是重复执行时的语句的写法，直接执行新函数就行，不能赋值给变量之后再执行

//直接执行
def fabonacci(n)
    return fabonacci(n-1)+fabonacci(n-2)
//赋值给变量再执行，错误
def fabonacci(n)
    n = n-1
    m = n-2
    return fabonacci(n)+fabonacci(m)

递归与回溯的区别

递归是一种算法结构。递归会出现在子程序中，形式上表现为直接或间接的自己调用自己。

回溯是一种算法思想，它是用递归实现的。回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。

比较通俗的说法来解释递归和回溯： 我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。 我们选择了一个方向，后来发现又有一个多岔路口，这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上，再做一次尝试，即在函数内部再调用一次函数，这就是递归的过程。 这样重复了若干次之后，发现这次选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。

leetcode例题：电话号码的字母组合 (opens new window)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

比如

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

class Solution:
    def letterCombinations(self, digits: str) -> list:
        KEY = {'2': ['a', 'b', 'c'],
               '3': ['d', 'e', 'f'],
               '4': ['g', 'h', 'i'],
               '5': ['j', 'k', 'l'],
               '6': ['m', 'n', 'o'],
               '7': ['p', 'q', 'r', 's'],
               '8': ['t', 'u', 'v'],
               '9': ['w', 'x', 'y', 'z']}
        if digits == '':
            return []
        ans = ['']
        for num in digits:
            ans = [pre+suf for pre in ans for suf in KEY[num]]
        return ans

经典问题：八皇后问题

国际象棋里皇后可以在横、竖、斜线上不限步数吃掉棋子。如何将8个皇后放在8*8的国际象棋棋盘上，使谁也不能被吃掉，也就是8个皇后中任意两个不能在同一直线、斜线或者横线上，共有多少种摆放方法（92）。

相同类型：数组全排列、字符串全排列

有数组[1,2,3,4],实现算法得到这个数组的全排列数组，[2,1,3,4],[1,3,2,4]等等

方法：迭代、递归

分割回文串131

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if len(s) == 0:
            return [[]]
        if len(s) == 1:
            return [[s]]
        tmp = []
        for i in range(1,len(s)+1):
            left = s[:i]
            right = s[i:]
            if left ==left[::-1]: #如果左侧不是回文的，则舍弃这种尝试
                right = self.partition(right)
                for i in range(len(right)):
                    tmp.append([left]+right[i])
        return tmp

迭代算法

迭代算法是用计算机处理问题的一种基本方法。它利用计算机运算速度快、适合做重复性操做的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。

使用迭代算法的步骤

（1）确定迭代变量 在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。

（2）建立迭代关系式 迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。

（3）对迭代过程进行控制 在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。通常可分为如下两种情况来控制迭代过程：

​ ① 所需的迭代次数是个确定的值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制；

​ ② 所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。

凡是迭代即可递归

双指针

二分查找

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

时间复杂度即是while循环的次数。

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如 果x<a[n/2]，则我们只要在数组 (opens new window)a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x

实例：

二分查找返回索引704

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

例：输入：nums = [-1,0,3,5,9,12], target = 9

输出：4

输入：nums = [-1,0,3,5,9,12], target = 2

输出：-1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
      	left, right = 0, len(nums) - 1
        
        while left <= right:
            middle = (left + right) // 2

            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                return middle
        return -1

二分查找返回布尔值

与上题704类似，返回布尔值

def search(self, nums: List[int], target: int) -> int:
  	lo,hi = 0, len(nums) - 1
    while lo <= hi:
      	mid = (lo + hi) >> 1
        if nums[mid] == target:
          	return True
        while lo < mid and nums[lo] == nums[mid]:
          	lo += 1
        if nums[lo] <= nums[mid]:
          	if nums[lo] <= target < nums[mid]:
              	hi = mid - 1
            else:
              	lo = mid + 1
        else:
    				if nums[mid] < target <= nums[hi]:
              	lo = mid + 1
            else:
              	hi = mid - 1
    return False

二维矩阵查找问题74

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

输入：matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]，搜索目标：3；

输出：true(laeetcode74题，中等)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
              return False
        r, c = len(matrix), len(matrix[0])
        get_value = lambda i: matrix[i // c][i % c]

        left, right = 0, r * c - 1
        while left <= right:
            middle = left + (right - left) // 2
            if get_value(middle) == target:
               return True
            elif get_value(middle) < target:
               left = middle + 1
            else:
               right = middle - 1
        return False

老鼠毒药问题

问题：有8 个一模一样的瓶子，其中有 7 瓶是普通的水，有一瓶是毒药。老鼠喝下毒药都会在一星期之后死亡。给定一周时间，至少需要几只老鼠才能检验出哪个瓶子里有毒药？

拓展问题：有1000 个一模一样的瓶子，其中有 999瓶是普通的水，有一瓶是毒药。老鼠喝下毒药都会在一星期之后死亡。给定一周时间，至少需要几只老鼠才能检验出哪个瓶子里有毒药？

问题1:3只老鼠

用二进制0和1表示老鼠没喝毒药和喝毒药两种状态。有000=0，001=1，010=2，011=3，100=4，101=5，110=6，111=7表示8个瓶子，也就是给1号老鼠喝1，3，5，7号瓶子的水，2号老鼠喝2，3，6，7瓶子的水，3号老鼠喝4，5，6，7瓶的水，每只老鼠有死不死两种状态，3只老鼠可以出现2^3>=8,所以可以表示7个瓶子一瓶毒药的八种状态。

问题2:10只老鼠。2的10次方为1024，大于1000，所以可以表示所有各种瓶子可能的状态，十只就够。

滑动窗口算法

滑动窗口算法是一种重要的思想，用于解决数组、字符串的子元素问题，可以将嵌套循环的问题转换为单层循环，降低事件复杂度，提高效率。

基本思想：将子字符串理解为一个滑动窗口，将这个窗口在数组上滑动，在窗口滑动的过程中左边出一个元素，右边进一个元素，然后对窗口内的元素进行计算。

思路：

1.使用双指针的左右指针技巧，初始化left=right=0，把索引区间[left,right]称为一个窗口。

2.先不断增加right扩大窗口，直到窗口符合要求

3.停止增加right，转而不断增加left缩小窗口，直到窗口的字符串不再符合要求，同时每增加一次left就更新一次结果

4.重复第二步和第三步，直到right到底。

第二步相当于找一个可行解，第三步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，同时不断向右滑动。

LRU缓存淘汰机制

LRU，LRU = Least Recently Used 最近最少使用原则，

当 Cache 储存满了的时候，使用 LRU 算法把旧数据清理出去，添加新数据。

LRU缓存机制146

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 (opens new window) 。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

python中使用有序字典

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity=capacity
        self.cache={}


    def get(self, key: int) -> int:
        if key in self.cache:
            v=self.cache.pop(key)
            self.cache[key]=v  #保证经常使用的在后面，不常使用的在前面
            return v
        return -1


    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
        self.cache[key]=value   #先放「密钥/数据值」，之后再判断是否达到上限
        if len(self.cache)>self.capacity:
            x=list(self.cache.keys())[0]    #取出最久未使用的密钥
            self.cache.pop(x)

LFU淘汰机制

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。 void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

输入： ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] 输出： [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

class LFUCache:

    def __init__(self, capacity: int):
        self.c, self.__count = capacity, 0
        self.keys = {}  # {key: int, value = [value, fre, time]}

    def get(self, key: int) -> int:
        self.__count += 1

        if key in self.keys:
            self.keys[key][1] += 1
            self.keys[key][2] = self.__count
            return self.keys[key][0]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        self.__count += 1

        if self.c == 0:
            return
        #  如果key不存在
        if key not in self.keys:
            if len(self.keys) >= self.c:
                #  寻找使用次数最少的key
                min_keys = []
                min_fre = self.keys[min(self.keys, key=lambda x:self.keys[x][1])][1]
                for k in self.keys:
                    if self.keys[k][1] == min_fre:
                        min_keys.append(k)
                #  在使用次数最少的key中寻找最近没有使用的
                min_time, least_key = 1e8, 0
                for k in min_keys:
                    if self.keys[k][2] < min_time:
                        min_time = self.keys[k][2]
                        least_key = k
                #  删除the least frequently used key
                del self.keys[least_key]
            self.keys[key] = [value, 1, self.__count]
        #  如果key存在
        else:
            self.keys[key][0] = value
            self.keys[key][1] += 1
            self.keys[key][2] = self.__count

DFS与BFS

深度优先搜索算法（英語：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 这个算法会尽可能深的搜索树的分支。 当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

广度优先算法（Breadth-First-Search），简称BFS，是一种图形搜索演算法。 简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。

权重随机数528

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

var Solution = function(w) {
  this.rates = []
  const sum = w.reduce((sum, item) => sum + item, 0)
  let temp = 0
  for (let i = 0; i < w.length; i++) {
    let rate = (w[i] / sum)
    temp += rate
    this.rates.push(temp.toFixed(2) * 1)
    rate = null
  }
};

Solution.prototype.pickIndex = function() {
  const num = Math.random().toFixed(2) * 1
  for (let i = 0; i < this.rates.length; i++) {
    if (num <= this.rates[i]) {
      return i
    }
  }
};

轮盘赌算法

新规则

智力题

不求答出，随手记录，自求多福

两根香烧完一个小时，计算15分钟

把其中一根两头都点上，另一根点单头，半小时双头的烧完后，再把单头的另一端点着，即为分钟

老师分饼干

https://www.jianshu.com/p/23adccda99f0

学习资源

https://ppsteven.github.io/

Https://leetcode.wang

各种算法整理： https://darktiantian.github.io/LeetCode%E7%AE%97%E6%B3%95%E9%A2%98%E6%95%B4%E7%90%86%EF%BC%88%E6%95%B0%E7%BB%84%E7%AF%87%EF%BC%89Array/