算法 ACM模式输入实践手册

背景

在面试做算法题时，有两种模式：

• leetcode模式，通常会留白一个函数，将输入以参数的方式传递，面试者只需实现这个函数的内容即可。
• ACM模式，只提供一个输入流，你需要自行编写解析输入的逻辑，然后再编写算法逻辑。

腾讯、字节等公司会倾向于使用前者的模式，而华为等公司会倾向于使用后者。对于大部分习惯做leetcode的同学，遇到ACM模式可能会拖延时间。本实践手册会记录几个经典例子，以python语言编写。

本文会介绍一种while+try-except的答题模板，只要背下一个模板，就可以复用在各种输入的题型。

例子1 循环模式的输入

算法描述

输入会遵循以下模式：

• 第一行包括一个正整数t(1 <= t <= 100)
• 接下来的t行，每行包括两个正整数a,b(1 <= a, b <= 1000)

输出要求，对于每一组a和b，输出a+b的结果。

示例1

输入例子：
2
1 5
10 20
1
3 4
输出例子：
6
30
7
1
2
3
4
5
6
7
8
9
10

解答

因为输入会循环固定的模式，可以用先写一个while大循环，然后用try-except来结束输入。
然后，在try语句块里，编写这轮循环的输入逻辑即可。

while True:
    try:
        n = int(input())
        for i in range(n):
            data = input().split()
            print(int(data[0])+int(data[1]))
    except:
        break

1
2
3
4
5
6
7
8
9

input()在输入流结束时，会抛出。读者可以将except语句块更改如下，自行验证抛出的错误。

except Exception as e:
      print(type(e))
      break
1
2
3

总结

这种while+try-except语法组合的好处是，可以轻易判断输入流的结束，然后在try代码块里编写单轮的输入逻辑即可。

例子2 字符串形式的输入

在上一例里，输入的都是整形数。有时候，输入的是一组字符串，比如本例。实际上这种情况更好解决，因为input().split()得到的就是按空格分隔的字符串list。

算法描述

输入：
多个测试用例，每个测试用例一行。

每行通过空格隔开，有n个字符，n＜100

输出：
对于每组测试用例，输出一行排序过的字符串，每个字符串通过空格隔开

示例1

输入例子：
a c bb
f dddd
nowcoder
输出例子：
a bb c
dddd f
nowcoder
1
2
3
4
5
6
7
8

解答

答案非常简短，直接在try代码块里写逻辑就行。这里的依然复用上一题的while+try-except答题模板。

import sys

while True:
    try:
        line = input().split()
        s = " ".join(sorted(line))
        print(s)
    except:
        break
1
2
3
4
5
6
7
8
9

总结

本文介绍了一种while+try-except的答题模板，它可以涵盖各种形式的输入，帮助减少拖延。该模式可以直接适配华为练习题：OJ在线编程常见输入输出练习的10道练习题。

这个答题模板灵感来自解答区其他人的答案。

写这篇文章的契机是因为笔者最近要准备面试华为OD，谁想到我一个硕士生面试外包岗呢？