Mock Interview - Google #1
2678 ワード
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 Passed1st 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 써야할 것 같은데 시간부족으로 탐구는 못했읍니다
Reference
この問題について(Mock Interview - Google #1), 我々は、より多くの情報をここで見つけました https://velog.io/@jwade/Mock-Interview-Google-1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol