關(guān)于井字游戲自己的解題思路吧.

wums 發(fā)布于2019-08-26 12:01 / 2103人閱讀

摘要：題目來(lái)源于面試公司先看看題目吧假設(shè)我們現(xiàn)在有一個(gè)的井字棋游戲，我們用一個(gè)二維數(shù)組代表棋盤，代表玩家下的棋子，代表玩家下的棋子，代表該格沒(méi)有棋子。

題目來(lái)源于面試公司,先看看題目吧

假設(shè)我們現(xiàn)在有一個(gè) 3 x 3 的井字棋游戲，我們用一個(gè)二維數(shù)組代表棋盤，’x’ 代表玩家 X 下的棋子，’o’ 代表玩家 O 下的棋子，’e’ 代表該格沒(méi)有棋子。例如：一個(gè)空白的棋盤以下面的二維數(shù)組表示:

[[‘e’, ‘e’, ‘e’],
 [‘e’, ‘e’, ‘e’],
 [‘e’, ‘e’, ‘e’]
]

如果玩家 X 在第一行第一列下了一步棋，玩家 O 在第二行第二列下了一步棋，則表示如下：

[[‘x’, ‘e’, ‘e’],
 [‘e’, ‘o’, ‘e’],
 [‘e’, ‘e’, ‘e’]]

現(xiàn)在需要一個(gè) function，接受一個(gè)已有任意棋子的棋盤（和上面二維數(shù)組一樣的格式），和玩家的標(biāo)志（’x’ 或 ‘o"），返回該玩家下一步有幾種可能的獲勝方式（獲勝方式以數(shù)組表示，[0, 0] 代表在第一行第一列下一步棋即可獲勝，[2, 2] 代表在第三行第三列下一步棋即可獲勝）。例如：

someFunction(
‘x’,
[[‘o’, ‘e’, ‘e’],
 [‘o’, ‘x’, ‘o’],
 [‘x’, ‘x’, ‘e’]])
// return [ [2, 2], [0, 1], [0, 2] ]
someFunction(
‘x’,
[[‘x’, ‘o’, ‘o’],
 [‘x’, ‘x’, ‘e’],
 [‘e’, ‘o’, ‘e’]])
// return [[2, 2], [1, 2], [2, 0]]
someFunction(
‘x’,
[[‘x’, ‘x’, ‘o’],
 [‘e’, ‘e’, ‘e’],
 [‘e’, ‘e’, ‘e’]])
// return [ ]
someFunction(
‘o’,
[[‘o’, ‘o’, ‘o’],
 [‘e’, ‘e’, ‘e’],
 [‘e’, ‘e’, ‘e’]])
// return [ ]

最后是加分項(xiàng):

代碼可讀性高

代碼量少

性能高

有可運(yùn)行的單元測(cè)試

使用 ES6 語(yǔ)法實(shí)現(xiàn)

使用 functional programming

下面是自己的代碼實(shí)現(xiàn).

var getSuccess;
+function(){
    //假設(shè)3個(gè)相連即可獲勝.
    const linkLen = 3;
    //實(shí)際上, 我們可以理解為, 圍繞某個(gè)沒(méi)有棋子的點(diǎn),在 X 和 十 字這4個(gè)方向上的比較
    //因此這里提供獲取該4個(gè)方向上獲取棋盤點(diǎn)的簡(jiǎn)易計(jì)算公式.
    const _getTraverlConfig = function(distance){
        return [{
            cStartRow : -1 * linkLen + 1, 
            cStartLine : -1 * linkLen + 1,
            rowAdd : 1,
            lineAdd : 1,
        }, {
            cStartRow : -1 * linkLen + 1, 
            cStartLine : linkLen - 1,
            rowAdd : 1,
            lineAdd : -1,
        }, {
            cStartRow : -1 * linkLen + 1, 
            cStartLine : 0,
            rowAdd : 1,
            lineAdd : 0,
        }, {
            cStartRow : 0, 
            cStartLine : -1 * linkLen + 1,
            rowAdd : 0,
            lineAdd : 1,
        }];
    }
    //提供一個(gè)target字符串重復(fù)n次自己的方法
    const _strRepeat =    function (target, n){
        var s = target, total = "";
        while( n > 0 ) {
            if(n % 2 == 1)
                total += s;
            if(n == 1) 
                break;
            s += s;
            n = n >>1 ;
        } 
        return total;
    }
    //最終對(duì)外暴露的方法, 第一個(gè)參數(shù)是下棋的人, 第二個(gè)是棋盤的點(diǎn)數(shù)組.
    getSuccess = function( piece, chessboard ){
        var availablePosition = [], distance = chessboard.length,
            traversalConfig, maxLen, compareStr, chessStr;
        //根據(jù)幾個(gè)點(diǎn)連成線獲取4個(gè)方向上的計(jì)算公式;
        traversalConfig = _getTraverlConfig(linkLen);
        //計(jì)算方向上的點(diǎn)數(shù)量.
        maxLen = 2 * (linkLen - 1) + 1;
        //如果傳入的piece為x,那么這里的值就為xxx
        compareStr = _strRepeat(piece, linkLen);
        //這一步很重要, 將棋盤轉(zhuǎn)為一個(gè)字符串,為的就是更快.
        chessStr = chessboard.reduce( 
                (x,y) => x + y.join("")
        , "")
        //檢查每一個(gè)字符串, 如果是空的話就判斷能否獲勝.
        for( let i = 0, len = chessStr.length; i < len; i++)
            if( "e" == chessStr.charAt(i) ) _checkAvailable(i);
            
        function _checkAvailable( sqnm ){
            //計(jì)算點(diǎn)在棋盤上的行和列.
            let curRow = Math.floor(sqnm / distance), curLine = sqnm % distance;
            //以傳入的參數(shù)填在該空點(diǎn)上,得到一個(gè)新的棋盤字符串.
            let tempChessStr = chessStr.substring(0, sqnm) + piece + chessStr.substring(sqnm + 1, chessStr.length);
            //4個(gè)方向上的檢查
            for( let i = 0, len = traversalConfig.length; i < len; i++) {
                let { cStartRow, cStartLine, rowAdd, lineAdd } = traversalConfig[i];
                let tempStr = "";
                let j = 0;
                let row = curRow + cStartRow;
                let line = curLine + cStartLine;
                
                while( j < maxLen ) {
                    //超出邊界視為空字符串.
                    if(row < 0 || row > distance || line > distance || line < 0){
                        tempStr += "";
                    }
                    else {
                        //方向上棋盤的實(shí)際棋子的集合字符串.
                        tempStr += tempChessStr.charAt(row * distance + line);
                    }
                    row += rowAdd;
                    line += lineAdd;
                    j++;
                }
                //如果在該字符串中含有需要比較的重復(fù)字符串即可認(rèn)為該點(diǎn)可以獲勝.
                if( -1 != tempStr.indexOf(compareStr) ) {
                    availablePosition.push([curRow, curLine]);
                    return;
                }
            }    
        }
        console.log(availablePosition);
    }
}();

寫的不好, 請(qǐng)多指教.