[演算法][JavaScript]演算法挑战系列(10)-Valid Sudoku

嗨啊，这是放暑假开始的第一篇文章，虽然在这里的大大几乎都没暑假了XD，不过还是让我们感染一下这种快乐好了，哈哈哈，说到学生时期，我很爱玩的一个游戏就叫数独，常常一天就废寝忘食的解上好几题，连大学打工在便利商店都会拿报纸起来找题目，哈哈哈，所以今天就来解个关于数读题目吧！不过没有大家想像的那么困难，我们只是要判断目前传进来的阵列算不算是一个正确的数读题目，那就直接来看个题目吧！

题目名称：Valid Sudoku
难易度：中
题目内容：输入一个9乘9的二维阵列，并判断是不是有效数独题目，规则如下：
一、每一行由1-9随机组成，并不得重複（如下图蓝色框框）。
二、每一列由1-9随机组成，并不得重複（如下图红色框框）。
三、把一个二维阵列分成九个九宫格，每一宫格的数字也是由1-9随机组成，并不得重複（如下图绿色框框）：

例如：
1.传入以下阵列：

[  ["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"]]

因为每一行、每一列及每一宫格都没有重複的数字，所以回传True。

2.传入以下阵列：

[  ["8","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"]]

因为在左上角的那一个九宫格中，数字8重複出现了，所以回传False。

说一下这次的解题过程好了，其实是在打预防针，哈哈哈，好啦！其实没什么，只是这次用暴力破解法来处理掉，也就是说如果没有提前判断到重複，或结果是True的话，最多必须判断...27次，然后迴圈会跑(9*9)+3次，时间複杂度应该是O(n²)，因为我跑了9行里面又跑了9列，其实我也很不会算，所以这次来抛砖引玉，偶尔也让我任性一下XD，以下是解法：

var isValidSudoku = function(board) {    //首先比较每个阵列中的内容有没有重複的    for(let i=0;i<=8;i++){        //把每一列列出来        let arrTemp = board[i];        //判断重複值，如果有重複就直接回传false        if (!checkRepeat(arrTemp))            return false;                //这边取每一行的值取出来        arrTemp = [];        for(let j=0;j<=8;j++){            //把值放进阵列中            arrTemp.push(board[j][i]);                        //这边另外写一个判断，因为九宫格是3*3的，所以判断每三行跑一次            if((i%3) == 0 && (j%3) == 0){                //宣告新的arrTemp                let arrTemp = [];                //用迴圈取目前行开始三行的位置                for(let k=i;k<(i+3);k++){                    //把用slice抓到的三个值合併到arrTemp阵列中                    arrTemp = arrTemp.concat(board[k].slice(j,j+3))                }                //判断重複值，如果有重複就直接回传false                if(!checkRepeat(arrTemp))                    return false;            }        }        //判断重複值，如果有重複就直接回传false        if (!checkRepeat(arrTemp))            return false;            }        return true;        /**判断阵列中有没有重複的值    这个function是参考网路上写出来的，会把出处连结放在文章结尾，    觉得用这个方式还满聪明的，大家可以看一下**/    function checkRepeat(arrTemp){        //把阵列内容输出成字串        var arrStr = JSON.stringify(arrTemp),str;        //跑所有阵列的值        for (let i=0; i<arrTemp.length;i++) {            //这边是我加的，因为.一定会重複，所以就不判断.了            if(arrTemp[i]=='.')                continue;            /*精华在这里，            用目前要判断的值去找在字串中第一次出现的位置和最后一次出现的位置，            如果有一样就代表没重複，不同就代表有重複，所以回传False*/            if (arrStr.indexOf(arrTemp[i]) != arrStr.lastIndexOf(arrTemp[i])){                return false;            }        };        //全部跑完没有回传false就代表没重複，所以在最后回传True        return true;    }};

好的，其实一直以来程式类的题目效能都满稳定的，可是这次我测出来特别飘XD，差不多在5X%到8X%，不晓得网路会不会有影响，哈哈哈哈，以下是成绩：

再来分享一个用物件来解的方式，这在讨论区上的标题注明了击败了100%的答案XD，让我们来看看这位大神怎么做：
原解答位置

var isValidSudoku = function(board) {    //首先跑每一列的迴圈    for(let i=0; i<9; i++){        /*宣告两个物件，objH是列，objV是行，        用来纪录出现过的值*/    let objH={}, objV={}        //跑每一行的迴圈    for(let j=0; j<9; j++){            //把目前位置的值放进cur1及cur2中    let cur1 = board[i][j], cur2 = board[j][i];            /*判断是不是.，如果是有数字的话，            就去判断先前有没有出现过这个数字，如果没出现就把它记录下来，            这样如果接下来有相同数字，就会有值，会直接回传false*/    if(cur1!=='.'){    if(objH[cur1]) return false;    objH[cur1]=1;    }            //行的也像列一样做判断处理    if(cur2!=='.'){    if(objV[cur2]) return false;    objV[cur2]=1;    }    }    }    //判断完行和列，接着再来判断九宫格的部分    for(let i=0; i<9; i++){        /*宣告用来纪录值的物件obj，以及用来判断行和列位置的m1和m2，        m1会是000333666 m2是036036036，m1是行、m2是列，        所以每列(m1)会跑三次，每次会都从(m2)第0行取到第2行、3取到6、6再取到8，        跑完m1在直接跳到位置三第四行，继续跑迴圈，        由上而下、由左至右的跑每个九宫格。*/    let obj={}, m1=Math.floor(i/3)*3, m2=(i%3)*3;    for(let j=0; j<3; j++){    for(let k=0; k<3; k++){                //用迴圈取九宫格的数字，并把目前的数字放进cur中    let cur = board[m1+j][m2+k];                /*判断是不是.，如果是有数字的话，                就去判断先前有没有出现过这个数字，如果没出现就把它记录下来，                这样如果接下来有相同数字，就会有值，会直接回传false*/    if(cur!=='.'){    if(obj[cur]) return false;    obj[cur]=1;    }    }    }    }    //全部跑完如果都没回传false代表是正确的题目，所以最后回传true    return true;};

以上的m1=Math.floor(i/3)*3, m2=(i%3)*3;真的有点难解释，不过如果试着用console.log把值给印出来就可以很明白的知道整个逻辑。如果以上有解释错误或不清楚的地方，都可以在下方留言告诉我，我会再想想怎么改会比较好，也欢迎各位大大提出自己的看法，我都会认真去看每个留言的！那这个礼拜的分享先到这边(不知道为什么这次的结尾非常词穷XD)，就谢谢大家观赏

参考文章：
JavaScript判断阵列重複内容的两种方法(推)