题目描述 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。 实现 LFUCache 类： LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。 void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。 注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。 当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。 示例： 输入： ["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] 解释： // cnt(x) = 键 x 的使用计数 // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的） LFUCache lFUCache = new LFUCache(2); lFUCache.put(1, 1); // cache=[1,_], cnt(1)=1 lFUCache.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lFUCache.get(1); // 返回 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lFUCache.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小 // cache=[3,1], cnt(3)=1, cnt(1)=2 lFUCache.get(2); // 返回 -1（未找到） lFUCache.get(3); // 返回 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lFUCache.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用 // cache=[4,3], cnt(4)=1, cnt(3)=2 lFUCache.get(1); // 返回 -1（未找到） lFUCache.get(3); // 返回 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lFUCache.get(4); // 返回 4 // cache=[3,4], cnt(4)=2, cnt(3)=3 提示： $0 \leq capacity, key, value \leq 10^4$ 最多调用 $10^5 $次 get 和 put 方法 进阶：你可以为这两种操作设计时间复杂度为 O(1) 的实现吗？ 解题思路 首先得定义一个缓存的结点结构： struct Node { int key; int value; int frenquency; Node(int _key,int _value,int _frequency):key(_key),value(_value),frenquency(_frequency){} }; 里面包含key，value和frenquency信息。 如果要让get操作达到$O(1)$的时间复杂度，缓存结点可以存储在动态数组或者哈希表中。但是如果用动态数组存储的话，put操作肯定无法达到$O(1)$的时间复杂度。要使put操作达到$O(1)$的时间复杂度，得用双向链表来组织缓存结点。所以，如果要让put和get操作同时达到$O(1)$的时间复杂度，我们可以考虑用哈希表+双向链表的方式来实现。 首先定义一个frequency_table哈希表，索引为频率frenquency，每一个索引存放一个双向链表，这个双向链表里面存放所有使用频率为frenquency的缓存。每一次添加的时候在这个双向链表的头部进行插入，在删除的时候在双向链表的尾部删除，这样就可以实现访问时间的有序排列，用于实现LFU。然后我们还需要定义一个变量来记录最小的使用频率minfreq，用于删除操作。 接着，我们还需要定义一个key_table的哈希表，索引为key，每一个索引存放这key值对应的frequency_table中链表的具体节点内存地址。然后利用这两个哈希表就可以让put和get操作同时达到$O(1)$的时间复杂度。 对于 get(key) 操作，我们能通过索引 key 在 key_table 中找到缓存在 frequency_table 中的链表的结点的内存地址，如果不存在直接返回 -1，否则我们能获取到对应缓存的相关信息，这样我们就能知道缓存的键值还有使用频率，直接返回 key 对应的值即可。但是，进行一次get(key)操作，这个缓存的使用频率就要加一，同时就需要更新这两个哈希表的值。还有可能需要更新minfreq的值。在整体的操作中，都是常数时间的复杂度，所以时间复杂度为$O(1)$。 对于 put(key, value) 操作，我们先通过索引 key在 key_table 中查看是否有对应的缓存，如果有的话，其实操作s类似于 get(key) 操作，唯一的区别就是我们需要将当前的缓存里的值更新为 value。如果没有的话，相当于是新加入的缓存，如果缓存已经到达容量，需要先删除最近最少使用的缓存，再进行插入。 先考虑插入，由于是新插入的，所以缓存的使用频率一定是 1，所以我们将缓存的信息插入到 frequency_table 中 1 索引下的列表头即可，同时更新 key_table[key] 的信息，以及更新 minfreq = 1。 那么剩下的就是删除操作了，由于我们实时维护了 minfreq，所以我们能够知道 frequency_table 里目前最少使用频率的索引，同时因为我们保证了链表中从链表头到链表尾的插入时间是有序的，所以 frequency_table[minfreq] 的链表中链表尾的节点即为使用频率最小且插入时间最早的节点，我们删除它同时根据情况更新 minfreq ，整个时间复杂度均为…

题目描述 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 解题思路 方法一：两层循环 刚开始我想复杂了，首先逐个遍历整个数组，如果碰到0，那么就在这个元素后面找一个非0的进行交换，如果找不到非0的，说明已经完成了。 参考代码如下： void moveZeroes(vector<int>& nums) { for(int i=0;i<nums.size();++i) { if(nums[i]!=0) continue; int j=i+1; for(;j<nums.size();++j) { if(nums[j]==0) continue; swap(nums[i],nums[j]); break; } if(j==nums.size()) break; } } 时间复杂度为：$O(n^2)$ 空间复杂度为：$O(1)$ 这个方法效率有点低，只击败了9%。。。 方法二：直接覆盖 这个方法的思想很简单，遍历整个数组，将数组中的非0元素直接映射到数组的前面，后面部分直接改为0就可以了。变量index记录了遍历过的部分有多少个非零元素，以及出现新的非0元素应该填入数组位置的下标。 具体细节如下述代码所示： void moveZeroes(vector<int>& nums) { int len=nums.size(); int index=0; for(auto num : nums) { if(num!=0) { nums[index++]=num; } } for(int i=index;i<len;++i) { nums[i]=0; } } 时间复杂度为：$O(n)$ 空间复杂度为：$O(1)$

题目描述 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。 示例： 输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。 提示： 0 <= nums.length <= 50000 1 <= nums[i] <= 10000 解题思路 这道题是简单题，思路一看就有，but，写了半天。。。 方法一 两层循环 首先想到的是，依次遍历整个数组，找到一个偶数，然后遍历它之后的元素，找到一个奇数，进行交换。循环往复，直至遍历结束。可以做一点小优化，找奇数的时候如果找不到就可以直接返回了。 具体细节可以参考以下代码： vector<int> exchange(vector<int>& nums) { bool existOdd=true; for(int i=0;i<nums.size();++i) { if(nums[i]%2==1) continue; int j=i+1; for(;j<nums.size();++j) { if(nums[j]%2==1) { swap(nums[i],nums[j]); break; } } if(j==nums.size()) existOdd=false; if(!existOdd) break; } return nums; } 时间复杂度为：$O(n^2)$ 空间复杂度为：$O(1)$ 毫无疑问，超时了！！！ 然后用快慢指针的方法优化了一下，减少了操作的次数，但仍然有两层循环，第二版的代码如下所示： vector<int> exchange(vector<int>& nums) { int len=nums.size(); int left=0; int right=0; while(left<len) { while(left<len&&nums[left]%2==1) { left++; } if(left>=len) break; right=left+1; while(right<len&&nums[right]%2==0) { right++; } if(right>=len) break; swap(nums[left],nums[right]); left++; right++; } return nums; } 时间复杂度为：$O(n^2)$ 空间复杂度为：$O(1)$ 这一版本虽然过了，但是击败了7%，丢脸的不行 方法二 一层循环 用left指针从左向右找偶数，用right指针从右向左找奇数，然后进行交换，直至相遇。 代码如下所示： vector<int> exchange(vector<int>& nums) { int len=nums.size(); int left=0; int right=len-1; while(left<right) { if(nums[left]%2==1) { left++; continue; } if(nums[right]%2==0) { right--; continue; } swap(nums[left++],nums[right--]); } return nums; } 时间复杂度为：$O(n)$ 空间复杂度为：$O(1)$ 证明了自己是个菜鸡的事实。。。

题目描述 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。 示例 1： 输入：nums = [10,2] 输出："210" 示例 2： 输入：nums = [3,30,34,5,9] 输出："9534330" 示例 3： 输入：nums = [1] 输出："1" 示例 4： 输入：nums = [10] 输出："10" 提示： $1 \leq nums.length \leq 100$ $0 \leq nums[i] \leq 10^9$ 解题思路 这道题如果数组中的数没有相同数字开头，那么这道题非常好做。直接将整数类型的数组转换为字符串类型的数组，然后直接按字符串比较大小的方式将里面的字符串从大到小排序（比较过程是，首先比较输入数组的每个元素的最高位，最高位相同比较次高位，以此类推），最后依次拼接起来就好。 但是这道题中输入数组包含有相同数字开头的情况，例如 [4,42] 和[4,45]。 对于 [4,42]，比较 442 > 424，需要把 4 放在前面； 对于 [4,45]，比较 445 < 454，需要把 45 放在前面。 因此我们需要比较不同的拼接顺序的结果，进而决定它们在结果中的排列顺序。 如果用暴力的方法去比较，时间复杂度爆炸。我们需要定义一种新的排序比较规则： 对于字符串 a ，和字符串 b ， ​ 如果 a + b > b +a ，那么 a 排在 b 前面； ​ 否则，a 排在 b 后面。 然后套用没有相同数字开头的情况的处理方法，并且用新定义的排序规则就可以解决包含有相同数字开头的情况。 具体的证明过程比较复杂，感兴趣的可以看官方解答。 具体细节详见下述代码： string largestNumber(vector<int>& nums) { if(nums.empty()) return ""; vector<string>trans; for(auto x:nums) { trans.push_back(to_string(x)); } sort(trans.begin(),trans.end(),[](string& a,string& b) { return a+b>b+a; }); if(trans[0]=="0") return "0"; string res=""; for(auto x:trans) { res+=x; } return res; }

题目描述 给定一棵二叉搜索树，请找出其中第k大的节点。 示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 示例 2: 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 4 限制： 1 ≤ k ≤ 二叉搜索树元素个数 解题思路 寻找二叉搜索树中的第k大元素，可以利用二叉搜索树的性质来做。二叉搜索树的中序遍历的结果是一个递增的有序序列，我们可以用count变量记录遍历的结点数量，然后在count==k的时候返回当前元素的值即可。 需要注意一点的是，如果按照左中右顺序遍历得到的是一个递增的序列，返回的是第k小的数；如果按照右中左的顺序遍历得到的是一个递减的序列，返回的是第k大的数。 具体的实现细节见代码： int res=INT32_MIN; void DFS(TreeNode* root,int k,int& count) { if(root==nullptr) return; DFS(root->right,k,count); count++; if(count==k) res = root->val; DFS(root->left,k,count); } int kthLargest(TreeNode* root, int k) { if(root==nullptr) return 0; int count=0; DFS(root,k,count); return res; } 时间复杂度为：$O(n)$，$n$为二叉树的结点个数 空间复杂度为：$O(n)$，$n$为二叉树的结点个数

题目描述 给定一个二叉树，确定它是否是一个完全二叉树。 百度百科中对完全二叉树的定义如下： 若设二叉树的深度为 h，除第 h 层外，其它各层 ($1 \quad to \quad h-1$) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 $1 \quad to \quad 2^h$ 个节点。） 示例 1： 输入：[1,2,3,4,5,6] 输出：true 解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。 示例 2： 输入：[1,2,3,4,5,null,7] 输出：false 解释：值为 7 的结点没有尽可能靠向左侧。 提示： 树中将会有 1 到 100 个结点。 解题思路 关于完全二叉树的定义还是比较熟悉的，但是乍一看到这道题有点懵。官方题解的方法是重新同一个code变量给每一个结点标记，规则为：父节点为i的话，左孩子为2i，右孩子为2i+1。其实的根节点标记为1。最后看最右端结点的code值是不是结点的数量。这个方法当然是可行的，但是有点繁琐。 有一个更加巧妙的方法。完全二叉树如果用广度优先搜索的方法，也就是层序遍历的话，当出现一个空节点的时候，后续就不能再出现非空结点。反过来说，如果在层序遍历的过程中，在出现空节点后又出现了非空结点，那么这个二叉树一定不是完全二叉树。 据此可以写出对应的代码： bool isCompleteTree(TreeNode* root) { if(root==nullptr) return true; queue<TreeNode*>q; bool isNullptr=false; q.push(root); while(!q.empty()) { TreeNode* cur=q.front(); q.pop(); if(cur==nullptr) { isNullptr=true; continue; } else{ if(isNullptr) { //在空节点后又出现非空结点 return false; } q.push(cur->left); q.push(cur->right); } } return true; } 时间复杂度为：$O(n)$，$n$为二叉树的结点个数 空间复杂度为：$O(n)$，$n$为二叉树的结点个数

题目描述 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2： 输入：coins = [2], amount = 3 输出：-1 示例 3： 输入：coins = [1], amount = 0 输出：0 示例 4： 输入：coins = [1], amount = 1 输出：1 示例 5： 输入：coins = [1], amount = 2 输出：2 提示： $1 \leq coins.length \leq 12$ $1 \leq coins[i] \leq 2^{31} - 1$ $0 \leq amount \leq 10^4$ 解题思路 这道题无疑需要用动态规划的思想去做，问题是怎么实现。 方法一：记忆化搜索（自顶向下） 假设我们用函数f(x)来表示凑成金额x所需的最少硬币数，那么我们可以很容易地得出下述的一个公式： $$ f(x)=min(f(x-coins[0]),f(x-coins[1]),\cdots,f(x-coins[coins.size()-1]))+1 $$ 根据这个公式，我们已经可以写出递归暴力的方法了。然后我们用记忆化搜索的方法来优化一下，用一个dp数组来记录已经算出来的值来避免重复计算。 具体的算法细节见下述代码： vector<int>dp; int dfs(int amount,vector<int>& coins) { if(amount<0) return -1; if(amount==0) return 0; if(dp[amount]!=0) return dp[amount]; int minSum=INT32_MAX; for(int i=0;i<coins.size();++i) { int t=dfs(amount-coins[i],coins); if(t>=0&&t<minSum) minSum=t+1; } dp[amount]=minSum==INT32_MAX?-1:minSum; return dp[amount]; } int coinChange(vector<int>& coins, int amount) { if(amount<1) return 0; dp.resize(amount+1); return dfs(amount,coins); } 时间复杂度：$O(Sn)$，其中 $S$ 是金额，$n$是面额数。 空间复杂度：$O(S)$，其中 $S$ 是金额。 方法二：动态规划（自底向上） 有了方法一中的公式，我们可以用动态规划的思想来实现它。 具体的实现细节见下述代码： int coinChange(vector<int>& coins, int amount) { if(amount<1) return 0; int maxSum=amount+2; vector<int>dp(amount+1,maxSum); dp[0]=0; for(int i=1;i<=amount;++i) { for(int j=0;j<coins.size();++j) { if(i>=coins[j]) { dp[i]=min(dp[i],dp[i-coins[j]]+1); } } } return dp[amount]>amount?-1:dp[amount]; } PS: 因为有对dp中元素加1的操作，如果将dp中元素初始化为INF32_MAX会发生溢出！ 时间复杂度：$O(Sn)$，其中 $S$ 是金额，$n$是面额数。 空间复杂度：$O(S)$，其中 $S$ 是金额。 虽然两种方法的时空复杂度是一样的，但是记忆化搜索的方法运行更高效。

题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 解题思路 这道题是一道关于树和链表转换的题，直接考虑用递归来完成。 用两个指针left和right来指示根节点root的左子树和右子树转换成一个有序的循环双向链表的头结点，然后根据条件判断，将left所指示的循环双向链表、root结点、right所指示的循环双向链表连接起来。在遇到空节点的时候不做任何操作，直接返回就行。 主要分为四种情况，分述如下： left==nullptr&&right==nullptr，也就是该节点为叶子结点。 if(left==nullptr&&right==nullptr) { root->right=root; root->left=root; head = root; } 直接将根节点转换成双向循环链表返回。 left==nullptr&&right!=nullptr，左子树为空，右子树已经转换成循环双链表。 if(left==nullptr&&right!=nullptr) { root->right=right; right->left->right=root; root->left=right->left; right->left=root; head = root; } 也就是将根节点和右子树转换成的循环双链表拼接起来。 left!=nullptr&&right==nullptr，右子树为空，左子树已经转换成循环双链表。 if(left!=nullptr&&right==nullptr) { root->left=left->left; left->left=root; root->left->right=root; root->right=left; head = left; } 也就是将根节点和左子树转换成的循环双链表拼接起来。 left!=nullptr&&right!=nullptr，左右子树都已经转换成循环双链表的情况。 if(left!=nullptr&&right!=nullptr) { root->left=left->left; root->right=right; left->left->right=root; left->left=right->left; left->left->right=left; right->left=root; head=left; } 这种情况最为麻烦，需要将根节点、左子树拼接成的双向循环链表、右子树拼接成的双向循环链表都连接起来。 最终，将各部分的代码组合起来就可。 具体细节见示例代码： Node* treeToDoublyList(Node* root) { if(root==nullptr) return root; Node* left=nullptr; Node* right=nullptr; if(root->left) left=treeToDoublyList(root->left); if(root->right) right=treeToDoublyList(root->right); Node* head=nullptr; if(left==nullptr&&right==nullptr) { root->right=root; root->left=root; head = root; } if(left==nullptr&&right!=nullptr) { root->right=right; right->left->right=root; root->left=right->left; right->left=root; head = root; } if(left!=nullptr&&right==nullptr) { root->left=left->left; left->left=root; root->left->right=root; root->right=left; head = left; } if(left!=nullptr&&right!=nullptr) { root->left=left->left; root->right=right; left->left->right=root; left->left=right->left; left->left->right=left; right->left=root; head=left; } return head; } 时间复杂度为：$O(n)$，$n$为二叉树的结点个数 空间复杂度为：$O(logn)$，$n$为二叉树的结点个数

题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。 示例 1： 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 示例 2： 输入：s = "a", t = "a" 输出："a" 提示： $1 \leq s.length, t.length \leq 10^5$ s 和 t 由英文字母组成 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ 解题思路 这道题要求给出时间复杂度为$O(n)$的算法，我们考虑用滑动窗口算法去解决。 思路如下：用两个指针分别指示窗口的边界，记为i和j，先向右滑动j指针，使得窗口内的字符串包含了字符串t，然后记录下起始下标start和长度minLen进行后续的比较。然后，接着向右滑动i指针，指针窗口内的字符串恰好刚刚不包含字符串t，再滑动指针j。循环往复，直至遍历完字符串s，得到最终答案。 这里面需要解决一个问题： 如何判断窗口内的字符串已经包含字符串t？ 我们首先初始化一个哈希表为字符串t中每一个字符出现的次数。这些初始化的字符次数都为正数，也就是表示了对于每一个字符我们还需要多少个。这样的话，在遍历字符串s中的字符的时候，对于出现的每一个字符我们将它在哈希表中减1(如果这个字符之前就在哈希表中，那么就在原来的次数上减1，否则先在哈希表中将这个字符的次数初始化为0，再减去1)，这样的话，次数就有可能为负数，这就表示这个字符我们多余了多少个。 可以用stl中的哈希表，但是比较慢，推荐使用int类型的vector，初始化为128 个长度，初始值为0，这样就可以用ASCII码来表示字符了，这样的哈希表速度更快。 使用哈希表后，其实我们已经可以实现这个功能了，比如：遍历哈希表，将每个次数大于0的字符的次数加起来，就是我们总共在窗口中还需要包含的字符的个数，当它为0的时候说明就已经全部包含了。再进行优化，直接用一个变量totalCount来表示这个总和，在过程中进行更新就可以了。 PS: 需要注意编码过程中的边界条件！ 具体细节可以参考示例代码： string minWindow(string s, string t) { unordered_map<char,int>mp; int totalCount=0; for(int i=0;i<t.size();++i) { mp[t[i]]++; totalCount++; } int i=0,j=0; int start=0; int minLen=INT32_MAX; while (j<=s.size()) { while(totalCount==0) { if(j-i<minLen) { minLen=j-i; start=i; } mp[s[i]]++; if(mp[s[i]]>0) { totalCount++; } i++; } if(mp[s[j]]>0) { totalCount--; } mp[s[j]]--; j++; } string ans=minLen==INT32_MAX?"":s.substr(start,minLen); return ans; } string minWindow(string s, string t) { vector<int>mp(128,0); int totalCount=0; for(int i=0;i<t.size();++i) { mp[t[i]]++; totalCount++; } int i=0,j=0; int minLen=INT32_MAX; string ans=""; while (j<=s.size()) { while(totalCount==0) { if(j-i<minLen) { minLen=j-i; ans=s.substr(i,minLen); } mp[s[i]]++; if(mp[s[i]]>0) { totalCount++; } i++; } if(mp[s[j]]>0) { totalCount--; } mp[s[j]]--; j++; } return ans; } 时间复杂度为：$O(n)$，$n$为字符串s的长度 空间复杂度为：$o(m)$，$m$为字符串t的长度

题目描述 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例 1： 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 示例 2： 输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u') 提示： 0 <= word1.length, word2.length <= 500 word1 和 word2 由小写英文字母组成 解题思路 涉及两个字符串之间的最大最小问题第一反应就是能不能使用动态规划，但是怎么定义状态，以及如何求出状态转移方程比较困难。 先研究一下题目。我们对一个单词的操作可以有三种，分别为： 插入一个字符 删除一个字符 替换一个字符 那么两个单词A和B加起来就有就有六种方式。但是这六种方式有等价的操作： 对单词 A 删除一个字符和对单词 B 插入一个字符是等价的； 对单词 B 删除一个字符和对单词 A 插入一个字符是等价的； 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。 也就是说只剩下了三种不同的操作： 在单词 A 中插入一个字符； 在单词 B 中插入一个字符； 修改单词 A 的一个字符。 现在我们研究一下如何用动态规划解决这个问题。如果我们定义$dp[i][j]$为word1中前i个字符变换到word2中前j个字符所需要的最短操作次数，$(i,j)$表示word1中前i个字符经过$dp[i][j]$次最少操作变换到word2中前j个字符后的一个状态。那么$(i,j)$状态是由$(i-1,j),(i,j-1),(i-1,j-1)$变化而来的，也就是说$dp[i][j]$的值跟$dp[i-1][j],dp[i][j-1],dp[i-1][j-1]$有关系了。 如果$(i,j)$由$(i-1,j)$变化而来，那么只需在$(i-1,j)$的基础上在单词 A 中插入一个字符，也就是说，存在等式： $$ dp[i][j]=dp[i-1][j]+1 $$ 如果$(i,j)$由$(i,j-1)$变化而来，那么只需在$(i,j-1)$的基础上在单词 B 中插入一个字符，也就是说，存在等式： $$ dp[i][j]=dp[i][j-1]+1 $$ 如果$(i,j)$由$(i-1,j-1)$变化而来，还需要考虑word1[i-1](word1的第i个字符)和word2[j-1](word2的第j个字符的值相等，则不需要任何操作；否则，修改单词 A 的一个字符。也就是存在以下公式： $$ dp[i][j]=dp[i-1][j-1]+1，\quad if \quad word1[i-1]=word2[j-1]\\ dp[i][j]=dp[i-1][j-1], \quad if \quad word[i-1]\neq word2[j-1] $$ 然后我们考虑一些特殊情况。 当A和B都是空字符串的时候，也就是$(0,0)$状态下，$dp[0][0]=0$； 当A或者B有且只有一个为空的时候，只需要逐个删除非空字符串的字符就可。也就是说： $$ if \quad A字符串为空字符串, \quad dp[0][j]=j;\\ if \quad B字符串为空字符串, \quad dp[i][0]=i; $$ 我们总结一下不难得到以下的动态规划条件： $$ \begin{eqnarray} && if \quad i=0 \quad 并且 \quad j=0,\quad dp[0][0]=0;\\ && if \quad i=0 \quad 并且 \quad j\neq 0,\quad dp[0][j]=j;\\ && if \quad i\neq 0 \quad 并且 \quad j=0,\quad dp[i][0]=i;\\ && if \quad i\neq 0 \quad 并且 \quad j\neq 0, \\ && dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1) ,\quad && if \quad word1[i-1] \neq word2[j-1];\\ && dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]), \quad && if \quad word1[i-1] = word2[j-1]; \end{eqnarray} $$ 据此可以写出对应代码，具体细节见示例代码： int minDistance(string word1, string word2) { int m=word1.size(); int n=word2.size(); vector<vector<int>>dp(m+1,vector<int>(n+1,0)); for(int i=1;i<m+1;++i) { dp[i][0]=i; } for(int i=1;i<n+1;++i) { dp[0][i]=i; } for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) { if(word1[i-1]!=word2[j-1])…