空놀이

https://leetcode.com/problems/01-matrix/

재귀함수 중급 문제인데 너무 오래걸렸다.

막상 짜고 보면 별거 없었는데....

class Solution(object):
    def findzero(self, r, c):
        if self.mat[r][c] == 0:
            self.distanceMap[r][c] = 0
            return self.distanceMap[r][c] + 1

        if self.distanceMap[r][c] != 10000:
            return self.distanceMap[r][c] + 1

        self.distanceMap[r][c] = 10001

        if(c > 0):
            target_r = r
            target_c = c-1
            if self.distanceMap[target_r][target_c] != 10001:
                findDistance = self.findzero(target_r, target_c)
                if self.distanceMap[r][c] > findDistance:
                    self.distanceMap[r][c] = findDistance
                    
        if(c < self.len_c - 1):
            target_r = r
            target_c = c+1            
            if self.distanceMap[target_r][target_c] != 10001:
                findDistance = self.findzero(target_r, target_c)
                if self.distanceMap[r][c] > findDistance:
                    self.distanceMap[r][c] = findDistance

        if(r > 0):
            target_r = r-1
            target_c = c
            if self.distanceMap[target_r][target_c] != 10001:
                findDistance = self.findzero(target_r, target_c)
                if self.distanceMap[r][c] > findDistance:
                    self.distanceMap[r][c] = findDistance

        if(r < self.len_r - 1):
            target_r = r+1
            target_c = c            
            if self.distanceMap[target_r][target_c] != 10001:
                findDistance = self.findzero(target_r, target_c)
                if self.distanceMap[r][c] > findDistance:
                    self.distanceMap[r][c] = findDistance


        return self.distanceMap[r][c] + 1
            
        
    def updateMatrix(self, matrix):
        self.len_r = len(matrix)
        self.len_c = len(matrix[0])
        
        self.distanceMap = [[10000 for k in range(self.len_c)] for l in range(self.len_r)]
        self.mat = matrix

        for i in range(self.len_r):
            for j in range(self.len_c):
                self.distanceMap[i][j] = 10000
                self.findzero(i, j)
                
        return self.distanceMap
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """

문제 : https://leetcode.com/problems/implement-queue-using-stacks/

스택은 나중에 들어간 것이 먼저 나오고,

큐는 먼저 들어간 것이 먼저 나온다.

큐와 스택을 헷깔려서, 마지막에 넣은걸 먼저 꺼냈다가 시간이 좀 걸렸다.

파이썬의 리스트를 활용해서 아래와 같이 구현해 보았다.

class MyQueue(object):

    def __init__(self):
        self.data = []
        self.size = 0
        
        """
        Initialize your data structure here.
        """
        

    def push(self, x):
        self.data.append(x)
        self.size += 1
        #print self.data
        
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        
    def pop(self):
        if(self.size > 0):
            self.size -= 1
            pop_data = self.data[0]
            self.data.remove(pop_data)
            return pop_data
            
        return 0
        
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        

    def peek(self):
        if(self.size > 0):
            #print self.data[0]
            return self.data[0]
        else:
            return 0
        
        """
        Get the front element.
        :rtype: int
        """
        

    def empty(self):
        if self.size == 0:
            return 1
        else:
            return 0
        
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

https://leetcode.com/problems/number-of-islands/

733 Flood Fill 과 비슷한 재귀 함수 문제..

약간만 더 생각하면 되는 문제였다. ㅎㅎ

오랜만에 파이썬을 했더니 프린트 하는 문법이 좀 헷깔렸다.

디버깅을 하기 위해 파이썬 2.x에서 프린트를 하려면 아래와 같이 해주면 되었다

괄호도 필요없고, 출력할 값은 %뒤에 괄호로 묶어서 적어주면 되었다.

print "print "grid[%d][%d] = %s" % (i, j, grid[i][j])

내가 쓴 답은 허접하지만 공유해 보겠다. ㅎㅎ

class Solution(object):
    
    def checkIslands(self, grid, r, c):        
        if self.g[r][c] == '0':
            return 0
        self.g[r][c] = '0'
        
        if r > 0:         self.checkIslands(grid, r-1, c)
        if r < self.r_len - 1: self.checkIslands(grid, r+1, c)   
        if c > 0:         self.checkIslands(grid, r, c - 1)
        if c < self.c_len - 1: self.checkIslands(grid, r, c+1)   
         
        return 1
    
    def numIslands(self, grid):
        self.r_len = len(grid)
        if(self.r_len > 0):
            self.c_len = len(grid[0])
        else:
            return 0
        cnt = 0
        self.g = grid

        for i in range(self.r_len):
            for j in range(self.c_len):
                if self.checkIslands(grid, i, j) == 1:
                    cnt+=1
                
        return cnt
        """
        :type grid: List[List[str]]
        :rtype: int
        """
       

사내 역량평가 준비를 위해 기초 문법 먼저 공부하기로 했다.

1. 232 : implement Queue using Stacks

2. 283 : Move Zeroes

3. 290 : word pattern

4. 485 : Max Consecutive Ones

5. 492 : Construct the Rectangle

BST

6. 501. Find Mode in Binary Search Tree
Minimum Absolute Difference in BST
543. Diameter of Binary Tree
563. Binary Tree Tilt

linked list
203. Remove Linked List Elements
206. Reverse Linked List

conversion
504. Base 7

string
557. Reverse Words in a String III
189. Rotate Array
599. Minimum Index Sum of Two Lists

matrix
566. Reshape the Matrix

783. Minimum Distance Between BST Nodes

Hash 

705. Design HashSet

그 다음에 graph로 넘어가기