상세 컨텐츠

본문 제목

[Go] Array and String - Spiral Matrix

Go/Leet Code

by Gopythor 2022. 3. 29. 20:51

본문

728x90
반응형

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

My Code

func spiralOrder(matrix [][]int) []int {
    m, n, d := len(matrix), len(matrix[0]), "right"
    row, col := 0, -1
    result := make([]int, m*n)
    right, down, left, up := n, m, 0, 0
    i := 0

    for i < len(result) {
        if d == "right" {
            for j := col + 1; j < right; j++ {
                if i == len(result) {
                    break
                }
                col = j
                result[i] = matrix[row][col]
                i++

            }
            up++
            d = "down"
        }

        if d == "down" {
            for j := row + 1; j < down; j++ {
                if i == len(result) {
                    break
                }
                row = j
                result[i] = matrix[row][col]
                i++

            }
            right--
            d = "left"
        }

        if d == "left" {
            for j := col - 1; j > left-1; j-- {
                if i == len(result) {
                    break
                }
                col = j
                result[i] = matrix[row][col]
                i++

            }
            down--

            d = "up"
        }

        if d == "up" {
            for j := row - 1; j > up-1; j-- {
                if i == len(result) {
                    break
                }
                row = j
                result[i] = matrix[row][col]
                i++
            }
            left++
            d = "right"

        }

    }

    return result
}
  • I was focusing on implementing code than simplicity.
  • So i made direction variable which is string
  • result slice will be made based on length of len(matrix) * len(matrix[0])
  • Restriction variables are also declared.
  • For loop will run until i reaches to end of slice.
  • But this doesn't work. So I put if condition which checks i in every for loop which allocate values to result slice.
  • Direction is clockwise.Right -> Down -> Left -> Up.
  • Becuase for loop runs until end of restrict, if condition for break is needed.
  • In right if coonditon, every row is printed so up will be increament.
  • and change direction to down.

sample 0 ms submission & sample 2000 KB submission

func spiralOrder(matrix [][]int) []int {
    m := len(matrix)
    n := len(matrix[0])

    // these pointers below act as a wall
    left := 0
    right := n - 1
    top := 0
    bottom := m - 1

    result := []int{}

    for left <= right && top <= bottom {
        // move from top left to top right
        for i := left; i <= right; i++ {
            result = append(result, matrix[top][i])
        }
        top++
        if  left > right || top > bottom {
            break
        }
        // move from top right to bottom right
        for i := top; i <= bottom; i++ {
            result = append(result, matrix[i][right])
        }
        right--
        if  left > right || top > bottom {
            break
        }
        // move from bottom right to bottom left
        for i := right; i >= left; i-- {
            result = append(result, matrix[bottom][i])
        }
        bottom--
        if  left > right || top > bottom {
            break
        }
        // move from bottom left to top left 
        for i := bottom; i >= top; i-- {
            result = append(result, matrix[i][left])
        }
        left++
        if  left > right || top > bottom {
            break
        }
    }

    return result
}

func print(t int, b int, l int, r int) {
    fmt.Printf("%v-%v-%v-%v\n",t,b,l,r)
}

sample 1 ms submission

func spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    res := make([]int, 0)
    top, left, bottom, right := 0, 0, m - 1, n - 1
    for len(res) < m * n {
        for j := left; j <= right; j++ {
            res = append(res, matrix[top][j])
        }
        for i := top + 1; i <= bottom; i++ {
            res = append(res, matrix[i][right])
        }
        if top != bottom {
            for j := right - 1; j >= left; j-- {
                res = append(res, matrix[bottom][j])
            }
        }
        if left != right {
            for i := bottom - 1; i > top; i-- {
                res = append(res, matrix[i][left])
            }
        }
        top++
        left++
        bottom--
        right--
    }
    return res
}
  • Variable m and n will have lenght of row and column.
  • Slice named res will be made with 0 length.
  • top, left, bottom and right will be used as wall.
  • For loop will run until len reaches to m * n
  • First for loop in main for loop runs until j reaches to right.
  • In there, values will be appended to res.
  • After finishing it, Second for look will run until i reaches to bottom
  • After finishing it, if condition checks whether top is not same with bottom.
  • If so, for loop will run from right to left.
  • After this, if condition checks whether left is not same with right.
  • If so, for loop will run from bottom to top.
  • After rotation ends, top and left will increase and bottom and right will decrease.

sample 2 ms submission

func spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    res := make([]int, 0, m * n) 
    i, j := 0, 0
    for i  >= 0 && j >=0 && i < len(matrix) && j < len(matrix[0]) && matrix[i][j] >= -100 {
        res = append(res, matrix[i][j])
        matrix[i][j] = -101

        for j + 1 < n && matrix[i][j+1] >= -100 {
            j++
            res = append(res, matrix[i][j])
            matrix[i][j] = -101
        }

        for i + 1 < m && matrix[i+1][j] >= -100 {
            i++
            res = append(res, matrix[i][j])
            matrix[i][j] = -101
        }

        for j - 1 >= 0 && matrix[i][j-1] >= -100 {
            j--
            res = append(res, matrix[i][j])
            matrix[i][j] = -101
        }

        for i - 1 >= 0 && matrix[i-1][j] >= -100 {
            i--
            res = append(res, matrix[i][j])
            matrix[i][j] = -101
        }

        j++
    }
    return res
}

sample 1800 KB submission

func spiralOrder(matrix [][]int) []int {
    var res []int
    m, n := len(matrix), len(matrix[0])
    up, down, left, right := 0, m-1, 0, n -1
    for {
        for i := left; i <= right; i++{
            res = append(res, matrix[up][i])
        }
        // 避免上下重叠
        up += 1
        if up > down {
            break
        }

        for i := up; i <= down; i++ {
            res = append(res, matrix[i][right])
        }
        // 避免左右重叠
        right -= 1
        if right < left {
            break
        }
        for i := right; i >= left; i-- {
            res  = append(res, matrix[down][i])
        }

        // 避免上下重叠
        down -= 1
        if down < up {
            break
        }
        for i := down; i >= up; i-- {
            res = append(res, matrix[i][left])
        }

        //避免左右重叠
        left += 1
        if left > right {
            break
        }


        // for i := ln; i <= rn; i++ {
        //     res = append(res, matrix[lm][i])
        // }
        // // 避免上下重叠
        // if lm + 1 > rm {
        //     break
        // }
        // for i := lm + 1; i <= rm; i++ {
        //     res = append(res, matrix[i][rn])
        // }
        // // 避免左右重叠
        // if rn -1 < ln {
        //     break
        // }

        // for i := rn -1 ; i >= ln; i-- {
        //     res = append(res, matrix[rm][i])
        // }
        // // 避免上下重叠
        // if rm - 1 < lm {
        //     break
        // }
        // for i := rm-1; i >=  lm + 1; i-- {
        //     res = append(res, matrix[i][ln])
        // }
        // // 避免左右重叠
        // if ln + 1 > rn {
        //     break
        // }

        // lm++
        // ln++
        // rm--
        // rn--
    }

    return res
}

sample 1900 KB submission

// traverse the contents of the matrix in clockwise spiral order
func spiralOrder(matrix [][]int) []int {
    result := []int{}

    rowCount := len(matrix)
    colCount := len(matrix[0])

    fmt.Println(rowCount)
    fmt.Println(colCount)
    done := make(map[string]bool)
    dr := []int{0, 1, 0, -1}
    dc := []int{1, 0, -1, 0}
    r := 0
    c := 0
    dir := 0
    for i := 0; i < (rowCount * colCount); {
        fmt.Println(i)
        strr := strconv.Itoa(r)
        strc := strconv.Itoa(c)
        key := strr + strc
        done[key] = true
        i += 1
        result = append(result, matrix[r][c])
        rc := r + dr[dir]
        cc := c + dc[dir]
        strr = strconv.Itoa(rc)
        strc = strconv.Itoa(cc)
        key = strr + strc
        if rc >= 0 && rc < rowCount && cc >= 0 && cc < colCount && !done[key] {
            r = rc
            c = cc
        } else {
            // every time we hit the wall or find a number already traversed
            // we change the direction
            dir = (dir + 1) % 4
            r += dr[dir]
            c += dc[dir]
        }

        fmt.Println("r,c,dir", r, c, dir)
    }

    return result
}
728x90
반응형

관련글 더보기

댓글 영역