技术栈

主页 > 移动开发 >

程序员进阶之算法练习(二十八)

技术栈 - 中国领先的IT技术门户

前言

四道题,分别锻炼哈希、贪心、贪心+排序、二分四个能力。
第一题较为简单,后续的题目都需要一定的基础。
贪心是最基础的能力,codeforce有专门的
Tag用以描述,叫做greedy;
二分是常用的一种降低时间复杂度方法,前提的要求是单调性;
哈希和排序是工程中常见的处理,前者用于映射,后者用于数据有序化。
这四个能力也多用于面试的算法题,因为其属于基础能力。

正文

1.Santa Claus and Keyboard Check

题目链接
题目大意:
小明把键盘的键都卸下来清洗,在装回去后,发现有些键装错了。
他看着键盘,打出一个字符串str,在屏幕显示出来一个字符串str';
现在他可以选择任意两个键,交换它们的位置,但是每个键只能交换一次;

问,小明是否能复原正确的键盘?
如果可以,先输出交换次数,接下来每行输出每次交换的字母;(顺序无关)
如果不可以,直接输出-1。

输入数据:
str长度不超过1000;

Examples
input
helloworld
ehoolwlroz
output
3
h e
l o
d z
input
merrychristmas
christmasmerry
output
-1

题目解析:
题目有个很重要的条件,每个键只能使用一次。
那么每次当遇到字符不同的时候,这两个字符就必须交换;如果这个字符已经交换过,那么无解。

实现逻辑,可以用一个简单字符hash来实现,对str的字符,每次先判断是有hash字符,如果有则转成hash后的符;
如果没有,添加hash[c]=c; 保证下次再遇到不会出错;
然后进行判断,如果hash后的字符和str'上的不对应,则无解;

2.Santa Claus and Robot

题目链接
题目大意:
有一个机器人,在一个网格的网格线上行走,每次有L/R/U/D四个方向;
当机器人从点p1走到点p2时,它会走最短的路径。
如果有3个点p1、p2、p3,机器人会按照最短的路径走向p1点,到达后再走向p2点,再到p3点;
现在假设机器人在原点,已知机器人走的序列(长度为n),求最少有几个点,可以满足机器人走的序列。

输入数据:
n (1 ≤ n ≤ 2·105)

Examples
input
6
RRULDD


output
2
input
26
RRRULURURUULULLLDLDDRDRDLD
output
7

题目解析:
看似很难,仔细分析一下,只要找到两点之间路径的规律即可。
当出现过R之后,本次路径,就不允许再出现L,同理L、U、D;
这样,R、L之间算一条路径,U、D之间算一条路径,加起来就是需要的最小点数。

3.Santa Claus and a Palindrome

题目链接
题目大意:
k个字符串,长度均为n;
每个字符串有一个权值a[i];
现在可以从k个字符串中,选择若干个字符串拼成一个新的回文串str,要求每个字符串只能用一次,并且不能改变原有字符串的字符排列顺序;
str的权值为所有拼成的串的权值和,求str的最大权值。
(注意,空串也是回文串,所有str的最大权值不小于0)

输入数据:
1 ≤ k, n ≤ 100 000; n·k  ≤ 100 000
- 10 000 ≤ a[i] ≤ 10 000

Examples
input
7 3
abb 2
aaa -3
bba -1
zyz -4
abb 5
aaa 7
xyx 4
output
12
样例解释:最后的结果是abbaaaxyxaaabba,组合第5, 2, 7, 6 和 3字符串。

题目解析:
每个字符串分两种,第一种是自身为回文,第二种是自身不为回文。
自身为回文串有两种选择,放在中心点(单独一个)和不放在中心点(两两配对分在左右);
自身不为回文串的字符串str,可以和str的reverse组合回文串;(比如abc和cba)
我们把字符串相同的放到同一个桶,把桶按照字符串是否为回文分成两类。
对于非回文串str,每次从str的桶里找一个最大的key值x,再从reverse(str)的桶里找一个最大的key值y,只要x+y>0,那么就组成一个匹配;
对于回文串paliStr,每次从paliStr的桶里找key值最大的两个x和y,如果x+y>0,那么就组成一个匹配;
这里有个trick:因为paliStr还可以单独放在中间,如果paliStr的两个权值是-3和5,那么选中-3其实是不划算的。
但是如果只选择x>0&&y>0的话,假设有多个-3和5的组合,就会失去-3+5=2的额外收益。
抉择是根源是在于paliStr可以选择放在中间!但是中间其实只能有一个字符串。
于是可以采取额外补偿的方式,我们还是采用x+y>0的选择,但是保留一个addition的收益,类似-3和5的组合,addition的收益是3;
同理,如果只剩下一个回文串,那么addition的收益是该回文串。
最后计算所有的收益和+addition收益得到答案。

思考

责任编辑:admin  二维码分享:
本文标签: str回文题目字符串数字ans