华为OD机试真题C卷-篇5_生成哈夫曼树 c++ od

生成Huffman树

• 给定一个数值数组weights，每个值代表二叉树叶子节点的权值（>=1）;
• 根据权值数组，生成哈夫曼树，并中序遍历输出；
• 左节点权值<= 右节点权值，根节点权值为左右节点权值之和；
• 左右节点权值相同时，左子树高度<=右子树;
  
  输入描述：
  第一行输入数组长度n;
  第二行输入权值，以空格分隔；
  输出描述：
  哈夫曼树的中序遍历序列，以空格分隔；

示例1
输入：
5
5 15 40 30 10
输出：
40 100 30 60 15 30 5 15 10
==思路：==建立哈夫曼树的过程

• 以每个权值创建一个节点（只有一个树根的二叉树），放入nodes_list，并按照权值从小到大排序；
• 取出权值最小的两个节点，进行合并，根节点权值为左右子节点的权值之和
  • 设置根节点的左子树、右子树
  • 当左右子树（根节点）权值相同时，对比两者的树高，高的子树作为右子树；
  • 统计子树的高度 max(h_left, h_right)，h_left为每次取左子树；
• 将合并后的root根节点放入nodes_list，继续以上步骤，直到nodes_list中只有一个根节点；

# 中序遍历结果
result = []
# 输入n
n = int(input().strip())
weights = [int(x) for x in input().strip().split()]
 

class TreeNode:
    def __init__(self, left, right, weight, height):
        self.left = left
        self.right = right
        self.weight = weight
        self.height = height
 

# 中序遍历
def dfs(node):
	# 中序遍历左子树
    if node.left is not None:
        dfs(node.left)
    # 中间处理根
    result.append(node.weight)
    # 中序遍历右子树
    if node.right is not None:
        dfs(node.right)
        
    
# 建立哈夫曼树
nodes_list = []
for i in range(n):
    nodes_list.append(TreeNode(None, None, weights[i], 1))

# 比较树高
def comp(o1, o2):
    if(o1.weight == o2.weight): # 权值相等
        if o1.height > o2.height:
            return 1
        else:
            return -1
    
    if o1.weight > o2.weight:
        return 1
    else:
        return -1


while True:
    if len(nodes_list) == 1:
        break
    else :
        nodes_list = sorted(nodes_list, key=lambda i:i.weight)
        node1 = nodes_list.pop(0)
        node2 = nodes_list.pop(0)
        root = TreeNode(None, None, node1.weight + node2.weight, max(node1.height, node2.height) + 1)
        if comp(node1, node2) == 1:
        	root.right = node1
        	root.left = node2
        else:
        	root.right = node2
        	root.left = node1
        nodes_list.append(root)
    
 
 
dfs(nodes_list[0]) # 传入树根，中序遍历
# 输出字符串
output_str = ""
for i in range(len(result)):
    output_str += str(result[i])
    if(i!=len(result)-1):
        output_str+=" "
print(output_str)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

 

小朋友来自多少小区

• 每个小朋友报出与自己同一个小区的人数，存入数组garden中；
• 计算至少有几个小区？多少小朋友？
  输入描述：
  输入garden数组，如2 2 3， 即第一个小朋友报出有2个小朋友跟自己同一个小区，第二个小朋友同样报出2个，依次类推; garden数组长度最大为999；
  输出描述：
  至少的小区数，小朋友数

示例1
输入：
2 2 3
输出：
2，7

示例2
输入：
2 2 2 2 2 3 3
输出：
3,10

思路：

• 贪心算法，依次遍历，让尽可能多的小朋友在同一个小区；
  • garden 升序排序；
  • 初始化 小区数areas=1, friend_nums = garden[0]+1，dist= garden[0]
  • 从i=1开始遍历garden，for i in range(1, len(garden)): 如果当前报数与前一个报数相同，则判断能否算入同一个小区；
    • 是，则dist-=1，继续下一次遍历；
    • 否，则areas += 1, friend_nums += garden[i] +1, dist=garden[i]
  • 输出areas,friend_nums

class GardenNum:
    def solution(self, garden):
        # 排序
        garden.sort()
        # 初始化
        areas = 1
        friend_nums = garden[0] + 1
        dist = garden[0]
        for i in range(1, len(garden)):
            if garden[i] == garden[i-1]: # 可能是同一个小区
                if dist > 0:
                    # 算入同一个小区
                    dist -= 1
                else:
                    areas += 1 #
                    friend_nums += garden[i] + 1
                    dist = garden[i]

            else:
                # 报数与前一个不同，肯定不是同一个小区
                areas += 1  #
                friend_nums += garden[i] + 1
                dist = garden[i]

        print(areas, end=",")
        print(friend_nums)


if __name__ == '__main__':
    garden_num = GardenNum()
    while True:
        try:
            garden = list(map(int, input().strip().split()))
            garden_num.solution(garden)
        except KeyboardInterrupt:
            break

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

其他基于索引的实现：

nums = [int(x) for x in input().split(" ")]
#index为报告的结果，zones[index]为报告相同结果的总人数
zones = [0 for x in range(1000)]
count = 0
 
i=0
while(True):
  if(i>=len(nums)):
    break
  else:
    zones[nums[i]]+=1
  
  i+=1
 
 
for j in range(1000):
    if (zones[j] <= 0):
      continue
    else:
      total = math.ceil(zones[j] / (j+1));
      count += total * (j+1);
print(count);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 

堆内存申请

 
 
n = int(input())
memorys = []
while (True) :
    try:
        nums = [int(x) for x in input().split(" ")]
        memorys.append([nums[0], nums[0]+nums[1]- 1])
    except:
        break
 
memorys.sort()
length = len(memorys)
flag = 0
for i in range(length):
    x = memorys[i][0]
    y = memorys[i][1]
    if (not ((x >= 0 and y >= 0 and x < 100 and y < 100 and x <= y) and 
        (not (i > 0 and x <= memorys[i-1][1])))) :
        flag = 1  
        break  
    
 
 
if (flag!=1) :
    offset = -1
    max_distance = 100
    start = memorys[0][0]
    if (start >= n and start < max_distance + n) :
        offset = 0
        max_distance = start - n
    
    i=1
    while(True):
        if(i>=length):
            break
        else :
            current = memorys[i][0]
            before = memorys[i-1][1]
            if (current - before > n):
                if(current - before < max_distance + n) :
                    offset = before + 1
                    max_distance = current - before - n
                    break
        i+=1
 
    end = memorys[length - 1][1]
    if (end<=99-n and end > 99-n-max_distance) :
        offset = end + 1
    
    print(offset)
else:
    print(-1)
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
47
48
49
50
51
52
53

 

跳格子3

 
n =int(input())
nums = [int(x) for x in input().split(" ")]
k = int(input())
queue = [[0 for i in range(2)] for j in range(n)]
cache =[0 for i in range(n)]
cache[0] = nums[0]
queue[0][0] = 0
queue[0][1] = cache[0]
index1 = 0
index2 = 1
 
i=1
while(True):
    if(i>=n):
        break
    else :
        while(index1<index2):
            if(queue[index1][0] < i - k):
                index1 +=1
            else :
                break
            
        
        cache[i] = nums[i] + queue[index1][1]
 
        while(index1<index2):
            if(queue[index1][1] <= cache[i]):
                index1 +=1
            else :
                break
        queue[index2][0] = i
        queue[index2][1] = cache[i]
        index2+=1
    
    i+=1
 
print(cache[n - 1])
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

 

测试用例执行计划

• 某产品有n个特性，每个特性有一个优先级；
• 设计m个测试用例，每个测试用例对应一个特性的集合，测试用例的优先级为其对应特性的优先级之和；
• 测试用例按照优先级大的先执行，优先级相同则ID小的先执行；
  输入描述：
  第一行输入n、m;
  后续n行输入特性 ID=1到 ID=n的优先级；
  后续m行输入测试用例ID=1到ID=m 对应的特性ID列表
  输出描述：
  按照执行顺序，输出测试用例的ID，每行一个ID;

示例1
输入：
5 4
1
1
2
3
5
1 2 3
1 4
3 4 5
2 3 4
输出：
3
4
1
2

示例2
输入：
3 3
3
1
5
1 2 3
1 2 3
1 2 3
输出：
1
2
3

思路：
简单排序问题

 
class TestCase:
    def solution(self, test_case_pri_list, m):
        idx_list = [i for i in range(m)]

        # 值相同时，索引保持从小到大
        idx_list.sort(key=lambda i: test_case_pri_list[i], reverse=True)
        for idx in idx_list:
            print(idx+1)


if __name__ == '__main__':
    test_case = TestCase()
    while True:
        try:
            n, m = list(map(int, input().strip().split()))
            feature_pri_list = []
            test_case_pri_list = []
            for i in range(n):
                feature_pri_list.append(int(input().strip()))
            for i in range(m):
                val = [feature_pri_list[j-1] for j in list(map(int, input().strip().split()))]
                test_case_pri_list.append(sum(val))
            test_case.solution(test_case_pri_list, m)
        except KeyboardInterrupt:
            break
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

 

贪吃的猴子

• 一只猴子获取香蕉，只能从数组（元素为香蕉数）的头部或者尾部开始获取；
• 最多只能取n次；
• 求最多获取的香蕉数；
  输入描述：
  第一行输入数组长度m;
  第二行输入数组的数据;
  第三行为获取次数n;
  输出描述:
  获取的最大数值

示例1
输入：
7
1 2 2 7 3 6 1
3
输出：
10

示例2
输入：
3
1 2 3
3
输出：
6

示例3
输入：
4
4 2 2 3
2
输出：
7

思路：

• 双指针，先从开头依次取n次，并求和total_bra;
• 依次从开头开始的第n次，减少一次，从末尾取，求和并与total_bra比较，取最大值；
• 依次类推

 
n = int(input())
nums = [int(x) for x in input().split(" ")]
count = int(input())
temp_sum = 0
for i in range(count):
    temp_sum += nums[i]

result = temp_sum
left = count - 1
right = n - 1

while (True):
    if (left < 0):
        break
    else:
        temp_sum += nums[right] - nums[left] # 减去左边的取值，加上当前末尾的取值
        if (temp_sum > result):
            result = temp_sum
        right -= 1
        left -= 1
print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 

小扇和小船的数字游戏

 
def getBinaryOneCount(num):
    count = 0
    while(True):
        if(num <=0):
            break
        else :
            count += num % 2
            num = int(num/2)
    return count
 
 
n = int(input())
m = n+1
while(True):
    if (getBinaryOneCount(m) == getBinaryOneCount(n)):
        break
    m+=1
print(m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 

幸存数之和

• nums为正整数数组，jump为跳数，left为幸存数量
• 运算过程：从索引为0开始向后跳，中间跳过jump个数字，命中索引为jump+1的数字，该数被敲出，并从该点起跳，依次类推，直到nums数组中幸存left个数，然后返回幸存数之和；
• 起点、命中点之间间隔jump个数字，已被敲出的数字不计入在内；
• 跳到数组末尾时，从头开始（循环查找）
• 若起始时， left >len(nums)， 则无需跳数处理，直接计算和；
  输入描述：
  第一行输入nums数组
  第二行输入jump跳数
  第三行输入left幸存数
  输出描述：
  输出幸存数之和

示例1
输入：
1,2,3,4,5,6,7,8,9
4
3
输出：
13
说明：
依次删除6 2 8 5 4 7

 
def sumOfLeft(nums, jump, left) :
    size = len(nums)
    start = 0
    while True:
        if len(nums) <= left:
            break
        else :
            start += jump + 1
            start = start % len(nums)
            nums.pop(start)
            start -=1 
    remain_sum = 0
    for i in range(len(nums)):
        remain_sum +=nums[i]
    return remain_sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 

CPU算力分配

 
params = [int(x) for x in input().split(" ")]
count1 = params[0]
count2 = params[1]
nums1 = [int(x) for x in input().split(" ")]
sum1 = sum(nums1)
nums2 = [int(x) for x in input().split(" ")]
sum2 = sum(nums2)
num2_map = {}
for key in nums2:
    num2_map[key] = 1
 
nums1.sort()
i=0
while(True):
    if(i>=count1):
        break
    else :
        target = nums1[i] - int((sum1-sum2)/2)
        if (target in num2_map) :
            print(str(nums1[i]) + " " + str(target))
            break
        
    
    i+=1
 
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

 

亲子游戏

• 在一个二维矩阵（n*n）的格子地图上，宝宝和妈妈抽签决定各自的位置，每个格子有不同数量的糖果，部分格子有障碍物；
• 游戏规则，妈妈必须在最短的时间（每次走一步）到达宝宝的位置，路上的糖果都可以拿走，不能走障碍物的格子，只能上下左右的走；
• 妈妈在最短到达宝宝位置的时间内最多拿到多少糖果。
  输入描述：
  第一行输入n;
  后续n行，每行有n个值，-3表示妈妈，-2表示宝宝，-1表示障碍物，>=0表示糖果数，0没有糖果，但可以通过；
  输出描述：
  妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，地图最大50*50；
  若无法到达宝宝位置，则输出-1

示例1
输入：
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
输出：
9

示例2
输入：
4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3
输出：
-1

思路：

• BFS/DFS
• 先找最短路径（最少步子），在最短路径的情况下，再找最多糖果数；
• 两次BFS

class MBGame:
    def solution(self, n, arr):
        self.visited = [[0 for j in range(n)] for i in range(n)]

        # 找妈妈的位置
        self.mother_pos = self.find_pos(n, arr, -3)

        # 找baby的位置
        self.baby_pos = self.find_pos(n, arr, -2)

        # 寻找最短路径（广度优先）
        steps = self.BFS(n)
        print("最短路径:", steps)

        # 计算在最短路径下的最大糖果数（走 steps 步）
        candy_arr = [[-1 for i in range(n)] for j in range(n)] # 不能用visited控制访问过程
        candy_arr[self.mother_pos[0]][self.mother_pos[1]] = 0 # 起始位置糖果数为0
        # 再次广度优先
        queue = [self.mother_pos]
        while True:
            if steps <= 0:
                break

            # 出队
            size = len(queue)
            for i in range(size):
                cur_pos = queue.pop(0)
                # 从当前格子走四个方向
                x, y = cur_pos
                directions = [(x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)]
                for new_x, new_y in directions:
                    # 新位置有效、不为-1、未走过，则可以走
                    if 0 <= new_x < n and 0 <= new_y < n and arr[new_x][new_y] != -1:
                        if candy_arr[new_x][new_y] == -1:
                            # 入队
                            queue.append((new_x, new_y))
                        # 更新新位置的糖果数
                        if arr[new_x][new_y] != -2: # 没到终点
                            candy_arr[new_x][new_y] = max(candy_arr[new_x][new_y],
                                                          candy_arr[x][y] + arr[new_x][new_y])
                        else: # 可以用2x2的 矩阵演示说明
                            candy_arr[new_x][new_y] = max(candy_arr[new_x][new_y],
                                                          candy_arr[x][y])
            steps -= 1
        for i in range(n):
            print("candy_arr:", candy_arr[i]) # 终点位置即为最大糖果数
        print(candy_arr[self.baby_pos[0]][self.baby_pos[1]])

    def BFS(self, n):
        # 起始点入队
        queue = []
        queue.append(self.mother_pos)

        # flag 标识是否能走到终点
        flag = False
        # 走的步子数
        steps = 0
        # 循环出队
        while True:
            size = len(queue)
            if size <= 0: # 判断队列是否为空
                break
            for i in range(size): # 当前层级的所有的位置，作为起始点(同时向外层走一步)
                start_pos = queue.pop(0)
                # 判断当前位置是否为终止位置
                x, y = start_pos
                if arr[x][y] == -2:
                    flag = True  # 走到终点，直接结束
                    break
                else:
                    # 从当前位置，开始走四个方向
                    directions = [(x, y+1), (x, y-1), (x-1, y), (x+1, y)]
                    for new_x, new_y in directions:
                        # 新位置有效、不为-1、未走过，则可以走
                        if 0 <= new_x < n and 0 <= new_y < n and arr[new_x][new_y] != -1 and \
                                self.visited[new_x][new_y] == 0:
                            self.visited[new_x][new_y] = 1 # 表示已走过
                            # 新位置入队
                            queue.append((new_x, new_y))
            if flag: # 走到终点，则提前终止外层循环
                break
            # 走一步
            steps += 1

        if not flag: # 无法到达终点
            return -1
        # 到达终点
        return steps # 第一个搜索到达的路径，一定是最短路径

    def find_pos(self, n, arr, val):
        for i in range(n):
            for j in range(n):
                if arr[i][j] == val:
                    m_pos = (i, j)
                    return m_pos


if __name__ == '__main__':
    mb_game = MBGame()
    # 3 2 1 -3
    # 1 -1 1 1
    # 1 1 -1 2
    # -2 1 2 3
    while True:
        try:
            n = int(input().strip())
            arr = []
            for i in range(n):
                arr.append(list(map(int, input().strip().split())))

            mb_game.solution(n, arr)
        except KeyboardInterrupt:
            break

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

 

传递悄悄话

• 给定一个二叉树，节点采用顺序存储，如 i=0 表示根节点，2i + 1 表示左子树根，2i + 2 表示右子树根;
• 每个节点站一个人，节点数值表示由父节点到该节点传递消息需要的时间；
• 输出从根节点，将消息传递给所有的人需消耗的时间；
  输入描述：
  0 9 20 -1 -1 15 17 -1 -1 -1 -1 3 2 ；节点的顺序存储；-1表示空节点
  输出描述：
  所有的人都收到消息所消耗的时间 38

示例1
输入：
0 9 20 -1 -1 15 17 -1 -1 -1 -1 3 2
输出：
38

示例2
输入：
0
输出：
0

示例3
输入：
0 9
输出：
9

说明：
还原出二叉树如下

思路：

• 求二叉树的最大路径和；
• BFS + 队列

class MaxPathSum:
    def solution(self, alist):
        # 广度优先入队
        queue = []
        queue.append((0, 0)) # 根节点入队  结构为-->（节点索引， 根节点到当前节点的路径和）
        result = 0 # 最大路径和
        while True:
            if len(queue) <= 0:
                break
            root_node = queue.pop(0)
            if self.is_leaf(root_node, alist):
                print("leaf:", root_node)
                result = max(result, root_node[1])
            else:
                # 继续找左子节点、右子节点
                left_node_idx = 2 * root_node[0] + 1
                if left_node_idx < len(alist) and alist[left_node_idx] != -1:
                    left_node_path_sum = alist[left_node_idx] + root_node[1]
                    # 新节点入队
                    queue.append((left_node_idx, left_node_path_sum))
                right_node_idx = 2 * root_node[0] + 2
                if right_node_idx < len(alist) and alist[right_node_idx] != -1:
                    right_node_path_sum = alist[right_node_idx] + root_node[1]
                    queue.append((right_node_idx, right_node_path_sum))

        print(result)

    def is_leaf(self, node, alist):
        node_idx = node[0]
        left_idx = 2 * node_idx + 1
        right_idx = 2 * node_idx + 2
        # 索引的有效性
        if left_idx >= len(alist):
            return True
        elif left_idx < len(alist) and right_idx >= len(alist):
            if alist[left_idx] == -1:
                return True
            return False
        else:
            # 索引均有效
            if alist[left_idx] != -1 or alist[right_idx] != -1:
                return False
            return True


if __name__ == '__main__':
    max_path_sum = MaxPathSum()
    while True:
        try:
            alist = list(map(int, input().strip().split()))
            max_path_sum.solution(alist)
        except KeyboardInterrupt:
            break

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
47
48
49
50
51
52
53
54