f****9
发帖数: 506 | 1 两人，没人45分钟。
第一个：从一个array里找出等于t的数，把它们放到array后面，其他元素相对位置保
持不变，顺次迁移；
第二个：一个m x n的方格，从左上角到右下角走，只能向右或向下，总共几种走法。
问题很简单又是老题。我也都答出来了，code也写了。第二个问题我开始用计算组合数
的方法，面试官还没见过这种解法。但是最后仍然被拒了。感觉可能是答题太慢了？或
者听力不好老让第一个面试官重复问题？没办法。。。 | X*********n
发帖数: 570 | 2 第二题dp啊
设每个格的走法为t(x,y),
if (x==1||y==1)
t(x, y)=1
else
t(x, y)=t(x-1, y)+t(x, y-1)
【在 f****9 的大作中提到】
: 两人，没人45分钟。
: 第一个：从一个array里找出等于t的数，把它们放到array后面，其他元素相对位置保
: 持不变，顺次迁移；
: 第二个：一个m x n的方格，从左上角到右下角走，只能向右或向下，总共几种走法。
: 问题很简单又是老题。我也都答出来了，code也写了。第二个问题我开始用计算组合数
: 的方法，面试官还没见过这种解法。但是最后仍然被拒了。感觉可能是答题太慢了？或
: 者听力不好老让第一个面试官重复问题？没办法。。。
| r***u
发帖数: 241 | 3 显然是组合数学的方法好啊
【在 X*********n 的大作中提到】
: 第二题dp啊
: 设每个格的走法为t(x,y),
: if (x==1||y==1)
: t(x, y)=1
: else
: t(x, y)=t(x-1, y)+t(x, y-1)
| X*********n
发帖数: 570 | 4 解释下呢？
【在 r***u 的大作中提到】
: 显然是组合数学的方法好啊
| f****9
发帖数: 506 | 5 我说用dp了。
感觉挺莫名其妙被拒的。第一个面试官问完了还说it‘s good，第二个面试官连计算组
合数的方法都不会。
可能是我听力不太好交流有点问题让他们印象是比较笨？还是我答题太慢了？莫非这种
难度的题45分钟应该完成多个，每个都在白板上完成code，才算合格了？
【在 X*********n 的大作中提到】
: 第二题dp啊
: 设每个格的走法为t(x,y),
: if (x==1||y==1)
: t(x, y)=1
: else
: t(x, y)=t(x-1, y)+t(x, y-1)
| P*******7
发帖数: 55 | 6 第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)
【在 f****9 的大作中提到】
: 两人，没人45分钟。
: 第一个：从一个array里找出等于t的数，把它们放到array后面，其他元素相对位置保
: 持不变，顺次迁移；
: 第二个：一个m x n的方格，从左上角到右下角走，只能向右或向下，总共几种走法。
: 问题很简单又是老题。我也都答出来了，code也写了。第二个问题我开始用计算组合数
: 的方法，面试官还没见过这种解法。但是最后仍然被拒了。感觉可能是答题太慢了？或
: 者听力不好老让第一个面试官重复问题？没办法。。。
| f****9
发帖数: 506 | 7 我说了，面试官还没见过用组合数的方法。
但是还是让写程序，而且要考虑有obstacle的情况，就是考虑有的方格不能通过的情况
。这种情况好像不能用组合数直接算吧？
【在 P*******7 的大作中提到】
: 第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)
| P*******7
发帖数: 55 | 8 对于第二个问题，如果面试官就问了这一题，你花的时间就长了。因为这道题后面还有
一问，如果你保
持向下的步子一直多于或等于你向右的步子，一共多少种走法。
【在 f****9 的大作中提到】
: 我说用dp了。
: 感觉挺莫名其妙被拒的。第一个面试官问完了还说it‘s good，第二个面试官连计算组
: 合数的方法都不会。
: 可能是我听力不太好交流有点问题让他们印象是比较笨？还是我答题太慢了？莫非这种
: 难度的题45分钟应该完成多个，每个都在白板上完成code，才算合格了？
| P*******7
发帖数: 55 | 9 这道题不是google经典题目么？面试者怎么会不知道组合数方法呢...那你太冤了
【在 f****9 的大作中提到】
: 我说了，面试官还没见过用组合数的方法。
: 但是还是让写程序，而且要考虑有obstacle的情况，就是考虑有的方格不能通过的情况
: 。这种情况好像不能用组合数直接算吧？
| s********y
发帖数: 161 | 10 第一题，pass一遍找到有多少t,从第一个t开始顺着写非t数，最后填t。
还有什么更好的解法么。 | | | j*****u
发帖数: 1133 | 11 第一遍就可以把非t前移，然后从最后一个位置把t填上
【在 s********y 的大作中提到】
: 第一题，pass一遍找到有多少t,从第一个t开始顺着写非t数，最后填t。
: 还有什么更好的解法么。
| j*****u
发帖数: 1133 | 12 c# implementation，还有没有更好方法？
static void ArrayShift(T[] array, T seed) where T:IComparable
{
if (array == null)
throw new ArgumentNullException("array");
int dest = 0;
for (int i = 0; i < array.Length; ++i)
{
if (i != dest && !array[i].Equals(seed))
{
array[dest++] = array[i];
}
}
for (int i = dest; i < array.Length; ++i)
{
array[i] = seed;
}
}
【在 j*****u 的大作中提到】
: 第一遍就可以把非t前移，然后从最后一个位置把t填上
| r*******g
发帖数: 43 | 13 我google第二题，竟然在“小学生VBS竞赛题库“里有。提示是杨辉三角算法或者回溯
法。这个回溯法应该就是DP, 杨辉三角是个什么？ | d**e
发帖数: 6098 | 14 你的方法是对的，但code是不是写错了点？
1, 2, 3, 4, 5, 6, 7, 8
seed = 5
但由于dest一直等于0，所以6不幸被换到去1的位置了.
【在 j*****u 的大作中提到】
: c# implementation，还有没有更好方法？
: static void ArrayShift(T[] array, T seed) where T:IComparable
: {
: if (array == null)
: throw new ArgumentNullException("array");
: int dest = 0;
: for (int i = 0; i < array.Length; ++i)
: {
: if (i != dest && !array[i].Equals(seed))
: {
| c***2
发帖数: 838 | 15 Original Array: 22 22 55 55 55 55 55 33 33 33
num=22:freq=2
num=55:freq=5
num=33:freq=3
Rotate 2:
55 55 55 55 55 33 33 33 22 22
Moved 44 to back:
0 moved:
55 55 55 55 55 33 33 33 22 22
Moved 33 to back:
3 moved:
55 55 55 55 55 22 22 33 33 33 | c***2
发帖数: 838 | 16 int move_num_to_array_end(int array[], int size, int num)
{
int i=0,j,from;
int count=0;
int total=0;
int tail=size;
while(i
count=0;
from=i;
while((array[i]==num)&&(i
if (i>=tail-1) return total;
if (count) {
for(j=i;j
array[j-count]=array[j];
tail -= count;
for(j=tail;j
array[j]=num;
i=from;
}
else
i++;
}
return total;
} | f*******r
发帖数: 180 | 17 请问这样做可以么?
// 从一个array里找出等于t的数, 把它们放到array后面, 其他元素相对位置保持不变
, 顺次迁移.
void move_num_to_array_end(int array[], int size, int t) {
int idx = 0;
for (int i = 0; i < size; i++) {
int curInt = array[i];
if (curInt != t) {
array[idx] = array[i];
idx++;
}
}
for (;idx < size; idx++)
array[idx] = t;
}
// 一个m x n的方格, 从左上角到右下角走, 只能向右或向下, 总共几种走法.
int move_topleft_to_bottomright(int m, int n) {
if (m == 1 || n == 1)
return 1;
return (move_topleft_to_bottomright(m-1,n)+move_topleft_to_bottomright(m
,n-1));
} | c***2
发帖数: 838 | 18 very good. Much cleaner than mine.
【在 f*******r 的大作中提到】
: 请问这样做可以么?
: // 从一个array里找出等于t的数, 把它们放到array后面, 其他元素相对位置保持不变
: , 顺次迁移.
: void move_num_to_array_end(int array[], int size, int t) {
: int idx = 0;
: for (int i = 0; i < size; i++) {
: int curInt = array[i];
: if (curInt != t) {
: array[idx] = array[i];
: idx++;
| g*********6
发帖数: 1149 | 19 第2题如果编程做，都不难。
如果用组合做，答案是等价于m+n-2个数里面取m-1个数，答案是c(m+n-2, m-1).因为总
共要走m+n-2，要在里面选m-1步向下走，或选n-1步向右走。
如果向下的步数不能超过向右的步数，该怎么算？
【在 P*******7 的大作中提到】
: 第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)
| f*******r
发帖数: 180 | 20 我觉得应该是c(m+n-2, n-1) 或者 c(m+n-2, m-1).
【在 P*******7 的大作中提到】
: 第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)
| | | g*********s
发帖数: 1782 | 21 如果有方格不能通过的情况，确实会比较麻烦。不过还是组合问题。
【在 f****9 的大作中提到】
: 我说了，面试官还没见过用组合数的方法。
: 但是还是让写程序，而且要考虑有obstacle的情况，就是考虑有的方格不能通过的情况
: 。这种情况好像不能用组合数直接算吧？
| g*********s
发帖数: 1782 | 22 还有优化的余地。如果数组里全是t，那第二个循环没必要了。不过不影响复杂度。
【在 f*******r 的大作中提到】
: 请问这样做可以么?
: // 从一个array里找出等于t的数, 把它们放到array后面, 其他元素相对位置保持不变
: , 顺次迁移.
: void move_num_to_array_end(int array[], int size, int t) {
: int idx = 0;
: for (int i = 0; i < size; i++) {
: int curInt = array[i];
: if (curInt != t) {
: array[idx] = array[i];
: idx++;
| l****i
发帖数: 396 | 23 这两个是等价的把
【在 f*******r 的大作中提到】
: 我觉得应该是c(m+n-2, n-1) 或者 c(m+n-2, m-1).
| x******3
发帖数: 245 | 24 用类似quick sort里得partition， 只要一次遍历数组就可以了， 但是需要3个指针
【在 g*********s 的大作中提到】
: 还有优化的余地。如果数组里全是t，那第二个循环没必要了。不过不影响复杂度。
| f*******r
发帖数: 180 | 25 sorry, cannot type Chinese in the lab.....
I think a easy fix would be #ofways(topleft->bottomright) - #ofways(topleft-
>blockA)*#ofways(blockA->bottomright) if you only face one blockA.
But it's more complicated when you face more than one blocks.
【在 g*********s 的大作中提到】
: 如果有方格不能通过的情况，确实会比较麻烦。不过还是组合问题。
| e**********6
发帖数: 78 | 26 void mv_t_to_end(int *a, int size, int t){
int i=0,j=0,k=size;
while(j
if(a[j]==t){
j++;
k--;
}
else
a[i++]=a[j++];
}
while(k
a[k++]=t;
} | h**6
发帖数: 4160 | 27 如果格子不多，障碍不少，令f(i, j)为各格子通往右下角的走法数，则：
f(n-1, m-1) = 1
f(i, j) = f(i+1, j) + f(i, j+1), if a[i][j]==1
f(i, j) = 0, if a[i][j]==0
f(0, 0)就是所求答案
如果格子不少，障碍不多，那么可以用包含与排除解决。 | i**********e
发帖数: 1145 | 28 这个解法不对，有 bug.
test case:
{22,11,33,33,44,22,11}
t = 22,
output=
{11 33 33 44 44 22 22}
expected=
{11 33 33 44 11 22 22}
第一题的解：
void shiftArrayEqualsTBack(int num[], int n, int t) {
int total = 0;
for (int i = 0; i < n; i++) {
if (num[i] == t)
total++;
else
num[i-total] = num[i];
}
for (int i = n-total; i < n; i++) {
num[i] = t;
}
}
第二题的解：
const int X_MAX = 4;
const int Y_MAX = 4;
bool validLocation(int x, int y) {
if (x <= -1 || x >= X_MAX || y <= -1 || y >= Y_MAX) return false;
return true;
}
bool canReach(int map[][Y_MAX], int x, int y, bool visited[][Y_MAX]) {
if (!validLocation(x, y)) return false;
if (map[x][y]) return false;
if (x == X_MAX-1 && y == Y_MAX-1) return true;
if (visited[x][y]) return false;
visited[x][y] = true;
return canReach(map, x, y-1, visited) ||
canReach(map, x+1, y, visited) ||
canReach(map, x, y+1, visited) ||
canReach(map, x-1, y, visited);
}
int main() {
int map[X_MAX][Y_MAX] = {
{0,0,1,0},
{1,0,1,0},
{0,1,0,1},
{0,1,0,0}
};
bool visited[X_MAX][Y_MAX] = {false};
cout << canReach(map, 0, 0, visited);
return 0;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 e**********6 的大作中提到】
: void mv_t_to_end(int *a, int size, int t){
: int i=0,j=0,k=size;
: while(j: if(a[j]==t){
: j++;
: k--;
: }
: else
: a[i++]=a[j++];
: }
|
|
