refer to: https://www.algoexpert.io/questions/Apartment%20Hunting
Arrays.Apartment Hunting.Hard
- 题目描述：
给定一组连续的block的信息链表，每个元素代表每一个街区的设备情况（是否有学校，健身房，超市），再给定一个requirements数组，包含需要考虑的元素（学校，健身房，超市）
求住在哪一个街区会使得去学校，健身房，超市的最大距离最小。
- 分析
1. 使用三个for循环
顺序遍历每一个街区，对于每一个街区，遍历每一个reqs，计算当前的街区满足所有reqs的至少要走多少步（所有reqs满足的最大值），最大值存到一个res数组中，代表住在每一个街区的前往三个位置至少要走多少步
计算res数组的最小值，最小的（至少走多少步到达学校，超市，健身房）
- 代码
-
1 import java.util.*; 2 3 //O(b^2*r) time | O(b) space 4 //b is the number of blocks, r is the number of requirements 5 class Program { 6 public static int apartmentHunting(List<Map<String, Boolean>> blocks, String[] reqs) { 7 int[] res = new int[blocks.size()];//the maxDistance needed to go to 3 places at each block 8 Arrays.fill(res, Integer.MIN_VALUE);//need to calculate max value, initialize as min value 9 10 for(int i = 0; i < blocks.size(); i++){//iterate all blocks 11 for(String req: reqs){//iterate all requiements 12 int minReq = Integer.MAX_VALUE;//min distance to satisfy each requirement at current block 13 for(int j = 0; j < blocks.size(); j++){ 14 if(blocks.get(j).get(req)){//check the list, if the boolean value is true, we find the req 15 minReq = Math.min(minReq, Math.abs(i-j));//update the min distance 16 } 17 } 18 res[i] = Math.max(res[i], minReq); //update the maxDistance needed to go to 3 places at each block 19 } 20 } 21 return getMinIdx(res);//get the min index according to the res array. 22 23 } 24 public static int getMinIdx(int[] Array){ //function to get min_value index from an array 25 int idx_min = 0; 26 int min_value = Integer.MAX_VALUE; 27 for(int i=0; i < Array.length; i++){ 28 if(min_value > Array[i]){ 29 min_value = Array[i]; 30 idx_min = i; 31 } 32 } 33 return idx_min; 34 } 35 }2. 简化时间复杂度：对于每一个地点，提前计算每一个街区到达每一个地点的最短距离，存储起来，得到一个二元数组，然后对于每一个街区，求每一个街区到达三个地点至少走多少步（maxDisAtBlocks）,这里得到一个一元数组存储maxDisAtBlocks，最后求maxDisAtBlocks的最小值的索引号。
-
代码
1 import java.util.*;
2 //O(br) time | O(br) space
3 //b: # of blocks, r: # of requirements
4 class Program {
5 public static int apartmentHunting(List<Map<String, Boolean>> blocks, String[] reqs) {
6 int[][] minDisFromBlocks = new int[reqs.length][];
7 for(int i = 0; i < reqs.length; i++){
8 minDisFromBlocks[i] = getMinDistance(blocks, reqs[i]);
9 //get the min distance from each block to each req.
10 }
11 int[] maxDisAtBlocks = getMaxDistanceAtBlocks(blocks, minDisFromBlocks);
12 //get the max distance for each block to go to the three required places13 return getMinIdx(maxDisAtBlocks);
14 }
15
16 public static int[] getMinDistance(List<Map<String, Boolean>> blocks, String req){
17 //the min distance from each block to each req.
18 int[] minDistance = new int[blocks.size()];
19 int closeReqIdx = Integer.MAX_VALUE;
20 for(int i = 0; i < blocks.size(); i++){
21 if(blocks.get(i).get(req)) closeReqIdx = i;
22 minDistance[i] = Math.abs(i-closeReqIdx);
23 }
24 for(int i = blocks.size() - 1; i >= 0; i--){
25 if(blocks.get(i).get(req)) closeReqIdx = i;
26 minDistance[i] = Math.min(minDistance[i], Math.abs(i-closeReqIdx));
27 }
28 return minDistance;
29 }
30
31 public static int[] getMaxDistanceAtBlocks(
32 //get the max distance to all reqs from each block
33 List<Map<String, Boolean>> blocks, int[][] minDisFromBlocks){
34 int[] maxDisAtBlocks = new int[blocks.size()];
35 for(int i = 0; i < blocks.size(); i++){
36 int[] minDisAtBlock = new int[minDisFromBlocks.length];
37 for(int j = 0; j < minDisFromBlocks.length; j++){
38 minDisAtBlock[j] = minDisFromBlocks[j][i];
39 }
40 maxDisAtBlocks[i] = arrayMax(minDisAtBlock);
41 }
42 return maxDisAtBlocks;
43 }
44
45 public static int getMinIdx(int[] Array){
46 //function to get min_value index from an array
47 int idx_min = 0;
48 int min_value = Integer.MAX_VALUE;
49 for(int i=0; i < Array.length; i++){
50 if(min_value > Array[i]){
51 min_value = Array[i];
52 idx_min = i;
53 }
54 }
55 return idx_min;
56 }
57
58 public static int arrayMax(int[] array){
59 //get the max value from an array
60 int max = array[0];
61 for(int a: array){
62 if(a>max){
63 max = a;
64 }
65 }
66 return max;
67 }
68
69 }