找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1561|回复: 3
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Valid Sudoku】【数组】-【刷题第一弹】

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 10-11-2014 11:14 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:46 AM 编辑

快速通道:
https://oj.leetcode.com/problems/valid-sudoku/


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================


思路:数独需要判断每行每列和每个3*3的部分是否出现重复的数字。
代码:
  1. public boolean isValidSudoku(char[][] board) {
  2.                 int nine = 9;
  3.                 if (board == null || board.length != nine || board[0].length != nine)
  4.                         return false;
  5.                 for (int i = 0; i < nine; i++) {
  6.                         boolean[] bline = new boolean[nine];
  7.                         for (int j = 0; j < nine; j++) {
  8.                                 char ij = board【i】[j];
  9.                                 if (ij == '.')
  10.                                         continue;
  11.                                 if (ij >= '1' && ij <= '9' && bline[ij - '1'] != true)
  12.                                         bline[ij - '1'] = true;
  13.                                 else
  14.                                         return false;
  15.                         }
  16.                 }

  17.                 for (int i = 0; i < nine; i++) {
  18.                         boolean[] brow = new boolean[nine];
  19.                         for (int j = 0; j < nine; j++) {
  20.                                 char ji = board[j]【i】;
  21.                                 if (ji == '.')
  22.                                         continue;
  23.                                 if (ji >= '1' && ji <= '9' && brow[ji - '1'] != true)
  24.                                         brow[ji - '1'] = true;
  25.                                 else
  26.                                         return false;
  27.                         }
  28.                 }

  29.                 for (int i = 0; i < nine; i++) {
  30.                         boolean[] part = new boolean[nine];
  31.                         for (int j = 0; j < nine; j++) {
  32.                                 char ij = board[(i % 3) * 3 + j % 3][(i/3)*3+j / 3];
  33.                                 if (ij == '.')
  34.                                         continue;
  35.                                 if (ij >= '1' && ij <= '9' && part[ij - '1'] != true)
  36.                                         part[ij - '1'] = true;
  37.                                 else
  38.                                         return false;
  39.                         }
  40.                 }
  41.                 return true;
  42.         }
复制代码

复杂度: O(n^2)

本帖被以下淘专辑推荐:

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 11-19-2014 09:22 PM | 显示全部楼层
复杂度是O(n^3),post出来也是因为样子好看,一上去先来个clear的solution,然后再优化,利用hashmap,或者别的方法,就可优化到O(n^2)了...楼主的方法就值得一学
  1.     public boolean isValidSudoku(char[][] board) {
  2.         for(int i=0; i<9; i++){
  3.             for(int j=0; j<9; j++){
  4.                 if(board[i][j]!='.'){
  5.                     for(int k=0; k<9; k++){
  6.                         if(board[k][j]==board[i][j] && k!=i) return false;
  7.                         if(board[i][k]==board[i][j] && k!=j) return false;
  8.                         if(board[i/3*3+k/3][j/3*3+k%3] == board[i][j] && i/3*3+k/3 !=i && j/3*3+k%3 !=j) return false;
  9.                     }
  10.                 }
  11.             }
  12.         }
  13.         return true;
  14.     }
复制代码
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 1-13-2015 11:24 PM | 显示全部楼层
楼主最后计算3*3方块的方法感觉很犀利,咋想出了的呀?还没看懂,求解释啊
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表