2019-03-16 头条笔试

发表于 |

总共4道算法题，全部AC，题目属于一般难度，没有涉及acm相关知识。

第一次为自己而做的笔试，给了头条，结果还算满意吧。

这里先申明一下，做的过程中我就直接在网页上写的代码，所以本地没有存储最后通过的代码，以下我写的代码都是我凭记忆写的（应该也不会出错，毕竟刚做，而且也不难），这也算一个教训，下次一定会记录下来

1. 硬币问题

Z国的货币系统包含面值1、4、16、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N(0<N<=1024)的商品，请问最少他会收到多少硬币？

输入描述：
一行，包含一个整数N
输出描述：
一行，包含一个数，表示最少收到的硬币数
示例1：
输入：200
输出：17
解释：824 = 64x12 + 16x3 + 4x2, 12 + 3 + 2 = 17

思路分析：
第一眼瞟过去以为是一个标准的零钱凑整问题，但是立马发现硬币的面值为定值且呈倍数关系
也就是能用大面值的情况，绝对不可能去使用小面值，故贪心可解。

1
2
3
4
5
6
7
n = int(input())
target = 1024 - n
res = 0
for val in [64,16,4,1]:
    res += target // val
    target %= val
print(res)

2. 校对程序

实现一个单词校对程序，实现以下几个功能：

  1. 如果有三个同样的字母连在一起，则需要去掉一个，如’helllo’ -> ‘hello’
  2. 如果有两对同样的字母(AABB型)连在一起，去掉第二对的一个字母，如’helloo’ -> ‘hello’
  3. 上面的规则都必须优先从左到右匹配，如’AABBCC’，要先处理第一个’AABB’，结果为’AABCC’

输入描述：
第一行包含一个数字n，表示本次用例包括多少个待校验的字符串
之后n行，每行为一个待校验的字符串。
输出描述：
n行，每行包括一个被修复后的字符串
示例1：
输入：
2
helloo
wooooooooow
输出：
hello
woow

思路分析：
题意其实还是比较明确的，对于当前遍历的字符v，只要分别判断他与前一个字符p，前前一个字符pp,前前前一个字符ppp之间的关系即可，若满足两种规则中的任意一种，则删去v字符。
这里我使用队列实现，我觉着这样写起来会更清晰一点（也可以使用指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import collections
n = int(input())

def solve(s):
    if len(s) < 3: return s
    res = []
    s = list(s)
    q = collections.deque(s[2:])
    # 初始不要ppp
    pp, p = s[0], s[1]
    ppp = None
    while q:
        v = q.popleft()
        # 第一种错误情况
        if v == p == pp: continue
        if ppp:
            # 第二种错误情况
            if v == p and pp == ppp: continue
            res.append(ppp)
        ppp, pp, p = pp, p, v
    res.extend([ppp, pp, p])
    return ''.join(res)

for _ in range(n):
    s = input()
    print(solve(s))

3. 奖品数量

有n个人参加编程比赛，比赛结束后每个人都有一个分数
现在所有人排成一个圈(第1个人和第n个人相邻)领取奖品，要求满足：

  1. 如果一个人比他相邻的人的分数高，那么他获得的奖品应该要多余相邻的人
  2. 每个人至少需要得到一个奖品

输入描述：
第一行是一个整数t，表示测试样例的个数
每个测试样例的第一行是一个正整数n，表示参加比赛的人数(0 < n < 100000)
第二行是n个整数a[i]，表示每个人的分数(0 < a[i] < 100000)
输出描述：
对每个测试样例，输出应该准备的最少奖品数
示例1
输入：
2
2
1 2
4
1 2 3 3
输出：
3
8

思路分析：
这道题和leetcode上的第135题candy几乎一模一样，只不过candy中是一列，而这里是一个环。

因为去年做candy的时候代码写的很长很乱，虽然通过但思路很不清晰，看了discuss发现原来两个循环就解决了，当时惊呆了所以印象特别深。

这道题也可以用candy的思路来做，不过需要多处理一下首尾的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
t = int(input())

def solve(a):
    count = [1] * n
    for i in range(n):
        if a[i] > a[(i-1)%n]:
            count[i] = count[(i-1)%n] + 1

    for i in range(n-1, -1, -1):
        if a[i] > a[(i+1) % n]:
            count[i] = max(count[i], count[(i+1)%n] + 1)

    # 做的时候，我本以为单靠上面两个循环应该已经够了
    # 自己也写了超多例子，也全部算出正确结果了，但通过率是0%
    # 我猜是首尾处的判断没有处理的特别好，某种特殊case没考虑到
    # 所以我将这两个循环再写了一遍，果然交上去就对了
    for i in range(n):
        if a[i] > a[(i-1)%n]:
            count[i] = max(count[i], count[(i-1)%n] + 1)

    for i in range(n-1, -1, -1):
        if a[i] > a[(i+1) % n]:
            count[i] = max(count[i], count[(i+1)%n] + 1)

    return sum(count)

for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(a))

4. 绳子裁剪

有N根绳子，第i根绳子的长度为l[i]，现在需要M根等长的绳子。
你可以对这N根绳子进行任意裁剪（不能拼接），请你计算出这M根绳子最长的长度

输入描述：
第一行包括两个整数N,M，含义如题所述(1 <= N,M <= 100000)
第二行包含N个整数，分别对应N根绳子的长度(0 < l[i] < 10^9)
输出描述：
一个数字，表示裁剪后最长的长度，保留两位小数
示例1
输入：
3 4
3 5 4
输出：
2.50
解释： 第一根和第三根绳子分别裁剪出一根2.50长度的绳子，第二根绳子刚好可以裁剪出两根2.50的长度绳子，刚好4根。

思路分析：
前些天才讲了二分法系列的详解，这种程度的题目根本不足以作为最后一道题啊

重点：找到一个数，这个数需要满足一定的条件，看到这种模式的题目马上要想到二分

三步法：

  1. 定区间。这里使用绳子的长度区间即可(lo,hi = 0, 10^9)
  2. 确定判断条件。对于我们找到的mid，我们需要判断如果剪成mid长度的绳子，计算最多能剪出来的绳子数量cnt，如果cnt >= m，说明此时当前的长度还小了，可以尝试去找更大的长度(lo=mid)，反之则找更小的长度(hi=mid)
  3. 循环外返回结果。因为结果可能是小数，那么只要lo,hi出循环的时候足够接近即可(hi - lo < 10^-6)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n,m = map(int, input().split())
l = list(map(int, input().split()))

def check(mid):     # 计算mid长度的绳子最多能获得多少根
    cnt = 0
    for ll in l:
        cnt += ll // mid    # 这里需要整除
    return cnt >= m

lo,hi = 1, 10**9
while hi - lo > 10**-6:# 差值大于10**-6时继续循环，保证出循环两者足够接近
    mid = lo + (hi-lo)/2    # 注意这里不能用整除，因为答案可能是小数
    if check(mid): lo = mid
    else: hi = mid
print('%.2f' % lo)      # 保留两位小数

这个代码多漂亮啊，嘻嘻！