1. 编辑距离
给你两个单词 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 由小写英文字母组成
以下程序实现了这一功能，请你填补空白处的内容：
```c++
#include <bits/stdc++.h> using namespace std; class Solution { public: int minDistance(string word1, string word2) { int l1 = word1.length(); int l2 = word2.length(); vector<int> dp(l2 + 1); for (int i = 0; i <= l2; i++) { dp[i] = i; } int up = 0; for (int i = 1; i <= l1; i++) { int left_up = dp[0]; dp[0] = i; for (int j = 1; j <= l2; j++) { up = dp[j]; _________________________; else { dp[j] = 1 + min(left_up, min(up, dp[j - 1])); } left_up = up; } } return dp[l2]; } }; ```
出处：
https://edu.csdn.net/practice/27452676
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int minDistance(string word1, string word2) { int l1 = word1.length(); int l2 = word2.length(); vector<int> dp(l2 + 1); for (int i = 0; i <= l2; i++) { dp[i] = i; } int up = 0; for (int i = 1; i <= l1; i++) { int left_up = dp[0]; dp[0] = i; for (int j = 1; j <= l2; j++) { up = dp[j]; if (word1[i - 1] == word2[j - 1]) { dp[j] = left_up; } else { dp[j] = 1 + min(left_up, min(up, dp[j - 1])); } left_up = up; } } return dp[l2]; } }; int main() { Solution s; string word1 = "horse"; string word2 = "ros"; cout << s.minDistance(word1, word2) << endl; word1 = "intention"; word2 = "execution"; cout << s.minDistance(word1, word2) << endl; return 0; }
输出：
3
5
2. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
出处：
https://edu.csdn.net/practice/27452677
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int majorityElement(vector<int> &nums) { unordered_map<int, int> counts; int majority = 0, cnt = 0; for (int num : nums) { ++counts[num]; if (counts[num] > cnt) { majority = num; cnt = counts[num]; } } return majority; } }; int main() { Solution s; vector<int> nums = {3,2,3}; cout << s.majorityElement(nums) << endl; nums = {2,2,1,1,1,2,2}; cout << s.majorityElement(nums) << endl; return 0; }
输出：
3
2
3. 求分数数列的前N项和
有一分数序列:2/1,-3/2,5/3,-8/5,13/8,-21/13,…, 由用户输入项目数N，求这个数列的前N 项之和
以下程序实现了这一功能，请你填补空白处内容：
```c++ #include <stdlib.h> #include <stdio.h> int main() { int n; scanf("%d", &n); int i; double a1 = 2, b1 = 1; double a2 = 3, b2 = 2; double sum = a1 / b1 - a2 / b2; if (n == 1) printf("%f\n", a1 / b1); else if (n == 2) printf("%f\n", sum); else { for (i = 0; i < n - 2; i++) { double exp = a2 / b2; _____________________; sum += exp; double a = a1 + a2; double b = b1 + b2; a1 = a2; b1 = b2; a2 = a; b2 = b; } printf("%f\n", sum); } return 0; } ```
出处：
https://edu.csdn.net/practice/27452678
代码：
#include <stdlib.h> #include <stdio.h> int main() { int n; scanf("%d", &n); int i; double a1 = 2, b1 = 1; double a2 = 3, b2 = 2; double sum = a1 / b1 - a2 / b2; if (n == 1) printf("%f\n", a1 / b1); else if (n == 2) printf("%f\n", sum); else { for (i = 0; i < n - 2; i++) { double exp = a2 / b2; if (i % 2 == 0) exp *= -1; sum += exp; double a = a1 + a2; double b = b1 + b2; a1 = a2; b1 = b2; a2 = a; b2 = b; } printf("%f\n", sum); } return 0; }
输出：
6
0.691667
