文档章节

接龙游戏

机智的帝江
 机智的帝江
发布于 2016/10/30 09:55
字数 473
阅读 3
收藏 0

题目描述 Description

给出了N个单词,已经按长度排好了序。如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙)。

你的任务是:对于输入的单词,找出最长的龙。
输入描述 Input Description

第一行为N(1<=N<=105)。以下N行每行一个单词(由小写组成),已经按长度排序。(每个单词长度<50)
输出描述 Output Description

仅一个数,为最长的龙的长度。
样例输入 Sample Input

5

i

a

int

able

inter
样例输出 Sample Output

3
数据范围及提示 Data Size & Hint

1<=N<=10^5

思路
这个题首先想到的是DP,但是数据范围是100000,显然不科学。
枚举每一个字符串显然也不科学。
但是。C++党表示还有一种叫做sort的东西。
使用快排对字符串进行排序。那么对于这个题来说前缀相同的字符串都在一起。
等等,我们好像发现了什么。没错!此题目能接起来的条件就是前缀!
所以我们利用一个叫做栈的神奇的东西,通过维护每一种前缀的最长长度取max来得到答案。
代码如下

#include <string>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

typedef struct data{
string s;
}data;

bool cmp(data x,data y)
{
int len = x.s.length() < y.s.length() ? x.s.length(): y.s.length();
for(int i = 0; i < len; i++)
{
if(x.s[i] < y.s[i])
return true;
else if(x.s[i] > y.s[i])
return false;
}
if(x.s.length() < y.s.length())
return true;
else return false;
}
data ch[100007];

int main()
{
int n;
cin>>n;
for(int i = 0; i < n; i++)
cin>>ch[i].s;

sort(ch,ch+n,cmp);
stack<data> mystatck;
int max = 1;
mystatck.push(ch[0]);
data tmp;
for(int i = 1; i < n; i++)
{
tmp = mystatck.top();
if(ch[i].s.find(tmp.s,0) == 0)
{
if(tmp.s.length() != ch[i].s.length())
mystatck.push(ch[i]);
}
else
{
while( !mystatck.empty()){
tmp = mystatck.top();
if(ch[i].s.find(tmp.s,0) == 0)
break;
mystatck.pop();
}
mystatck.push(ch[i]);
}
max = max > mystatck.size() ? max : mystatck.size();

}
cout<<max<<endl;
return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49019365

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
Freecell Solver 3.20.1 发布,接龙游戏开发包

Freecell Solver 3.20.1 修复了 Win32/MinGW 构建过程中的 bug。 Freecell Solver 是一个开发包,可以帮你自动处理纸牌接龙游戏开发过程中的问题,同时提供了跟 Solitaire 类似的变种。...

oschina
2013/07/03
500
0
C# 空当接龙 自动收牌的问题

我现在正在学习C#,在做空当接龙这个游戏的过程中,对于自动收牌这个问题弄了好久还是不会。可能是因为自己对于原程序还没有掌握的原因,希望大牛可以帮我看看程序,提出编写的方式。(留下你...

hebe518
2013/11/20
155
1
仿微信红包积分娱乐系统 红包接龙+红包扫雷

仿微信红包积分娱乐平台简介 平台以模仿微信红包功能为基础,针对当下微信群里的一些流行玩法,如接龙、牛牛、扫雷玩法戏开发出规范的游戏化流程,以虚拟币论输赢的方式进行娱乐。平台可对接...

天天科技
2016/10/14
13
0
Freecell Solver 3.26.0 发布,接龙游戏开发包

Freecell Solver 3.26.0 发布,此版本修复了一些输出的崩溃问题,已经更新在 GCC, CMake 和 Games-Solitaire-Verify;添加了尝试性的"pseudo-DFS" 解决方案;还包括一些代码清理,现代化元素...

oschina
2014/05/21
411
0
【算法趣题】Q14 世界杯参赛国的国名接龙

感谢关注天善智能,走好数据之路↑↑↑ 欢迎关注天善智能,我们是专注于商业智能BI,人工智能AI,大数据分析与挖掘领域的垂直社区,学习,问答、求职一站式搞定! 对商业智能BI、大数据分析挖...

天善智能
2018/05/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

spring mvc主流程源码阅读(剖析)

第一步,通过web.xml的配置可以知道,用户访问url第一次先走到DispatchServlet,(默认你学过基本的java的Servlet开发) <servlet><servlet-name>springServlet</servlet-name><serv......

小海bug
5分钟前
0
0
vmstat命令详解

https://www.cnblogs.com/ggjucheng/archive/2012/01/05/2312625.html

流光韶逝
39分钟前
1
0
如何理解算法时间复杂度的表示

先从O(1) 来说,理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的,所以拿到一个关键 字,用哈希函数转换一下,就可以直接从表中取出对应的值。和现存数据有多少毫无关系,故而每次执...

yky20190625
55分钟前
5
0
分布式架构 实现分布式锁的常见方式

一、我们为什么需要分布式锁? 在单机时代,虽然不需要分布式锁,但也面临过类似的问题,只不过在单机的情况下,如果有多个线程要同时访问某个共享资源的时候,我们可以采用线程间加锁的机制...

太猪-YJ
今天
8
0
GitLab Docker 安装记录

安装环境 环境Centos7.4 64 1.拉取镜像文件 docker pull gitlab/gitlab-ce:latest 2.docker 安装 git.zddts.com 为访问域名或换成可以访问的IP docker run -d --hostname git.***.com -p ......

侠者圣
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部