深度搜索问题-LeetCode 200、130（DFS，Coredumped问题）
深度搜索问题-LeetCode 200、130（DFS，Coredumped问题）
深度优先遍历：LeetCode #200 130
1
编程题
Linux Coredump如何解决呢？
这个是某公司的面试题，但对于笔者来说，这是linux C++必须掌握的技能！不然真的小白了！ 假设下面的程序，很明显，这是一个错误的程序，不可以将一个字符串直接拷贝到空指针中！
#include<iostream>
#include<cstring>
using namespace std;
int do_print(){
printf("in print ...\n");
char* p = NULL;
const char* buffer = "hello";
memcpy(p, buffer, 5); // 这里有错误
return 0;
}
int main(){
int res = do_print();
return 0;
}我们先不管它，假装不知道，我是小白，哈哈，接着使用g++进行编译，编译指令为g++ -g coredump.cpp
teddyzhang@teddy:~/test$ g++ -g coredump.cpp
teddyzhang@teddy:~/test$太厉害了我，竟然没有错误，哥就是这么强！由于我没有限定输出文件名，默认为a.out，好了我现在要运行这个可执行文件了！运行指令为：./a.out
teddyzhang@teddy:~/test$ ./a.out
in print ...
Segmentation fault (core dumped)
teddyzhang@teddy:~/test$ 啊啊啊啊啊，出错了，段错误，还没有提示错在哪一行了，我懵逼了，我是谁，我在哪里！不要担心，可以解决的！！！
进入正题，coredump了如何进行调试，一般使用gdb与core文件进行搭配调试！什么是core文件？就是操作系统在程序异常时会生成一个文件快照，文件中有可回溯函数栈，记录程序生前都经过哪些函数栈！ 通过对core文件进行分析，可以帮助我们快速定位错误，对于内存泄漏，或者越界等非文本代码错误，有很大意义！
使用之前首先检查系统可否生成core文件，即ulimit -c， 如果是0，则不产生core文件，更改为ulimit -c1024 接着使用gdb进行调试，指令为：gdb a.out core，首先，使用bt指令查看可回溯函数栈，可以看到程序down掉之前进入过do_print()函数，在第一帧中，接着使用frame 1指令查看函数帧.
哈哈，找到了，第11行的memcpy(p, buffer, 5)错误了！emmm, 原来是空指针拷贝的问题！调试完成！
【LeetCode #200】岛屿问题
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入: 11110 11010 11000 00000 输出: 1
解题思路：
注意题目说的是岛屿，因此思路是，寻找grid中值为'1'的个数，当元素为'1'时，进入感染函数，将其周围为'1'的元素全部变成'0'，直到感染递归函数遇到'0'或者越界为止，结束递归！ 在主函数中用res进行标记个数，返回即可！
class Solution {
public:
void infect(vector<vector<char>>& grid, int i, int j){
if(i < 0 || i >= grid.size() ||
j < 0 || j >= grid[0].size() || grid[i][j] != '1')
return;
grid[i][j] = '0';
infect(grid, i+1, j);
infect(grid, i, j+1);
infect(grid, i-1, j);
infect(grid, i, j-1);
}
int numIslands(vector<vector<char>>& grid) {
int res= 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[0].size(); j++){
if(grid[i][j] == '0') continue;
res++;
infect(grid, i, j);
}
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-islands
【LeetCode #130】被包围的区域
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例: X X X X X O O X X X O X X O X X 运行你的函数后，矩阵变为： X X X X X X X X X X X X X O X X
解释: 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解题思路：
这个题目应该适用于"排除法"，由于题中被围绕的区间不会存在于边界上，并且边界的'O'不会被填充成'X'，换一个思路也就是说，上、下、左、右四个边界上的所有'O'的连通域都应该保留。其余的'O'都会变成'X'，注意使用引用传递，可以改变board数组。
class Solution {
public:
int row, col;
void dfs(vector<vector<char>>& board, int i, int j){
if(i < 0 || i >= row ||
j < 0 || j >= col || board[i][j] != 'O')
return;
board[i][j] = '-';
dfs(board, i-1, j);
dfs(board, i+1, j);
dfs(board, i, j-1);
dfs(board, i, j+1);
}
void solve(vector<vector<char>>& board) {
if(board.size() == 0)
return;
row = board.size();
col = board[0].size();
for(int i = 0; i < row; i++){
dfs(board, i, 0);
dfs(board, i, col-1);
}
for(int j = 0; j < col; j++){
dfs(board, 0, j);
dfs(board, row-1, j);
}
for(int i = 0;i < row; ++i){
for(int j = 0;j < col; ++j){
if(board[i][j] == 'O')
board[i][j] = 'X';
if(board[i][j] == '-')
board[i][j] = 'O';
}
}
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/surrounded-regions