春节7天练 Day 6：图
你好，我是王争。初六好！
为了帮你巩固所学，真正掌握数据结构和算法，我整理了数据结构和算法中，必知必会的30个代码实现，分7天发布出来，供你复习巩固所用。今天是第六篇。
和之前一样，你可以花一点时间，来手写这些必知必会的代码。写完之后，你可以根据结果，回到相应章节，有针对性地进行复习。做到这些，相信你会有不一样的收获。
关于图的几个必知必会的代码实现
图
- 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
- 实现图的深度优先搜索、广度优先搜索
- 实现Dijkstra算法、A*算法
- 实现拓扑排序的Kahn算法、DFS算法
对应的LeetCode练习题（@Smallfly 整理）
- Number of Islands（岛屿的个数）
英文版：https://leetcode.com/problems/number-of-islands/description/
中文版：https://leetcode-cn.com/problems/number-of-islands/description/
- Valid Sudoku（有效的数独）
英文版：https://leetcode.com/problems/valid-sudoku/
中文版：https://leetcode-cn.com/problems/valid-sudoku/
做完题目之后，你可以点击“请朋友读”，把测试题分享给你的朋友，说不定就帮他解决了一个难题。
祝你取得好成绩！明天见！
- 色即是空 👍（2） 💬（1）
有效数独，就是穷举遍历方法求解，跟这一节练习的图，没有什么关系啊！放这个题目的时候是怎么考虑的啊？
2019-06-27 - ext4 👍（1） 💬（1）
有效的数独 class Solution { public: bool isValidSudoku(vector< vector<char> >& board) { set<char> numset; for (int i = 0; i < 9; i++) { numset.clear(); for (int j = 0; j < 9; j++) { char val = board[i][j]; if (val != '.') { if (numset.count(val) != 0) return false; numset.insert(val); } } } for (int j = 0; j < 9; j++) { numset.clear(); for (int i = 0; i < 9; i++) { char val = board[i][j]; if (val != '.') { if (numset.count(val) != 0) return false; numset.insert(val); } } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { numset.clear(); for (int p = 0; p < 3; p++) { for (int q = 0; q < 3; q++) { char val = board[i * 3 + p][j * 3 + q]; if (val != '.') { if (numset.count(val) != 0) return false; numset.insert(val); } } } } } return true; } };
2019-02-10 - Nereus 👍（0） 💬（1）
并查集—go实现 func numIslands(grid [][]byte) int { if len(grid) == 0 { return 0 } N := len(grid)*len(grid[0]) + 1 u := NewUnionSet(N) for i := 0; i < len(grid); i ++ { for j := 0; j < len(grid[i]); j ++ { if grid[i][j] == '1' { // 联通下边 if i+1 < len(grid) { if grid[i+1][j] == '1' { u.join(i*len(grid[i])+j, (i+1)*len(grid[i])+j) } } // 联通右边 if j+1 < len(grid[i]) { if grid[i][j+1] == '1' { u.join(i*len(grid[i])+j, i*len(grid[i])+j+1) } } } else { u.join(i*len(grid[i])+j, N-1) } } } return u.counts() -1 } type UnionSet []int func NewUnionSet(n int) UnionSet { var u UnionSet u = make([]int, n) for i := 0; i < len(u); i ++ { u[i] = i } return u } func (u UnionSet) find(i int) int { tmp := i for u[tmp] != tmp { tmp = u[tmp] } j := i for j != tmp { tt := u[j] u[j] = tmp j = tt } return tmp } func (u UnionSet) connected(i, j int) bool { return u.find(i) == u.find(j) } func (u UnionSet) counts() int { var count int for idx, rec := range u { if idx == rec { count++ } } return count } func (u UnionSet) join(i, j int) { x, y := u.find(i), u.find(j) if x != y { if y > x { u[x] = y } else { u[y] = x } } }
2019-02-14 - 拉欧 👍（0） 💬（1）
Number of Islands（岛屿的个数）go语言实现，亲测通过： func numIslands(grid [][]byte) int { isSearch:=make([][]int,len(grid)) island:=0 for i:=0;i<len(isSearch);i++{ isSearch[i]=make([]int,len(grid[0])) } for i,line:=range grid{ for j,_:=range line{ if isSearch[i][j]==0 && grid[i][j]=='1'{ Search(grid,isSearch,i,j) island++ } } } return island } func Search(grid [][]byte,isSearch [][]int, i int,j int){ if isSearch[i][j]==1{ return } isSearch[i][j]=1 if grid[i][j]=='1'{ if i>=1{ Search(grid,isSearch,i-1,j) } if i<len(grid)-1{ Search(grid,isSearch,i+1,j) } if j>=1{ Search(grid,isSearch,i,j-1) } if j<len(grid[0])-1{ Search(grid,isSearch,i,j+1) } }else{ return } }
2019-02-14 - 蚂蚁内推+v 👍（0） 💬（1）
岛屿数Java实现 public int numIslands(char[][] grid) { int m = grid.length; if (m == 0) return 0; int n = grid[0].length; int ans = 0; for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) if (grid[y][x] == '1') { ++ans; dfs(grid, x, y, n, m); } return ans; } private void dfs(char[][] grid, int x, int y, int n, int m) { if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0') return; grid[y][x] = '0'; dfs(grid, x + 1, y, n, m); dfs(grid, x - 1, y, n, m); dfs(grid, x, y + 1, n, m); dfs(grid, x, y - 1, n, m); }
2019-02-11 - mgxian 👍（0） 💬（1）
有效的数独 go 语言实现 package main import ( "fmt" ) func hasRepeatedNumbers(numbers []byte) bool { var numbersExistFlag [9]bool for _, num := range numbers { if num == '.' { continue } index := num - '0' - 1 if numbersExistFlag[index] { return true } numbersExistFlag[index] = true } return false } func isValidSudoku(board [][]byte) bool { sudokuSize := 9 sudokuUnitSize := 3 for _, line := range board { if hasRepeatedNumbers(line) { return false } } for columnIndex := 0; columnIndex < sudokuSize; columnIndex++ { columnNumbers := make([]byte, 0) for lineIndex := 0; lineIndex < sudokuSize; lineIndex++ { columnNumbers = append(columnNumbers, board[lineIndex][columnIndex]) } if hasRepeatedNumbers(columnNumbers) { return false } } sudokuUnitCountEachLine := sudokuSize / sudokuUnitSize for i := 0; i < sudokuUnitCountEachLine; i++ { for j := 0; j < sudokuUnitCountEachLine; j++ { sudokuUnitNumbers := make([]byte, 0) for _, line := range board[i*3 : (i+1)*3] { sudokuUnitNumbers = append(sudokuUnitNumbers, line[j*3:(j+1)*3]...) } if hasRepeatedNumbers(sudokuUnitNumbers) { return false } } } return true } func main() { testData1 := [][]byte{ {'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}} fmt.Println(isValidSudoku(testData1)) }
2019-02-10 - kai 👍（3） 💬（0）
今天根据老师的课程，总结了一下图的相关知识点，然后用代码实现了一下图的相关的算法，感觉图还是要难于其他数据结构，需要接着多练习~
2019-02-10 - 李皮皮皮皮皮 👍（3） 💬（0）
图很复杂😢
2019-02-10 - kai 👍（1） 💬（0）
实现图的深度优先搜索、广度优先搜索: import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; public class BFSAndDFS { class Node { public int value; //Node 值 public int in; //入度：指向该节点的边有几条 public int out; //出度：指向其他节点的边有几条 public ArrayList<Node> nexts; public ArrayList<Edge> edges; public Node(int value) { this.value = value; this.in = 0; this.out = 0; this.nexts = new ArrayList<>(); this.edges = new ArrayList<>(); } } public static void bfs(Node node) { if (node == null) { return; } Queue<Node> queue = new LinkedList<>(); HashSet<Node> set = new HashSet<>(); queue.add(node); set.add(node); while (!queue.isEmpty()) { Node cur = queue.poll(); System.out.print(cur.value + " "); for (Node next : cur.nexts) { if (!set.contains(next)) { queue.add(next); set.add(next); } } } } public static void dfs(Node node) { if (node == null) { return; } Stack<Node> stack = new Stack<>(); HashSet<Node> set = new HashSet<>(); stack.push(node); set.add(node); System.out.print(node.value + " "); while (!stack.isEmpty()) { Node cur = stack.pop(); for (Node next : cur.nexts) { if (!set.contains(next)) { stack.push(cur); stack.push(next); set.add(next); System.out.print(next.value + " "); break; } } } } }
2019-02-11 - 纯洁的憎恶 👍（1） 💬（1）
1.在邻接矩阵中找出连通图个数即可。在每个顶点执行DFS或BFS，执行次数即为岛屿数，也可以使用并查集。 2. 依次考察9✖️9数独各行各列是否有重复数字（可以用9位数组统计），然后再考察每个3✖️3子矩阵是否有重复数字。都没有则成功。
2019-02-10 - 杨建斌(young) 👍（0） 💬（0）
有效数独 int[][] row = new int[10][10]; int[][] col = new int[10][10]; boolean retFlag = true; for (int i = 0; i < grid.length; i += 3) { for (int j = 0; j < grid[0].length; j += 3) { boolean xx = xx(row, col, grid, i, j);//模块左上角第一个元素位置 if (!xx) { retFlag = false; break; } } if (!retFlag) { break; } } public static boolean xx(int[][] row, int[][] col, String[][] grid, int i, int j) { Map map = new HashMap(); for (int ii = i; ii < i + 3; ii++) { for (int jj = j; jj < j + 3; jj++) { if (map.get(grid[ii][jj]) != null) { return false; } if (!".".equals(grid[ii][jj])) { map.put(grid[ii][jj], "1"); int haveRow = row[ii][Integer.parseInt(grid[ii][jj])]; int haveCol = col[jj][Integer.parseInt(grid[ii][jj])]; if (haveCol == 1 || haveRow == 1) { return false; } row[ii][Integer.parseInt(grid[ii][jj])] = col[jj][Integer.parseInt(grid[ii][jj])] = 1; } } } return true; }
2023-07-03 - 杨建斌(young) 👍（0） 💬（0）
岛屿的个数 public static void main(String[] args) { int[][] grid = new int[][]{ {1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 1} }; int cnt = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { xx(grid, i, j); cnt++; } } } System.out.println(cnt); } public static void xx(int[][] grid, int i, int j) { if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) { return; } if (grid[i][j] == 0) { return; } //等于1 grid[i][j] = 0; if (i > 0) { xx(grid, i - 1, j); } if (j > 0) { xx(grid, i, j - 1); } if (i < grid.length - 1) { xx(grid, i + 1, j); } if (j < grid[0].length - 1) { xx(grid, i, j + 1); } }
2023-07-03 - Geek_97afb1 👍（0） 💬（0）
入坑第一百天 -brandon
2022-06-22 - Bax 👍（0） 💬（0）
数独，还没测试
2022-02-18 - 阿甘 👍（0） 💬（0）
class Solution { public int numIslands(char[][] grid) { int num = 0; for (int i = 0; i < grid.length; i++) { // rows for (int j = 0; j < grid[i].length; j++) { // cols if (grid[i][j] == '1') { num++; dfs(grid, i, j, grid.length, grid[i].length); } } } return num; } private void dfs(char[][] grid, int i, int j, int rows, int cols) { if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] == '0') { return; } grid[i][j] = '0'; // visit dfs(grid, i - 1, j, rows, cols); dfs(grid, i, j - 1, rows, cols); dfs(grid, i + 1, j, rows, cols); dfs(grid, i, j + 1, rows, cols); } }
2021-06-29