程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode || Spiral Matrix

leetcode || Spiral Matrix

編輯:C++入門知識

leetcode || Spiral Matrix


problem:

 

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

 

Hide Tags Array 題意:順時針螺旋輸出矩陣

 

thinking:

(1)首先想到方法是DFS,把外圈的數字輸出之後,矩陣的行和列都縮減了2,遞歸調用。思路簡單。

 

(2)全局搜索,考慮用DFS。與方法一類似,只是DFS思路略有不同,這裡參考:http://www.cnblogs.com/remlostime/archive/2012/11/18/2775708.html

一直關注他的實現,簡潔高效,膜拜中

開一個數組用來保存,之前這個單元是否被使用過,並配合邊界判斷,DFS,最後得出結果。空間復雜度O(n*m),時間O(n*m)

code:

 

class Solution {
private:
    int step[4][2];
    vector ret;
    bool canUse[100][100];
public:
    void dfs(vector > &matrix, int direct, int x, int y)
    {
        for(int i = 0; i < 4; i++)
        {
            int j = (direct + i) % 4;
            int tx = x + step[j][0];
            int ty = y + step[j][1];
            if (0 <= tx && tx < matrix.size() && 0 <= ty && ty < matrix[0].size() && canUse[tx][ty])
            {
                canUse[tx][ty] = false;
                ret.push_back(matrix[tx][ty]);                
                dfs(matrix, j, tx, ty);               
            }            
        }
    }
    
    vector spiralOrder(vector > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        step[0][0] = 0;
        step[0][1] = 1;
        step[1][0] = 1;
        step[1][1] = 0;
        step[2][0] = 0;
        step[2][1] = -1;
        step[3][0] = -1;
        step[3][1] = 0;
        ret.clear();
        memset(canUse, true, sizeof(canUse));
        dfs(matrix, 0, 0, -1);
        
        return ret;
    }
};


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved