图论
图论
岛屿数量
力扣题目连接：岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出：1
示例 2：
输入：grid = [
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出：3//深度优先
class Solution {
int[] dr = new int[]{0, -1, 1, 0};
int[] dc = new int[]{-1, 0, 0, 1};
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0){
return 0;
}
int R = grid.length;
int C = grid[0].length;
int ans = 0;
for(int r = 0; r < R; r++){
for(int c = 0; c < C; c++){
if(grid[r][c] == '1'){
ans++;
dfs(grid, r, c);
grid[r][c] = '0';
}
}
}
return ans;
}
public void dfs(char[][] grid, int row, int col){
int R = grid.length;
int C = grid[0].length;
if(row < 0 || row >= R || col < 0 || col >= C || grid[row][col] == '0'){
return;
}
for(int i = 0; i < 4; i++){
dfs(grid, row + dr[i], col + dc[i]);
grid[row][col] = '0';
}
}
}
//深度优先一般会使用递归解决，可以往这方面思考边界条件等//广度优先搜索
class Solution {
int[] dr = new int[]{0, -1, 0, 1};
int[] dc = new int[]{-1, 0, 1, 0};
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0){
return 0;
}
int R = grid.length;
int C = grid[0].length;
int ans = 0;
for(int r = 0; r < R; r++){
for(int c = 0; c < C; c++){
if(grid[r][c] == '1'){
Queue<Integer> deque = new ArrayDeque<>();
grid[r][c] = '0';
deque.add(r * C + c);
ans++;
while(!deque.isEmpty()){
int code = deque.remove();
int row = code / C;
int col = code % C;
if(row - 1 >= 0 && grid[row - 1][col] == '1'){
deque.add((row - 1) * C + col);
grid[row - 1][col] = '0';
}
if(row + 1 < R && grid[row + 1][col] == '1'){
deque.add((row + 1) * C + col);
grid[row + 1][col] = '0';
}
if(col - 1 >= 0 && grid[row][col - 1] == '1'){
deque.add(row * C + col - 1);
grid[row][col - 1] = '0';
}
if(col + 1 < C && grid[row][col + 1] == '1'){
deque.add(row * C + col + 1);
grid[row][col + 1] = '0';
}
}
}
}
}
return ans;
}
}
// 广度优先搜索一般用队列来实现腐烂的橘子
力扣题目链接：腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。//广度优先搜索，在上面加上深度属性
class Solution {
int[] dr = new int[]{-1 , 0, 1, 0};
int[] dc = new int[]{0 , -1, 0, 1};
public int orangesRotting(int[][] grid) {
int R = grid.length;
int C = grid[0].length;
Queue<Integer> deque = new ArrayDeque<>();
Map<Integer, Integer> depth = new HashMap<>();
int ans = 0;
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
if(grid[i][j] == 2){
int code = i * C + j;
deque.add(code);
depth.put(code, 0);
}
}
}
while(!deque.isEmpty()){
int code = deque.remove();
int r = code / C;
int c = code % C;
for(int i = 0; i < 4; i++){
int nr = r + dr[i];
int nc = c + dc[i];
if(nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1){
grid[nr][nc] = 2;
int ncode = nr * C + nc;
deque.add(ncode);
depth.put(ncode, depth.get(code) + 1);
ans = depth.get(ncode);
}
}
}
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
if(grid[i][j] == 1){
return -1;
}
}
}
return ans;
}
}课程表
力扣题目连接：课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
分析：这就是一个拓扑排序的典型题目，分为两种方法，广度优先和深度优先。
- 深度优先：我们将各个节点以及他的下一个节点们记录下来，每个节点记录状态（0：未搜索，1：搜索中，2：已完成），无环时从随机一个节点出发（可以按节点存储顺序），如果这个节点没有被搜索过，则深度递归该节点的下一个节点们，递归过程中如果又出现一个搜索中的节点，说明存在环，结束后要回溯将该节点的状态标记为2，同时将该节点放到栈的顶部（如果要返回最终拓扑结构的话，要使用一个栈来记录）。
//要返回拓扑结构
class Solution {
List<List<Integer>> edges;
//0:not 1:doing 2:finished
int[] visited;
// as stack
int[] result;
//circle or not?
boolean valid;
//stack`s index
int index;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
visited = new int[numCourses];
result = new int[numCourses];
index = numCourses - 1;
valid = true;
for(int i = 0; i < numCourses; i++){
edges.add(new ArrayList<Integer>());
}
for(int[] prerequisite : prerequisites){
edges.get(prerequisite[1]).add(prerequisite[0]);
}
for(int i = 0; i < numCourses && valid; i++){
if(visited[i] == 0){
dfs(i);
}
}
if(!valid){
return new int[0];
}
return result;
}
public void dfs(int u){
visited[u] = 1;
for(int v : edges.get(u)){
if(visited[v] == 0){
dfs(v);
if(!valid){
return;
}
}
else if(visited[v] == 1){
valid = false;
return;
}
}
visited[u] = 2;
result[index--] = u;
}
}//不返回结构，只验证是否有效
class Solution {
List<List<Integer>> edges;
int[] visited;
boolean valid;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
visited = new int[numCourses];
valid = true;
for(int i = 0; i < numCourses; i++){
edges.add(new ArrayList<Integer>());
}
for(int[] prerequisite : prerequisites){
edges.get(prerequisite[1]).add(prerequisite[0]);
}
for(int i = 0; i < numCourses && valid; i++){
if(visited[i] == 0){
dfs(i);
}
}
return valid;
}
public void dfs(int u){
visited[u] = 1;
for(int v : edges.get(u)){
if(visited[v] == 0){
dfs(v);
if(!valid){
return;
}
}
else if(visited[v] == 1){
valid = false;
}
}
visited[u] = 2;
}
}- 广度优先：不同于深度优先递归到最后的节点，广度优先会先将前置的节点（入度已经为0）放到队列中，并根据队列中的节点依次遍历他的下一个节点们，并让他们的入度减一，每次都取出队列的第一个节点，直到队列为空。最后判断结果的数量或者索引的值是否与课程数相等。
class Solution {
List<List<Integer>> edges;
int[] indeg;
int[] result;
int index;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
indeg = new int[numCourses];
result = new int[numCourses];
index = 0;
for(int i = 0; i < numCourses; i++){
edges.add(new ArrayList<Integer>());
}
for(int[] prerequisite : prerequisites){
edges.get(prerequisite[1]).add(prerequisite[0]);
indeg[prerequisite[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(indeg[i] == 0){
queue.add(i);
}
}
while(!queue.isEmpty()){
int u = queue.remove();
result[index++] = u;
for(int v : edges.get(u)){
indeg[v]--;
if(indeg[v] == 0){
queue.add(v);
}
}
}
if(index != numCourses){
return new int[0];
}
return result;
}
}前缀树Trie
力扣题目连接：前缀树
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
分析：这个题乍一看会无从下手，不知道题目要求我们实现什么，其实是将每个Trie都看作一个节点，内部使用children来存储下一个Trie节点，因为题目表明只有小写字母，所以children可以使用26长度的数组表示，若有子节点就在相关位置赋值。除此之外，还需要判断该节点是否为一个前缀结尾，因此Trie节点还需要isEnd属性来判别，当然这只是个判断标志，他仍然可以有children子节点。
最近有在学ES，可以见得ES中的term index使用的就是前缀树结构，加快检索效率。
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for(int i = 0; i < word.length(); i++){
char ch = word.charAt(i);
int index = ch - 'a';
if(node.children[index] == null){
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
return searchPre(word) != null && searchPre(word).isEnd;
}
public boolean startsWith(String prefix) {
return searchPre(prefix) != null;
}
private Trie searchPre(String prefix){
Trie node = this;
for(int i = 0; i < prefix.length(); i++){
char ch = prefix.charAt(i);
int index = ch - 'a';
if(node.children[index] == null){
return null;
}
node = node.children[index];
}
return node;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/