算法引入 动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。 斐波那契数列定义为：由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。 暴力递归依然可以运用动态规划的思想，我们可以得到状态转移方程 ： f(n)=f(n-1)+f(n-2 ...

题目地址275. H 指数 II 解题思路题目概述： 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。 h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。 提示：如果 h 有多种可能的值，h 指数 是其中最大的那个。 请你设计并实现对数时间复杂度的算法解决此问题。 根据题意可以抓住两个关键点，citations 已经按照 升序排列和h 指数的定义。看到数组是有序的，自然就应该想到用二分搜索，接下来就看这个h指数，能否根据h指数的定义写出对应的判断条件来缩小二分搜索可能的取值区间。 步骤一根据二分搜索的代码模板，写出大致代码框架。 1234567891011121314class Solution: def hIndex(self, citations: List ...

什么是生成器英文说法 A function which returns a generator iteratorUsually refers to a generator function, but may refer to a generator iterator in some contexts. In cases where the intended meaning isn’t clear, using the full terms avoids ambiguity. 翻译过来 一个返回生成器迭代器的函数，通常指的是生成器函数，但是在一定的语境下也可以指代生成器迭代器。为了避免歧义，推荐使用完整的术语。 123456def gen(): print("hello") if 0: yieldprint(gen, gen()) <function gen at 0x7f64f86a5750> <generator object gen at 0x7f64f4545a10> 根据上面示例就可以很好理解了，生成 ...

可迭代对象什么是可迭代对象简单理解：可以被for遍历的对象 代码层面：如果一个对象实现了iter方法，那么这个对象就是可迭代对象 123456str_iterable = "hello world!"for x in str_iterable: print(x) h e l l o w o r l d ! 12print(str_iterable.__iter__())print(iter(str_iterable)) # iter是内建方法，等同于执行了可迭代对象的__iter__方法 <str_iterator object at 0x7fdfc5c2ac20> <str_iterator object at 0x7fdfc5c2ad40> 可迭代对象之间的共同点可以借助一个方法来看不同可迭代对象之间，有什么共同的方法或者属性 12345678910# 查看可迭代对象之间的共同属性def common_attrs_of_iterable(*iterables): res = set() for iterable in ...

题目地址162. 寻找峰值 解题思路二分搜索的关键就是根据每一次得到的mid来确定目标值的区间范围，根据本题的寻找峰值，那么就有三种情况： 下标mid对应的元素，大于它左边和右边的元素，则mid就是峰值下标，直接返回 下标mid对应的元素，小于它左边的元素，此时区间左移 下标mid对应的元素，大于它左边的元素，此时区间右移 注意，本题有$nums[-1] = nums[n] = -∞nums[−1]=nums[n]=−∞$，所以不管往左还是往右，必定会存在一个峰值元素。 代码实现12345678910111213141516171819class Solution: def findPeakElement(self, nums: List[int]) -> int: left = 0 right = len(nums) - 1 min_val = -float("inf") while left <= right: mid = left + (right - lef ...

题目地址解题思路本题的关键还是在于求$f(mid)=count$（数字在范围[1,mid]区间，包含的丑数个数为count） 比如： 输入：n = 3, a = 2, b = 3, c = 5此时就有：$f(1)=0$，$f(2)=1$，$f(3)=2$，$f(4)=3$，$f(5)=3$ 可以看到，这个函数是一个单调不递减的，有单调性自然就可以用二分搜索了。 根据容斥原理，可以列出此方程为: $f(mid)=mid / a + mid / b + mid / c - mid / lcm\underline{\hspace{.05in}}{ab} - mid / lcm\underline{\hspace{.05in}}{ac} - mid / lcm\underline{\hspace{.05in}}{bc} + mid / lcm\underline{\hspace{.05in}}{abc}$ 其中lcm表示最小公倍数。 代码实现12345678910111213141516171819202122232425import mathclass Solution: def ...

Redis 没有直接使用 C 语言的字符串表示，而是定义了一种称为 SDS(simple dynamic string)的类型，并作为 Redis 默认字符串的表示。那么 Redis 为什么要这么做呢？有什么好处呢？接下来咱们就探讨一下。 SDS 定义src/sds.h/sdshdr 123456789struct sdshdr { // 所保存的字符串长度 unsigned int len; // buf数组中未使用的字节数 unsigned int free; // 字节数组，用于保存字符串 char buf[];}; 图 2.1 展示了一个字符串“Redis”的例子： len为 5，是字符串“Redis”的长度，表示SDS保存了一个长度为 5 字节的字符串。 free为 0，表示SDS无分配未使用的空间。 buf是一个char类型的数组，数组前五个字节依次为R、e、d、i、s，最后一个字节为空字符\0。 可以看到SDS遵循了C字符以空字符结尾的惯例，这么做的好处是可以重用一部分C字符串中的函数（比如printf）。 ...

题目在排序数组中查找元素的第一个和最后一个位置 思路 数组是排序数组，要求$target$值的最小和最大下标，直接套用二分法模板。 以求$target$的最小下标为例: 搜索区间$[left, rigt]$的闭区间，初始值为$[0, len(nums)-1]$ $nums[mid] = target$，则区间左移，$right=mid-1$ $nums[mid] \lt target$，则区间左移，$right=mid-1$ $nums[mid] \gt target$，则区间右移，$left=mid+1$ 其实只要仔细分析每次搜索区间的缩小条件，问题就会变得很简单。 代码完全按照思路分析中的步骤，用代码实现如下： 1234567891011121314151617181920212223242526272829class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: n = len(nums) if n == 0: ...

题目搜索旋转排序数组 思路 此题是很明显的二分法求确切值，思考方法跟求边界值略有不同 首先可以确定循环条件为$[left,right]$，因为既然是求明确值，那么肯定是$left$和$right$的闭区间（$left$和$right$的值也被包含进去） 然后再确定左右边界的移动方式 假定当前$mid$不符合（$left$右移），此时可能符合条件的区间应$[mid+1, right]$（需要将$mid$排除在外，因为$mid$已经不符合了） 同理当$mid$不符合（$right$左移）也是一样，此时符合区间应为$[left,mid-1]$ 再回归到此题，此题的不同之处是，将原本有序的序列进行了旋转，变为了两个有序的序列，乍看起来不太好做，实际上一分析，做法还是相同，只要根据条件判断每一次$left$右移和$right$左移的条件就行了。 代码123456789101112131415161718192021class Solution: def search(self, nums: List[int], target: int) -> int: lef ...

题目在 D 天内送达包裹的能力思路 搜索区间为$[left, right]$，初始$left=max(weights)$，$right=sum(weights)$ 能运送完，下一搜索区间$[left, mid-1]$ 不能送完，下一搜索区间$[mid+1, right]$ 代码1234567891011121314151617181920212223242526class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: def can_finish(w): cnt = 0 temp = 0 for weight in weights: temp += weight if temp > w: temp = weight cnt += ...