Leetcode第418周赛
第一题
因为数组的个数有限，直接将数字转为二进制字符串，通过数组的自定义排序方法进行排序（根据题意是拼接而不是二进制相加），最后将排序后的结果依次拼接，转为10进制。
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
class Solution {
public int maxGoodNumber(int[] nums) {
String[] binaryReprs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
binaryReprs[i] = Integer.toBinaryString(nums[i]);
}
Arrays.sort(binaryReprs, (a, b) -> (b + a).compareTo(a + b));
StringBuilder largestBinary = new StringBuilder();
for (String binary : binaryReprs) {
largestBinary.append(binary);
}
return Integer.parseInt(largestBinary.toString(), 2);
}
}
第二题
认真读题，就是先将点边顺序存储起来，然后根据以bug点出发做深度搜索，全部标记为异常，做好之后，再判断剩余点是否存在到异常点的情况，如果存在就返回全部，否则返回剩余点。
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
class Solution {
public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
List<List<Integer>> graph = new ArrayList<>();
List<Integer> reT = new ArrayList<>();
for(int i = 0 ;i<n;i++){
reT.add(i);
graph.add(new ArrayList<>());
}
for(int[] invocation : invocations){
graph.get(invocation[0]).add(invocation[1]);
}
boolean[] sus = new boolean[n];
dfs(k, graph, sus);
for(int i=0;i<n;i++){
if(!sus[i]){
for(int next: graph.get(i)){
if(sus[next]){
return reT;
}
}
}
}
List<Integer> re = new ArrayList<>();
for(int i=0;i<n;i++){
if(!sus[i]){
re.add(i);
}
}
return re;
}
void dfs(int k, List<List<Integer>> graph, boolean[] sus){
sus[k] = true;
for(int next: graph.get(k)){
if(!sus[next]){
dfs(next, graph, sus);
}
}
}
}
第三题
这个题，没看到样例二想当然认为矩阵是根n*根n，最后没时间修改。我的思路是，先将点边信息存储起来，得到所有点的相临点个数。根据相邻点个数能确定矩阵的形状，进行矩阵初始化。从相邻点个数最低的点开始做dfs，直到遍历所有的点。在做dfs的过程中要用到回溯。
- 001
- 002
- 003
- 004
- 005
- 006
- 007
- 008
- 009
- 010
- 011
- 012
- 013
- 014
- 015
- 016
- 017
- 018
- 019
- 020
- 021
- 022
- 023
- 024
- 025
- 026
- 027
- 028
- 029
- 030
- 031
- 032
- 033
- 034
- 035
- 036
- 037
- 038
- 039
- 040
- 041
- 042
- 043
- 044
- 045
- 046
- 047
- 048
- 049
- 050
- 051
- 052
- 053
- 054
- 055
- 056
- 057
- 058
- 059
- 060
- 061
- 062
- 063
- 064
- 065
- 066
- 067
- 068
- 069
- 070
- 071
- 072
- 073
- 074
- 075
- 076
- 077
- 078
- 079
- 080
- 081
- 082
- 083
- 084
- 085
- 086
- 087
- 088
- 089
- 090
- 091
- 092
- 093
- 094
- 095
- 096
- 097
- 098
- 099
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
class Solution {
int[][] nums;
// 用于打印邻接表的方法
private static void printGraph(List<List<Integer>> graph) {
for (int i = 0; i < graph.size(); i++) {
System.out.println("节点 " + i + " 的邻接节点: " + graph.get(i));
}
}
private int[] findBestDimensions(int n) {
int r = 1, c = n; // 从最坏的 1 x n 尝试开始
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
// i 是 n 的约数，i 和 n/i 可以组成合法矩阵
r = i;
c = n / i;
}
}
return new int[] { r, c }; // 返回行列组合
}
public int[][] constructGridLayout(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for(int i=0;i<n;i++){
graph.add(new ArrayList<>());
}
for(int[] edge: edges){
int to = edge[0];
int from = edge[1];
graph.get(to).add(from);
graph.get(from).add(to);
}
int start = 0;
int max = graph.get(0).size();
int min = graph.get(0).size();
for(int i=1;i<graph.size();i++){
if(graph.get(i).size() < graph.get(start).size()) {
start = i;
min = graph.get(i).size();
}
max = Math.max(max, graph.get(i).size());
min = Math.min(min, graph.get(i).size());
}
boolean[] user = new boolean[n];
if(min==1){
nums = new int[1][n];
}else if(max==3){
nums = new int[n/2][2];
}else {
int[] dims = findBestDimensions(n); // 找到最优的 (rows, cols) 组合
int rows = dims[0];
int cols = dims[1];
nums = new int[rows][cols];
}
// nums = new int[(int)Math.sqrt(n)][(int)Math.sqrt(n)];
for (int[] row : nums) Arrays.fill(row, -1);
int[][] nums_nodes = new int[(int)Math.sqrt(n)][(int)Math.sqrt(n)];
for(int i=0;i<nums_nodes.length;i++){
for(int j=0;j<nums_nodes[i].length;j++){
// 如果是角落（四个）
if ((i == 0 && j == 0) || // 左上角
(i == 0 && j == nums_nodes.length - 1) || // 右上角
(i == nums_nodes.length - 1 && j == 0) || // 左下角
(i == nums_nodes.length - 1 && j == nums_nodes.length - 1)) { // 右下角
nums_nodes[i][j] = 2; // 角落有2个邻居
}
// 如果是边界但不是角落
else if (i == 0 || i == nums_nodes.length - 1 || j == 0 || j == nums_nodes.length - 1) {
nums_nodes[i][j] = 3; // 边界上有3个邻居
}
// 如果是中间的非边界区域
else {
nums_nodes[i][j] = 4; // 中间有4个邻居
}
}
}
dfs(start, user, graph,nums_nodes, 0, 0);
return nums;
}
boolean dfs(int node, boolean[] user,List<List<Integer>> graph ,int[][] nums_nodes, int i, int j){
if(i < 0 || i >= nums.length || j < 0 || j >= nums[0].length || nums[i][j] != -1 || graph.get(node).size() != nums_nodes[i][j] || user[node] ) return false;
nums[i][j]=node;
user[node] = true;
boolean success = true;
for(int next: graph.get(node)){
if (!user[next]) {
// 尝试从 (i, j) 的四个方向进行 DFS 遍历
if (!dfs(next, user, graph, nums_nodes, i+1, j) && // 向下
!dfs(next, user, graph,nums_nodes, i-1, j)&& // 向上
!dfs(next, user, graph, nums_nodes, i, j-1) && // 向右
!dfs(next, user, graph, nums_nodes, i, j+1)) { // 向左
// 如果没有可行的方向，回溯：撤销当前状态
success = false;
break;
}
}
}
if (!success) {
nums[i][j] = -1;
user[node] = false;
}
return success;
}
}
第四题
哈哈，三题选手从来不考虑四题的事
