广州天河区是市中心吗_制作网线的要点_网络营销的四种方式_营销培训课程ppt

概念

基本的概念

• 子序列： 由原序列中若干个元素组成，元素可以不连续，但和原序列的顺序一致。
• 最长公共子序列： 一个序列即是甲序列的子序列，也是乙序列的子序列，则该序列称为为甲和乙的公共子序列。长度最长的公共子序列，即最长公共子序列。
• 两个序列的公共子序列不一定是唯一的。

递归

算法

• lcs(s1,s2)表示：串s1和s2的最大公共子序列长度，并返回其值
• 先比较两个串的首字符，如果相等，递归实现lcs(s1+1,s2+1)+1即可
• 如果不相等，则返回lcs(s1,s2+1),lcs(s1+1,s2)中较大的。
  
• 由上图可以看出，最大公共子序列的值为3，但不唯一，abc,bca的长度都是3。

代码

#include<iostream>
using namespace std;
int lcs(const char* a,const char* b){if(*a == 0 || *b==0) return 0;if(*a==*b)return lcs(a+1,b+1)+1;return max(lcs(a,b+1),lcs(a+1,b));
} 
int main(){cout<<lcs("axbcydz","xayybcxd")<<endl;return 0;
}

优化

• 递归的优点是思路简单，但是耗费资源，重复递归调用。
• 如下图，草拟相同圈处是重复递归计算的地方，如果串长些，那么这种重计划量将非常繁巨，以致电脑无法计算。
  
• 所以需改进，改进的方法是，相同的串相互比较求最大公共子序列时，就将其存储起来，放入map，下次再遇到相同的2个串比较时，直调从map中取值。
• 因为加入了参递，所以递归函数需要增参。
• 递归函数f(m,s1,k1,s2,k2)
• 参数说明。m是map记录着2个子串的最大公共子序列，s1、s2是子串，k1、k2是从子串的哪个下标开始比较。
• 即只需以k1\k2的位置作为键，递归函数的返回值(最大公共子序列的长度)作为值，存入map中即可。

map基础

• 头文件，#include
• map存取键-值对，查找速度快。键需能比较，此应用中键为2个int，int。
• stl中的pair可以保存<int,int>。定义为

#include <utility> // 包含 std::pair 的头文件
#include <iostream>
using namespace std;
int main() {// 直接初始化 std::pairpair<int, double> pair1(1, 3.14);// 使用 std::make_pair 函数初始化 std::pairpair<string, int> pair2 = make_pair("Kimi", 2024);// 访问 pair 的元素cout << "pair1: " << pair1.first << ", " << pair1.second << endl;cout << "pair2: " << pair2.first << ", " << pair2.second << endl;// 修改 pair 的元素pair1.first = 2;pair2.second = 2025;return 0;
}

• map中统计键pair出现的次数

#include <iostream>
#include <map>
using namespace std;
int main() {map<pair<int, int>, string> map;// 插入键值对map[make_pair(1, 2)] = "12";map[make_pair(1, 2)] = "21"; // 注意：这实际上是更新了键(1, 2)的值map[make_pair(3, 4)] = "34";// 要查找的键pair<int, int> key_to_count(1, 2);// 使用count查找键size_t count = map.count(key_to_count);cout << "The key (" << key_to_count.first << ", " << key_to_count.second << ") appears " << count << " times." << endl;return 0;
}

• map中查找pair对

#include <iostream>
#include <map>
#include <utility> // For std::pair
using namespace std;
int main() {// 创建一个map，键为pair<int, int>，值为stringmap<pair<int, int>, string> map;// 插入键值对map[make_pair(1, 2)] = "12";map[make_pair(3, 4)] = "34";// 要查找的键pair<int, int> key_to_find(1, 2);// 使用find查找键auto it = map.find(key_to_find);if (it != map.end()) {cout << "Found key: (" << it->first.first << ", " << it->first.second << ") with value: " << it->second << endl;} else {cout << "Key not found." << endl;}return 0;
}

• map遍历

#include <iostream>
#include <map>int main() {std::map<int, std::string> myMap;// 插入一些键值对myMap[1] = "one";myMap[2] = "two";myMap[3] = "three";// 使用 begin() 获取指向第一个元素的迭代器auto it = myMap.begin();// 检查迭代器是否不是 end()（即检查 map 是否不为空）if (it != myMap.end()) {// 使用迭代器访问并打印第一个元素std::cout << "The first key-value is: " << it->first << " => " << it->second << std::endl;}// 使用范围基于的 for 循环遍历 mapfor (const auto& pair : myMap) {std::cout << pair.first << " => " << pair.second << '\n';}return 0;
}

• 自定义pair对

#include <iostream>
#include <map>
using namespace std;
// 定义一个结构体作为键
struct IntPair {int first;int second;// 必须定义比较运算符，以便map可以比较键bool operator<(const IntPair& other) const {return first < other.first || (first == other.first && second < other.second);}
};
int main() {// 定义一个map，键为IntPair，值为stringstd::map<IntPair, std::string> map;// 插入键值对map[{1, 2}] = "12";map[{3, 4}] = "34";// 访问键值对for (const auto& kv : map) {cout << "Key: (" << kv.first.first << ", " << kv.first.second << ") Value: " << kv.second << endl;}return 0;
}

优化代码

#include<iostream>
#include<map>
using namespace std;
int f(map<pair<int,int>,int>& m,const char* s1,int k1,const char* s2,int k2){if(s1[k1]==0 || s2[k2]==0)return 0;pair<int,int> p(k1,k2); //构建子串pair对 if(m.count(p))//查找map中是否有相应的子串最大公共子序列值return m[p];//如果存储了，则直接返回子序列长度，不必再递归计算 //map中未记录，才计算最大公共子序列的长度 if(s1[k1]==s2[k2]){ int t=f(m,s1,k1+1,s2,k2+1)+1;m[make_pair(k1,k2)]=t;return t;}int t1=f(m,s1,k1+1,s2,k2);int t2=f(m,s1,k1,s2,k2+1);int t=max(t1,t2);m[make_pair(k1,k2)]=t;return t;
}
int lcs(const char* s1,const char* s2){
//	map<int,int>ma;map<pair<int,int>,int> m;//定义一个map，键为pair<int,int>,值为int。 return f(m,s1,0,s2,0);
} 
int main(){cout<<lcs("axbcydz","xayybcxd")<<endl;cout<<lcs("axbcydzaxbcydz","xayybcxdaaaaabbbxxccc")<<endl;return 0;
}