- 设计思想:
-视频讲解链接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 };