双向广搜-

2025-03-14 约 322 字预计阅读 1 分钟

https://bing.ee123.net/img/rand?artid=146266053

双向广搜

从两侧同时展开,那测数据少就从哪侧展,两者展开结果出现一样的,返回答案

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(),wordList.end());
    if(dict.find(endWord)==dict.end())
    return 0;
    unordered_set<string> smalllevel,biglevel,nextlevel;
    smalllevel.insert(beginWord);
    biglevel.insert(endWord);
    for(int len=2;!smalllevel.empty();len++)
    {
        for(string s:smalllevel)
        {
            string w=s;
            for(int i=0;i<w.length();i++)
            {
                char old=w[i];
                for(char ch='a';ch<='z';ch++)
                {
                    if(ch!=old)
                    {
                    w[i]=ch;
                    if(biglevel.find(w)!=biglevel.end())
                    return len;
                    if(dict.find(w)!=dict.end())
                    {
                        //塞入nextlevel
                        nextlevel.insert(w);
                        dict.erase(w);
                    }
                    }
                }
                w[i]=old;
            }
        }
    if(nextlevel.size()<=biglevel.size())
    {
        smalllevel=nextlevel;
        nextlevel.clear();
    }
    else
    {
        smalllevel=biglevel;
        biglevel=nextlevel;
        nextlevel.clear();
    }
    }
    return 0;
    }
};

第二种用法:分成左右两半时暴力展开,把所有结果再整合再一起

牛牛的背包问题

由于这道题目的数据范围过大,达到10的9次方,所以动态规划方法无法通过

#include<bits/stdc++.h>
using namespace std;
const int maxn=40;
long long arr[maxn],w;
vector<long long>lsum,rsum;
int n;
void dfs(int i,int end,long long path,vector<long long> &ans)
{
	if(path>w)
	return;
	if(i==end+1)
	ans.push_back(path);
	else
	{
		dfs(i+1,end,path+arr[i],ans);
		dfs(i+1,end,path,ans);
	}
}
int main()
{
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	cin>>arr[i];
	dfs(1,n/2,0,lsum);
	dfs(n/2+1,n,0,rsum);
	sort(lsum.begin(),lsum.end());
	sort(rsum.begin(),rsum.end());
	long long ans=0;
	for(int i=lsum.size()-1,j=0;i>=0;i--)
	{
		while(j<rsum.size()&&lsum[i]+rsum[j]<=w)
		j++;
		ans+=j;
	}
	cout<<ans;
}

最接近目标的子序列和

class Solution {
public:
 vector<int> lsum,rsum;
    int minAbsDifference(vector<int>& nums, int goal) {
    int n=nums.size();
    f(0,n/2,nums,lsum,0);
    f(n/2,n,nums,rsum,0);
    sort(lsum.begin(),lsum.end());
    sort(rsum.begin(),rsum.end());
    int ans=INT_MAX;
    for(int l=0,r=rsum.size()-1;l<lsum.size();l++)
    {
        while(r>0&&abs(lsum[l]+rsum[r]-goal)>=abs(lsum[l]+rsum[r-1]-goal))
        r--;
        ans=min(ans,abs(lsum[l]+rsum[r]-goal));
    }
    return ans;
    }
    void f(int i,int end,vector<int> &nums,vector<int>& ans,long long path)
    {
        if(i==end)
        ans.push_back(path);
        else
        {
            //这里选择了按组展开
            int j=i+1;
            for(;j<end&&nums[j]==nums[i];j++);
            for(int k=0;k<=j-i;k++)
            f(j,end,nums,ans,path+k*nums[i]);
        }
    }
};

目录

双向广搜-

双向广搜