肯尼亚网站域名,万能进销存软件免费版,网站 建设 计划,沈阳做网站黑酷科技双向广搜常见用途
1#xff1a;小优化。bfs的剪枝策略#xff0c;分两侧展开分支#xff0c;哪侧数量少就从哪侧展开。 2#xff1a;用于解决特征很明显的一类问题。特征#xff1a;全量样本不允许递归完全展开#xff0c;但是半量样本可以完全展开。过程#xff1a;把…双向广搜常见用途
1小优化。bfs的剪枝策略分两侧展开分支哪侧数量少就从哪侧展开。 2用于解决特征很明显的一类问题。特征全量样本不允许递归完全展开但是半量样本可以完全展开。过程把数据分成两部分每部分各自展开计算结果然后设计两部分结果的整合逻辑。 下面通过几个题目加深理解。 题目一
测试链接https://leetcode.cn/problems/word-ladder
分析这个就是双向广搜的第一个用途。分别从beginWord和endWord开始广度优先遍历得到转换成的单词序列对于得到的两个单词序列选择单词数较少的再次使用广度优先遍历。当得到的单词序列中有和另一序列中重复的单词代表beginWord可以转化成endWord。如果广度优先遍历的次数大于wordList的长度加1则代表不能转换。代码如下。
class Solution {
public:setstring beginLevel;setstring endLevel;setstring nextLevel;setstring dict;void build(string beginWord, string endWord, vectorstring wordList){int length wordList.size();for(int i 0;i length;i){dict.insert(wordList[i]);}beginLevel.insert(beginWord);endLevel.insert(endWord);}int ladderLength(string beginWord, string endWord, vectorstring wordList) {build(beginWord, endWord, wordList);setstring temp;int ans 0;string cur;char cur_char;int cur_length;if(dict.count(endWord) 0){return ans;}ans 2;while (true){if(beginLevel.size() endLevel.size()){for(setstring::iterator it beginLevel.begin();it ! beginLevel.end();it){cur *it;cur_length cur.size();for(int i 0;i cur_length;i){cur_char cur[i];for(char j a;j z;j){cur[i] j;if(dict.count(cur) ! 0 j ! cur_char){if(endLevel.count(cur) ! 0){return ans;}else{nextLevel.insert(cur);}}}cur[i] cur_char;}}temp beginLevel;beginLevel nextLevel;nextLevel temp;nextLevel.clear();ans;}else{for(setstring::iterator it endLevel.begin();it ! endLevel.end();it){cur *it;cur_length cur.size();for(int i 0;i cur_length;i){cur_char cur[i];for(char j a;j z;j){cur[i] j;if(dict.count(cur) ! 0 j ! cur_char){if(beginLevel.count(cur) ! 0){return ans;}else{nextLevel.insert(cur);}}}cur[i] cur_char;}}temp endLevel;endLevel nextLevel;nextLevel temp;nextLevel.clear();ans;}if(ans wordList.size()1){break;}}return 0;}
};
其中采用哈希表来快速判断是否有重复单词。 题目二
测试链接https://www.luogu.com.cn/problem/P4799
分析这个就是双向广搜的第二个用途。刚拿到这个题会很容易地想到使用动态规划但是一看到数据量就知道一定会超时。而将每场门票分成两部分分别使用广度优先搜索得到每一种搭配的花费。对这两部分使用广度优先搜索得到的搭配从小到大排序后使用双指针即可得到所有方案的个数。代码如下。
#include iostream
#include vector
#include algorithm
using namespace std;
int N;
long long M;
long long price[40];
vectorlong long l;
vectorlong long r;
void f(int i, int e, long long sum, long long bound, vectorlong long ans){if(sum bound){return ;}if(i e){ans.push_back(sum);}else{f(i1, e, sum, bound, ans);f(i1, e, sumprice[i], bound, ans);}
}
int main(void){int middle;long long left, right;long long l_length, r_length;long long ans 0;scanf(%d%ld, N, M);for(int i 0;i N;i){scanf(%ld, price[i]);}middle N / 2;f(0, middle, 0, M, l);f(middle, N, 0, M, r);sort(l.begin(), l.end());sort(r.begin(), r.end());l_length l.size();r_length r.size();left 0;right r_length-1;for(;left l_length right 0;left){while (right 0 l[left] r[right] M){--right;}if(right 0){ans (right 1);}}printf(%ld, ans);
}
其中f函数是一个递归函数代表下标从i到e当前和为sum不能超过bound的搭配的花费将花费存储在ans数组中得到了l和r两个花费数组后排序然后利用双指针搭配数组两边之和不超过bound就代表是一种方案。 题目三
测试链接https://leetcode.cn/problems/closest-subsequence-sum
分析这道题和题目二基本一致。主体代码相同只是求的东西不一样。代码如下。
class Solution {
public:vectorint l;vectorint r;void f(int i, int e, int sum, int bound, vectorint ans, vectorint nums){if(i e){ans.push_back(sum);}else{f(i1, e, sum, bound, ans, nums);f(i1, e, sumnums[i], bound, ans, nums);}}int minAbsDifference(vectorint nums, int goal) {int length nums.size();int ans -((1 31) 1);f(0, length/2, 0, goal, l, nums);f(length/2, length, 0, goal, r, nums);sort(l.begin(), l.end());sort(r.begin(), r.end());int l_length l.size();int r_length r.size();int left 0, right r_length-1;for(;left l_length right 0;left){while (right 0 l[left] r[right] goal){--right;}if(right 0){ans ans abs(l[left] r[right] - goal) ? ans : abs(l[left] r[right] - goal);if(right r_length-1){ans ans abs(l[left] r[right1] - goal) ? ans : abs(l[left] r[right1] - goal);}}else{ans ans abs(l[left] r[0] - goal) ? ans : abs(l[left] r[0] - goal);}}return ans;}
};
其中主体代码也是利用f函数得到搭配序列然后排序使用双指针得到结果。
