3.29 携程算法笔试

10个选择题，4个编程题

选择题大部分问的都是机器学习算法，少部分概率论。难度尚可

编程题：

第一题

纯送分，0,6,9有一个0；8有两个0；给你一串数字，问一共有几个0

s = input().strip()

n = 0

for i in range(len(s)):

    if s[i] == '0' or s[i] == '6' or s[i] == '9':

        n += 1

    elif s[i] == '8':

        n += 2

    else:

        continue

print(n)

第二题

好元素，给一个n一个k。n是一共有从1,2...n的一个数组，然后让你用这n个元素构建有k个好元素的数组。好元素的定义是对于第i个元素，ai是前i个元素的最大值。好元素不能相邻

这个题想到的是把数组两两组合，一个大一个小，同时保证大的那个是好元素即可。有几个好元素就从倒数第几个数开始数就可以。比如5,2。就是4,1,5,2,3

n, k = map(int, input().split())

list_ = [0] * n

max_xulie = n - k + 1

min_xulie = 1

i = 0

while k >0:

    list_[i] = str(max_xulie)

    max_xulie += 1

    k -= 1

    i += 2

for j in range(n):

    if list_[j] == 0:

        list_[j] = str(min_xulie)

        min_xulie += 1

    else:

        continue

print(' '.join(list_))

第三题

输入一个N

问|x!*y-y-n|怎么最小

x,y可以随意取

这里的n可以有10^9，所以一看就是要控制时间复杂度。但是我没想出来太好的解决办法，只能把小于2n的x!全记录下来，这样后面再用就可以直接取。另外对于y递增，x递增，需要考虑什么时候循环递增停止。我选的是-n以后>0就停止，但是记录一下第一次>0的值。

import math

n = int(input())

x = 1

jiecheng_list = []

while math.factorial(x) <= (2*n):

    jiecheng_list.append(math.factorial(x))

    x += 1

# print(jiecheng_list)

x = 1

y = 1

flags = False   #   True表示遇到0，退出

res = [1, 1, abs((jiecheng_list[x - 1] - 1) * y -n)]

def try_gengxin(x, y, now_res):

    if abs(now_res) < res[2]:

        res[0] = x

        res[1] = y

        res[2] = abs(now_res)

for y in range(1, n):

    if y == 2:

        continue

    y_now_res = 1 * y - n

    if y_now_res == 0:

        try_gengxin(1, y, y_now_res)

        flags = True

        break

    elif y_now_res > 0:

        try_gengxin(1, y, y_now_res)

        break

    else:

        for x in range(1, len(jiecheng_list)):

            if x == 2:

                continue

            now_res = (jiecheng_list[x - 1] - 1) * y - n

            if now_res == 0:

                try_gengxin(x, y, now_res)

                flags = True

                break

            elif now_res < 0:

                try_gengxin(x, y, now_res)

            elif now_res > 0:

                try_gengxin(x, y, now_res)

                break

    if flags is True:

        break

print(res[0], res[1])

第四题

这个说给你一个树（其实就是一个图），每条边有一个权值。给树上色，如果这条边上色了，那临近的其他所有边都不能上色。问最多可以给多少的权值上色。没时间了，只是想了个大概的思路就不记录了