前言
算法题是锻炼思维的好工具，在解决问题的层面考察思考能力。
正文
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时，剩下的茶包数量相等，交替使用即可；
如果使用的是茶包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的时间。我觉得曾经算法练习能很好帮我解决问题，过去类似的思考都转化为现在的灵光。
网友评论