N*****a 发帖数: 17 | 1 题目:像apple tv,chrome tv之类的,用户可以搜索电影名字,但只能用remote在一
个虚拟的keyboard上搜索,只能在虚拟键盘上下左右移动。现在给定键盘如下:
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z
如果用户要搜索电影名字为 cars,那么需要先往右走两步到c,输入enter,再往左走
两步到a,输入enter,再往下走3步往右走2步到r,输入enter,再往右走一步到s,输
入enter。现在规定L,R,U,D分部代表左,右,上,下移动一步,!代表输入enter,
那么用户动作可以表示成 RR!LL!DDDRR!R!
要求写一个函数,输入为一个string代表电影名字,输出为一个string代表用户的动作。
小印面试官,面了当天晚上给negative feedback,挂了。我面试中做的不好的是,没
有立马想到最佳solution,一开始提用bfs,被他否定后来提示下,想到用2d array坐
标,后来code写的还算顺利。但还是被小印无情的挂了。 |
r****7 发帖数: 2282 | 2 2d array怎么写的?
不过这个题可能就直接加加减减注意取模更简单吧
【在 N*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目:像apple tv,chrome tv之类的,用户可以搜索电影名字,但只能用remote在一 : 个虚拟的keyboard上搜索,只能在虚拟键盘上下左右移动。现在给定键盘如下: : a b c d e : f g h i j : k l m n o : p q r s t : u v w x y : z : 如果用户要搜索电影名字为 cars,那么需要先往右走两步到c,输入enter,再往左走 : 两步到a,输入enter,再往下走3步往右走2步到r,输入enter,再往右走一步到s,输
|
k***a 发帖数: 1199 | 3 you are right
在一
左走
,输
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2d array怎么写的? : 不过这个题可能就直接加加减减注意取模更简单吧
|
d******b 发帖数: 73 | 4 挂了没事,下次继续努力。
这个题还有一个最快解法,直接打表。
创建 一个 26 × 26 的字符串矩阵。
知道上一个位置和下一个位置直接查表得结果。 |
h*******0 发帖数: 270 | 5 你是想说26 * 2的矩阵把?抛开方法不谈,这题返回的字符串不是唯一的把?
【在 d******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 挂了没事,下次继续努力。 : 这个题还有一个最快解法,直接打表。 : 创建 一个 26 × 26 的字符串矩阵。 : 知道上一个位置和下一个位置直接查表得结果。
|
z*******o 发帖数: 4773 | |
k****r 发帖数: 807 | 7 是这样的solution吗?
其中returnPosition的function应该不难写,但面试会要求写吗?
应该像上面的牛人说的,建个char-》position的表格最好了,不然每次还要算。
结果应该不唯一,估计面试follow up需要decode。
public class remoteControl {
String[] dic = {"abcde", "fghij", "klmno","pqrst", "uvwxy", "z"};
public String remoteControl(String name) {
int x = 0;
int y = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < name.length(); i++) {
Point curr = returnPosition(name.charAt(i), dic);
for (int j = y; j > curr.y; j--) {
sb.append('U');
}
for (int j = y; j < curr.y; j++) {
sb.append('D');
}
for (int j = x; j < curr.x; j++) {
sb.append('R');
}
for (int j = x; j > curr.x; j--) {
sb.append('L');
}
sb.append('!');
x = curr.x;
y = curr.y;
}
return sb.toString();
}
} |
f**********e 发帖数: 288 | 8 题目现场做,会很有压力。 楼主拍拍。
public static String getStep(String movieName){
int curCol = 0, curRow = 0;
StringBuffer buffer = new StringBuffer();
for(int i = 0; i < movieName.length(); i++){
if(i > 0 && movieName.charAt(i-1) == movieName.charAt(i)){
buffer.append("!");
} else {
int nextRow = (movieName.charAt(i) - 'a') / 5, nextCol = (
movieName.charAt(i) - 'a') % 5;
// moving col
String movingCol = curCol > nextCol ? "L" : "R";
String movingRow = curRow > nextRow ? "U" : "D";
for(int j = 0; j < Math.abs(curCol - nextCol); j++){
buffer.append(movingCol);
}
for(int j = 0; j < Math.abs(curRow - nextRow); j++){
buffer.append(movingRow);
}
buffer.append("!");
curRow = nextRow;
curCol = nextCol;
}
}
return buffer.toString();
} |
c*******t 发帖数: 123 | 9 一般情况容易写。但从一般字母到z,从z到其它不容易。我现场也处理不好边界情况。
下面是编译通过的。
string appleKeyBoard(string input){
string output;
int preX=0;
int preY=0;
int u_x=0;
int u_y=4;
int z_x=0;
int z_y=5;
for(auto c:input){
int difference=c-'a';//relative position to origin point
int X=difference%5;//x coorindate
int Y=difference/5;//y coordinate
int diffX,diffY;
if((preX==z_x&&preY==z_y)&&(X!=z_x||Y!=z_y)){//if pre is 'z', go
other than z
output.push_back('U');//first go u, from u go there
diffX=X-u_x;
diffY=Y-u_y;
}
else if((preX!=z_x||preY==!z_y)&&X==z_x&&Y==z_y){//if pre is not 'z'
, has to go z
diffX=u_x-preX;//from preX go u first, when finished, from u go
z
diffY=u_y-preY;
}
else{//regular, including from other than z go other than z, from z
go z.
diffX=X-preX;
diffY=Y-preY;
}
if(diffX>0){
while(diffX-->0) output.push_back('R');
}
else if(diffX<0){
while(diffX++<0) output.push_back('L');
}
if(diffY>0){
while(diffY-->0) output.push_back('D');
}
else if(diffY<0){
while(diffY++<0) output.push_back('U');
}
if((preX!=z_x||preY==!z_y)&&X==z_x&&Y==z_y){
output.push_back('D');//from u go z.
}
output.push_back('!');
preX=X;
preY=Y;
}
return output;
} |
h*********n 发帖数: 11319 | 10 这个键盘是循环的话稍微复杂点,否则很直接啊
【在 N*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目:像apple tv,chrome tv之类的,用户可以搜索电影名字,但只能用remote在一 : 个虚拟的keyboard上搜索,只能在虚拟键盘上下左右移动。现在给定键盘如下: : a b c d e : f g h i j : k l m n o : p q r s t : u v w x y : z : 如果用户要搜索电影名字为 cars,那么需要先往右走两步到c,输入enter,再往左走 : 两步到a,输入enter,再往下走3步往右走2步到r,输入enter,再往右走一步到s,输
|
y**********a 发帖数: 824 | 11
public static String boardMove(String s, char c, int n) {
StringBuilder res = new StringBuilder();
for (int i = 0; i
move(c, s.charAt(i), n, res);
c = s.charAt(i);
}
return res.toString();
}
static void move(char c1, char c2, int n, StringBuilder res) {
int a = c1-'a', b = c2-'a';
int x1 = a/n, x2 = b/n, y1 = a%n, y2 = b%n;
int dx = Math.abs(x1-x2), dy = Math.abs(y1-y2);
char v = x1
char h = y1
for (int i=0; i
res.append(h);
for (int i=0; i
res.append(v);
res.append('!');
}
public static void main(String[]args) {
String s = "cars";
char c = 'a';
System.out.println(boardMove(s, c, 5));
}
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2d array怎么写的? : 不过这个题可能就直接加加减减注意取模更简单吧
|