LeetCode 每周算法 10（多维动态规划、技巧）
LeetCode 每周算法 10（多维动态规划、技巧）
多维动态规划算法：
class Solution {
public:
// 定义一个公开的方法，用于计算独特路径的数量
int uniquePaths(int m, int n) {
// 创建一个二维动态规划数组dp，用于存储到达每个网格的独特路径数量
// dp[i][j] 表示到达 (i, j) 网格的独特路径数量
vector<vector<int>> dp(m, vector<int>(n));
// 初始化第一列的所有网格，因为从左上角到第一列的任意网格都只有一条路径（一直向下走）
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
// 初始化第一行的所有网格，因为从左上角到第一行的任意网格都只有一条路径（一直向右走）
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
// 填充dp数组的其他部分
// 对于每个网格 (i, j)，其独特路径数量等于从上方网格 (i-1, j) 和左侧网格 (i, j-1) 到达的路径数量之和
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// 返回右下角网格 (m-1, n-1) 的独特路径数量
return dp[m - 1][n - 1];
}
};
class Solution {
public:
// 函数计算从网格左上角到右下角的最小路径和
int minPathSum(vector<vector<int>>& grid) {
// 获取网格的行数和列数
int m = grid.size();
int n = grid[0].size();
// 创建一个动态规划数组dp，用于存储到达每个网格位置的最小路径和
vector<vector<int>> dp(m, vector<int>(n));
// 初始化起点位置的最小路径和为网格起点的值
dp[0][0] = grid[0][0];
// 初始化第一列的最小路径和，只能从上面到达
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 初始化第一行的最小路径和，只能从左边到达
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 填充dp数组的其余部分，对于每个网格位置，选择从上面或左边到达的最小路径和
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
}
}
// 返回右下角网格位置的最小路径和
return dp[m - 1][n - 1];
}
};
class Solution {
public:
string longestPalindrome(string s) {
// 初始化结果字符串为s的第一个字符，作为最保守的初始选择。
// 这意味着，在最坏的情况下，我们将返回字符串中的一个单字符作为回文子串。
string result = s.substr(0, 1);
// 创建一个二维动态规划数组dp，其中dp[i][j]表示子串s[i...j]（包含索引i和j的字符）是否为回文串。
// 数组的大小为s.size() x s.size()，因为我们需要检查所有可能的子串。
vector<vector<bool>> dp(s.size(), vector<bool>(s.size()));
// 从字符串的末尾开始向前遍历，这样我们可以在计算dp[i][j]时利用之前已经计算过的dp值。
// 这种自底向上的方法允许我们逐步构建更长的回文子串的解。
for (int i = s.size() - 1; i >= 0; i--) {
// 对于每个起始索引i，我们遍历所有可能的结束索引j（其中j > i）。
for (int j = i + 1; j < s.size(); j++) {
// 如果子串的长度小于等于2（即j - i <= 2），我们只需要检查两个字符是否相等。
// 在这种情况下，不需要考虑子串内部的回文性，因为子串太短了。
if (j - i <= 2) {
dp[i][j] = (s[i] == s[j]); // 如果两个字符相等，则子串是回文串；否则不是。
} else {
// 对于更长的子串，我们需要检查两个条件：
// 1. 子串的首尾字符是否相等（s[i] == s[j]）。
// 2. 去掉首尾字符后的子串（s[i+1...j-1]）是否是回文串（dp[i + 1][j - 1]）。
// 只有当这两个条件都满足时，整个子串才是回文串。
dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
}
// 如果当前子串是回文串，并且它的长度大于我们之前找到的最长回文子串的长度，
// 则更新结果字符串为当前子串。
if (dp[i][j] && j - i + 1 > result.size()) {
result = s.substr(i, j - i + 1); // 提取子串s[i...j]并更新结果。
}
}
}
// 返回找到的最长回文子串。
return result;
}
};
// 中心扩散法：
// class Solution {
// public:
// string longestPalindrome(string s) {
// int n = s.size();
// string ans = "";
// for(int i = 0; i < n; i++)
// {
// int l = i, r = i + 1;
// while(l >= 0 && r < n && s[l] == s[r]) l--, r++;
// if(ans.size() < r - l - 1) ans = s.substr(l + 1, r - l - 1);
// l = i - 1, r = i + 1;
// while(l >= 0 && r < n && s[l] == s[r]) l--, r++;
// if(ans.size() < r - l - 1) ans = s.substr(l + 1, r - l - 1);
// }
// return ans;
// }
// };
class Solution {
public:
// 函数用于计算两个字符串的最长公共子序列的长度
int longestCommonSubsequence(string text1, string text2) {
// 创建一个二维动态规划数组dp，大小为(text1.size() + 1) x (text2.size() + 1)
// 数组的所有元素初始化为0，dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
// 遍历text1的所有字符
for (int i = 1; i <= text1.size(); i++) {
// 遍历text2的所有字符
for (int j = 1; j <= text2.size(); j++) {
// 如果text1的第i个字符和text2的第j个字符相等
if (text1[i - 1] == text2[j - 1]) {
// 则dp[i][j]等于dp[i-1][j-1]加1，表示找到了一个公共字符，最长公共子序列长度加1
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 如果不相等，则dp[i][j]为dp[i-1][j]和dp[i][j-1]中的较大值
// 这表示我们不考虑当前text1的第i个字符或者当前text2的第j个字符，看哪种情况能得到更长的公共子序列
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 最后，dp[text1.size()][text2.size()]存储了text1和text2的最长公共子序列的长度
return dp[text1.size()][text2.size()];
}
};
class Solution {
public:
// 计算两个字符串word1和word2之间的最小编辑距离
int minDistance(string word1, string word2) {
// 创建一个二维动态规划数组dp，dp[i][j]表示word1的前i个字符转换为word2的前j个字符所需的最小编辑距离
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
// 初始化第一行，表示当word1为空字符串时，转换为word2的前j个字符所需的最小编辑距离（即插入操作次数）
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
// 初始化第一列，表示当word2为空字符串时，将word1的前i个字符转换为空字符串所需的最小编辑距离（即删除操作次数）
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
// 填充dp数组的其余部分
for (int i = 1; i <= word1.size(); i++) { // 遍历word1的每个字符
for (int j = 1; j <= word2.size(); j++) { // 遍历word2的每个字符
if (word1[i - 1] == word2[j - 1]) {
// 如果word1的第i个字符和word2的第j个字符相等，则不需要进行编辑操作
dp[i][j] = dp[i - 1][j - 1]; // 继承之前的状态
} else {
// 如果不相等，则考虑三种操作：插入、删除、替换，并取这三种操作中的最小值加1
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
// 分别表示替换（虽然这里没有单独写出，但替换的效果已经通过取这三个值中的最小值隐含在内了）、
// 删除word1的第i个字符（dp[i - 1][j] + 1）和在word1的第i个位置插入word2的第j个字符（dp[i][j - 1] + 1）
}
}
}
// 返回word1转换为word2所需的最小编辑距离
return dp[word1.size()][word2.size()];
}
};
技巧算法：
// 定义一个名为Solution的类
class Solution {
public:
// 定义一个成员函数，用于找出数组中只出现一次的数字
// 输入参数是一个整数类型的向量（数组）
// 返回值是一个整数，表示数组中只出现一次的数字
int singleNumber(vector<int>& nums) {
// 初始化一个变量result为0，用于存储最终的结果
// 这里利用了异或运算的性质：a ^ a = 0, a ^ 0 = a
// 以及异或运算的交换律和结合律，使得我们可以将所有相同的数字异或成0
// 而只出现一次的数字与0异或后仍然是它本身
int result = 0;
// 遍历数组中的每一个数字
for (auto num: nums) {
// 对result和当前数字num进行异或运算
// 由于异或运算的性质，所有成对出现的数字都会被异或成0
// 而只出现一次的数字会被保留下来
result ^= num;
}
// 返回最终结果，即数组中只出现一次的数字
return result;
}
};
// 定义一个名为Solution的类
class Solution {
public:
// 定义一个成员函数，用于找出数组中的多数元素（出现次数超过一半的元素）
// 输入参数是一个整数类型的向量（数组）
// 返回值是一个整数，表示数组中的多数元素
int majorityElement(vector<int>& nums) {
// 初始化候选元素为0，计数器也为0
// 这里利用了Boyer-Moore投票算法的思想
int candidate = 0;
int count = 0;
// 遍历数组中的每一个数字
for (int num : nums) {
// 如果当前数字与候选元素相同，则计数器加1
if (num == candidate) {
++count;
}
// 如果当前数字与候选元素不同，则计数器减1
// 如果计数器减到0以下，说明候选元素可能不是多数元素
// 因此更新候选元素为当前数字，并将计数器重置为1
else if (--count < 0) {
candidate = num;
count = 1;
}
}
// 由于Boyer-Moore投票算法的特性
// 在一轮遍历后，候选元素要么是多数元素，要么是多数元素的候选者之一
// 为了确保正确性，我们通常需要再遍历一次数组来验证候选元素的出现次数
// 但在这个特定的问题中，由于题目已经保证了存在一个多数元素
// 因此我们可以直接返回候选元素作为结果
// 注意：在一般情况下，如果没有多数元素存在的保证，这一步验证是必要的
// 返回候选元素作为多数元素
return candidate;
}
};
// 定义一个名为Solution的类
class Solution {
public:
// 定义一个成员函数，用于对包含0、1、2的数组进行排序
// 输入参数是一个整数类型的向量（数组），通过引用传递，允许直接修改原数组
void sortColors(vector<int>& nums) {
// 初始化三个指针：left指向0的右侧，mid用于遍历数组，right指向2的左侧
int left = 0; // left指针左边的元素都是0
int mid = 0; // mid指针用于遍历数组
int right = nums.size() - 1; // right指针右边的元素都是2
// 当mid指针没有超过right指针时，继续循环
while (mid <= right) {
// 如果当前元素是0，将其与left指针指向的元素交换，并将left和mid指针都向右移动一位
if (nums[mid] == 0) {
swap(nums[left++], nums[mid++]);
}
// 如果当前元素是2，将其与right指针指向的元素交换（注意此时mid指针不动）
// 因为交换过来的元素可能是0、1或2，需要mid指针再次检查这个新元素
// 而right指针向左移动一位，因为它已经确定了一个2的位置
else if (nums[mid] == 2) {
swap(nums[right--], nums[mid]); // 注意这里没有增加mid，因为新元素未检查
}
// 如果当前元素是1，则只需要将mid指针向右移动一位
// 因为1已经处于正确的位置（在0和2之间），无需交换
else {
mid++;
}
}
// 循环结束后，数组已经按照0、1、2的顺序排序好了
// 注意：由于题目要求原地排序，因此没有使用额外的数组空间
}
};
class Solution {
public:
// 定义一个函数，用于找到并修改给定数组的下一个排列
void nextPermutation(vector<int>& nums) {
// 从倒数第二个元素开始向前遍历，找到第一个不满足从前往后递增的元素
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 如果找到了这样的元素（即i >= 0），说明从i+1到数组末尾是递减的
// 我们需要找到i之后（不包括i）比nums[i]大的最小元素，并与nums[i]交换
if (i >= 0) {
int j = nums.size() - 1;
// 从数组末尾开始向前遍历，找到第一个比nums[i]小的元素
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
// 交换nums[i]和nums[j]，这样nums[i]之后的序列仍然是递减的，但nums[i]变大了
swap(nums[i], nums[j]);
}
// 最后，将i之后的所有元素反转，使它们变为递增序列
// 这样做是为了得到比当前排列大且最接近的下一个排列
reverse(nums.begin() + i + 1, nums.end());
}
};
class Solution {
public:
// 定义一个函数，用于在一个包含n+1个整数的数组中找到任意一个重复的数字
int findDuplicate(vector<int>& nums) {
// 初始化快慢指针，都从数组的第一个元素开始
int slow = nums[0], fast = nums[nums[0]];
// 使用do-while循环来移动快慢指针，直到它们相遇
// 快指针每次移动两步（nums[nums[fast]]），慢指针每次移动一步（nums[slow]）
// 当快慢指针不相遇时，继续循环
while (slow != fast) {
slow = nums[slow]; // 慢指针移动一步
fast = nums[nums[fast]]; // 快指针移动两步
}
// 当快慢指针相遇时，我们知道存在一个环（即重复的数字）
// 为了找到环的起点（即重复的数字），我们将慢指针重新设置为数组的起始位置
// 然后同时移动快慢指针，直到它们再次相遇，相遇点即为环的起点（重复的数字）
slow = 0;
// 使用while循环来同时移动快慢指针，直到它们再次相遇
while (slow != fast) {
slow = nums[slow]; // 慢指针移动一步
fast = nums[fast]; // 快指针也移动一步（此时不需要再移动两步，因为我们已经知道存在环）
}
// 返回相遇点的值，即为重复的数字
return slow;
}
};