d**********o
发帖数: 1321 | 1 一个单词引发的血案（2）
如果说，因为12、12这个周五upload到github上去的review docs上一个词特别刺眼，
那一定是批在review第二页纸下方的这个“practice”了。
记得那个周五中午，我见代课老师的办公室门是开着的，便敲门应允进去了。老师说他
正在改我的review。说到最后，他指给我看我review的最后几段的“practise”说，他
知道英国等一些国家名字也用“practise”，但在美国，作动词用时是practise, 但作
名词用的时候还是用“practice”，并把这名词规规矩矩、端端正正地写在了这页纸的
下方。我不以为意。
及至这天下午紧接着系里发出的邮件，我也以为天上掉馅饼，系里有多的奖学金的话，
不是说我春天也可以拿到TA了吗？LinkedIn上当天也刮这种风，虽然自己当时并不没有
回，但晚上临睡前还是发信回复给系里，问一下到底是什么情况。但系里小秘第二天中
午用她的周末时间给我的回复是，那是发给全系的邮件，即使系里有奖学金，我是没有
资格的，因为先前导师与我已经讲好了春天我只能注册一个学分。我友好地回复系里小
秘的邮件。不给奖学金不是... 阅读全帖 |
|
d*******l
发帖数: 338 | 2 我觉得那个解答非常有道理啊。每次找当前禁止注水的格子中高度最小的进行
floodfill，更新“禁止注水”格子的集合，直到所有格子都禁止注水。“禁止注水”
格子相当于桶的边界，从桶的边界的最低点开始注水，逐步缩小剩下的范围，想法很巧
妙。
你的例子举的不错，但上面的解法应该能正常工作，因为假设每次取的格子高度是h，
高度小于等于h的且能通过floodfill达到的范围内，周围的一圈格子都会被放进“禁止
注水”集合。用你的例子来说明，开始的时候禁止注水的是最外一圈，然后假设选出的
高度最小的用“*”表示：
1. 没有新的“禁止注水”格子被加入
. . . . .
. 3 1 2 .
. 3 0 2 .
. . . . * |
|
d***n
发帖数: 65 | 3 第八题， 贴个时间O(n)，空间O(1)的，试了前面提到的所有test case。貌似全都正确
。整个数组只需扫描一遍。
int floodFill(int B[], int n)
{
int w = 0;
int i = 0, j = n;
int maxL = 0, maxR = 0;
while(i
{
while(B[i]<=max(maxL, maxR) && i
{
if(B[i]>maxL)
maxL = B[i];
else
w +=maxL - B[i];
i++;
}
if(i==j) break;
maxL = B[i];//found new high
while(B[--j]
{
if(B[j]>maxR)
... 阅读全帖 |
|
d***n
发帖数: 65 | 4 第八题， 贴个时间O(n)，空间O(1)的，试了前面提到的所有test case。貌似全都正确
。整个数组只需扫描一遍。
int floodFill(int B[], int n)
{
int w = 0;
int i = 0, j = n;
int maxL = 0, maxR = 0;
while(i
{
while(B[i]<=max(maxL, maxR) && i
{
if(B[i]>maxL)
maxL = B[i];
else
w +=maxL - B[i];
i++;
}
if(i==j) break;
maxL = B[i];//found new high
while(B[--j]
{
if(B[j]>maxR)
... 阅读全帖 |
|
|
S******t
发帖数: 151 | 6 直接对边界floodfill一下，注意控制不要走到水里去(cells with 0 heights)，然后
对每个连通分量求值最小的元素就可以了。 |
|
|
S******t
发帖数: 151 | 8 就直接四连通的floodfill啊...就是个DFS嘛
大概类似于
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
bool valid(int r,int c) {
return 0<=r&&r
}
void dfs(int x, int y)
visited[x][y] = true;
for(int i=0;i<4;i++) {
int nx=x+dx[i],ny=y+dy[i];
if(valid(nx,ny)&&!visited[nx][ny]&&d[nx][ny]!=0)
dfs(nx,ny);
}
} |
|
|
S******t
发帖数: 151 | 10 floodfill是找连通分量的
找完之后我们就知道池子的形状以及最低点的高度了 |
|
i******r
发帖数: 793 | 11 在这个matrix里面，有一些格子是禁止积水的
每次从禁止积水的格子里面取最低的一个做floodfill，同时扩展一些格子作为禁止积
水的格子
第一次从边缘上最低的格子开始
用一个binary heap来存放所有禁止积水的格子，复杂度mnlog(mn) |
|
|
d**********o
发帖数: 1321 | 13 探访表哥（三）
从南侧侧腰走廊左转，就转到了东侧长走廊，这个长长的走廊里，灯光明显明亮起来，
而这个距离自己最近的第一个门，就是表哥的新办公室了。我轻手轻脚、蹑手蹑脚地挪
到表哥办公室前，见两年前来找表哥时我在表哥的办公室门上画过的小太阳还在，小太
阳里面长着像向日葵一样的一个娃娃笑脸，这个向日葵娃娃笑脸（此刻敲下这段，我怎
么会忽然想起高一报名前，初到大姐大哥家时，几姊妹里大哥买给我一个人吃的娃娃脸
？），后来在我的android app programming中bitmap level的floodfill功能案例里也
如此设计和画过，图片还在github上放着呢。两年前我用表哥门上的笔和白板画这个向
日葵娃娃笑脸的时候表哥就在屋子里坐着呢，他当然知道这是我画的。回想起这些，我
心中不免多了几分感动和满足。
我悄悄地拧了拧门把手，门是锁着的，那我就先静静地在门外呆会儿吧。楼里的暖气很
足，我把外套羽绒服脱掉，折叠挂在左侧手臂上，再搭右手、双手搂抱在胸前，就像
2010年12月表哥陪我去他们学校图书馆，我在那里去用洗手间出来时看见的，表哥抱着
我的外套、双手搂抱在胸前等待我的样子。。。... 阅读全帖 |
|
