华为OD机试面经20220213

2月15日更新：
感谢牛友Mr_小迪分享，力扣上找到了第二题升级版 LC179。
我自己的第二题代码也微调了下：增加考虑首位为0的情况。此外新增一版解法，可惜没有后台用例来测试了。

第一题：三数之和

给定一个数字列表，和一个整数n。
现在要求在列表中选三个数，相加之和<n，可能有多种不同的选法对应不同的和。
求和最大的方案（输出最大的和），如果没有三个数相加之和<n则输出 -1

样例1 - 输入：
23,26,36,27
78
输出：76

样例2 - 输入：
23 30 31
26
输出：-1

思路用了穷举。就是取数字列表任三个数字的全排列，求和，符合条件就计入tmp列表，最后输出tmp最小值。
逻辑不复杂，细节要谨慎。一开始卡了输入分隔符","，然后又卡了检验条件 add<=n 。调整之后AC。

import itertools
inp = sorted(list(map(int,input().split(','))))
n = int(input())
tmp = []
for i in itertools.permutations(range(len(inp)),3):
    add = inp[i[0]] + inp[i[1]] + inp[i[2]]
    if add<=n: 
        tmp.append(add)

if tmp!=[]: print(max(tmp))
else: print(-1)

第二题：拼接最小数字

给定一个数字列表，要求选取三个数字，拼在一起得到一个新的数字。例如：1,2,3,4,5 其中可以拿出 1,2,3 拼成 123（原题目的示例数列没记住，意思一样），也可以拿出 2,3,4 拼成 234。要求在各种方案中，输出最小数字方案。
如果列表不够三个数字，就用列表里所有的数字拼出最小数字方案。
列表中的数字数量 1<n<100 每个数字的大小 1<n<10000

样例一 - 输入：26,27,30,36
输出：262730

样例二 - 输入：5,12
输出：125

又是3元素全排列，今天跟3杠上了。
思路跟前一题相似，还是选三个，拼出数字，不断更新当前最小数值。
用例过90%, 想了半天没想出来还有咋样的特殊情况，就这么交了。

import itertools
inp = sorted(input().split(','))
if len(inp)<=1: print(inp[0])
elif len(inp)==2: print(min(int(inp[0]+inp[1]),int(inp[1]+inp[0])))
else:
    mins = 10**12+10**8+10000 #最小值初始化要覆盖到可能拼出来的最大数字，这里卡了至少20%用例
    for i in itertools.permutations(range(len(inp)),3):
        if inp[i[0]]=='0': continue #首位不应为'0'
        add = int(inp[i[0]]+inp[i[1]]+inp[i[2]])
        mins = min(mins,add)
    print(mins)

02.15 新增解法 - 三步排序法：
(内个，我本地 IDE 测试对于长度<3 的样例（如[5] [5,12]）均能正确运行，就不额外处理了。
如果小伙伴们遇到溢出列表溢出问题就加一步处理列表长度<3 情况吧~)

from functools import cmp_to_key

def comparator(a:int, b:int):
    return 0 if str(a)+str(b)>str(b)+str(a) else -1

inp = sorted(input().split(','))  # 先按字典序（也就是首位数字的大小）排序  
res = sorted(list(map(str,inp)), key=len)  # 再按位数（就是数字一共有几位）排序，此时位数少的、开头数字小的会排在最前面，大致满足"拼接结果最小"要求

if '0' in res: 
    print(min(int(res[1]+'0'+res[2]),int(res[2]+'0'+res[1]))) # 输出前处理一下0，如果有0放在第二位
else: 
    print(''.join(sorted(res[0:3],key=cmp_to_key(comparator)))) # 最后按比较函数排序，获得最小拼接结果

第三题：分积木

哥哥弟弟分一堆积木，每块积木重量不同。弟弟要求平分两组，每组数量可以不同但总重量必须相等。
然而弟弟只会二进制并且加法不进位。例如三块积木 3,5,6 分成两组 [3] 和 [5,6]
弟弟认为 5（二进制1001）加上6（二进制1010）是0011：
1001
1010
-------
0011
然后 3 的二进制也是 0011，所以弟弟认为两组积木等重，接受这种分配方案。哥哥实际能分到 5+6=11 块积木。
要求输出哥哥能拿的最大实际重量。如果给定的积木没法按弟弟视角分成重量相等的两组，就输出‘NO’。

样例 - 输入：5,6,3
输出：11

记得哪里刷到过这题，然而考完又找了下没找到。
我的思路是遍历所有积木分配组合（每边至少1块），分别对于两组内部元素求异或，比较结果判定方案是否可行。
如果可行就加和（也就是十进制总重量）放进方案列表存着，最后输出方案列表里最大值。
实现过程有个步骤没来得及调完。临场只过50%用例就不放代码献丑了。大家有AC版的可以相互交流。

总结

临场心态一定要提前调整好，不要把考试想得特别难特别可怕，遇到卡住的点不要畏难，尽量保持放松，觉得紧绷的时候深呼吸几下。
然后如果做完一部分觉得分数够了也不要急着交，机试总分会影响后续评级，所以一定要争取拿越多分越好。

许愿这次应聘顺利。祝大家都有心仪的Offer。