春节7天练 | Day 6：图

精选留言

• kai

  2019-02-10 13:02:30

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

  2019-02-10 08:07:02

  图很复杂😢
• 
  色即是空

  2019-06-27 18:44:01

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

  作者回复

  好像确实暴力就能解决

  2019-06-28 07:02:30

• kai

  2019-02-11 10:54:03

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

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

  2019-02-10 09:35:07

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

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 10:55:11

• 
  杨建斌(young)

  2023-07-03 16:44:54

  有效数独
  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;
  }
• 
  杨建斌(young)

  2023-07-03 14:05:14

  岛屿的个数
  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);
  }
  }
• 
  Geek_97afb1

  2022-06-22 07:08:17

  入坑第一百天
  -brandon
• 
  Bax

  2022-02-18 12:44:46

  数独，还没测试
• 
  阿甘

  2021-06-29 17:15:41

  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);
  }
  }
• 
  yaoyue

  2020-03-27 21:27:07

  幸甚至哉，歌以咏志
• 
  苦行僧

  2019-08-26 11:26:04

  有效的数独确实可以用暴力匹配法解决
• Nereus

  2019-02-14 17:34:55

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

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您10元无门槛优惠券，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:11:55

• 
  拉欧

  2019-02-14 14:18:20

  Valid Sudoku（有效的数独）go语言实现
  
  func isValidSudoku(board [][]byte) bool {
  
  isValid:=true
  for i:=0;i<9;i++{
  for j:=0;j<9;j++{
  if board[i][j]=='.' {
  continue
  }else{
  if !judgeLine(board,i,j){
  return false
  }
  }
  }
  }
  
  return isValid
  }
  
  func judgeLine(board [][]byte,i,j int) bool{
  hash:=make(map[byte]int,9)
  for k:=0;k<9;k++{
  if board[i][k]!='.'{
  if hash[board[i][k]]==0{
  hash[board[i][k]]=1
  }else{
  return false
  }
  }
  }
  hash=make(map[byte]int,9)
  for k:=0;k<9;k++{
  if board[k][j]!='.' {
  if hash[board[k][j]]==0{
  hash[board[k][j]]=1
  }else{
  return false
  }
  }
  }
  hash=make(map[byte]int,9)
  for m:=i/3*3;m<i/3*3+3;m++{
  for n:=j/3*3;n<j/3*3+3;n++{
  if board[m][n]!='.'{
  if hash[board[m][n]]==0{
  hash[board[m][n]]=1
  }else{
  return false
  }
  }
  }
  }
  return true
  
  }
  
  
  
• 
  拉欧

  2019-02-14 10:45:02

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

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:00:33

• 
  molybdenum

  2019-02-11 13:10:33

  island 我用的深搜，把所有的1探索，用visited保存访问过访问的，搜索次数便是岛屿个数
• 
  蚂蚁内推+v

  2019-02-11 10:30:36

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

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您10元无门槛优惠券，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:08:22

• 
  黄丹

  2019-02-10 23:05:34

  已经初六啦，就快要到去学校的时间了，难受。
  图的邻接矩阵表示法是使用一个二维数组int[0..n-1][0...n-1]来保存顶点和边的，对于无权图，1表示有边，0表示两个顶点没有变，有权图，值代表权重。
  图的邻接表则是采用数组+链表的结构来表示的，数组里存的是顶点，链表存储的是边的信息，当然链表也可以换做二叉搜索树，散列表等高效查找的数据结构。
  今天的两道leetcode题的解题思路和代码如下：
  1. Number of Islands （岛屿的个数）
  解题思路：遍历数组，遇到1时，使用深度/广度遍历，将连通的1都置为0，然后将岛屿个数加1.
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/graph/Problem200_NumberofIslands.java
  2. Valid Sudoku  （有效的数独）
  解题思路：emm，不知道为什么这道题要放在图论的专题下，我的解法就是横着一行行判断，竖着一列列的判断，然后每个3*3的子块进行判断。没有用到图的知识。
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/graph/Problem36_ValidSudoku.java
  
• 
  虎虎❤️

  2019-02-10 21:32:39

  基于临接表实现的联通分量求法， go 语言实现：
  package graph_basics
  
  type Components struct {
  graph Graph
  visited []bool
  id []int
  ccount int
  }
  
  func InitComponents(g Graph) *Components {
  return &Components{
  graph: g,
  visited: make([]bool, g.V()),
  id: make([]int, g.V()),
  ccount: 0,
  }
  }
  
  func (c *Components) dfs(index int) {
  c.visited[index] = true
  c.id[index] = c.ccount
  adj := c.graph.Iterator(index)
  for i := range adj {
  if !c.visited[adj[i]] {
  c.dfs(adj[i])
  }
  }
  }
  
  func (c *Components) CalculateComponents() {
  for i := 0; i < c.graph.V(); i++ {
  if c.visited[i] {
  continue
  }
  c.dfs(i)
  c.ccount++
  }
  }
  
  func (c *Components) Count() int {
  return c.ccount
  }
  
  func (c *Components) IsConnected(p int, q int) bool {
  return c.id[p] == c.id[q]
  }
  
  临接表的实现：
  package graph_basics
  
  import "fmt"
  
  type SparseGraph struct {
  v int
  e int
  direct bool
  g [][]int
  }
  
  func InitSparseGraph(n int, direct bool) *SparseGraph {
  graph := make([][]int, n)
  return &SparseGraph{
  v: n,
  e: 0,
  direct: direct,
  g: graph,
  }
  }
  
  func (sg *SparseGraph) V() int {
  return sg.v
  }
  
  func (sg *SparseGraph) E() int {
  return sg.e
  }
  
  func (sg *SparseGraph) AddEdge(p int, q int) {
  sg.g[p] = append(sg.g[p], q)
  if !sg.direct {
  sg.g[q] = append(sg.g[q], p)
  }
  
  sg.e++
  }
  
  func (sg *SparseGraph) HasEdge(p int, q int) bool {
  for i := 0; i < len(sg.g[p]); i++ {
  if sg.g[p][i] == q {
  return true
  }
  }
  return false
  }
  
  func (sg *SparseGraph) Show() {
  for i := range sg.g {
  fmt.Printf("vertex %d :\t", i)
  for j := range sg.g[i] {
  fmt.Printf("%d\t", sg.g[i][j])
  }
  fmt.Println()
  }
  }
  
  func (sg *SparseGraph) Iterator(v int) []int {
  return sg.g[v]
  }