hot100之图论
<h3 id="岛屿数量200">岛屿数量(200)</h3><pre><code class="language-java">class Solution {
public int numIslands(char[][] grid) {
int res = 0;
int m = grid.length;
int n = grid.length;
for (int i = 0; i < m ; i++){
for (int j = 0; j < n; j++){
if (grid == '1'){
res+=1;
markLand(grid, i, j);
}
}
}
return res;
}
private void markLand(char[][] grid, int i, int j){
if (i < 0 || i > grid.length-1 || j < 0 || j > grid.length-1 || grid == '0'){
return ;
}
grid = '0';
markLand(grid, i+1, j);
markLand(grid, i-1, j);
markLand(grid, i, j+1);
markLand(grid, i, j-1);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>简单的四向寻找</p>
<h3 id="腐烂的橘子994">腐烂的橘子(994)</h3>
<pre><code class="language-java">class Solution {
private static final int[][] DIRECTIONS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public int orangesRotting(int[][] grid) {
int res = 0;
int fresh = 0;
int m = grid.length;
int n = grid.length;
Deque<int []> rotArray = new ArrayDeque<>();
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid == 1)fresh++;
else if (grid == 2)rotArray.addFirst(new int[] {i, j});
}
}
while (fresh > 0 && !rotArray.isEmpty()){
res+=1;
int len = rotArray.size();
for (int i = 0; i < len; i++){
int[] temp = rotArray.removeLast();
for (int[] dir : DIRECTIONS){
int row = temp + dir;
int col = temp + dir;
if (0 <= row && row < m && 0 <= col && col < n
&& grid == 1){
fresh--;
grid = 2;
rotArray.addFirst(new int[] {row, col});
}
}
}
}
return fresh>0 ? -1 : res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>相比于普通的四向寻找, 难点在于轮次, 可以类比于二叉树的层序遍历, 一层一层扩展</p>
<h3 id="课程表207">课程表(207)</h3>
<pre><code class="language-java">class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] line = new ArrayList;
Arrays.setAll(line, i -> new ArrayList<>());
for (int[] p : prerequisites){
line].add(p);
}
int[] colors = new int;
for (int i = 0; i < numCourses; i++){
if (colors == 0 && dfs(i, colors, line)) return false;
}
return true;
}
private boolean dfs(int i, int[] colors,List<Integer>[] line){
colors = 1;
for (int j : line){
if (colors == 1 || colors == 0 && dfs(j, colors, line)){
return true;
}
}
colors = 2;
return false;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>判断图中是否有环</p>
<p>利用三色标记法 {0, 1, 2} →{未达, 正在使用, 可达}</p>
<h3 id="实现tire208">实现Tire(208)</h3>
<p>代码太长了就不放了</p>
<pre><code class="language-java"> private static class Node {
Node[] son = new Node;
boolean end;
}
private final Node root;
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>insert() 部分 实际上是开辟道路<code>if (curr.son == null) curr.son = new Node();</code></p>
<p>search() 和 startsWith() 实际上都是一路沿son下移, 遇到没开辟完的路线 <code>return false</code></p>
<p>如果移动结束了, 如果当前节点的<code>end == true</code> 则为完整单词 , 否则为前缀</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18929456
頁:
[1]