字节跳动春招算法四道编程题

Posted on | Post modified

P1

Problem description:

总共有1024元，买一件价格为N元的商品，N为1到1024间的整数。
找零都以硬币形式给出，可能值为1元，4元，16元，64元。问最少找零硬币数。

Soution:

典型的递归问题。

python code:

1
2
3
4
5
6
7
8
9
10
11
12
def how_many_coins(x):
    if x==0:
        return 0
    if x>=64:
        return how_many_coins(x-64)+1
    if x>=16:
        return how_many_coins(x-16)+1
    if x>=4:
        return how_many_coins(x-4)+1
    if x>=1:
        return how_many_coins(x-1)+1
how_many_coins(65)

output:

1
2

P2

Problem description:

给定一字符串，对其做如下修改: 若出现AABB, 修改为AAB；若出现连续三个或以上的A，比如AAA，修改为AA；算法从前向后匹配，譬如碰到AABBCC，就改为AABCC。

Solution:

对一个字符串从前往后搜索，并维护一个至多有两个元素的字典。算法复杂度为O(n)。

python code:

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
31
32
33
34
35
36
37
38
39
40
def correct(x):
    res={}
    y=[]
    for i in x:
        if len(res)==0:
            y.append(i)
            res[i]=1
        elif len(res)==1:
            if i in res:
                if res[i]<2:
                    y.append(i)
                    res[i]=2
                else:
                    continue
            else:
                if list(res.values())[0]==1:
                    res={}
                    res[i]=1
                    y.append(i)
                else:
                    res[i]=1
                    y.append(i)
        else:
            key=list(res.keys())
            if i in res:
                if i==key[1]:
                    continue
                else:
                    y.append(i)
                    res={}
                    res[i]=1
            else:
                y.append(i)
                res={}
                res[i]=1          
    return "".join(y)

a=["aabb","aaa","aabbcc"]
for i in range(len(a)):
    print(correct(a[i]))

output:

1
2
3
aab
aa
aabcc

P3

Problem description:

n个人围坐成一个圈，每个人都被分配了一个数字，现在给所有人分发礼物，分礼物时要满足如下条件：如果某人分配到的数字大于他左手边的人，那么他得到的礼物必须也比他左手边的人得到的礼物多；同理右手边也一样。已知每人至少能拿到一件礼物，问最少需要分配的礼物总数。

Solution:

首先给所有人一个礼物，然后从分配到最小的数字的人开始，顺时针扫一遍，按题目要求更新每个人的礼物数。然后逆时针扫一遍，在顺时针扫完一遍的基础上更新每个人的礼物数，算法复杂度为O(n)。

python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minPrize(num, scores):
    if num == 0:
        return 0
    res = [1] * num
    index = scores.index(min(scores))
    for i in range(0, num - 1):
        if scores[(index + i + 1)%num] > scores[(index + i)%num]:
            res[(index + i + 1) %num] = res[(index + i) %num] + 1

    for i in range(0, num - 1):
        if scores[(index - i - 1)%num] > scores[(index - i) % num]:
            res[(index - i - 1)%num] = max(res[(index - i - 1)%num], res[(index - i) % num] + 1)

    return sum(res)


num = 4
scores = [1,3,3,4]
res = minPrize(num, scores)
print(res)

output:

1
6

P4

Problem description:

有M根绳子，长度由一个M个元素的列表给出，要把这M根绳子切成N段等长为L的绳子，问L的最大值。

Solution:

这道题比较难。感谢狂魔提供的解题思路。需要用到一个前提假设：即最长的那根绳子切的段数不得少于比它短的绳子。为此我们维护一个M元数组，数组的每一项表示该绳子被使用的段数。举个例子，M=[2，4]，N=3。此时凭直觉给出答案L=2。具体实现方法是把长度为4的绳子且为两段，长度为2的绳子不动。在这个例子中，我们首先降序sort这个M元的列表，得到M’=[4，2]，然后建立一个长度为M的新列表K，新列表的第i个元素表示M’[i]这条绳子被利用了多少段，这里，K=[2，1]。有了这个思路以后，我们只需要穷举所有可能的绳子切割方法，并计算出每一种方法L的值，再从所有方法中挑出最大的L即可。

python code:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# permute function can generate all possible combinations of cutting max_len ropes into N ropes.
def permute(N,max_len):  
    def helper(N,max_len,thres):
        res=[]
        if max_len==0:
            return [[]]
        i=min(thres,N)
        while i>=N/max_len:
            temp=helper(N-i,max_len-1,i)
            for j in temp:
                res.append([i]+j)
            i-=1
        return res
    return helper(N,max_len,N)
permute(5,4)

# output
[[5, 0, 0, 0],
 [4, 1, 0, 0],
 [3, 2, 0, 0],
 [3, 1, 1, 0],
 [2, 2, 1, 0],
 [2, 1, 1, 1]]

# calculate L for each combinations
def calculate_L(method:list,mPrime:list):
  res=[]
  for i in range(len(method)):
    if method[i]==0:
      res.append(mPrime[i])
    else:
      res.append(mPrime[i]/method[i])
  return min(res)
calculate_L([2,1],[5,4])

# output
2.5

# main
def main(M,N):
  mPrime=sorted(M,reverse=True)
  res=[]
  methodList=permute(N,len(M))
  for i in methodList:
    res.append(calculate_L(i,mPrime))
  return max(res)

  print(main([4,2],3))
  print(main([4,3],2))
  print(main([1,1,2,2],4))

# output
2.0
3.0
1.0