leetcode-200-206

leetcode200题206题:

leetcode200题(岛屿的数量):

给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例:

示例

解答:

思路:该题可以采用深度优先遍历进行解决;遍历二维数组中的每一个值,当它是’1’的时候,对该位置进行深度优先遍历,将与其连接构成岛屿的所有’1’都置为’0’,那么遍历原本是’1’的位置的元素时,由于其已经是’0’,就不会多计算岛屿的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var numIslands = function(grid) {
var count = 0;
for(var i=0;i<grid.length;i++){
for(var j=0;j<grid[0].length;j++){
if(grid[i][j]=='1'){
count++;
dfs(grid,i,j);
}
}
}
return count;
};
function dfs(grid,i,j){
var rowNum = grid.length;
var columnNum = grid[0].length;
grid[i][j] = '0';
if(i-1>=0&&grid[i-1][j]=='1'){
dfs(grid,i-1,j);
}
if(j+1<columnNum&&grid[i][j+1]=='1'){
dfs(grid,i,j+1);
}
if(i+1<rowNum&&grid[i+1][j]=='1'){
dfs(grid,i+1,j);
}
if(j-1>=0&&grid[i][j-1]=='1'){
dfs(grid,i,j-1);
}
}

leetcode206题(反转链表):

反转一个单链表。

示例:

输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

解答:
1
2
3
4
5
6
7
8
9
10
11
var reverseList = function(head) {
var pre = null;
var node = head;
while(node!=null){
var next = node.next;
node.next = pre;
pre = node;
node = next;
}
return pre;
};
分享到