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 的大作中提到】
: 题目：像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 的大作中提到】
: 2d array怎么写的？
: 不过这个题可能就直接加加减减注意取模更简单吧
|
d******b
发帖数: 73 | 4 挂了没事，下次继续努力。
这个题还有一个最快解法，直接打表。
创建 一个 26 × 26 的字符串矩阵。
知道上一个位置和下一个位置直接查表得结果。 |
h*******0
发帖数: 270 | 5 你是想说26 ＊ 2的矩阵把？抛开方法不谈，这题返回的字符串不是唯一的把？
【在 d******b 的大作中提到】
: 挂了没事，下次继续努力。
: 这个题还有一个最快解法，直接打表。
: 创建 一个 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 的大作中提到】
: 题目：像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 的大作中提到】
: 2d array怎么写的？
: 不过这个题可能就直接加加减减注意取模更简单吧
|
