您现在的位置是:首页 >技术交流 >C/C++每日一练(20230510) 编辑距离、多数元素、数列累和网站首页技术交流

C/C++每日一练(20230510) 编辑距离、多数元素、数列累和

Hann Yang 2024-06-14 17:18:27
简介C/C++每日一练(20230510) 编辑距离、多数元素、数列累和

目录

1. 编辑距离  ???

2. 多数元素  ?

3. 求分数数列的前N项和  ※

? 每日一练刷题专栏 ?

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


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/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每日一练 专栏

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。