Tuesday, December 30, 2014

LeetCode 59 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].


Solution

Code first:

vector<int> spiralOrder(vector<vector<int> > &matrix) {
    vector<int> result;
    if (matrix.size() < 1) 
        return result;
    int top = 0;
    int button = matrix.size() - 1;
    int left = 0;
    int right = matrix[0].size() - 1;
    while (top <= button && left <= right) {
        for (int x = left; x <= right; x++) { //left to right
            result.push_back(matrix[top][x]);
        }
        top++;

        for (int y = top; y <= button; y++) { //top to button
            result.push_back(matrix[y][right]);
        }
        right--;
        if (button >= top) { // check if the button line haven't been pushed
            for (int x = right; x >= left; x--) {
                result.push_back(matrix[button][x]);
            }
            button--;
        }

        if (right >= left) { //check if the left line haven't been pushed
            for (int y = button; y >= top; y--) {
                result.push_back(matrix[y][left]);
            }
            left++;
        }

    }
    return result;
}

The solution is easy to understand, just iterate upper left -> upper right -> lower right -> lower -> left -> upper left. So we need four variable top, button, left, right to shrink to center step by step. The only tricky part is when we move from right to left and button to top, we should check if there are still space for this two operations. In fact, when I implement this, I debugged almost one hour and than find this.


Written with StackEdit.

1 comment:

  1. bại, hắn cũng biết rõ thực lực của Nhạc Thành, ngay lúc này, cũng muốn nghe lời của Nhạc Thành.

    - Chúng ta nghĩ biện pháp qua, nhưng cứ lao ra, nhất định là rất khó khăn.

    Nhạc Thành nói.

    - Có phải muốn qua dãy núi ma thú, chúng ta cũng không có biện pháp gì, ngoại trừ xông vào, chúng ta còn có thể làm cái gì đây.dongtam
    mu moi ra hom nay
    tim phong tro
    http://nhatroso.com/
    nhạc sàn
    tổng đài tư vấn luật
    văn phòng luật hà nội
    tổng đài tư vấn luật
    thành lập công ty trọn gói
    http://we-cooking.com/
    chém gió
    trung tâm tiếng anh

    Trần gia Thanh niên nói, trong ánh mắt bất đắc dĩ vô cùng.

    - Chúng ta bây giờ đầu tiên phải biết ma thú ở dãy núi rốt cuộc là có bao nhiêu con, nếu không chúng ta sợ không thể qua được, nếu biết ró ma thú ở đây như thế nào, có lẽ ta có biện pháp.

    Nhạc Thành nói.

    Nhạc Thành sớm đã là nghĩ một số biện pháp, nếu gặp phải rất đông ma thú thì hắn sẽ cho mị người tiến vào bên trong tháp Hạo Thiên, sau đó bản thân dùng tới độn địa phù trực tiếp tiến vào lòng đất là được rồi.

    Nhưng Nhạc Thành không biết rõ vùng núi này có bao nhiêu con ma thú, vạn nhất đến lúc đi ra mà chui vào ổ ma thú, thì càng thêm phiền toái.

    ReplyDelete