-
Number of Recent Calls
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class RecentCounter {
Queue<Integer> ts;
public RecentCounter() {
ts = new LinkedList<>();
}
public int ping(int t) {
while (!ts.isEmpty() && ts.peek() < t - 3000) {
ts.poll();
}
ts.offer(t);
return ts.size();
}
} -
Shortest Bridge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64class Solution {
public int shortestBridge(int[][] a) {
Set<Integer> visited = new HashSet<>();
boolean done = false;
for (int i = 0; i < a.length; i++){
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 1) {
dfs(a, i, j, visited);
done = true;
break;
}
}
if (done) break;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++){
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
int dist1 = bfs(a, i, j, 1);
int dist2 = bfs(a, i, j, 2);
int dist = (dist1 - 1) + (dist2 - 1) + 1;
if (dist < min) min = dist;
}
}
}
return min;
}
private int bfs(int[][] a, int x, int y) {
Queue<int[]> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
q.offer(new int[]{x, y});
int dist = 0;
while (!q.isEmpty()) {
int len = q.size();
for (int i = 0; i < len; i++) {
int[] cur = q.poll();
if (cur[0] < 0 || cur[0] >= a.length | cur[1] < 0 || cur[1] >= a[0].length || visited.contains(cur[0] * a[0].length + cur[1])) continue;
if (a[cur[0]][cur[1]] == island) {
return dist;
}
visited.add(cur[0] * a[0].length + cur[1]);
q.offer(new int[]{cur[0] + 1, cur[1]});
q.offer(new int[]{cur[0] - 1, cur[1]});
q.offer(new int[]{cur[0], cur[1] + 1});
q.offer(new int[]{cur[0], cur[1] - 1});
}
dist++;
}
return Integer.MAX_VALUE / 2 - 1;
}
private void dfs(int[][] a, int i, int j, Set<Integer> visited) {
if (i < 0 || i >= a.length || j < 0 || j >= a[0].length || a[i][j] != 1 || visited.contains(i * a[0].length + j)) return;
a[i][j] = 2;
visited.add(i * a[0].length + j);
dfs(a, i+1, j, visited);
dfs(a, i-1, j, visited);
dfs(a, i, j-1, visited);
dfs(a, i, j+1, visited);
}
} -
Knight Dialer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class Solution {
int[][] stops = {{4,6}, {6,8}, {7,9}, {4,8}, {0,3,9}, {5,5}, {0,1,7}, {2,6}, {1, 3}, {2, 4}};
List<String> res = new ArrayList<>();
long ans = 0;
public int knightDialer(int N) {
if(N == 0) return 0;
long[][] dp = new long[N][10];
for(int i = 0; i < 10; i++){
dp[0][i] = 1;
}
for(int i = 1; i < N; i++){
for(int j = 0; j < 10; j++){
if(j == 5) continue;
if(j == 0){
dp[i][j] += dp[i-1][4] + dp[i-1][6];
}else if(j == 1){
dp[i][j] += dp[i-1][8] + dp[i-1][6];
}else if(j == 2){
dp[i][j] += dp[i-1][7] + dp[i-1][9];
}else if(j == 3){
dp[i][j] += dp[i-1][4] + dp[i-1][8];
}else if(j == 4){
dp[i][j] += dp[i-1][0] + dp[i-1][9] + dp[i-1][3];
}else if(j == 6){
dp[i][j] += dp[i-1][0] + dp[i-1][1] + dp[i-1][7];
}else if(j == 7){
dp[i][j] += dp[i-1][2] + dp[i-1][6];
}else if(j == 8){
dp[i][j] += dp[i-1][1] + dp[i-1][3];
}else if(j == 9){
dp[i][j] += dp[i-1][2] + dp[i-1][4];
}
dp[i][j] %= 1000000007;
}
}
for(int j = 0; j < 10; j++){
ans += dp[N-1][j];
ans %= 1000000007;
}
return (int)(ans);
}
}
近期评论