https://leetcode-cn.com/problems/maximize-distance-to-closest-person/
我们将有人的座位的下标记录到一个list中,剩下的事情就是要找一个点,距离list中某个元素的最大距离
以示例1为例,我们构造了一个list,为[0,4,6],那么你想找的那个点的下标一定是在0-4和4-6之间,所以只需要求出他们之间的中点距离即可。以示例2为例,我们构造了一个list,为[0],那么你想找的那个店的下标一定在0-seats.length之间,依次比较即可。
所以我们可以将此题抽象出来,假设有一个seats数组,为[a0,a1,a2.....an],其中有人的为i,j,k,那么我们要找的点就一定在0-i,i-j,j-k和k-seats.length之间,依次比较即可。
public class Main {
public static void main(String[] args) {
Main main = new Main();
int[] a = {1, 0, 0, 0, 1, 0, 1};
System.out.println(main.maxDistToClosest(a));
}
public int maxDistToClosest(int[] seats) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < seats.length; i++) {
if (seats[i] == 1)
list.add(i);
}
int start = list.get(0);
int end = seats.length - list.get(list.size() - 1) - 1;
int max = Math.max(start, end);
for (int i = 0; i < list.size() - 1; i++) {
int temp = (list.get(i + 1) - list.get(i)) / 2;
if (temp > max) max = temp;
}
return max;
}
}
https://leetcode-cn.com/problems/reveal-cards-in-increasing-order/
提供一个新思路,以[17,13,11,2,3,5,7]为例,首先新建等长list=[1,2,3,4,5,6,7],然后对新的list按照题目的做法处理得到[1,3,5,7,4,2,6]。这时候注意[1,3,5,7,4,2,6]和[2,3,5,7,11,13,17]是一一对应的,因此我们构建对应关系[(1,2),(3,3),(5,5),(7,7),(4,11),(2,13),(6,17)] 最后按照元组的第一个元素排序得到的结果就是答案 [x1,x2,x3,x4,x5,x6,x7] -> [2,3,5,7,11,13,17] [1,2,3,4,5,6,7] -> [1,3,5,7,4,2,6] 从->右边得到对应关系,然后左边用这个对应关系就可以得到x1,x2,....x7
public int[] deckRevealedIncreasing(int[] deck) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < deck.length; i++) {
list.add(i + 1);
}
int len = list.size();
boolean flag = true;
for (int i = 0; i < list.size(); i++) {
if (!flag) {
int temp = list.get(i);
list.remove(i);
i--;
list.add(temp);
flag = true;
} else {
flag = false;
}
}
Arrays.sort(deck);
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
map.put(list.get(i), deck[i]);
}
int[] result = new int[len];
for (int i = 0; i < len; i++) {
result[i] = map.get(i + 1);
}
return result;
}