2023-09-16 深信服笔试

Q1

题目:

验证一个字符串是否是合法的DNS域名.DNS域名的格式要求如下:

1. 域名由一系列以点为分隔的标签组成.每个标签最长可为63个字符.域名的总长度不能超过255字节,包括点.域名至少有2个标签组成.
2. 域名标签只能包含字符a-z,A-Z,0-9和 - (连字符).不能在标签的开头或结尾指定连字符.域名支持大小写但是不区分大小写.

输入

一行字符串

输出

如果字符串是合法域名,输出true,如果不是,输出false

示例:

输入:163.com
输出:true

输入:test-1.com
输出:true

输入:baidu.com
输出:true

输入:baidu-.com
输出:false

代码:AC 96.67%

验证一个字符串是否是合法的DNS域名view raw

import sys
import re

def check_dns(s):
    if len(s) > 255: return False

    s_parts = s.split('.')
    if len(s_parts) < 2:
        return False
    
    for i in s_parts:
        if len(i) > 63: return False
        if i.startswith('-') or i.endswith('-'):
            return False
        pattern = r'^[a-zA-Z0-9-]+$'
        if not re.match(pattern, i):
            return False
    
    return True
if __name__ == "__main__":
    for line in sys.stdin:
        result = check_dns(line)
        if result:
            print("True")
        else:
            print("False")

自写的pytest测试代码:

Q1测试view raw

import pytest
from Q1 import check_dns

def test_valid_dns():
    assert check_dns("example.com") == True
    assert check_dns("subdomain.example.com") == True
    assert check_dns("sub-domain.example-123.com") == True
    assert check_dns("a.com") == True
    assert check_dns("1.com") == True

def test_invalid_length():
    assert check_dns("a" * 256) == False
    assert check_dns("subdomain." + "a" * 64 + ".com") == False

def test_invalid_characters():
    assert check_dns("invalid_domain_!") == False
    assert check_dns("example#.com") == False
    assert check_dns("example_.com") == False
    assert check_dns("-.com") == False

def test_single_character():
    assert check_dns("a.com") == True
    assert check_dns("1.com") == True
    assert check_dns("-.com") == False

def test_empty_string():
    assert check_dns("") == False

def test_missing_dot():
    assert check_dns("example") == False
    assert check_dns("exampledomaincom") == False

def test_start_with_dot():
    assert check_dns(".example.com") == False

def test_end_with_dot():
    assert check_dns("example.com.") == False

def test_consecutive_dots():
    assert check_dns("example..com") == False
    assert check_dns("sub..domain.com") == False

def test_long_labels():
    assert check_dns("a" * 64 + ".com") == False
    assert check_dns("subdomain." + "a" * 63 + ".com") == True

def test_mixed_case():
    assert check_dns("Example.com") == False
    assert check_dns("exAmple.cOm") == False

Q2

题目:

平台运行过程中出现异常时一般会将信息记录在后台日志文件中,定位问题时通常使用关键字进行过滤.正则表达式具备很强大的文本匹配功能,能够快速高效地处理文本.常见元字符为:
^:匹配字符串开头
$:匹配字符串结尾
.:匹配任意字符
*:匹配前面的字符零次或多次
+:匹配前面的字符一次或多次
?:匹配前面的字符零次或一次

给定一个输入字符串s和一个输入字符模式p,s和p的长度均在100以内.
要求实现一个支持’.’和’*’的正则表达式匹配.字符模式必须能够完全匹配输入字符串.
如果匹配成功返回1,匹配失败返回0.
请设计一个时间复杂度为O(mn)或更优的算法来解决这个问题.如果使用内置正则库得0分.

输入

第一行输入为字符串s
第二行输入为字符模式p

输出

如果匹配成功返还1,匹配失败返还0

示例:

输入:
aaa
a*
输出:
1

输入:
abaa
ab*a
输出:
0

输入:
abaa
ab.a
输出:
1

代码:AC 100%【没看到不能用内置库,服了】

正则匹配view raw

import sys
import re

# 2023-09-18笔试后添加，不使用re模块来实现.和*的正则匹配
def is_match(s, p):
    m, n = len(s), len(p)
    
    # 创建一个二维数组来保存匹配结果，默认为 False
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # 空字符串与空模式匹配
    dp[0][0] = True
    
    # 处理模式中的 * 号
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]
    
    # 填充动态规划表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))
    
    return dp[m][n]



if __name__ == "__main__":
    inputs = []
    for line in sys.stdin:
        inputs.append(line)

    if re.match(inputs[1], inputs[0]):
        print('1')
    else:
        print('0')

自写的pytest测试代码:

Q2测试view raw

import pytest
from Q2 import is_match

def test_empty_string():
    assert is_match("", "") == True
    assert is_match("a", "") == False
    assert is_match("", "a") == False

def test_single_character_match():
    assert is_match("a", "a") == True
    assert is_match("a", "b") == False
    assert is_match("a", ".") == True
    assert is_match("a", "*") == False

def test_dot_star_combination():
    assert is_match("aa", "a*") == True
    assert is_match("ab", ".*") == True
    assert is_match("mississippi", "mis*is*p*.") == False

def test_dot_star_edge_cases():
    assert is_match("a", ".*") == True
    assert is_match("ab", ".*c") == False
    assert is_match("", ".*") == True
    assert is_match("a", "a*") == True
    assert is_match("aa", "a*a") == True
    assert is_match("a", "a*a") == True
    assert is_match("aa", "a*a*a*") == True

def test_long_strings():
    assert is_match("a" * 1000, "a*") == True
    assert is_match("a" * 1000, "b*") == False

def test_mixed_characters():
    assert is_match("aAa", "a*a") == False
    assert is_match("AaA", ".*") == True

def test_complex_patterns():
    assert is_match("aaaab", "a*a*a*b") == True
    assert is_match("abcd", ".*..d*") == True

def test_nested_star():
    assert is_match("abcde", "a.*c.*e") == True

def test_complex_cases():
    assert is_match("aaaaab", "a*a*a*a*a*c") == False
    assert is_match("aaaaac", "a*a*a*a*a*c") == True

Q3

题目:

给定一个数组,找出其中不含有重复数字的最长子数组的长度.

输入

使用空格分割一行数字,对应于数组中的元素

输出

数字,符合题目要求的最长子数组的长度

示例:

输入: 1 2 3 1 2
输出: 3

输入:1 1 1 2 2 2 1 1 3
输出:2

输入:1 2 3 1 2 3 4 1 4 2 7
输出:4

代码:AC 100%

最长不重复子数组view raw

import sys

def find_longest_sublist(lst):
    if not lst:
        return 0

    start = 0
    max_len = 0
    max_start = 0
    int_index_map = {}
    for end in range(len(lst)):
        if lst[end] in int_index_map and int_index_map[lst[end]] >= start:
            start = int_index_map[lst[end]] + 1
        int_index_map[lst[end]] = end
        if end - start + 1 > max_len:
            max_len = end - start + 1
            max_start = start
    return max_len

if __name__ == "__main__":
    inputs = input().split(' ')
    print(find_longest_sublist(inputs))

自写的pytest测试代码:

Q3测试view raw

import pytest
from Q3 import find_longest_sublist

def test_empty_list():
    assert find_longest_sublist([]) == 0

def test_single_element_list():
    assert find_longest_sublist([1]) == 1
    assert find_longest_sublist([0]) == 1
    assert find_longest_sublist([-1]) == 1

def test_unique_elements():
    assert find_longest_sublist([1, 2, 3, 4, 5]) == 5
    assert find_longest_sublist([5, 4, 3, 2, 1]) == 5

def test_duplicate_elements_at_start():
    assert find_longest_sublist([1, 1, 2, 3, 4]) == 4

def test_duplicate_elements_at_end():
    assert find_longest_sublist([1, 2, 3, 4, 4]) == 4

def test_duplicate_elements_in_middle():
    assert find_longest_sublist([1, 2, 3, 2, 4]) == 3

def test_long_list():
    assert find_longest_sublist(list(range(1000))) == 1000

def test_longest_sublist_at_end():
    assert find_longest_sublist([1, 2, 3, 4, 5, 1, 2, 3]) == 5

def test_longest_sublist_in_middle():
    assert find_longest_sublist([1, 2, 3, 1, 2, 3, 4, 5]) == 5

def test_negative_numbers():
    assert find_longest_sublist([-1, -2, -3, -4, -5]) == 5
    assert find_longest_sublist([-5, -4, -3, -2, -1]) == 5

def test_mixed_positive_and_negative_numbers():
    assert find_longest_sublist([-1, 2, -3, 4, -5]) == 5
    assert find_longest_sublist([-1, 2, -3, 4, -5, 6, -7, 8]) == 8

Q4

题目:

一个游戏玩家有k点体力,在一个m*n的表格中,其中(k,m,n都为正整数),玩家位于(0,0),需要到达终点(m,n).玩家只能上下左右移动,且每次只能移动1的长度并消耗1的体力,当体力耗尽的时候玩家无法移动.
给定k,m,n,问玩家能否移动到终点,如能,则给出能到达终点的最短路径的走法数目.
其中:
0 < m <= 30
0 < n <= 30

输入

依次输入三个数(每行一个),第一个数为k, 第二个数为m, 第三个数为n

输出

如能到达终点,则输出所有路径的数目,如不能,则输出0

示例:

输入:
4
1
1
输出:2

代码:AC 100%

到达终点的最短路径和走法数目view raw

import sys
import math

def get_numof_paths(k, m, n):
    def dfs(x, y, k):
        if x < 0 or x >= m + 1 or y < 0 or y >= n + 1 or k < 0:
            return 0
        if x == m and y == n:
            return 1
        if visited[x][y][k]:
            return 0
        visited[x][y][k] = True
        paths = dfs(x + 1, y, k - 1) + dfs(x, y + 1, k - 1)
        visited[x][y][k] = False
        
        return paths
    visited = [[[False] * (k + 1) for _ in range(n + 1)] for _ in range(m + 1)]
    
    return dfs(0, 0, k)

def get_numof_paths_2(m, n):
    return math.comb(m + n - 2, n - 1)

if __name__ == "__main__":
    inputs = []
    for line in sys.stdin:
        inputs.append(int(line))
    
    [k,m,n] = inputs
    
    if k >= m + n:
        # print(get_numof_paths(k, m, n))
        print(get_numof_paths_2(m + 1, n + 1))
    else:
        print(0)

自写的pytest测试代码:

Q4测试view raw

import pytest
from Q4 import get_numof_paths, get_numof_paths_2

def test_get_numof_paths():
    assert get_numof_paths(4, 1, 1) == 2  # k=4, m=1, n=1，有两种路径

def test_get_numof_paths_2():
    assert get_numof_paths_2(1, 1) == 2  # m=1, n=1，有两种路径