iT邦幫忙

7

[演算法][JavaScript]演算法挑戰系列(5)-Spiral Matrix

HI啊,又到了一個禮拜一次的燒腦時間,其實這一次我真的很怕生不出來,所以我禮拜一就開始準備了,哈哈哈,今天的題目其實上禮拜就要Po了,可是那時候真的在電腦前面鬼打牆很久,就直接換到Hard難度的SQL題目了,所以這篇算是來還債的XD,感謝大家持續支持這個系列/images/emoticon/emoticon37.gif
這一次的題目有些人應該會很熟悉,其實就題目名稱來說也算滿常聽到的,只是小的我第一次碰到,所以實作時苦惱很久/images/emoticon/emoticon70.gif,那還是一樣廢話不多說,直接來吧!
題目名稱:Spiral Matrix
難易度:中
題目內容:傳入一個二維陣列,依序由上、右、下、左,從外面往裡面用螺旋的方式取值,回傳該陣列中的所有元素。
例如:
1.傳入以下陣列:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
會回傳陣列:[1,2,3,6,9,8,7,4,5]
2.傳入以下陣列:
[
[1, 2, 3 ],
[4, 5, 6 ],
[7, 8, 9 ],
[10,11,12]
]
會回傳陣列:[1,2,3,6,9,12,11,10,7,4,5,8]

好的,那以下是我苦思後的解法:

var spiralOrder = function(matrix) {
    
    //如果傳進來是空陣列就回傳空陣列
    if(matrix.length === 0){
        return [];
    }
    
    //用來裝解答
    let ans = [];
    //陣列中所有的數字有幾個
    let indexCount = matrix.length * matrix[0].length;
    //用來記錄目前的流程(0:上,1:右,2:下,3:左)
    let seq = 0;
    //指定回傳的位置值
    //第一維度是x,第二維度是y(等等進入迴圈後y會先+1所以初始值為-1)
    let x = 0;
    let y = -1;
    //跑迴圈(如果解答陣列中的長度小於matrix的所有元素就繼續跑,因為ans最後的陣列長度一定會和matrix一樣)
    while(ans.length < indexCount){
        //指定位置
        changeIndex(1);
        //宣告一個變數用來放目前要抓的值
        let nowValue;
        //取值用try迴圈包起來
        try{
            //用目前指定的位置把值從陣列取出來
            nowValue = matrix[x][y];
        }
        catch(err){
            //如果超出該陣列範圍就回傳undefined
            nowValue = undefined;
        };

        //如果回傳的值不在ans裡面又不是undefined就把他放進ans中
        if(ans.indexOf(nowValue) ===- 1 && nowValue !== undefined){
            ans.push(nowValue);
        }
        else{
            /*這裡是因為如果取出來undefuned或是重複的值,
            要先把這一次迴圈加的位置減回來,
            等於回復進入這一次迴圈前的狀態。*/
            changeIndex(-1);
            //這裡用來變動流程,依序由上:0,右:1,下:2,左:3去取值
            if(seq === 3){
                seq = 0;
            }
            else{
                seq+=1;
            }
        };
    };
    
    //用來變動位置,index傳入變動值
    function changeIndex (index){
        //確認目前流程,依照流程來做變動(如果傳進-1就是回復之前的狀態)
        switch(seq){
            case 0:{
                //如果是0(上),就是往右一格,所以y+1
                y+=index;
                break;
            };
            case 1:{
                //如果是1(右),就是往下一格,所以x+1
                x+=index;
                break;
            };
            case 2:{
                //如果是2(下),就是往左一格,所以y-1
                y-=index;
                break;
            };
            case 3:{
                //如果是3(左),就是往上一格,所以x-1
                x-=index;
                break;
            };
        };
    };

    //最後回傳裝完所有值的陣列
    return ans;
    
};

接著我分享一下這一次的成績,執行時間大概是56ms,然後贏過了77.16%的解答,其實一開始我送答案的時候才7%,一個嚇到吃手手,立馬修了第二版本出來XD,另外之前SQL之所以沒有貼上執行成績是因為送答案的人太少了,才讓那個系統沒辦法產生圖表,所以這一次分享一下!
https://ithelp.ithome.com.tw/upload/images/20180601/20106935dZagEQqmcC.jpg
還有我在討論區看到一個贏過95%答案的神之解答,完全用函式解決一堆邏輯上的問題,看完後真覺得自己對JS的熟練度還真的低到爆炸XD,那來看一下大神解法:
原解答網址

var spiralOrder = function (matrix) {

    "use strict";

    //宣告一個新陣列
    var res = [];

    //一個function來判斷陣列內是否還有值,如果有就回傳false,沒有就true
    var isEmpty = function isEmpty() {
        return matrix.length === 0 || matrix[0].length === 0;
    };

    //如果他還不是空的就繼續跑迴圈
    while (!isEmpty()) {

        //抓出matrix的第一個陣列位置,並把他放進res中(處理上面的部分)
        res = res.concat(matrix.shift()); 

        //確認目標陣列是否為空,如果是空的就跳出
        if (isEmpty()) break;

        //去跑迴圈,經過目前的所有位置
        for (var i = 0; i < matrix.length; i++) {
            //把每個位置的最後一個值抓出來放進res中(處理右邊的部分)
            res.push(matrix[i].pop()); 
        }
        
        //確認目標陣列是否為空,如果是空的就跳出
        if (isEmpty()) break;

        //把最後一個位置抓出來,反轉後放進res中(處理下面的部份)
        res = res.concat(matrix.pop().reverse());

        //確認目標陣列是否為空,如果是空的就跳出
        if (isEmpty()) break;

        //去跑迴圈,經過目前的所有位置
        for (var _i = matrix.length - 1; _i >= 0; _i--) {
            //把每個位置的第一個值抓出來放進res中(處理左邊的部分)
            res.push(matrix[_i].shift());
        }
    }

    //重複以上流程,直到目標陣列被處理到空了為止。
    return res;
};

上面的程式碼可能會和原文解答有點不同,因為我把它從ES6轉到ES5的語法,也照慣例的加了一堆註解,不然我真的還不太熟ES6/images/emoticon/emoticon06.gif
那以上是這禮拜的分享,雖然總算回到熟悉的JavaScript但也同時覺得世界還很大,有更多要學習的地方,算是一個收穫滿滿的一個禮拜XD。那一樣歡迎各位大大一起來討論各自的解法,如果以上文章中有不小心手誤、或是有問題的地方還請大家告訴我,我會立即改進!這一週依然感謝大家!沒有你們我一定堅持不到現在!/images/emoticon/emoticon41.gif


2 則留言

2
fysh711426
iT邦研究生 2 級 ‧ 2018-06-01 23:15:47

用了老方法,邏輯簡單但效能很難再優化,
然後剛剛一陣大 LAG 後,發現不小心發了五個留言。
/images/emoticon/emoticon16.gif
https://ithelp.ithome.com.tw/upload/images/20180601/20106865xRHk4r1Duj.jpg

class Solution
{
  public:
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        //分別對應,左->下->右->上
        int dir_x[4] = {0, 1, 0, -1};
        int dir_y[4] = {1, 0, -1, 0};
        
        //取得矩陣邊長
        int size_x = matrix.size();
        int size_y = size_x == 0 ? 0 : matrix[0].size();

        vector<int> output(size_x * size_y);

        int current = 0;   //紀錄回傳結果的索引
        int index = 0;     //紀錄行走方向的索引
        int x = 0;         //當前的 x 座標
        int y = 0;         //當前的 y 座標

        for (int i = 0; i < size_x * size_y; i++)
        {
            //將當前座標的值寫入結果,並在寫入後設為 0
            output[current++] = matrix[x][y];
            matrix[x][y] = 0;
            
            //前進
            x += dir_x[index];
            y += dir_y[index];
            
            //遇到邊界或已走過的座標
            if (x < 0 || x >= size_x ||
                y < 0 || y >= size_y ||
                matrix[x][y] == 0)
            {
                //退回
                x -= dir_x[index];
                y -= dir_y[index];
                
                //轉彎
                index = (index + 1) % 4;
                
                //前進
                x += dir_x[index];
                y += dir_y[index];
            }
        }
        return output;
    }
};

哈哈哈哈,嚇我一跳怎麼跑出那麼多通知XD
雖然我看不太懂C++,可是大大的解法應該也是去尋訪傳進來陣列的所有值,然後控制x和y把對應的值放進output陣列裡,最後再進入下一個迴圈前先判斷下一次要取的位置有沒有在陣列的索引,如果有的話就在回復x和y然後依照目前的index給他們新的值吧?(很不確定哈哈哈)
這樣子就可以比我少跑好幾次迴圈!3ms感覺超級厲害/images/emoticon/emoticon12.gif

fysh711426 iT邦研究生 2 級 ‧ 2018-06-02 22:22:02 檢舉

我的邏輯和大大差不多,遇到邊界就轉彎,
大大是用 try catch 和 indexOf 判斷邊界,
我是用 size_x, size_y 和 matrix[x][y] == 0。

然後 3ms 是 C++ 的原因,不是程式快。
/images/emoticon/emoticon37.gif

突然發現小財神默默把多的留言刪掉了/images/emoticon/emoticon37.gif

3
小魚
iT邦大師 1 級 ‧ 2018-06-02 11:07:34

感謝神Q超人幫我們精心準備的題目,
既然有JavaScript跟C++,
那小弟就來個C#獻醜一下吧...

static int[] GetArray(int[][] array)
{
    int length1 = array.Length;
    int length2 = array[0].Length;

    //先檢查是不是全部都一樣大小
    for (int i = 0; i < length1; i++)
        if (array[i].Length != length2)
            return null;

    int[] ans = new int[length1 * length2];

    EDirection dir = EDirection.RIGHT;
    int x = 0;
    int y = 0;
    int index = 0;

    while(index < length1 * length2)
    {
        ans[index] = array[y][x];
        switch(dir)
        {
            case EDirection.RIGHT: //向右
                if (x + y == length2 - 1)
                {
                    dir = EDirection.DOWN;
                    y += 1;
                }
                else
                    x += 1;
                break;
            case EDirection.DOWN: //向下
                if (x - y == length2 - length1)
                {
                    dir = EDirection.LEFT;
                    x -= 1;
                }
                else
                    y += 1;
                break;
            case EDirection.LEFT: //向左
                if (x + y == length1 - 1)
                {
                    dir = EDirection.UP;
                    y -= 1;
                }
                else
                    x -= 1;
                break;
            case EDirection.UP: //向上
                if (y == x + 1)
                {
                    dir = EDirection.RIGHT;
                    x += 1;
                }
                else
                    y -= 1;
                break;
        }
        index++;
    }

    return ans;
}
看更多先前的回應...收起先前的回應...

哈哈,我只是分享而已啦!我沒有那麼聰明可以設計題目XD
剛剛看到以下這段程式碼就覺得小魚大大很細心,雖然原網站的題目上是說傳入m * n的二維陣列,不過我忽略這點沒有再說明上註明!但是大大還是考慮到他傳進來的有可能是梯形陣列!所以如果不符合要解析的陣列就直接return掉!

for (int i = 0; i < length1; i++)
    if (array[i].Length != length2)
        return null;

接下來這行,大大應該是用enum去控制上、下、左、右的流程。

EDirection dir = EDirection.RIGHT;

最後也是去算有沒有超過陣列長度,如果有的話就轉換流程,然後更新接下來要抓的位置!如果有哪裡搞錯了還麻煩告訴我/images/emoticon/emoticon13.gif,下禮拜也歡迎燒腦XD

小魚 iT邦大師 1 級 ‧ 2018-06-02 14:01:57 檢舉

分享也是要花時間找題目啊,
我就沒什麼時間找題目,
只做別人準備好的題目,哈~

是用enum沒錯,
我覺得四個方向分開來處理比較好處理,
而且重點是array[y][x],
我原本用array[x][y]就完全不對,
這方面就比較沒那麼直觀...
/images/emoticon/emoticon39.gif

我剛剛本來想說把switch內的x和y互換應該就可以,
不過我突然發現到一件事情,
大大在判斷什麼時候要轉向左的條件是(x == y)
但如果傳進來的是像範例二的陣列:
[
[1, 2, 3 ],
[4, 5, 6 ],
[7, 8, 9 ],
[10,11,12]
]
他跑完RIGHT的部分時,會以y=0x=2的值進入DOWN
之後在跑DOWN的時候,會在y=2x=2,回傳9的地方,就會因為(x == y)的關係進去LEFT中,而不會繼續往下走到12!

不好意思,早上剛睡醒回覆沒有仔細看清楚.../images/emoticon/emoticon16.gif

小魚 iT邦大師 1 級 ‧ 2018-06-02 16:11:14 檢舉

對齁,
忘了兩個有可能不一樣,
看來我應該拿3x4來試試看...

小魚 iT邦大師 1 級 ‧ 2018-06-02 16:30:45 檢舉

偷偷把原稿改了兩個地方,
目前測試 3x3, 3x4, 4x3 都正確,
應該是沒問題了吧...

小魚 iT邦大師 1 級 ‧ 2018-06-02 17:09:48 檢舉

https://ithelp.ithome.com.tw/upload/images/20180602/201056940uh4KUdJsX.jpg
看起來好像討論很熱烈的感覺
/images/emoticon/emoticon01.gif

感覺這樣應該沒問題了/images/emoticon/emoticon13.gif
我一開始也是要用這樣子的方式!可是那時候邏輯打結了,一直想不出來要怎樣判斷才能讓他再對的地方轉向/images/emoticon/emoticon20.gif
沒想到大大可以再那麼短的時間修改完成,感覺思緒很清晰XD

ㄛ對啊!因為一場意外/images/emoticon/emoticon25.gif
不曉得有沒有辦法可以把多留的留言刪除XD

小魚 iT邦大師 1 級 ‧ 2018-06-02 21:17:00 檢舉

似乎是沒辦法的,
除非請小財神刪資料庫...

fysh711426 iT邦研究生 2 級 ‧ 2018-06-02 22:34:01 檢舉

恩,因為一場意外,哈哈哈/images/emoticon/emoticon16.gif

小魚 iT邦大師 1 級 ‧ 2018-06-02 23:33:58 檢舉

說不定會帶來人氣
/images/emoticon/emoticon01.gif

如果能就太好了,哈哈哈/images/emoticon/emoticon37.gif

我要留言

立即登入留言