第一题：统计被覆盖的建筑
题目：
给你一个正整数
n，表示一个n x n的城市，同时给定一个二维数组buildings，其中buildings[i] = [x, y]表示位于坐标[x, y]的一个 唯一 建筑。如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。返回 被覆盖 的建筑数量。
思路：
也是借鉴了题解的优秀思路。
可以枚举给定的建筑中，每一行的和每一列的最大值和最小值，存入两个数组中，最后遍历一建筑数组，判断当前坐标的行和列是否大于该行/列的最小值，并且小于该行/列的最大值，那末这个坐标就是一个覆盖建筑。
代码实现
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
/**
* /\_̃__
* ( o.o )
* > ^ <
* 代码一遍过
*/
class Solution {
public int countCoveredBuildings(int n, int[][] buildings) {
int[][] r = new int[n+1][]; // 行，第 i 行的最大 x 值和最小 x 值
int[][] c = new int[n+1][]; // 列，第 j 列的最大 y 值和最小 y 值
for(int i = 0;i < buildings.length;i++) {
int x = buildings[i][0];
int y = buildings[i][1];
if(c[x] == null) c[x] = new int[]{y,y};
else {
c[x][0] = Math.min(c[x][0],y);
c[x][1] = Math.max(c[x][1],y);
}
if(r[y] == null) r[y] = new int[]{x,x};
else {
r[y][0] = Math.min(r[y][0],x);
r[y][1] = Math.max(r[y][1],x);
}
}
int ans = 0;
for(int i = 0;i < buildings.length;i++) {
int x = buildings[i][0];
int y = buildings[i][1];
if(y > c[x][0] && y < c[x][1] && x > r[y][0] && x < r[y][1])
ans ++;
}
return ans;
}
}
第二题：针对图的路径存在性查询 I
题目：
给你一个整数
n，表示图中的节点数量，这些节点按从0到n - 1编号。同时给你一个长度为
n的整数数组nums，该数组按 非递减 顺序排序，以及一个整数maxDiff。如果满足
|nums[i] - nums[j]| <= maxDiff（即nums[i]和nums[j]的 绝对差 至多为maxDiff），则节点i和节点j之间存在一条 无向边 。此外，给你一个二维整数数组
queries。对于每个queries[i] = [ui, vi]，需要判断节点ui和vi之间是否存在路径。返回一个布尔数组
answer，其中answer[i]等于true表示在第i个查询中节点ui和vi之间存在路径，否则为false。
思路：
借鉴了其他人的题解和自己的一些理解。
首先，想到的暴力解决方法就是穷举所有的两两一组的情况，然后，利用并查集的特点，将符合要求的放在同一个集合中，最后遍历所有的询问，看看是否在同一个集合中即可。但是由于数组的长度较大穷举所有的情况会出现超时的情况。
根据题目，观察可得出，数组是非递减数组，这个性质没有使用，根据这个性质，后一项一定大于或等于前一项，因此，只需要遍历所有的相邻的元素即可。因为如果出现了 a i + 1 − a i > m a x D i f f a_{i+1} - a{i} > maxDiff ai+1−ai>maxDiff 那末， i i i 前面的所有项，都不可能与第 i + 1 i+1 i+1 项相连接，因此，只要遇到 a i + 1 − a i > m a x D i f f a_{i+1} - a{i} > maxDiff ai+1−ai>maxDiff 情况，那末 i i i 前面的所有项一定互相联通，因此，可以优化。
代码实现
/**
* /\_̃__
* ( o.o )
* > ^ <
* 代码一遍过
*/
class Solution {
public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
boolean[] ans = new boolean[queries.length];
int[] p = new int[n];
// 初始化并查集
for(int i = 0;i < n;i++) p[i] = i;
// 遍历所有的两两配对（超时）
// for(int i = 0;i < n;i++)
// for(int j = i;j < n;j++)
// if(nums[j] - nums[i] <= maxDiff) p[j] = find(i,p);
// else break;
// 根据数组的特点，优化后
int index = 0;
for(int i = 0;i < n-1;i++) {
if(nums[i+1] - nums[i] > maxDiff) index = i+1;
p[i+1] = find(index,p); // 第 0 项一定是自己，因此从第 i + 1 项开始
}
for(int i = 0;i < queries.length;i++)
ans[i] = find(queries[i][0],p) == find(queries[i][1],p);
return ans;
}
int find(int x,int[] p){
while(p[x] != x) {
x = p[x];
p[x] = find(x,p);
}
return p[x];
}
}
第三题：判断连接可整除性
题目
给你一个正整数数组
nums和一个正整数k。当
nums的一个 排列 中的所有数字，按照排列顺序 连接其十进制表示 后形成的数可以 被k整除时，我们称该排列形成了一个 可整除连接 。返回能够形成 可整除连接 且 字典序 最小 的排列（按整数列表的形式表示）。如果不存在这样的排列，返回一个空列表。
思路
借鉴了题解 + 自己的理解
由题意可知，需要把所给的数组，按照某一种特定的顺序重新排列后，所组成的拼接后的数字可以被
k整除，且字典序最小的排列顺序。 字典序最小：不是拼接后的字典序，而是排列后的字典序最小。即：
2 33 14重新排列的一种情况，23314和14332，显然，第一种(23314) 的字典序最小，因为：23314 = 2 + 33 + 14，14332 = 14 + 33 + 2，显然2的字典序大于14的字典序。 明白了字典序最小，就可以知道，如果刚开始排列的时候，我就是按照从字典序最小的开始排列，后面依次增大，那末，第一次遇到的能被
k整除的排列，一定是字典序最小且被k整除的排列，这样就可以节省一大部分的时间。 然而，又会出现一个问题，就是如果给定的数组，没有任何一种排列所组成的数字能够被
k整除，那末，即使是从最小的字典序开始遍历，也一定要遍历所有的情况才能确定最后的结果是空数组。那末，能不能提前这个判断条件呢？仔细思考其实是可以的。 经过思考，可以发现，如果有两种排列，他们选择的数字都一样，余数的结果也一样，那末，只需要遍历一种情况就好，而另一种情况和这一种的情况相同。我们举个栗子理解一下：
a = {1,2,3,4,5} , k = 2 其中一种排列：2 4 x x x 同样另一种为：4 2 x x x 当遍历过所有 2 4 x x x 的情况的时候，其实与 4 2 x x x 的情况相同 因为：(2 4 1 3 5) % k ---> (2 * 10000 % k) + (4 * 1000 % k) + (1 * 100 % k) + (3 * 10 % k) + (5 % k) 对于：(4 2 1 3 5) % k ---> (4 * 10000 % k) + (2 * 1000 % k) + (1 * 100 % k) + (3 * 10 % k) + (5 % k) 可以看到，由于前面两项的结果相同，因此，因此都可以看为：0 + (1 * 100 % k) + (3 * 10 % k) + (5 % k) 故，后面不论有多少种，只需要遍历一次即可，不需要 2 4 、4 2 分别遍历一次通过这个简单的例子，相信已经了解了其中的原理。让我们继续。
有了思路，方法写起来就非常简单了。
1、字典序从小大遍历：只需要将原数组排序，然后选择数字的时候，从 0 号下标开始选择，结果即为字典序从小到大排列
2、记录每种排列：由于每种排列都可以用一个二进制表示，选择了那几个，比如： 111 1 ( 2 ) 1111_{(2)} 1111(2) 表示什么都没选， 000 1 ( 2 ) 0001_{(2)} 0001(2) 表示选择了第 0 号，因此，可以定义一个二维布尔数组，记录每种选择以及对应的余数。
vis[i][j]表示，选择 i 时，余数为 j 的访问情况。
代码实现
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* /\_̃__
* ( o.o )
* > ^ <
* 代码一遍过
*/
class Solution {
public int[] concatenatedDivisibility(int[] nums, int k) {
// 排序
Arrays.sort(nums);
// 用于后续方便拼接数组，即：1 23 2 --> (1 * 100 + 23) * 10 + 2，每次乘的都是10的后一位的位数次方
int[] pow10 = new int[nums.length];
for(int i = 0;i < nums.length;i++) {
pow10[i] = (int)Math.pow(10,String.valueOf(nums[i]).length());
}
// 状态记录数组
boolean[][] vis = new boolean[1 << nums.length][k];
return solve((1 << nums.length) - 1,nums, 0, new ArrayList<>(), new boolean[nums.length], k,
0,0,pow10,vis);
}
int[] solve(int s,int[] num, int index, List<Integer> list,boolean[] st,int k,
int tempRes,int diffLen,int[] pow10,boolean[][] vis){
if(index == num.length) {
if(tempRes == 0) {
int[] ans = new int[num.length];
for(int i = 0;i < ans.length;i++) ans[i] = list.get(i);
return ans;
}
return new int[0];
}
if(vis[s][tempRes]) return new int[0];
vis[s][tempRes] = true;
// 这里通过循环保证，所有的数字全部选择完成
for(int i = 0;i < num.length;i++) {
if(!st[i]) {
st[i] = true;
list.add(num[i]);
int[] p = solve(s ^ 1 << i,num, index+1, list, st, k,
(tempRes * pow10[i] + num[i]) % k,
diffLen + (num[i]+"").length(),pow10,vis);
if(p.length != 0) return p; // 如果找到直接返回
list.remove(index);
st[i] = false;
}
}
return new int[0];
}
}
第四题：针对图的路径存在性查询 II
目前难度有点大，后期理解后再补全😅