华为OD机试真题C卷-篇3

查找一个有向网络的头节点和尾节点

• 在一个有向图中，有向边用两个整数表示，第一个整数表示起始节点，第二个整数表示终止节点；
• 图中只有一个头节点，一个或者多个尾节点；
• 图可能存在环，有环则输出-1；
• 输出图中的头节点（入度为0）、尾节点（出度为0），如图头节点为1，尾节点为4。
  
  输入描述：
  第一行输入n，n >=0
  第二行为n个数对，表示n条边；
  输出描述：
  输出一行，头节点、尾节点以空格隔开，多个尾节点则从大到小输出。
   
  示例1
  输入：
  4
  1 2 1 3 2 4 3 4
  输出：
  1 4

思路：

• 拓扑排序，判断有向图是否有环，有环则直接输出-1；
• 只有一个起始点，一个或多个结尾点；

relations = {}
indegree = {}
head = -1
tails = []def find_head():global relations,indegree,headfor  keys in relations:if (keys in indegree) :continueelse :head = keysbreakdef find_tails():global relations,indegree,tailsfor keys in indegree :if (keys in relations) :continueelse :tails.append(keys)n = int(input())
nums = [int(x) for x in input().split(" ")]i=0
while(i < 2 * n):if(nums[i] in relations):relations[nums[i]].append(nums[i + 1])else :relations[nums[i]] = []relations[nums[i]].append(nums[i + 1])if(nums[i + 1] in indegree):indegree[nums[i + 1]] += 1else :indegree[nums[i + 1]] = 1i += 2find_head()
find_tails()
tails.sort()queue = []
queue.append(head)
while (True) :if(len(queue)<=0):breakelse :temp = queue[0]queue.pop(0)if(temp in relations):temp_list = relations[temp]for  x in temp_list:indegree[x]= indegree[x] - 1if (indegree[x] == 0) :queue.append(x)
flag = 1
for key in indegree:if (indegree[key] > 0) :flag = 0if (flag==0) :print(-1)
else: output_str = str(head) + " "for x in tails:output_str += str(x) + " "print(output_str[:-1])

 

幼儿园篮球游戏

双指针+ 线性表

import functools
import sys
import copy
import re
import mathnums = [int(x) for x in input().split(",")]
target_nums = [int(x) for x in input().split(",")]arr = [float('inf') for i in range(300)]left = 0
right = 0
target_pos = 0result = ""
i=0
while(True):if(i>=len(nums)):breakelse :arr[right] = nums[i]right+=1while (True) :if(right <= left):breakelse :if (arr[left] == target_nums[target_pos]) :result += "L"left += 1target_pos += 1continueelif (arr[right-1] == target_nums[target_pos]) :result += "R"right -= 1target_pos += 1continuebreaki+=1if (left != right) :print("NO")
else :print(result)