大概是一个风高气爽的一天，我在实习公司莫得事干偷了本Python深度学习看的时候，旁边的程序猿小哥哥大概是看我太无聊？反正在微信里丢给我一个网站——Lintcode。
说实话我很喜欢编程，虽然对循环和函数间数据传递一直傻fufu的，但是出于对编程的喜爱，在高三的时候偷偷摸摸发愤图强自学了大一上班学期的C语言一半的内容……大概，还是挺不容易的？但是可能是跟acm无缘，也可能机遇不够，没有白胡子编程爷爷拉着我传道受业解惑，直到现在开始渐渐明白要学什么了，额，或者说是对自己想要提高编程能力有了更清晰的自主意识，才恍然发觉自己太菜了。（所以继续发愤图强叭23333）
跑题跑题，说回小哥哥给我发的这道题。（这题怎么排版都丑，将就着看吧）
433. 岛屿的个数
- 描述：
给一个01矩阵，求不同的岛屿的个数。0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。- 样例：
在矩阵
[[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]]
中有 3 个岛
然后我肝了很久……头发少了不少（大概因为周末出去剪了个头？）……
| 提交时间 | 我的代码 | 面试真题 | 运行时间 | 语言 |
|---|---|---|---|---|
| 37 分钟前 | Accepted | 岛屿的个数 | 50 ms | C++ |
| 40 分钟前 | Accepted | 岛屿的个数 | 151 ms | C++ |
| 42 分钟前 | Wrong Answer | 岛屿的个数 | 151 ms | C++ |
| 44 分钟前 | Wrong Answer | 岛屿的个数 | 151 ms | C++ |
| 1 小时前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 小时前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 小时前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 1 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
| 5 天前 | Wrong Answer | 岛屿的个数 | 50 ms | C++ |
| 5 天前 | Wrong Answer | 岛屿的个数 | 50 ms | C++ |
| 5 天前 | Wrong Answer | 岛屿的个数 | 50 ms | C++ |
| 5 天前 | Running Error | 岛屿的个数 | 151 ms | C++ |
第一天摸到这个题我很傻很天真地发现我不知道这个函数怎么传参的，瞅了半天的vector，那种仿佛唤醒了尘封的记忆的感觉23333，毕竟是半年前学的，学完就没怎么用的东西呢~然后会用了vector也不会做题，无奈去肝了几道入门级的题。（没错就是winng的一月题目2333）
做了几道题，感觉自己ok了，懂了这个成员函数怎么传参，我思量了一下这道题，感觉应该循环嵌套然后计数。
然后做出了5天前的3个Wrong Answer/捂脸
苦思冥想，明白了程序哪里有问题，然后换了递归的算法打算大侠重新来过。然后发现自己不会传参嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤（事实上最后我也没传参）。于是继续刷题深造，winng的一月题目就此新鲜出炉（当然当时并没整理）。
周末社会实践，碰到了竞赛大佬，讲之，大佬为我指点了一波迷津：“你这个应该用队列做啊~”，但是当时递归归得很开心的我并不理解大佬的深意，只是又觉得自己ok了，没曾想测试程序都运不行，更不必说上传测试了。
然后我认清自己传不好参的事实。当然了，主要是做了别的题发现递归的确跟大佬说的那样容易炸裂……于是一边再继续刷题深造，刷好了三道二月一周题目（请问你这个月咋分的/捂脸）一边开始着手摸索queue的算法。
然后做出了昨天的一连串Running Error，过去一周的平均提交次数3->7
当然了，昨天写好了所有的算法，只剩debug，直到今天1小时前我终于de完了，感动得无以复加，恨不能奔走相告，然额我要是真的去大街上奔走相告会被抓起来的，所以只能记录一下以抒发我的胸中郁结之气~~~
代码呢最后就是这样（把cout的测试数据删掉运行时间从151ms蹭地变成50ms）：
#include<queue>
class Solution {
public:
/**
* @param grid: a boolean 2D matrix
* @return: an integer
*/
int numIslands(vector<vector<bool>> &grid) {
// write your code here
if (grid.empty()){
return 0;
}
int num=0,now,x,y;
int m=grid.size();
int n=grid[0].size();
int a[m*n]={0};
queue<int> q;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(!a[i*n+j]&&grid[i][j]){
a[i*n+j]=1;
q.push(i*n+j);
num++;
while(!q.empty())
{
now=q.front();
x=now/n;
y=now%n;
if(x!=0&&!a[(x-1)*n+y]&&grid[x-1][y]){
a[(x-1)*n+y]=1;
q.push((x-1)*n+y);
}
if(x!=m-1&&!a[(x+1)*n+y]&&grid[x+1][y]){
a[(x+1)*n+y]=1;
q.push((x+1)*n+y);
}
if(y!=0&&!a[x*n+y-1]&&grid[x][y-1]){
a[x*n+y-1]=1;
q.push(x*n+y-1);
}
if(y!=n-1&&!a[x*n+y+1]&&grid[x][y+1]){
a[x*n+y+1]=1;
q.push(x*n+y+1);
}
q.pop();
}
}
}
}
return num;
}
};
- 一开始想用vector存走过的图，存一个二维数组，后来发现也不好调用数组的两个参数……后来又想用结构体还是咋着，最后我发现这还是一个数学问题……算就好了。
- 最大的bug是m和n弄反了，后来改了两遍
- 另外就是四个if之前不小心写成了if-elseif-elseif-elseif……
总之是写完了，我可以继续看Python的深度学习了QAQ
深度学习：谢谢你还记得我: (
我：qqqqqvq
网友评论