いいものをつくろう

CTOの日記

アルゴリズム

leetcode medium rotate image

投稿日:

みなさま、目標に近づいてますでしょうか?

おはようございます。

今日は配列のインプレイス回転の問題です。

leetcode 48 rotate image

個人的にはこれはめっちゃ難しです。

これが出されたら解けないですw

いかが私の最初の回答です。完成すらいきません。。。

class Solution:
    def __init__(self):
        self.__di = 'right'

    def shift(self, matrix, s, e, i, j):
        if self.__di == 'right':
            self.__di == 'down'
        elif self.__di == 'down':
            self.__di == 'left'
        elif self.__di == 'left':
            self.__di == 'up'
        elif self.__di == 'up':
            self.__di == 'right'
        else:
            assert(True)

    def next(self, matrix, s, e, i, j):
        if self.__di == 'right':
            j += 1
        elif self.__di == 'down':
            i -= 1
        elif self.__di == 'left':
            j -= 1
        elif self.__di == 'up':
            i += 1
        else:
            assert(True)

        if self.is_valide(matrix, s, e, i, j):
            pass
        else:
            # revert
            if self.__di == 'right':
                j -= 1
            elif self.__di == 'down':
                i += 1
            elif self.__di == 'left':
                j += 1
            elif self.__di == 'up':
                i -= 1
            else:
                assert(True)
            self.shift(matrix, s, e, i, j)
            self.next(matrix, s, e, i, j)

        return (i, j)


    def is_valide(self, matrix, s, e, i, j):
        if i >= s and i <= e and j >=s and j <= e:
            return True
        else:
            return False

    def rotate(self, matrix: List[List[int]]) -> None:
        rows = len(matrix)
        cols = len(matrix[0])

        for r in range(int(math.ceil(rows/2))):
            s = r
            e = (cols - r) - 1
            print("s:%s, e:%s" % (s, e))
            print("left upper corner:%s" % matrix[s][s])
            print("right upper corner:%s" % matrix[s][e])

 

自分で正解にたどり着かなかったので

回答を見ました。

そして自分で複写したものがこちらです

class Solution():
    def show(self, mat: List[List[int]]):
        for row in mat:
            print (row)


    def rotate(self, mat: List[List[int]]) -> None:
        N = 4
        for x in range(0, int(N/2)):

            # Consider elements in group
            # of 4 in current square
            for y in range(x, N-x-1):

                # store current cell in temp variable
                temp = mat[x][y]
                mat[x][y] = mat[N-1-y][x] # left-bottom to left-top
                mat[N-1-y][x] = mat[N-1-x][N-1-y]
                mat[N-1-x][N-1-y] = mat[y][N-1-x]
                mat[y][N-1-x] = temp
                #
                # # move values from right to top
                # mat[x][y] = mat[y][N-1-x]
                #
                # # move values from bottom to right
                # mat[y][N-1-x] = mat[N-1-x][N-1-y]

matrix = [
    [ 1, 2, 3, 4],
    [ 5, 6, 7, 8],
    [ 9,10,11,12],
    [12,13,14,15]
]

Solution().rotate(matrix)
Solution().show(matrix)

 

この回転を全部表す技が秀逸すぎやしませんか!?

こんなもの正しく思いつくにはどうしたらいいんですか?!

 

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.