[Mock] Google

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

My Answer 1: Accepted (Runtime: 192 ms - 80.92% / Memory Usage: 18.4 MB - 81.19%)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

My Answer 2: Accepted (Runtime: 192 ms - 80.92% / Memory Usage: 18.5 MB - 57.88%)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        mid = len(s) // 2 - 1
        for i in range(len(s)-1, mid, -1):
            temp = s[i]
            s[i] = s[len(s)-1-i]
            s[len(s)-1-i] = temp

양심상.. 한번 더 풀어줬읍니다

---

1504. Count Submatrices With All Ones

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

My Answer 1: Wrong Answer (20 / 72 test cases passed.)

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        count = 0
        
        # 1 의 개수
        for i in range(len(mat)):
            count += mat[i].count(1)
        
        def rowfunc(mat, i, j, cnt):
            if mat[i][j] == 0:
                return cnt
            
            if i + 1 < len(mat) and mat[i+1][j] == 1:
                cnt += rowfunc(mat, i+1, j, 0) + 1
            
            return cnt
        
        def colfunc(mat, i, j, cnt):
            if mat[i][j] == 0:
                return cnt
            
            if j + 1 < len(mat[0]) and mat[i][j+1] == 1:
                cnt += colfunc(mat, i, j+1, 0) +1
                
            return cnt
            
        def squarefunc(mat, i, j, cnt):
            if mat[i][j] == 0:
                return cnt
            
            if i + 1 < len(mat) and mat[i+1][j] == 1 and j + 1 < len(mat[0]) and mat[i][j+1] == 1 and mat[i+1][j+1] == 1:
                cnt += squarefunc(mat, i+1, j, 0) +1
                cnt += squarefunc(mat, i, j+1, 0)
                cnt += squarefunc(mat, i+1, j+1, 0)
            
            return cnt
        
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                if mat[i][j] == 1:
                    count += rowfunc(mat, i, j, 0)
                    count += colfunc(mat, i, j, 0)
                    count += squarefunc(mat, i, j, 0)
        
        return count

원래 이렇게 풀 생각이 아니었는데 시간관계상 이렇게 됐읍니다...

생각난 거는 Backtracking / 재귀였음

def isSubmatrix(mat, i, j, cnt):
    print(i, j)
    if mat[i][j] == 0:
        return cnt
           
    if i + 1 < len(mat) and mat[i+1][j] == 1:
        cnt += isSubmatrix(mat, i+1, j, 0) +1
           
    if j + 1 < len(mat[0]) and mat[i][j+1] == 1:
        cnt += isSubmatrix(mat, i, j+1, 0) +1
           
    return cnt

이런 식으로 하나의 재귀 함수를 쓰려고 했으나.. fail