Phone List POJ-3630 字典树 or 暴力

题意

目前有 t 组数据， n 个电话号码，如果拨打号码的时候先拨通了某个号码，那么这一串号码就无法全部拨通。

举个例子 911 和 9112016652 相比后者就无法被拨通，因为 911 会先被拨通。

如果都可拨通输出 YES 不然输出 NO。

解题思路

这里我是对insert函数进行了修改，在插入的过程中进行判断。

具体过程是这样的，flag数组记录两个信息，一是以这个结点结尾是不是一个完整的字符串，如果是那么就赋值为1，如果这个结点不是一个完整的字符串的结尾的话，那么这个结点是不是一个长字符串的中间结点呢？如果是，那么就赋值为-1。如果是0的话，那么说明这个点没有字符串经过，更谈不上是一个字符串的结尾了。这样我们在插入一个新的字符串的时候就要进行判断了，判断什么？判断这个结果的结点是不是前面一个已经插入结点的结尾，如果是的话，那么这个样例就可以结束了，后面的输入也不用再次插入了，节省时间。

另一个方法是进行sort函数对字符串进行排序，这个让我眼前一亮，字符串也可以排序！之后就是进行模拟了。

代码实现

字典树

#include<cstdio>

#include<cstring>

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

const int maxn=1e5+7;

int tree[maxn][11];

int flag[maxn];

int tot;

bool insert(char *str)

{

	int len=strlen(str);

	int root=0;

	for(int i=0; i<len; i++)

	{

		int id=str[i]-'0';

		if(!tree[root][id])

			tree[root][id]=++tot;

		if(flag[root]==1) //表示这个点是一个完整的数

			return false;

		if(flag[root]==0) //表示没有经过，也没有完整的数

			flag[root]=-1; //表示经过这里

		root=tree[root][id];

	}

	if(flag[root]!=0)

		return false;

	flag[root]=1;

	return true;

}

int main()

{

	int t, n, f=1;

	char buf[15];

	scanf("%d", &t);

	while(t--)

	{

		memset(tree, 0, sizeof(tree));

		memset(flag, 0, sizeof(flag));

		scanf("%d",&n);

		f=1;

		tot=0;

		while(n--)

		{

			scanf("%s", buf);

			if(f)

			{

				if(insert(buf)==false)//如果这个号码插入过程中，发现前缀是另一个号码，那么就可以令f=0

					f=0;//后续的字符串就不用进行插入了。

			}

		}

		if(f==1)

			printf("YES\n");

		else printf("NO\n");

	}

	return 0;

}

暴力

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

string s[100005];

int main()

{

	char p[12];

	int t,flag=0,n,i,j;

	scanf("%d",&t);

	while(t--)

	{

		flag=0;

		scanf("%d",&n);

		for(int i=0;i<n;i++)

		{

			scanf("%s",&p);

			s[i]=p;

		}

		sort(s,s+n);

		for(int i=1;i<n;i++)

		{

			cout<<s[i-1]<<endl;

			if(s[i].size()>s[i-1].size())//如果当前的字符串比前一个还要短的话，那么当前的字符串肯定不受影响

			{

				for(j=0;j<s[i-1].size();j++)

				   if(s[i][j]!=s[i-1][j])

				       break;

			    if(j==s[i-1].size())

			    {

			    	flag=1;

			    	break;

				}

			}

		}

		if(flag) printf("NO\n");

		else printf("YES\n");

	}

	return 0;

}

巴特西

Phone List POJ-3630 字典树 or 暴力

Phone List POJ-3630 字典树 or 暴力

题意

解题思路

代码实现

最新文章

热门文章