华为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,head
    for  keys in relations:
        if (keys in indegree) :
            continue
        else :
            head = keys
            break
 
def find_tails():
    global relations,indegree,tails
    for keys in indegree :
        if (keys in relations) :
            continue
        else :
            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]] += 1
    else :
        indegree[nums[i + 1]] = 1
    i += 2
    
 
find_head()
find_tails()
tails.sort()
 
queue = []
queue.append(head)
while (True) :
    if(len(queue)<=0):
        break
    else :
        temp = queue[0]
        queue.pop(0)
        if(temp in relations):
            temp_list = relations[temp]
            for  x in temp_list:
                indegree[x]= indegree[x] - 1
                if (indegree[x] == 0) :
                    queue.append(x)
flag = 1
for key in indegree:
    
    if (indegree[key] > 0) :
        flag = 0
 
if (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 math
 
nums = [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 = 0
 
result = ""
i=0
while(True):
    if(i>=len(nums)):
        break
    else :
        arr[right] = nums[i]
        right+=1
        while (True) :
            if(right <= left):
                break
            else :
                if (arr[left] == target_nums[target_pos]) :
                  result += "L"
                  left += 1
                  target_pos += 1
                  continue
                elif (arr[right-1] == target_nums[target_pos]) :
                  result += "R"
                  right -= 1
                  target_pos += 1
                  continue
                 
                break
    i+=1
 
if (left != right) :
  print("NO")
else :
  print(result)