首页 >程序人生

程序员进阶之算法练习

2018-02-02 11:14 编辑: 枣泥布丁 分类:程序人生 来源:落影loyinglin

前言

算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。

正文

1. Compote

题目链接

题目大意:

给出a、b、c三种材料,可以1:2:4组成d,不能拆分成0.5,问最多有多少材料参与制作。

1个a 2个b 4个c 组成一个d,参与的材料有1+2+4=7。

a,b,c (1 ≤ a,b,c ≤ 1000)

Examples

input

2

5

7

output

7

input

4

7

13

output

21

input

2

3

2

output

0

题目解析:

题意非常清晰,暴力的做法是枚举,每次给a/b/c分别减去1/2/4,直到其中一种材料不足。

更快的做法是ans = min(a * 7, min(b / 2 * 7, c / 4 * 7));

2. Decoding

题目链接

题目大意:

定义一个“median letter”的概念:

1、如果字符串长度为奇数,那么为中间的字符;

2、如果字符串长度为偶数,那么为中间偏左的字符;


现在对一个字符串,选择median letter,并且将这个字符拿出来,重复这个操作;

每次取出来的字符串依次排好,得到一个新字符串。

例如:volga 分别取出来的字符是l,o,g,v,a,组成一个新的字符串 logva 。


现在给出字符串的长度n,还有一个字符串str;

求一个字符串strNew,要求strNew按照上面的规则,组成是新字符串是str。

Examples

input

5

logva

output

volga

input

2

no

output

no

input

4

abba

output

baba

题目解析:

先来看这个提取的过程:每次都是选出中间的字符。

那么在恢复原来字符串的时候,只要按照原来的顺序,假设有n个字符串。

那么第一个字符串是n/2, 然后再假设一个left 和 right 指针,然后轮流往两边延伸即可。

核心点:strNew和str相同长度

3.Tram

题目链接

题目大意:

在一条直线上,有一辆公共汽车从点0到点s,不断往返,速度为t1秒每米;

有一个人,要从点x1到点x2,速度为t2秒每米;

当人和车子的位置重叠时,人可以上车,之后可以随时下车;(上下车时间忽略)

现在求人到达目的地的最短时间是多少?

输入数据有三行,分别是:

s, x1 and x2 (2 ≤ s ≤ 1000, 0 ≤ x1, x2 ≤ s, x1 ≠ x2)

t1 and t2 (1 ≤ t1, t2 ≤ 1000)

p and d (1 ≤ p ≤ s - 1, d is either 1 or -1) p表示当前车子所在的位置,d表示方向 只能为1或者-1

Examples

input

4 2 4

3 4

1 1

output

8

input

5 4 0

1 2

3 1

output

7

题目解析:

题目有一个很重要的限制 0 ≤ x1, x2 ≤ s, 表示车子的行程最终是会覆盖到x1和x2。

那么,就不会出现人上车后下车再走的情况。

用贪心的策略可以知道,要么一直走到终点站(我们假设时间为time1);

要么走一段距离,然后上车,直到终点(我们假设时间为time2)。

人直接走到终点的时间为 time1 = t2 * |x2 - x1|;

为了简化计算,第二种情况采用这样的计算方式:

假设人站在x1不动,等着车子来接。

计算车子第一次经过终点的时间,同时考虑这个路程有没有经过点x1;

如果没有再计算车子第二次经过终点的时间,直到有经过点x1,得到时间time2;

ans = min(time1, time2);

巧妙的一个题目,非常喜欢。

4. Green and Black Tea

题目链接

题目大意:

小明喜欢喝茶,每天都要用一个茶包,每个茶包只能用一次;

他有a个绿茶包,b个黑茶包;

小明不喜欢连续喝同一种茶超过k天。

问是否存在适合的茶包分配方案,使得小明能喝到n天。(a+b=n)

如果存在,则输出茶包的使用顺序,G表示绿茶包,B表示黑茶包;

如果不存在,则输出NO;

输入数据

n, k, a and b (1 ≤ k ≤ n ≤ 1e5, 0 ≤ a, b ≤ n)

Examples

input

5 1 3 2

output

GBGBG

input

7 2 2 5

output

BBGBGBB

input

4 3 4 0

output

NO

题目解析:

题目的要求是分配茶包。

容易想到这样的贪心:每天优先使用多的茶包,当使用了k次之后,就用一次少的茶包,直到茶叶包一样多,之后可以采取交替的方式。

这样的实现方案会比较复杂,首先需要每天判断一次a、b的大小,然后还要记录当前茶包是否连续使用了k次。

我们可以用另外一种贪心:当a>b的时候,我们直接连续使用min(k, a - b)个b茶包。

容易知道,当a-b

如果使用的是茶包k时,证明a比b多超过k,这时先使用k个a不会影响最后的结果。

这个题的思路很多,选择一个较好实现的。

5.Numbers Exchange

题目链接

题目大意:

小明有n张卡片,每张卡片上有一个数字a[i];

小红有m张卡片,卡片上的数字分别从1~m;

现在小明可以和小红交换卡片,每次用他的一张卡片去交换小红的一张卡片;

要求:小明所有奇数的卡片和偶数的卡片一样多,并且每一张的数字各不相同。

输入数据:

n and m (2 ≤ n ≤ 2·1e5, 1 ≤ m ≤ 1e9)

a1, a2, ..., an (1 ≤ ai ≤ 1e9)

如果可以达到,先输出最小的交换次数;

然后输出n个数字b[i], b[i]=a[i]表示这张卡片没变,b[i]!=a[i],表示小明用第i张卡片去交换了小红的第b[i]张卡片;

如果不能达到,输出-1;

Examples

input

6 2

5 6 7 9 4 5

output

1

5 6 7 9 4 2

input

8 6

7 7 7 7 8 8 8 8

output

6

7 2 4 6 8 1 3 5

input

4 1

4 2 1 10

output

-1

题目解析:

从结果来反推。

假设小明最后能达成条件,那么需要n/2张奇数和偶数的卡片,即是需要各不相同的奇数和偶数各n/2;

即是小明和小红的卡片去重后,奇数和偶数的数量都要大于等于n/2;

容易知道,小明需要把去重时的卡片、大于n/2张的奇偶卡片去和小红交换;

那么对于一张奇数卡片a[i],假设当前奇数卡片剩下sum1张,如果还有多余的卡片a[i]或者sum1>n/2 || (sum1==n/2 && 剩余卡片>1)那么这张卡需要交换;

当所有卡片处理完之后,判断奇数、偶数卡片是否等于n/2即可。

思考:

代码比较长,所以在提交之后查看别人的解法。

其实不需要去重之后,再来遍历卡片,判断是否应该交换;

在一开始输入的时候,如果一个卡片是重复的(之前已经出现过),或者当前类型(奇偶数)剩余的卡片已经�大于等于n/2,这张卡片就是多余的,可以加入交换queue里面;

输入完成时,会有一个交换queue,这个queue就是需要交换的卡片;

再按照奇偶数卡片的数量,去和小红交换,最后得到奇偶卡片的数量,再判断。

总结

五道题都是想法题。

第3、4、5题要求思路清晰,稍有遗漏,就会遇到错误,是很不错的题目。

手机附:

实际开发中,最常见的就是“贪心”,“时间与空间互换”,“减少重复计算”,“lazy加载”等思想,这些想法都是算法的一个延伸。

最近做的一个功能,涉及到环形缓冲区的优化和二进制流处理,每次处理仅有12ms的时间。我觉得曾经算法练习能很好帮我解决问题,过去类似的思考都转化为现在的灵光。

搜索CocoaChina微信公众号:CocoaChina
微信扫一扫
订阅每日移动开发及APP推广热点资讯
公众号:
CocoaChina
我要投稿   收藏文章
上一篇:我在南山写代码,是改变世界还是养家糊口?
下一篇:盘点那些让程序员目瞪口呆的Bug都有什么?
我来说两句
发表评论
您还没有登录!请登录注册
所有评论(0

综合评论

相关帖子

sina weixin mail 回到顶部