Mock Interview - Google #1

Reverse String

class Solution {
    public void reverseString(char[] s) {
        int l = s.length;
        for (int i = 0; i < l / 2; i++) {
            char temp = s[i];
            s[i] = s[l - i - 1];
            s[l-i-1] = temp;
        }
    }
}

Runtime: 1 ms, faster than 96.34% of Java online submissions for Reverse String.
Memory Usage: 46.1 MB, less than 34.80% of Java online submissions for Reverse String.

5분컷~~~!

Count Submatrices With All Ones

class Solution {
 
    public int numSubmat(int[][] mat) {
        int h = mat.length;
        int w = mat[0].length;
        
        //int[][] ea = new int[h][w];
        
        int ea = 0; 
        boolean prev = false; 
    
        return helper(mat, ea, 0, 0, false); 
        
    }
    
    public int helper(int[][] mat, int ea, int i, int j, boolean prev) {
        if (i >= mat.length || j >= mat[0].length) {
            return 0;
        }
        
        if (prev && mat[i][j] == 1) {
            ea++;
        }
        
        if (mat[i][j] == 1) {
            ea++;
            prev = true; 
        } else {
            prev = false; 
        }
        
        return ea + helper(mat, ea, i + 1, j, prev) + helper(mat, ea, i, j + 1, prev);
        
    }
}

2 / 72 Test Cases Passed

1st attempt
재귀를 사용하기..
1들을 2번씩 더해버려서 실패

class Solution {
 
    public int numSubmat(int[][] mat) {
        int h = mat.length;
        int w = mat[0].length;
        
        //int[][] ea = new int[h][w];
        
        int ea = 0; 
        //boolean prev = false; 
        
        for (int i = 0; i < h; i++) {
            int cont = 0; 
            
            for (int j = 0; j < w; j++) {
                if (mat[i][j] == 1) {
                    ea = ea + 1 + cont;
                    cont++;
                } else {
                    cont = 0; 
                }
            }
           
        }
        
        
        for (int k = 0; k < w; k++) {
            int cont2 = 0; 
            for (int l = 0; l < h; l++) {
                
                if (mat[l][k] == 1) {
                    ea += cont2;
                    cont2++; 
                } else {
                    cont2 = 0; 
                }
                
            }
            
        }
    
        return ea; 
        
    }
}

12 / 72 test cases passed.

2nd attempt


한 방향으로만 가는것을 세고 여러 방향은 못셈..ㅠ
greedy나 dfs 써야할 것 같은데 시간부족으로 탐구는 못했읍니다