資訊專欄INFORMATION COLUMN
Problem
In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Example 1:
Input: [[0,1],[1,0]]
Output: 1
Example 2:
Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3:
Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1
Note:
1 <= A.length = A[0].length <= 100
Ai == 0 or Ai == 1
class Solution {
public int shortestBridge(int[][] A) {
//find the first island, using dfs
int m = A.length, n = A[0].length;
boolean[][] visited = new boolean[m][n];
Queue queue = new LinkedList<>(); //for bfs
int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
boolean found = false;
for (int i = 0; i < m; i++) {
if (found) break;
for (int j = 0; j < n; j++) {
if (A[i][j] == 1) {
found = true;
dfs(A, i, j, visited, dirs, queue);
break;
}
}
}
int count = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
for (int[] dir: dirs) {
int x = cur[0]+dir[0], y = cur[1]+dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) continue;
if (A[x][y] == 1) return count;
queue.offer(new int[]{x, y});
visited[x][y] = true;
}
}
count++;
}
return -1;
}
private void dfs(int[][] A, int i, int j, boolean[][] visited, int[][] dirs, Queue queue) {
int m = A.length, n = A[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || A[i][j] == 0 || visited[i][j]) return;
queue.offer(new int[]{i, j});
visited[i][j] = true;
for (int[] dir: dirs) {
dfs(A, i+dir[0], j+dir[1], visited, dirs, queue);
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72626.html
摘要：題目鏈接題目分析從給定的一個(gè)字符串中提取字符。若出現(xiàn)次數(shù)相同，則返回第一個(gè)符合條件的單詞。假定結(jié)果必定存在。思路先提取字符，轉(zhuǎn)換成小寫，并計(jì)算字符出現(xiàn)的次數(shù)。短則覆蓋，長(zhǎng)則拋棄。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D86 748. Shortest Completing Word 題目鏈接 748. Shortest Completing Word 題目分析 從給定的一個(gè)...
摘要：返回字符串中每一個(gè)字符離給定的字符的最短距離。否則，當(dāng)當(dāng)前下標(biāo)大于上一個(gè)出現(xiàn)字符的位置，且存在下一個(gè)字符時(shí)，距離為兩者中最小的那個(gè)。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D49 821. Shortest Distance to a Character 題目鏈接 821. Shortest Distance to a Character 題目分析 給定一個(gè)字符串s和一個(gè)字符...
Problem Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the l...
摘要：代碼第一次寫入就先不比較第一次寫入就先不比較哈希表法復(fù)雜度時(shí)間空間思路因?yàn)闀?huì)多次調(diào)用，我們不能每次調(diào)用的時(shí)候再把這兩個(gè)單詞的下標(biāo)找出來(lái)。我們可以用一個(gè)哈希表，在傳入字符串?dāng)?shù)組時(shí)，就把每個(gè)單詞的下標(biāo)找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...
Problem Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string. Example 1: Input: S = loveleetcode, C = eOutput: [3, 2, 1...
閱讀 1565·2021-11-25 09:43
閱讀 2349·2019-08-30 15:55
閱讀 1474·2019-08-30 13:08
閱讀 2687·2019-08-29 10:59
閱讀 825·2019-08-29 10:54
閱讀 1597·2019-08-26 18:26
閱讀 2559·2019-08-26 13:44
閱讀 2662·2019-08-23 18:36
