今日学习记录
1. 拆分合并数组leetcode.3690
关键词: bfs
问题分析：
- 一开始没看到数据这么小,所以没有想到暴力,结果要搜索的范围这么小,那就是暴力搜索了,但是搜索也要技巧
核心思路
- 既然就是搜索,那么不要再想有什么方法去限制了,直接搜索,但是这个不是简单的全排列,把一个 nums1 排列变成 nums2 的排列,但是每次操作却可以操作一个整个子字符串,所以怎么弄,别想多了就是一个个位子枚举,就是这个数组操作我不太收悉,而且不能使用哈希 set 来进行快速去重,要使用红黑树实现的 set 或者手写哈希函数
- 还能提升,将这两个数组转成字符串再来进行剪切拼接的操作,字符串的操作更加简单,最最关键的是 string 可以直接使用哈希 set,减少了大部分麻烦的事,而且性能更好,跟最快的位运算版本差不了多少
- 虽然但是,还能再提升,就是位运算了
**最终代码：
class Solution {
public:
int minSplitMerge(vector<int>& nums1, vector<int>& nums2) {
if(nums1==nums2) return 0;
unordered_set<string> st;
string str1 = "";
for(int x:nums1) str1 += x-'0';
string str2 = "";
for(int x:nums2) str2 += x-'0';
vector<string> q = {str1};
int n = nums1.size();
for(int ans = 0;;ans++){
vector<string> next;
for(auto arr:q){
if(arr==str2){
return ans;
}
for(int l = 0;l<n;l++){
for(int r = 1;r<=n-l;r++){
auto b = arr;
string temp = b.substr(l,r);
b.erase(l,r);
for(int d = 0;d<b.size();d++){
auto c = b;
c.insert(d,temp);
if(st.insert(c).second) next.push_back(c);
}
}
}
}
q = move(next);
}
return 1;
}
};学到的点：
- bfs