首页 > 试题广场 >

牛牛收集卡片

[编程题]牛牛收集卡片

热度指数：313 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛在玩一个游戏，他操纵的游戏角色现在在一个坐标系的(0,0)处，他每次操纵该游戏角色都只能使它往上走或者往右走，向上走记为'U'，向右走记为'R'。在这个坐标系中散落着n张卡片，当该游戏角色移动到卡片的位置上时即可收集到这张卡片。游戏胜利的条件是：收集到所有的卡片。

现在，牛牛想知道他能否赢得游戏，所以他想请聪明的你帮他写一个程序，如果可以赢得游戏，请返回移动的路径序列(例如："RURURUR")，如果不可以，请返回"NO"。当然，如果有多条路径都可以赢得游戏，请输出字典序最小的一条路径。

示例1

输入

2,[[0,2],[2,0]]

输出

"NO"

说明

无法通过只向上或向右移动收集到所有的卡片。

示例2

输入

5,[[1,1],[1,3],[2,3],[5,5],[4,3]]

输出

"RUUURRRRUU"

说明

通过RUUURRRRUU的移动方式，可以收集到所有的卡片，且该移动方式字典序最小。

备注:

算法知识视频讲解

Python 3

ZhongHaoWang

简单排序

class Solution:
    def collectCards(self , n , a ):
        # write code here
        # 存在一个非严格递增的(x,y)序列
        a.sort(key = lambda x:x[0])
        for i in range(1,len(a)):
            if a[i][1] < a[i - 1][1]:
                return 'NO'
            
        # 按照递增序列依次遍历一定有最短的字典序
        # 优先向右走
        ans = ''
        cur_x,cur_y = 0,0
        for i in range(len(a)):
            x,y = a[i][0],a[i][1]
            ans += 'R' * (x - cur_x)
            ans += 'U' * (y - cur_y)
            cur_x,cur_y = x,y
        return ans

发表于 2021-08-27 19:34:36 回复(0)