2605. 从两个数字数组里生成最小数字
给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ，每个数组中的元素 互不相同 ，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。
示例 1：
输入：nums1 = [4,1,3], nums2 = [5,7]
输出：15
解释：数字 15 的数位 1 在 nums1 中出现，数位 5 在 nums2 中出现。15 是我们能得到的最小数字。
示例 2：
输入：nums1 = [3,5,2,6], nums2 = [3,1,7]
输出：3
解释：数字 3 的数位 3 在两个数组中都出现了。
提示：
1 <= nums1.length, nums2.length <= 9
1 <= nums1[i], nums2[i] <= 9
每个数组中，元素 互不相同 。解答：直接用两个set+排序
class Solution {
public int minNumber(int[] nums1, int[] nums2) {
Set<Integer> set1=new HashSet<>();
Set<Integer> set2=new HashSet<>();
for(int n:nums1)set1.add(n);
for(int n:nums2)set2.add(n);
int res=100000;
for(int n:nums1){
if(set2.contains(n))res=Math.min(res,n);
}
Arrays.sort(nums1);
Arrays.sort(nums2);
int a=nums1[0],b=nums2[0];
if(a<b)res=Math.min(res,a*10+b);
else res=Math.min(res,b*10+a);
return res;
}
}2606. 找到最大开销的子字符串
给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。
子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。
字符的价值 定义如下：
如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
比方说，'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。
否则，如果这个字符在 chars 中的位置为 i ，那么它的价值就是 vals[i] 。
请你返回字符串 s 的所有子字符串中的最大开销。
示例 1：
输入：s = "adaa", chars = "d", vals = [-1000]
输出：2
解释：字符 "a" 和 "d" 的价值分别为 1 和 -1000 。
最大开销子字符串是 "aa" ，它的开销为 1 + 1 = 2 。
2 是最大开销。
示例 2：
输入：s = "abc", chars = "abc", vals = [-1,-1,-1]
输出：0
解释：字符 "a" ，"b" 和 "c" 的价值分别为 -1 ，-1 和 -1 。
最大开销子字符串是 "" ，它的开销为 0 。
0 是最大开销。
提示：
1 <= s.length <= 10^5
s 只包含小写英文字母。
1 <= chars.length <= 26
chars 只包含小写英文字母，且 互不相同 。
vals.length == chars.length
-1000 <= vals[i] <= 1000解答：Set+贪心
class Solution {
public int maximumCostSubstring(String s, String chars, int[] vals) {
int[] res=new int[26];
Set<Integer> set=new HashSet<>();
for(int i=0;i<chars.length();i++){
char c=chars.charAt(i);
res[c-'a']=vals[i];
set.add(c-'a');
}
for(int i=0;i<26;i++){
if(set.contains(i))continue;
else res[i]=i+1;
}
int ans=0;
int sum=0;
for (int i=0;i<s.length();i++){
if(sum<=0)sum=0;
char c=s.charAt(i);
sum+=res[c-'a'];
ans=Math.max(ans,sum);
}
return ans;
}
}6351. 标记所有元素后数组的分数
给你一个数组 nums ，它包含若干正整数。
一开始分数 score = 0 ，请你按照下面算法求出最后分数：
从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
将选中的整数加到 score 中。
标记 被选中元素，如果有相邻元素，则同时标记 与它相邻的两个元素 。
重复此过程直到数组中所有元素都被标记。
请你返回执行上述算法后最后的分数。
示例 1：
输入：nums = [2,1,3,4,5,2]
输出：7
解释：我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,1,3,4,5,2] 。
- 2 是最小未标记元素，所以标记它和左边相邻元素：[2,1,3,4,5,2] 。
- 4 是仅剩唯一未标记的元素，所以我们标记它：[2,1,3,4,5,2] 。
总得分为 1 + 2 + 4 = 7 。
示例 2：
输入：nums = [2,3,5,1,3,2]
输出：5
解释：我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,3,5,1,3,2] 。
- 2 是最小未标记元素，由于有两个 2 ，我们选择最左边的一个 2 ，也就是下标为 0 处的 2 ，以及它右边相邻的元素：[2,3,5,1,3,2] 。
- 2 是仅剩唯一未标记的元素，所以我们标记它：[2,3,5,1,3,2] 。
总得分为 1 + 2 + 2 = 5 。
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6解答：中位数贪心+裴蜀定理
class Solution {
public long makeSubKSumEqual(int[] arr, int k) {
int n = arr.length;
k = gcd(k, n);
long ans = 0;
for (int i = 0; i < k; ++i) {
var b = new ArrayList<Integer>();
for (int j = i; j < n; j += k)
b.add(arr[j]);
Collections.sort(b);
int mid = b.get(b.size() / 2);
for (int x : b)
ans += Math.abs(x - mid);
}
return ans;
}
private int gcd(int a, int b) {
return b==0?a:gcd(b,a%b);
}
}2608. 图中的最短环
现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。
返回图中 最短 环的长度。如果不存在环，则返回 -1 。
环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。
示例 1：
输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出：3
解释：长度最小的循环是：0 -> 1 -> 2 -> 0
示例 2：
输入：n = 4, edges = [[0,1],[0,2]]
输出：-1
解释：图中不存在循环
提示：
2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= ui, vi < n
ui != vi
不存在重复的边解答：BFS
class Solution {
public int findShortestCycle(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>(); // 邻接表
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
int shortestCycle = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
Queue<Integer> queue = new LinkedList<>();
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[i] = 0;
queue.offer(i);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj.get(u)) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
queue.offer(v);
} else if (v != i && v != u && dist[v] >= dist[u]) {
shortestCycle = Math.min(shortestCycle, dist[u] + dist[v] + 1);
}
}
}
}
return shortestCycle == Integer.MAX_VALUE ? -1 : shortestCycle;
}
}
