l*****a
发帖数: 14598 | 1 前一阵子有人发的google电面题。我想了想，解法如下，请批评指正。
简化为判断每一行/一列/3*3矩阵是否是1-9的一个permutation
for(i=0;i<9;i++)
{
if((a[i]>9)||(a[i]<0)) { return false;}
}
for(i=0;i<9;i++)
{
a[a[i]-1]+=9;
}
for(i=0;i<9;i++)
{
if((a[i]>2*9+1)) //for location i+1,add 9 at least twice so that there
is duplicate elements i+1
{ return false;}
}
return true.
time complexity O(n2) |
r****o
发帖数: 1950 | 2
没看懂。假如i=0时，a[0]=2, 则a[1]+=9,那i=1时不就返回false了?
【在 l*****a 的大作中提到】
: 前一阵子有人发的google电面题。我想了想，解法如下，请批评指正。
: 简化为判断每一行/一列/3*3矩阵是否是1-9的一个permutation
: for(i=0;i<9;i++)
: {
: if((a[i]>9)||(a[i]<0)) { return false;}
: }
: for(i=0;i<9;i++)
: {
: a[a[i]-1]+=9;
: }
|
s*********t
发帖数: 1663 | 3 今天才知道啥是sudoku
【在 l*****a 的大作中提到】
: 前一阵子有人发的google电面题。我想了想，解法如下，请批评指正。
: 简化为判断每一行/一列/3*3矩阵是否是1-9的一个permutation
: for(i=0;i<9;i++)
: {
: if((a[i]>9)||(a[i]<0)) { return false;}
: }
: for(i=0;i<9;i++)
: {
: a[a[i]-1]+=9;
: }
|
l*****a
发帖数: 14598 | 4 谢谢提醒
看来还得加一趟扫描
【在 r****o 的大作中提到】
:
: 没看懂。假如i=0时，a[0]=2, 则a[1]+=9,那i=1时不就返回false了?
|
d**e
发帖数: 6098 | 5 很久以前我也不知道，突然有天有个朋友问我喜欢玩吗，他天天上厕所就拿着来玩 -_-!
【在 s*********t 的大作中提到】
: 今天才知道啥是sudoku
|
s*********t
发帖数: 1663 | 6 看介绍上说，不需要猜就可以推出来，还是唯一的，这难道不是很弱智么
_-!
【在 d**e 的大作中提到】
: 很久以前我也不知道，突然有天有个朋友问我喜欢玩吗，他天天上厕所就拿着来玩 -_-!
|
s********a
发帖数: 1447 | 7 能给一下是什么题目吗？
【在 l*****a 的大作中提到】
: 前一阵子有人发的google电面题。我想了想，解法如下，请批评指正。
: 简化为判断每一行/一列/3*3矩阵是否是1-9的一个permutation
: for(i=0;i<9;i++)
: {
: if((a[i]>9)||(a[i]<0)) { return false;}
: }
: for(i=0;i<9;i++)
: {
: a[a[i]-1]+=9;
: }
|
d**e
发帖数: 6098 | 8 其实用来打发时间也不错，哈哈
【在 s*********t 的大作中提到】
: 看介绍上说，不需要猜就可以推出来，还是唯一的，这难道不是很弱智么
:
: _-!
|
s********y
发帖数: 3811 | 9 后来得了智窗...
_-!
【在 d**e 的大作中提到】
: 很久以前我也不知道，突然有天有个朋友问我喜欢玩吗，他天天上厕所就拿着来玩 -_-!
|
l*****a
发帖数: 14598 | 10 you replied that question before
forgot it?
发信人: sunnylibra (雨过天晴), 信区: JobHunting
标 题: Re: [攒rp] Facebook & Google onsite 面筋
发信站: BBS 未名空间站 (Fri Apr 16 14:37:24 2010, 美东)
Thanks for sharing!
问一下 在你的店面面经里面
google的第一题
“1.1. 输入: 一个数独的解
输出: 判断是否是成功的
”
这个输入的是什么啊？没看明白:(
【在 s********a 的大作中提到】
: 能给一下是什么题目吗？
|
S******a
发帖数: 862 | 11 这道题我觉得就是看看编程基本功，把程序写对就行。
我onsite还碰到过找出数组里最大的数，汗。。
具体来讲，思路就用bitmap
以下是以前的讨论：
======================================================
则：
======================================================
非常感谢你的回答！
我觉得用一个a[9]，然后扫描三次，每行，每列，每block。你的虽然扫描一次，但每
个元素要跟多个不同的a[9]比较，总的比较次数应该和我说的一样，但我说的用的a[9]
少一些。你觉得呢？我是不是哪里理解不对？
========================================================
======================================================== |
s********a
发帖数: 1447 | 12 。。。。。。
谢谢 大侠记性好~~ 呵呵
【在 l*****a 的大作中提到】
: you replied that question before
: forgot it?
: 发信人: sunnylibra (雨过天晴), 信区: JobHunting
: 标 题: Re: [攒rp] Facebook & Google onsite 面筋
: 发信站: BBS 未名空间站 (Fri Apr 16 14:37:24 2010, 美东)
: Thanks for sharing!
: 问一下 在你的店面面经里面
: google的第一题
: “1.1. 输入: 一个数独的解
: 输出: 判断是否是成功的
|
