資訊專欄INFORMATION COLUMN
摘要：從第一個(gè)點(diǎn)出發(fā)表示空地，表示已經(jīng)走過(guò)的空地，避免重復(fù)?？雌饋?lái)就像一層層的涂色。
1 0 2 0 1 0 0 0 0 0 0 0 1 0 0
第一個(gè)building, 把涂色把0變成-1, 同一層最終會(huì)涂成相同顏色-1
1 -1 2 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1
距離矩陣
0 1 0 5 0 1 2 3 4 5 2 3 0 5 6
第一個(gè)building, 把涂色把-1變成-2, 同一層最終會(huì)涂成相同顏色-2
1 -2 2 -2 1 -2 -2 -2 -2 -2 -2 -2 1 -2 -2
距離矩陣
0 6 0 6 0 6 6 6 6 6 8 8 0 8 8
第一個(gè)building, 把涂色把-2變成-3, 同一層最終會(huì)涂成相同顏色-3
1 -3 2 -3 1 -3 -3 -3 -3 -3 -3 -3 1 -3 -3
距離矩陣
0 9 0 9 0 9 8 7 8 9 10 9 0 9 10
為了避路徑重復(fù)，我們有兩種方法，一種是用額外的空間visited, 一種是改變輸入。
從第一個(gè)點(diǎn)出發(fā)0表示空地，-1表示已經(jīng)走過(guò)的空地，避免重復(fù)。
從第二個(gè)點(diǎn)出發(fā)-1表示空地，-2表示已經(jīng)走過(guò)的空地，避免重復(fù)。
看起來(lái)就像一層層的涂色。
public class Solution {
private int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
private int min = Integer.MAX_VALUE;
public int shortestDistance(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
int m = grid.length, n = grid[0].length;
int[][] distance = new int[m][n]; // 記錄累加距離
int start = 0;
for(int i=0; i q = new ArrayDeque<>();
q.offer(new int[]{i,j});
int level = 0, m = grid.length, n = grid[0].length;
min = Integer.MAX_VALUE;
while(!q.isEmpty()){
int size = q.size(); // 涂色的時(shí)候，記錄當(dāng)前層的大小
level++; // 進(jìn)入下一層，需要增加距離
for(int k=0; k=0 && y>=0 && x
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66713.html
Problem You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or...
摘要：如果該沒(méi)有被之前所有的訪問(wèn)過(guò)，就不可能成為答案根據(jù)要求的位置能到所有的，其他與它相鄰的點(diǎn)也是這樣。和用矩陣比，縮小了每次遍歷的范圍。 Shortest Distance from All Buildings 題目鏈接：https://leetcode.com/problems... 這道題要求最短的距離，一般這種要求可以到的地方的距離，都需要把整個(gè)圖遍歷一遍，遍歷一般就是bfs和dfs...
摘要：存放過(guò)程中的所有集合為所有的結(jié)尾，則順序存放這個(gè)結(jié)尾對(duì)應(yīng)的中的所有存放同一個(gè)循環(huán)的新加入的，在下一個(gè)循環(huán)再依次對(duì)其中元素進(jìn)行進(jìn)一步的把首個(gè)字符串放入新，再將放入，并將鍵值對(duì)放入，進(jìn)行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...
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...
摘要：代碼第一次寫(xiě)入就先不比較第一次寫(xiě)入就先不比較哈希表法復(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 ...
閱讀 2879·2021-09-01 10:30
閱讀 1733·2019-08-30 15:52
閱讀 1045·2019-08-29 18:40
閱讀 1205·2019-08-28 18:30
閱讀 2451·2019-08-23 17:19
閱讀 1401·2019-08-23 16:25
閱讀 2801·2019-08-23 16:18
閱讀 3058·2019-08-23 13:53
