127. 拓扑排序
https://www.lintcode.com/zh-cn/problem/topological-sorting/#
这道题分为三步。第一步遍历所有图上的点，生成一个点对应入度的MAP。第二步找到所有入度为0的点，存进队列。第三步，依次把队列里的值放入结果集，随后更新MAP的入度。把相应的邻居入度-1。
public class Solution {
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> res = new ArrayList<>();
Map<DirectedGraphNode,Integer> indegree = new HashMap<>();
for(DirectedGraphNode node : graph) {
for(DirectedGraphNode nei : node.neighbors){
indegree.put(nei,indegree.getOrDefault(nei,0)+1);
}
}
Queue<DirectedGraphNode> q = new LinkedList<>();
for(DirectedGraphNode node : graph){
if(indegree.containsKey(node)) continue;
q.offer(node);
}
while(!q.isEmpty()){
DirectedGraphNode cur = q.poll();
res.add(cur);
for(DirectedGraphNode nei : cur.neighbors){
indegree.put(nei,indegree.get(nei)-1);
if(indegree.get(nei) == 0){
q.offer(nei);
}
}
}
return res;
}
}
- 克隆图
https://www.lintcode.com/zh-cn/problem/clone-graph/#
这道题分为三步。
第一步，用BFS找到图上所有的点（这里是图的遍历BFS需要用一个HASHSET来记录已经遍历过的点）
第二步，根据所有的点，生成一个旧的点到新的点 映射的MAP
第三步，根据这个MAP，对所有新的点 构造边。
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
List<UndirectedGraphNode> res = bfs(node);
Map<UndirectedGraphNode,UndirectedGraphNode> old2New = new HashMap<>();
for(UndirectedGraphNode cur : res) {
UndirectedGraphNode newN = new UndirectedGraphNode(cur.label);
old2New.put(cur,newN);
}
for(UndirectedGraphNode cur : old2New.keySet()) {
UndirectedGraphNode newN = old2New.get(cur);
for(UndirectedGraphNode nei : cur.neighbors){
newN.neighbors.add(old2New.get(nei));
}
}
return old2New.get(node);
}
private List<UndirectedGraphNode> bfs(UndirectedGraphNode node){
Queue<UndirectedGraphNode> q = new LinkedList<>();
HashSet<UndirectedGraphNode> seen = new HashSet<>();
q.offer(node);
seen.add(node);
while(!q.isEmpty()){
UndirectedGraphNode cur = q.poll();
for(UndirectedGraphNode nei : cur.neighbors){
if(seen.contains(nei)) continue;
q.offer(nei);
seen.add(nei);
}
}
return new ArrayList<UndirectedGraphNode>(seen);
}
第二种，递归写法
Map<Integer,UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
if(map.containsKey(node.label)) return map.get(node.label);
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node.label,copy);
for(UndirectedGraphNode nei : node.neighbors){
copy.neighbors.add(cloneGraph(nei));
}
return copy;
}
615. 课程表
https://www.lintcode.com/zh-cn/problem/course-schedule/
有向图判定是否有环，用拓扑排序。
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer,Integer> ind = new HashMap<>();
int all = 0;
Map<Integer,Set<Integer>> chds = new HashMap<>();
Set<String> seen = new HashSet<>();
for(int[] pre : prerequisites) {
if(seen.contains(pre[0]+","+pre[1])) continue;
seen.add(pre[0]+","+pre[1]);
ind.put(pre[1],ind.getOrDefault(pre[1],0)+1);
all++;
chds.compute(pre[0],(a,b)->{
if(b == null){
Set<Integer> s = new HashSet<>();
s.add(pre[1]);
return s;
}
b.add(pre[1]);
return b;
});
}
Queue<Integer> q = new LinkedList<>();
for(int i=0; i<numCourses; i++){
if(ind.containsKey(i)) continue;
q.offer(i);
}
while(!q.isEmpty()){
int node = q.poll();
if(!chds.containsKey(node)) continue;
for(int chd : chds.get(node)){
ind.put(chd,ind.get(chd)-1);
all--;
if(ind.get(chd) == 0)
q.offer(chd);
}
}
return all==0;
}
605. 序列重构
https://www.lintcode.com/zh-cn/problem/sequence-reconstruction/
拓扑排序的应用，每次只能有一个入度为0的点，这样能构成唯一的拓扑排序，最后再用拓扑排序的序列和ORIGIN序列做匹配。
EDGE CASE：邻接点可能是NULL，还有SEQ 序列可能是空
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
Map<Integer,Integer> in = new HashMap<>();
Set<String> s = new HashSet<>();
Set<Integer> all = new HashSet<>();
Map<Integer,Set<Integer>> neis = new HashMap<>();
for(int[] seq : seqs){
if(seq.length == 0) continue;
all.add(seq[0]);
for(int i=0;i<seq.length-1;i++){
if(s.contains(seq[i]+","+seq[i+1])) continue;
all.add(seq[i+1]);
s.add(seq[i]+","+seq[i+1]);
in.put(seq[i+1],in.getOrDefault(seq[i+1],0)+1);
if(neis.containsKey(seq[i])){
neis.get(seq[i]).add(seq[i+1]);
}else{
Set<Integer> cur = new HashSet<>();
cur.add(seq[i+1]);
neis.put(seq[i],cur);
}
}
}
//get all 0 degree
Queue<Integer> q = new LinkedList<>();
for(int node : all){
if(!in.containsKey(node)){
q.offer(node);
}
}
List<Integer> top = new ArrayList<>();
while(!q.isEmpty()){
int qsize = q.size();
// System.out.println(qsize);
if(qsize!=1) return false;
int cur = q.poll();
top.add(cur);
if(neis.get(cur) == null){
continue;
}
for(int nei : neis.get(cur)){
in.put(nei,in.get(nei)-1);
if(in.get(nei) == 0){
q.offer(nei);
}
}
}
if(top.size() != org.length){
return false;
}
for(int i=0;i<org.length;i++){
if(top.get(i)!=org[i]){
return false;
}
}
return true;
}
433. 岛屿的个数
https://www.lintcode.com/zh-cn/problem/number-of-islands/
遍历每一个点，一旦发现岛屿，用FLOODFILL去抹除。这个题是BFS的入门题，自己看代码应该可以理解。
public int numIslands(boolean[][] grid) {
// write your code here
int count = 0;
int h = grid.length;
if(h == 0) return 0;
int l = grid[0].length;
for(int i=0; i < h; i++) {
for(int j=0; j < l; j++) {
if(grid[i][j]){
dfs(grid,i,j);
count++;
}
}
}
return count;
}
private void dfs(boolean[][] grid, int y,int x) {
int h = grid.length;
int l = grid[0].length;
grid[y][x] = false;
if(y>0 && grid[y-1][x]) dfs(grid,y-1,x);
if(x>0 && grid[y][x-1]) dfs(grid,y,x-1);
if(y<h-1 && grid[y+1][x]) dfs(grid,y+1,x);
if(x<l-1 && grid[y][x+1]) dfs(grid,y,x+1);
}
542. 01 Matrix
https://leetcode.com/problems/01-matrix/description/
首先把0的点加入到队列。其余的点，全部设为最大值。从这些点开始进行BFS。一旦更新了一个点，就把这个更新的点也放进队列。再一次更新。
public int[][] updateMatrix(int[][] matrix) {
int h = matrix.length;
int l = matrix[0].length;
Queue<int[]> q = new LinkedList<>();
for(int i = 0;i<h;i++){
for(int j=0;j<l;j++){
if(matrix[i][j] == 1){
matrix[i][j] = Integer.MAX_VALUE-1;
}else
q.offer(new int[]{i,j});
}
}
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while(!q.isEmpty()){
int[] cur = q.poll();
for(int[] dir : dirs){
int ny = cur[0]+dir[0];
int nx = cur[1]+dir[1];
if(ny<0 || nx<0 || ny==h || nx==l ) continue;
if(matrix[ny][nx]>matrix[cur[0]][cur[1]]+1){
matrix[ny][nx]=matrix[cur[0]][cur[1]]+1;
q.offer(new int[]{ny,nx});
}
}
}
return matrix;
}
解法2，DP
public int[][] updateMatrix(int[][] matrix) {
int h = matrix.length;
int l = matrix[0].length;
for(int i = 0;i<h;i++){
for(int j=0;j<l;j++){
if(matrix[i][j] == 1){
matrix[i][j] = Math.min(i==0?10000:matrix[i-1][j],j==0?10000:matrix[i][j-1])+1;
}
}
}
for(int i = h-1;i>=0;i--){
for(int j=l-1;j>=0;j--){
if(matrix[i][j] == 0) continue;
matrix[i][j] = Math.min(matrix[i][j],Math.min(i==h-1?10000:matrix[i+1][j],j==l-1?10000:matrix[i][j+1])+1);
}
}
return matrix;
}
310. Minimum Height Trees
https://leetcode.com/problems/minimum-height-trees/description/
这道题的思路就是先找到叶子节点，然后抹去，然后再找剩余节点的叶子节点。不断重复。最后只剩下一个或2个就是解。
所以第一步要先根据题目的输入，把GRAPH 构建出来。随后找到所有邻居节点数量为1 的节点。进行更新。然后不断循环。
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> res = new ArrayList<>();
if(n == 1){
res.add(0);
return res;
}
List<Set<Integer>> gra = new ArrayList<>();
for(int i=0;i<n;i++){
gra.add(new HashSet<>());
}
for(int[] edge : edges){
gra.get(edge[0]).add(edge[1]);
gra.get(edge[1]).add(edge[0]);
}
for(int i=0;i<n;i++){
if(gra.get(i).size() == 1) res.add(i);
}
while(n > 2){
n -= res.size();
List<Integer> newRes = new ArrayList<>();
for(int key : res){
int tar = gra.get(key).iterator().next();
gra.get(tar).remove(key);
if(gra.get(tar).size()==1){
newRes.add(tar);
}
}
res = newRes;
}
return res;
}
787. Cheapest Flights Within K Stops
https://leetcode.com/problems/cheapest-flights-within-k-stops/description/
首先构造图。
随后开始从起点开始BFS，这里有个剪枝，一旦以走过的路线到了一个之前去过的站点，并且这个走过的路线的票价要贵，那么这个走法就可以抛弃。
K因为是可以停的次数。我用K++，是表示，可以飞几次。
可以停0次=飞1次。
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
if(src == dst) return 0;
K++;
List<Set<int[]>> gra = new ArrayList<>();
for (int i = 0; i < n; i++) {
gra.add(new HashSet<>());
}
for (int[] f : flights) {
gra.get(f[0]).add(new int[]{f[1],f[2]});
}
int res = Integer.MAX_VALUE;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{src,0});
Map<Integer,Integer> s = new HashMap<>();
s.put(src,0);
while(!q.isEmpty() && K>=0){
int qsize = q.size();
while(qsize > 0){
qsize--;
int[] cur = q.poll();
if(cur[0] == dst){
if(cur[1]<res) res = cur[1];
}
for(int[] nei : gra.get(cur[0])){
if(s.getOrDefault(nei[0],Integer.MAX_VALUE) < nei[1]+cur[1]) continue;
s.put(nei[0],nei[1]+cur[1]);
q.offer(new int[]{nei[0],nei[1]+cur[1]});
}
}
K--;
}
return res==Integer.MAX_VALUE?-1:res;
}
这道题的另外一种解法是DP。dp[i][j] 表示从SRC到I，最多飞J次，要花的最少的钱。
那么转移方程的思考就是 DP I J = MIN(DP I J-1，所有的 flight 里DP【flight[0]】[j-1]+price)
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
K++;
int[][] dp = new int[n][K+1];
for(int i=0;i<n;i++)
Arrays.fill(dp[i],Integer.MAX_VALUE-10000);
dp[src][0] = 0;
for(int j=1;j<=K;j++){
for(int i=0;i<n;i++){
dp[i][j] = dp[i][j-1];
for(int[] f : flights){
if(f[1] != i) continue;
dp[i][j] = Math.min(dp[i][j],dp[f[0]][j-1]+f[2]);
}
}
}
return dp[dst][K]==Integer.MAX_VALUE-10000?-1:dp[dst][K];
}
做一次优化
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
K++;
int[][] dp = new int[n][K+1];
for(int i=0;i<n;i++)
Arrays.fill(dp[i],Integer.MAX_VALUE-10000);
dp[src][0] = 0;
for(int j=1;j<=K;j++){
for(int i=0;i<n;i++){
dp[i][j] = dp[i][j-1];
}
for(int[] f : flights){
dp[f[1]][j] = Math.min(dp[f[1]][j],dp[f[0]][j-1]+f[2]);
}
}
return dp[dst][K]==Integer.MAX_VALUE-10000?-1:dp[dst][K];
}
752. Open the Lock
https://leetcode.com/problems/open-the-lock/description/
这道题的核心就是想到每一个字符的这个节点，通过移一步，可以有8个状态。然后就是BFS常规，找最短路径了。
public int openLock(String[] deadends, String target) {
String source = "0000";
Set<String> s = new HashSet<>();
for(String dead : deadends){
s.add(dead);
}
if(s.contains(source)) return -1;
Set<String> seen = new HashSet<>();
Queue<String> q = new LinkedList<>();
q.offer(source);
seen.add(source);
int step = 0;
while(!q.isEmpty()) {
step++;
int qsize = q.size();
while(qsize>0){
qsize--;
String cur = q.poll();
char[] curs = cur.toCharArray();
for(int i=0;i<4;i++){
for(int j=-1;j<=1;j+=2){
char tmp = curs[i];
curs[i] = (char) ((((curs[i]-'0'+10)+j)%10)+'0');
String news = new String(curs);
curs[i] = tmp;
if(target.equals(news)) return step;
if(seen.contains(news) || s.contains(news)) continue;
seen.add(news);
q.offer(news);
}
}
}
}
return -1;
}
