春节7天练 | Day 6：图

有效数独，就是穷举遍历方法求解，跟这一节练习的图，没有什么关系啊！放这个题目的时候是怎么考虑的啊？

有效的数独 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; } };

并查集—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 } } }

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 } }

岛屿数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); }

有效的数独 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)) }

今天根据老师的课程，总结了一下图的相关知识点，然后用代码实现了一下图的相关的算法，感觉图还是要难于其他数据结构，需要接着多练习~

图很复杂😢

实现图的深度优先搜索、广度优先搜索: 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; } } } } }

1.在邻接矩阵中找出连通图个数即可。在每个顶点执行DFS或BFS，执行次数即为岛屿数，也可以使用并查集。 2. 依次考察9✖️9数独各行各列是否有重复数字（可以用9位数组统计），然后再考察每个3✖️3子矩阵是否有重复数字。都没有则成功。