关于笔试做题的相关问题总结回顾

记录一些笔试做题可能遇到的问题，每次笔试之前，一定要抽空先看看。

整理一些牛客网做题可能遇到的问题

没有对输入比照样例进行严格检查，导致一直无法AC。

时间

20200415华为暑期实习笔试

题目

统计votes = ["Tom", "Lily", "Tom", "Lucy", "Tomy", "Tomy", "Jack", "To", "To", "To"]的投票结果，出现并列第一时按照，第一原则：字母越小越在前面。第二原则：字母一样的，短小的越在前面。两大原则选择唯一一个名字作为优胜者。

示例

1
2
3
4
5
6
votes = ["Tom", "Lily", "Tom", "Lucy", "Lucy", "Jack"]
answer = 'Lucy'  # Lucy(L) < Tom(T)
votes = ["Tom", "Lily", "Tom", "Lucy", "Lucy", "Tom", "Jack"]
answer = 'Tom'  # Tom get 3 votes
votes = ["Tom", "Lily", "Tom", "Lucy", "Tomy", "Tomy", "Jack", "To", "To", "To"]
answer = 'To'  # len(To) < len(Tom) < len(Tomy)

思路很简单

1、构建hash map，统计名字和得票率。2、基于value对hash map进行排序。3、取出排在前面的name，如果有排名一样的，就一起放到 res（一个list）中。4、判断 res 长度，大于1说明有重复，用 res = sorted(res) 去对名字排序，能够满足上述两个原则，最后 returnn res[-1]

我犯的错

1、对 Python dict 和 lambd 函数还是不是熟悉，写用 _t = sorted(_d.items(), key=lambda item: item[1], reverse=True) 时浪费了不少时间。 2、明明可以用 res = sorted(res) 对输出的名字进行排序也满足题目要求，但是还是自己写了一大段代码来实现这个功能。在面试时，可以这么干，但是在笔试的时候，优先考虑把题做完为第一要务，能复用的就复用。 3、最终只AC了37.8%，主要是由于，没对输入进行检查。要遍历整个输入，输入中的每个字符都必须是逗号或小写或大写；其次切分输入后，遍历所有的名字，所有名字的第一位必须是大写，其他位必须是小写；这两个判断做了后，就可以大大提高AC的概率了。

教训

需要进一步夯实语言基础 优先使用简单的方案完成代码功能 最惨痛的教训是：写主要逻辑代码之前，一定要认真严格的检查输入，保证和样例的输入一模一样。否则不会AC。

没有认真读题，缺失了重要条件，导致无法AC。

时间

20200415华为暑期实习笔试

题目

输入一个字符串

1
_str = "read read[addr=0x17,mask=0xff,val=0x7],read_his[addr=0xff,mask=0xff,val=0x1],read[addr=0xf0,mask=0xff,val=0x80]"，

第一个词 read 是寄存器名称，提取出字符串中该寄存器 read 的所有地址addr、掩码mask和值val。

示例

1
2
3
4
5
read read[addr=0x17,mask=0xff,val=0x7],read_his[addr=0xff,mask=0xff,val=0x1],read[addr=0xf0,mask=0xff,val=0x80]

Answer
0x17 0xff 0x7
0xf0 0xff 0x80

思路也不难

一直用Python的 splite 方法去按照 " "、"["、"addr="、",mask="、",val="分割就行。

我犯的错

1、没有认真读题，题目中要求了，val必须要以 0x 或者 0X 开头，不然就返回 FAIL。还有一个要求是全部没有匹配到输出 FAIL，或者某一行匹配不全输出 FAIL。题目里说了没有匹配成功，就要返回 FAIL，但是我写代码时完全没有注意到这一点。太大意了。 2、读题是可能出现了理解错误，本来不应该在最后一行加换行的，但是我理解成了要加换行。差点通过不了，输出一直判定有问题，后面好好研究了一下给的输出样例，去掉了最后一行的换行，才通过一部分。

教训 读题一定要认真，不然是无法AC的，甚至 0% 的通过率。 当输出不满足条件，通过率 0% 时，别紧张，好好读题，把输出改成给定的输出样例的样子再试试。

太依赖模板思想，没有灵活解决问题，导致没有AC。

时间

20200415华为暑期实习笔试

题目

输入

1
2
a = {1: [2, 3], 2: [3, 4, 5], 3: [4]}  # 函数调用关系
b = {1: 20, 2: 30, 3: 40, 4: 60:, 5: 80}  # 每个函数占用的内存

找到哪一个调用关系占用的栈内存最大？

1
150  # 1->2->3->4->5的调用关系占用的栈最大 为 20+30+40+60=150

示例

1
2
3
4
5
6
7
8
9
10
# Input
5 2 3 1 0 0  # 5个函数 分别调用了2、3、1、0、0个函数
1 20 2 3     # 第1个函数占用20内存 调用了2、3函数
2 30 3 4 5   # 第2个函数占用30内存 调用了3、4、5函数
3 50 4       # 第3个函数占用50内存 调用了4 函数
4 60         # 第4个函数占用60内存
5 80         # 第5个函数占用80内存

# Output
150

看似复杂仔细想想其实也不难

1、就是调用深度优先遍历进行回溯，一条道走到黑，然后返回上一层，选另一条道走。 2、获取所有调用关系之后，遍历计算每一个调用关系的内存开销。

我犯的错

因为很容易想到是用深度优先遍历来做，我就想起了这个模板。

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表): / if 选择条件: # 选择列表是由一系列参数组成的
    if 满足结束条件:
        result.add(路径)  # 路径就是要添加的结果
        return           # 大多数情况下，有return会运行快一点。

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

想尽一切办法，往里面套，结果浪费了宝贵时间。实际上，这道题的终止条件是写在for循环中的。

1
2
3
4
5
6
7
def _dfs(select, nums):
    for i in range(len(nums)):
        # 终止条件不在这里
        if nums[i] in a:  # 还可以递归
            _dfs(select+[nums[i]], a[nums[i]])
        else:  # 不能递归了  终止条件在这里
            res.append(select[:] + [nums[i]])

教训

理解算法思想，避免盲目崇拜算法模板。

时间安排不当

时间

20200415华为暑期实习笔试

教训

这次笔试，一共三道题，做完前两道，就还剩20%。我不应该去做第三道题目，而是应该回去读第一道题目和第二道题目，找我漏掉了那些关键信息，争取前两道题目AC，或者通过率更高。第三道题目应该主动放弃。后面第三题也没通过，后面20分钟也没改进前两道题，白白浪费。可惜。

总结

以后做题，不要着急，先花上五分钟，把每道题的大概意思读一下，分析一下具体做大致有哪些步骤，然后根据实际情况，确定做题顺序。一道一道题的好好扣细节，争取AC，不要在不同题目之间跳来跳去。

测试用例安排不当

时间

20200429 SAP Vacation Training Project 笔试

教训

代码中有这么一段

1
2
if len(hash_map) == 2:  # 最理想状态 2 2 3 3
	return hash_map.items()[0] * hash_map.items()[1]

这里实际上是写错了，因为 dict.items() 返回的是一个 tuple ，利用下标去获取数值再相乘就会报错。正确的写法如下：

1
2
3
if len(hash_map) == 2:  # 最理想状态 2 2 3 3
	tmp = list(hash_map.keys())
	return tmp[0] * tmp[1]

但是，我没有测试过这段代码，所以就凉凉了。如果我使用 [2, 2, 3, 3] 这个测试用例，输入进去测试一下，就会发现这个错误。

总结

以后做题，提前准备好写好输入读取代码、 Solution 类和 unittest 类的 *.py 文件。利用 unittest 好好把代码中所有流程都走一遍。模板如下：

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
import unittest

class Solution():

    def func(self, items):
        """ *** 
        :param items: List[int]
        :return: int
        """
        res = 100
        # 其他相关代码

        return res

class Test_Solution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()
    
    def test_getMaxArea(self):
        # 测试样例根据实际情况而定
        inputs = [[2, 2, 5, 5], [2, 2, 4, 5], [2, 3, 4, 5]]
        answers = [100, 100, 100]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.func(inputs[i]))
        self.assertEqual(res, answers)
    
    def tearDown(self):
        del self.test_class

if __name__ == "__main__":

    # 代码提交模式
    # import sys
    # res = []
    # s = sys.stdin.readline().strip("\n") 
    # while s != "":
    #     res.append(s)
    #     s = sys.stdin.readline().strip("\n")
    # 关键参数获取根据实际情况而定
    # items = [int(x) for x in res[1].split(' ')]
    # solution = Solution()
    # print(solution.getMaxArea(items))

    # 代码编写模式
    unittest.main()

检查是否存在语法错误或者数组越界访问等情况python

  • 解释一

在笔试时，我们在自己的 ide 上运行测试案例，没有问题，但一复制粘贴到牛客上就会报错： 请检查是否存在语法错误或者数组越界访问等情况。 请问怎么解决？ 搜了大量资料，有着么几个原因： 1、数组确实越界了，注意数组的索引。 2、如果递归爆栈，也会报这个错误。内存过大。本地不报错，因为我们本地内存很大，牛客上每个题都会有内存限制。这个问题，通过更换做题语言为C++可以解决。 3、有可能是特殊案例，没有考虑周全，例如为空等

以上仅供参考，欢迎指正，补充。 ———————————————— 版权声明：本文为CSDN博主「飞奔的帅帅」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/ustbbsy/article/details/80274382

  • 解释二

我在写python的时候发现了一件事情，我看了很多评论才找到什么原因的。 当你写好，提交调试后，90%用例通过了 请检查是否存在语法错误或者数组越界非法访问等情况 case通过率为90.00% 我实在是找不出自己代码的错误了。 然后看到了个评论： 牛客网的输入里可能混扎了空行，所以导致了这个情况 例如: 

1
2
3
4
5
6
3 1
1 2
3 3
# 注意这里就是输入的空行
5 4
1 2 3 4 5 6
明明题目说了 每个输入包含一个测试用例。 每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。 接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。 接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。 保证不存在两项工作的报酬相同。

由于那个空行 当你用split(’ ')之后得到的list本来有len为2，最后len变为1,导致你的数组越界非法访问。 有一定概率出现这种情况，反正这个问题我是服了。

———————————————— 版权声明：本文为CSDN博主「ken1oo」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/ken1oo/article/details/100642407

笔试

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！