您现在的位置是:首页 >技术交流 >C/C++每日一练(20230510) 编辑距离、多数元素、数列累和网站首页技术交流
C/C++每日一练(20230510) 编辑距离、多数元素、数列累和
目录
1. 编辑距离 ???
2. 多数元素 ?
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
", a1 / b1);
else if (n == 2)
printf("%f
", 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
", 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
", a1 / b1);
else if (n == 2)
printf("%f
", 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
", sum);
}
return 0;
}
输出:
6
0.691667
? 每日一练刷题专栏 ?
✨ 持续,努力奋斗做强刷题搬运工!
? 点赞,你的认可是我坚持的动力!
? 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
Golang每日一练 专栏 | |
Python每日一练 专栏 | |
C/C++每日一练 专栏 | |
Java每日一练 专栏 |