【岛屿数量】
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
思路：
很经典也很基础的图搜题，bfs或者dfs都行，这题先用dfs写一下。
每次开启函数（而不是被递归调用），会将当前起点能接触到的所有陆地都访问一次再退出，记录函数开启的次数即可。
对每个格子，我们向上下左右四个方向拓展，对其中位置合法的、是陆地的、还没被访问过的格子进行递归调用，直到所有能访问的格子都访问完毕。
代码其实跟树的dfs也大同小异，区别只在出口的判断条件，以及可能递归的方向从两颗子树变成了四个方向（网格的情况，普通图的话就是变成所有neighbors）。
class Solution {
public:
//合法性判断
bool inArea(vector<vector<char>>& grid, int r, int c) {
return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
}
// dfs
void dfs(vector<vector<char>>& grid, int r, int c) {
//不合法
if (!inArea(grid, r, c))
return;
//来过了
if (grid[r][c] != '1')
return;
//标记并扩展
grid[r][c] = '2';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
int numIslands(vector<vector<char>>& grid) {
int ans = 0;
for (int r = 0; r < grid.size(); r++) {
for (int c = 0; c < grid[0].size(); c++) {
if (grid[r][c] == '1') {
dfs(grid, r, c);
ans++;
}
}
}
return ans;
}
};【腐烂的橘子】
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
思路：
看到最短时间，想必也知道这题很可能是要选bfs了。
理论上来说应该是要重新开辟空间来记录橘子的腐烂时间的，但我发现这题把原数组处理一下就可以直接使用而且不用担心信息丢失的问题。
剩下思路直接看注释，这题的注释我写得可认真啦。
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
//建立记录腐烂时间的数组,或改造原数组
// vector<vector<int> > visited(m, vector<int>(n, -1));
//顺便把初始腐烂的橘子入队
queue<pair<int, int>> q;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
grid[i][j] -= 2;
if (grid[i][j] == 0)
q.push(make_pair(i, j));
}
}
//取一个烂橘子，把四周还新鲜的橘子污染，记录污染时间，并把新的烂橘子入队，直到没有待处理的烂橘子
int curTime = 0, r = 0, c = 0;
int rMax = grid.size(), cMax = grid[0].size();
while (!q.empty()) {
//取
auto cur = q.front();
q.pop();
r = cur.first;
c = cur.second;
curTime = grid[r][c];
//污染
if (0 <= r - 1 && grid[r - 1][c] == -1) {
q.push(make_pair(r - 1, c));
grid[r - 1][c] = curTime + 1;
}
if (r + 1 < rMax && grid[r + 1][c] == -1) {
q.push(make_pair(r + 1, c));
grid[r + 1][c] = curTime + 1;
}
if (0 <= c - 1 && grid[r][c - 1] == -1) {
q.push(make_pair(r, c - 1));
grid[r][c - 1] = curTime + 1;
}
if (c + 1 < cMax && grid[r][c + 1] == -1) {
q.push(make_pair(r, c + 1));
grid[r][c + 1] = curTime + 1;
}
}
//检查有无新鲜橘子剩下,顺便找最大时间
int maxTime = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == -1)
return -1;
maxTime = max(maxTime, grid[i][j]);
}
}
return maxTime;
}
};【课程表】
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
思路：
从这题开始离开了美好的网格，变成了普通的图，好在这是一个超经典拓扑序列题，我们捋一下拓扑序列的思路就好了。
- 建立入度表，出边表，存储当前可上课程的队列，已上课的数量；
- 入度为零的是当前可以上的课，把它入队；
- 每次从队列中取一节可以上的课，把它上了，已上课数量++；
- 把这门课出边表里的邻居节点的入度都减一，如果减到零那么该邻居也可以上了，把它入队；
- 当队伍空了，说明当前没有可以上的课了，检查已上课数量和应上课数量，就可以知道答案。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//建立入度表
vector<int> inDegree(numCourses, 0);
//建立出边表
unordered_map<int, vector<int>> outTable;
//记录数据
for (int i = 0; i < prerequisites.size(); i++) {
inDegree[prerequisites[i][0]]++;
outTable[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
//建立可上课队列
queue<int> q;
//把当前能上的课入队
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0)
q.push(i);
}
//计数
int cnt = 0;
//队列不空（还有课能上）时循环
while (!q.empty()) {
//取出一门，上，计数，出边表里的课全都减入度，减到0的入队
int cur = q.front();
q.pop();
cnt++;
for (int i = 0; i < outTable[cur].size(); i++) {
if (--inDegree[outTable[cur][i]] == 0)
q.push(outTable[cur][i]);
}
}
//对比计数，返回结果
return cnt == numCourses;
}
};【前缀树】
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
思路：
数据结构类的题好像没什么思路可言，倒是对熟练c++面向对象思想挺有帮助的。本题精髓在于26格的next数组，直接看代码吧。
class Trie {
private:
bool isEnd;
Trie* next[26];
public:
Trie() {
isEnd = false;
for (int i = 0; i < 26; i++) {
next[i] = nullptr;
}
}
void insert(string word) {
Trie* cur = this;
for (char c : word) {
if (cur->next[c - 'a'] == nullptr) {
cur->next[c - 'a'] = new Trie();
}
cur = cur->next[c - 'a'];
}
cur->isEnd = true;
}
bool search(string word) {
Trie* cur = this;
for (char c : word) {
if (cur->next[c - 'a'] == nullptr)
return false;
cur = cur->next[c - 'a'];
}
return cur->isEnd;
}
bool startsWith(string prefix) {
Trie* cur = this;
for (char c : prefix) {
if (cur->next[c - 'a'] == nullptr)
return false;
cur = cur->next[c - 'a'];
}
return true;
}
};
