华为5.24笔试题

1.连续空间内存合并管理。

思路：对数组进行排序，寻找最大的整数区间的左端点和区间长度。

def func():
    memory_list = map(int, input().strip().split(','))
    memory_list = list(set(memory_list))


    memory_list.sort()

    max_start = memory_list[0]
    max_length = 1

    start = memory_list[0]
    length = 1
    for i in range(1, len(memory_list)):
        if memory_list[i] == start+length:
            length += 1
        else:
            if length>max_length:
                max_start = start
                max_length = length
            start = memory_list[i]
            length = 1

    if length>max_length:
        max_start = start
        max_length = length
	print('{},{}'.format(max_start, max_length))

2.海量日志抑制

思路：

（1）定义一个长度为10的缓存区间

（2）一个辅助函数（判断相似日志）

（3）判断2ms内的连续2个日志的相同性

（4）判断10ms内的连续10个日志的相似性

from collections import deque
def func():
    # 定义一个缓存，用于存储最近的日志信息，因为是要看前10条信息，故缓存长度为10
    log_cache = deque(maxlen=10)
    # 定义一个函数，用于判断两条日志是否相似

    def is_similarity(log1, log2):
        return ''.join(filter(lambda x: not x.isdigit(), log1)) == ''.join(filter(lambda x: not x.isdigit(), log2))

    n = int(input())
    for i in range(n):
        log = input().strip()
        timestamp, content = log.split(':', 1)
        timestamp = int(timestamp)
        if len(log_cache) >= 1 and timestamp-log_cache[-1][0]<10 and content == log_cache[-1][1]:
            # 10ms内打印相同的日志，只保留第一条日志
            continue
        elif len(log_cache) >= 9 and timestamp -log_cache[0][0]<100 and is_similarity(content, log_cache[0][1]):
            # 100ms内打印相似的日志，仅保留前9条
            continue
        else:
            print(log)
            log_cache.append((timestamp, content))

3.网络升级改造

思路：1.就是leetcode上的337.打家劫舍3

2.直接把数组转换为二叉树。

3.直接按照337.打家劫舍3的思路进行

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def build_tree():
    n = int(input())

    nums = map(int, input().split())

    nums = list(nums)

    if not nums:
        return None
    root = TreeNode(nums[0])
    queue = [root]

    i = 1
    while i < len(nums):
        node = queue.pop(0)

        if nums[i] is not None:
            node.left = TreeNode(nums[i])
            queue.append(node.left)
        i += 1
        if i >= len(nums):
            break

        if nums[i] is not None:
            node.right = TreeNode(nums[i])
            queue.append(node.right)
        i += 1
    return root


def rob(root):
    dp = trasversal(root)
    print(max(dp))


def trasversal(node):
    if not node:
        return (0, 0)

    left = trasversal(node.left)
    right = trasversal(node.right)

    val_0 = max(left[0], left[1]) + max(right[0], right[1])

    val_1 = node.val + left[0] + right[0]

    return (val_0, val_1)


def func():
    root = build_tree()
    rob(root)