本文主要是介绍10.2（583. 两个字符串的删除操作 80. 删除排序数组中的重复项 II），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
583. 两个字符串的删除操作
思路：
求出最大公共子列和，然后把总长度减去两倍的公共子列和的长度即可。
效率：100%
程序代码：
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
//583. 两个字符串的删除操作
//思路、找到最长公共子列的长度即可（动态规划）
using namespace std;
class Solution {
public:int minDistance(string word1, string word2) {int sum = word1.size() + word2.size();//表示一共的长度int m = word1.size();int n = word2.size();vector<vector<int>> matrix(m+1);vector<int> vec(n+1);//都想外围扩展了一圈//首先进行初始化for (int i = 0; i < m + 1; i++) {for (int j = 0; j < n + 1; j++) {vec[j] = 0;}matrix[i] = vec;}for (int i = 1; i < m + 1; i++) {for (int j = 1; j < n + 1; j++) {if (word1[i-1] == word2[j-1]) matrix[i][j] = matrix[i - 1][j - 1]+1;else matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1]);}}return (sum - 2*matrix[m][n]);}int max(int &a, int &b) {return (a > b ? a : b);}};int main()
{Solution bb;string word1, word2;cin >> word1 >> word2;cout<<bb.minDistance(word1,word2)<<endl;return 0;
}80. 删除排序数组中的重复项 II
思路：使用向量自带的删除函数进行删除，感觉效率可能不高，我觉得每一次删除可能都是后面的所有内容进行一次移动（还没看迭代器的相关知识，自我感觉是全体的移动）
效率：12.62%，果然低得感人。。。。必须得改进。。。
程序代码：
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
//80. 删除排序数组中的重复项 II
//思路、直接在原有的基础上删除，使用erase函数，但是感觉效率应该不会很高，还可以使用其他的方法
using namespace std;class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n == 0||n==1||n==2)return n;vector<int>::iterator i = nums.begin()+2; //从向量申请迭代器while(i!=nums.end()) {if (*i == *(i-1) && *i == *(i-2)) i=nums.erase(i);else i++;}return nums.size();}
};int main()
{Solution bb;int n;//表示数组的数量cin >> n;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}cout<<bb.removeDuplicates(nums)<<endl;return 0;
}
使用原位交换算法得到的程序代码如下：
效率：37.21% 。。。。。。无语
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
//80. 删除排序数组中的重复项 II
//思路、直接在原有的基础上删除，使用erase函数，但是感觉效率应该不会很高，还可以使用其他的方法
using namespace std;class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n == 0 || n == 1 || n == 2) return n;int i = 2, j = 3;while (j <n) {if (nums[j] == nums[i - 1] && nums[j] == nums[i - 2])j++;else if(nums[i]==nums[i-1]&&nums[i]==nums[i-2]||(nums[j] != nums[i - 1] || nums[j] != nums[i - 2])&&(nums[i]<nums[i-1])){swap(nums[i], nums[j]);i++;j++;}else {i++;j++;}}if ((nums[i] != nums[i - 1] || nums[i] != nums[i - 2])&&nums[i]>=nums[i-1]) i++;return i;//返回的结果就是i}void swap(int &a, int &b) {int tmp = a;a = b;b = tmp;}};int main()
{Solution bb;int n;//表示数组的数量cin >> n;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}cout<<bb.removeDuplicates(nums)<<endl;return 0;
}
以下是排名第一的方法：
static const auto __ = []() {ios::sync_with_stdio(false);cin.tie(nullptr);return nullptr;
}();class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.empty())return 0;int index = 1;int notRepeat = 1;int count = 1;int lastNum = nums[0];for(int i = 1; i < nums.size(); i++){if(nums[i] == lastNum){count++;if(count <= 2){swap(nums[index], nums[i]);index++;}}else{count = 1;lastNum = nums[i];swap(nums[index], nums[i]);index++;}}return index;}
};
优秀！！其实和我的思路差不多，之不是改成通过计数的方式了。
这篇关于10.2（583. 两个字符串的删除操作 80. 删除排序数组中的重复项 II）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
