- 题目描述:
图片说明
- 题目链接:
https://www.nowcoder.com/practice/57024a5e7b734fd7904f81f34f696ae9?tpId=196&&tqId=37689&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking

- 设计思想:
图片说明

-视频讲解链接B站视频讲解
- 复杂度分析:
图片说明
- 代码:
c++版本:

bool cmd(vector<int>&a, vector<int>&b){
    ///为了满足字典序最小,所以只能先右后上
    //如果x值相同,就按照y来排序
    if(a[0] == b[0]) return a[1] < b[1];
    else return a[0]<b[0];
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 如果可以赢得游戏,返回字典序最小的序列,反之返回"NO"
     * @param n int整型 卡片的数量
     * @param a int整型vector<vector<>> 卡片的坐标数组
     * @return string字符串
     */
    string collectCards(int n, vector<vector<int> >& a) {
        // write code here
        string res = "";
        a.push_back({0,0});//添加一个起点
        sort(a.begin(), a.end(), cmd);
        for(int i = 1;i < n+1;i ++){
            ///此时没有办法收集全部的卡片
            if(a[i][1] < a[i-1][1]) return "NO";
            else{
                int x = a[i][0] - a[i-1][0];//计算两点的x距离
                int y = a[i][1] - a[i-1][1];//计算两点的y距离
                //看x移动几次就加几个R
                while(x --){
                    res += "R";
                }
                //看y移动几次就加几个U
                while(y--){
                    res += "U";
                }
            }
        }
        return res;
    }
};

Java版本:

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 如果可以赢得游戏,返回字典序最小的序列,反之返回"NO"
     * @param n int整型 卡片的数量
     * @param a int整型二维数组 卡片的坐标数组
     * @return string字符串
     */
    public String collectCards (int n, int[][] a) {
        // write code here
        Arrays.sort(a, Comparator.comparingInt((int[] o) -> o[0]).thenComparingInt(o -> o[1]));
        StringBuilder sb = new StringBuilder();
        //从起点到第一个卡片所需的移动方法
        for(int i = 0;i < a[0][0];i ++){
            sb.append('R');
        }
        for(int i = 0;i < a[0][1];i ++){
            sb.append('U');
        }
        for(int i = 1;i < a.length;i ++){
            ///此时没有办法收集全部的卡片
            if(a[i][1] < a[i-1][1]) return "NO";
            else{
                int x = a[i][0] - a[i-1][0];//计算两点的x距离
                int y = a[i][1] - a[i-1][1];//计算两点的y距离
                //看x移动几次就加几个R
                while(x -- >0){
                    sb.append('R');
                }
                //看y移动几次就加几个U
                while(y-- >0){
                    sb.append('U');
                }
            }
        }
        return sb.toString();
    }
}

Python版本:

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 如果可以赢得游戏,返回字典序最小的序列,反之返回"NO"
# @param n int整型 卡片的数量
# @param a int整型二维数组 卡片的坐标数组
# @return string字符串
#
class Solution:
    def collectCards(self , n , a ):
        # write code here
        a.sort(key = lambda x:x[0])
        res = ""
        #从起点到第一个卡片所需的移动方法
        res += ("R" * a[0][0])
        res += ("U" * a[0][1])
        for i in range(1,len(a)):
            #此时没有办法收集全部的卡片
            if(a[i][1] < a[i-1][1]): return "NO"
            else:
                x = a[i][0] - a[i-1][0]#计算两点的x距离
                y = a[i][1] - a[i-1][1]#计算两点的y距离
                #看x移动几次就加几个R
                while x > 0:
                    res += "R"
                    x -= 1
                #看y移动几次就加几个U
                while y > 0:
                    res += "U"
                    y -= 1
        return res

JavaScript版本:

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 如果可以赢得游戏,返回字典序最小的序列,反之返回"NO"
 * @param n int整型 卡片的数量
 * @param a int整型二维数组 卡片的坐标数组
 * @return string字符串
 */
function collectCards( n ,  a ) {
    // write code here
       a.sort(function(x, y){
        if(x[0] == y[0])return x[1]-y[1];
           else return x[0] - y[0];
       });
        let res = ""
        //从起点到第一个卡片所需的移动方法
        for(let i = 0;i < a[0][0];i ++){
            res += 'R';
        }
        for(let i = 0;i < a[0][1];i ++){
            res += 'U';
        }
        for(let i = 1;i < a.length;i ++){
            ///此时没有办法收集全部的卡片
            if(a[i][1] < a[i-1][1]) return "NO";
            else{
                let x = a[i][0] - a[i-1][0];//计算两点的x距离
                let y = a[i][1] - a[i-1][1];//计算两点的y距离
                //看x移动几次就加几个R
                while(x -- >0){
                    res += 'R';
                }
                //看y移动几次就加几个U
                while(y-- >0){
                    res += 'U';
                }
            }
        }
        return res;
}
module.exports = {
    collectCards : collectCards
};