目录
一，3309. 连接二进制表示可形成的最大数值
本题数据范围较小，可以使用递归枚举每一种排列方式，计算出最大值，代码如下：
class Solution {
int ans = 0;
public int maxGoodNumber(int[] nums) {
dfs(0, "", nums);
return ans;
}
void dfs(int i, String res, int[] nums){
if(i == (1<<3)-1){
ans = Math.max(ans, Integer.parseInt(res, 2));
return;
}
for(int j=0; j<3; j++){
if((i>>j&1)==1) continue;
dfs(i|1<<j, res + Integer.toBinaryString(nums[j]), nums);
}
return ;
}
}但是该方式只适用于数据范围较小的题，下面介绍一种 O(nlogn) 的做法，我们先用十进制的方式来思考一下，给你一个数组 [9，10] ，如何使得这个数组用十进制并接得到的值更大？我们当然是比较一下：是9在前大，还是10在前大，然后决定这两个拼接的顺序。那么拓展到大小为 n 的数组如何决定它们的顺序？和上述做法一样，相邻的数依次比较，类似于冒泡排序。那么对于本题使用二进制拼接也是同理，代码如下：
class Solution {
public int maxGoodNumber(int[] t) {
Integer[] nums = new Integer[t.length];
for(int i=0; i<t.length; i++)
nums[i] = t[i];
//注意要想按照自己的想法排序，必须使用Integer数组
Arrays.sort(nums, (x, y)->{
int len_x = Integer.toBinaryString(x).length();
int len_y = Integer.toBinaryString(y).length();
int xy = x << len_y | y;
int yx = y << len_x | x;
return yx - xy;
});
int ans = 0;
for(int x : nums){
int len = Integer.toBinaryString(x).length();
ans = ans << len | x;
}
return ans;
}
}二，3310. 移除可疑的方法
本题题意给你一个可疑方法 k，如果被 k 直接调用/间接调用，那么这些方法也被视为可疑方法（注意：调用可疑方法的方法不是可疑方法），如果没有其他方法调用可疑方法，返回非可疑方法；否则，返回所用方法。
我们可以建立一个图，使用 dfs/bfs 找到所有的可疑方法，然后枚举 invocations 数组，比如每个元素为 [x，y]，如果 x 不是可疑方法 && y 是可疑方法，说明有非可疑方法调用可疑方法，返回所有方法；否则只返回非可疑方法。
代码如下：
class Solution {
public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
List<Integer> ans = new ArrayList<>();
List<Integer>[] g = new ArrayList[n];
Arrays.setAll(g, e->new ArrayList<>());
for(int[] e : invocations){
g[e[0]].add(e[1]);
}
Queue<Integer> que = new LinkedList<>();
que.add(k);
Set<Integer> set = new HashSet<>();
set.add(k);
while(!que.isEmpty()){
int x = que.poll();
for(int y : g[x]){
if(!set.contains(y)){
que.add(y);
set.add(y);
}
}
}
for(int[] e : invocations){
if(!set.contains(e[0]) && set.contains(e[1])){
for(int i=0; i<n; i++)
ans.add(i);
return ans;
}
}
for(int i=0; i<n; i++){
if(!set.contains(i))
ans.add(i);
}
return ans;
}
}三，3311. 构造符合图结构的二维矩阵
本题可以想象成拼拼图，我们可以先找到四个角落的点（如果行列>=3，那么它只有两个相邻的点），然后不断的往里拼，但是本题不知道四个角的对应位置，所以我们可以先找到一个角洛的点，然后往一边拼，注意一个边上点（除了角落的点），它们相邻的点有三个，不断的填充，直到找到一个这条边的另一个角落（即只有两个相邻点的点），这样我们就拼出一个边了，然后通过这个边不断的往下拼就行了。
上述是行列>=3的情况，如果它只有一行/列，那么它所有点中最少的相邻点必须为1，所以只需要判断最少的相邻是否为1，就直到是否是一行/列。
如果它只有两行/列，那么只需要判断所有点中最多的相邻点是否为4，如果不为4且不是一行/列，说明它只用两行/列。
代码如下：
class Solution {
public int[][] constructGridLayout(int n, int[][] edges) {
List<Integer>[] g = new ArrayList[n];
Arrays.setAll(g, e->new ArrayList<>());
for(int[] e : edges){
g[e[0]].add(e[1]);
g[e[1]].add(e[0]);
}
int[] node = new int[5];
Arrays.fill(node, -1);
for(int x=0; x<n; x++){
node[g[x].size()] = x;
}
List<Integer> row = new ArrayList<>();
if(node[1] != -1){
row.add(node[1]);
}else if(node[4]==-1){
int x = node[2];
for(int y : g[x]){
if(g[y].size() == 2){
row.add(x);
row.add(y);
break;
}
}
}else{
int x = node[2];
row.add(x);
int pre = x;
x = g[x].get(0);
while(g[x].size() == 3){
row.add(x);
for(int y : g[x]){
if(y != pre && g[y].size() < 4){
pre = x;
x = y;
break;
}
}
}
row.add(x);
}
int k = row.size();
int[][] ans = new int[n/k][k];
boolean[] vis = new boolean[n];
for(int j=0; j<k; j++){//把第一行放进去
int x = row.get(j);
ans[0][j] = x;
vis[x] = true;
}
for(int i=1; i<ans.length; i++){
for(int j=0; j<k; j++){
for(int y : g[ans[i-1][j]]){
if(!vis[y]){
vis[y] = true;
ans[i][j] = y;
break;
}
}
}
}
return ans;
}
}四，3312. 查询排序后的最大公约数
本题最重要的部分就是计算出每个 gcd 出现的次数，对于查询，我们可以使用二分前缀和的方式算出答案。
如何计算每个 gcd 出现的次数？假设要计算 gcd 等于 2 出现的次数，比如说有 n 个 2 的倍数，那么我们可以得到 Cn2 个数对（即 (n-1)*n/2 ），但是这么多数对，不一定每一个 gcd 的值都为 2，比如 4 和 8 的 gcd 就为 4，6 和 12 的 gcd 就为 6，所以我们需要从 (n-1)*n/2 个数对中减去数对的 gcd 为 4，6，8，....。这样就能得到 gcd 为 2 的数对个数了。
定义 cntGcd[i] 表示 gcd 为 i 的数对的个数，cntGcd[i] = (n-1)*n/2 - cntGcd[2*i] - cntGcd[3*i] - ...，从上述公式可以看出，要想计算出 cntGcd[i]，必须先计算出 cntGcd[2*i]、cntGcd[3*i]，所以我们需要从后往前遍历。
代码如下：
class Solution {
//cnt[2] = C(n,2) - cnt[4] - cnt[6] - ...
public int[] gcdValues(int[] nums, long[] queries) {
int[] cntX = new int[50001];
int mx = 0;
for(int x : nums){
cntX[x]++;
mx = Math.max(mx, x);
}
long[] cnt = new long[mx+1];
for(int i=mx; i>=1; i--){
int s = 0;
for(int j=i; j<mx+1; j+=i){
s += cntX[j];
cnt[i] -= cnt[j]; //去除2i,3i,4i...（虽然j从i开始，但是cnt[i]初始值为0，所以实际上没有减去i）
//为什么不是从2*i开始？因为要计算i的倍数的和s，如果从2i开始会少计算i出现的个数！！
}
cnt[i] += (long)(s - 1) * s / 2;
}
for(int i=1; i<mx+1; i++){
cnt[i] += cnt[i-1];
}
int[] ans = new int[queries.length];
for(int i=0; i<queries.length; i++){
int l = 1, r = mx;
while(l <= r){
int mid = (l + r) / 2;
if(cnt[mid] <= queries[i]){
//为什么加=？因为query[i]可以取到0（当然也可以写成cnt[mid]-1 < queries[i]）
l = mid + 1;
}else{
r = mid - 1;
}
}
ans[i] = l;
}
return ans;
}
}本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » Leetcode - 周赛418
发表评论 取消回复