力扣第 101 场双周赛
链接：https://leetcode.cn/contest/biweekly-contest-101/
# T1. 从两个数字数组里生成最小数字
题目链接：https://leetcode.cn/problems/form-smallest-number-from-two-digit-arrays/
# 思路
贪心：若两个数组的交集不为空，则取交集中的一个最小的数组；否则分别取两个数组中的最小数字，组成最小的两位数。
# 代码
class Solution { | |
public int minNumber(int[] nums1, int[] nums2) { | |
int[] map = new int[10]; | |
int ans = 0; | |
int min1 = 10; | |
for (int num : nums1) { | |
min1 = Math.min(min1, num); | |
++map[num]; | |
} | |
int min2 = 10; | |
for (int num : nums2) { | |
if (map[num] > 0) { | |
ans = ans == 0 || ans > num ? num : ans; | |
} | |
min2 = Math.min(min2, num); | |
++map[num]; | |
} | |
if (ans > 0) return ans; | |
return min1 > min2 ? min2 * 10 + min1 : min1 * 10 + min2; | |
} | |
} |
# T2. 找到最大开销的子字符串
题目链接：https://leetcode.cn/problems/find-the-substring-with-maximum-cost/
# 思路
动态规划：
dp [i] 表示以 chars [i] 结尾的子字符串的最大开销，则动态规划转移方程为：
dp [i] = Math.max (只取当前字符的最大开销，dp [i-1])
因为 dp[i] 取值仅与 dp[i-1] 有关，所以可用 原地 dp，只需定义一个 pmax ，表示以前一个字符结尾的字符串所能得到的最大开销。
# 代码
class Solution { | |
public int maximumCostSubstring(String s, String chars, int[] vals) { | |
int n = s.length(); | |
int[] m = new int[26]; | |
Arrays.fill(m, 1001); | |
for (int i = vals.length - 1; i >= 0; --i) { | |
m[chars.charAt(i) - 'a'] = vals[i]; | |
} | |
int ret = 0; | |
int pmax = 0; | |
for (int i = 0; i < n; ++i) { | |
int idx = s.charAt(i) - 'a'; | |
int cur = m[idx] == 1001 ? idx + 1 : m[idx]; | |
pmax = Math.max(cur, pmax + cur); | |
ret = Math.max(pmax, ret); | |
} | |
return ret; | |
} | |
} |
# 提交结果
# T2. 使子数组元素和相等
题目链接：https://leetcode.cn/problems/make-k-subarray-sums-equal/
# 思路
整体思路是贪心：
就是尽可能分多的分组，然后使得组内所有元素相等即可，根据题意，对于数组 arr 中的元素，必须满足：
arr[i] == arr[(i + k) % n]
其中，n 是数组的长度，0<=i<=n-1
- 下面通过举例来说明如何确定最大的组数：
对于数组
[x0, x1, x2, x3, x4, x5]，取 k = 4，则：x0+x1+x2+x3 == x1+x2+x3+x4 -> x0 == x4 x1+x2+x3+x4 == x2+x3+x4+x5 -> x1 == x5 同理可得： x2 == x0 x3 == x1 x4 == x2 x5 == x3 总结可得： x0 == x2 == x4 x1 == x3 == x5 即最多可以分两组，且每组三个元素，奇偶下标拆分对于数组
[x0, x1, x2, x3, x4, x5, x6]，取 k = 4，则：x0 == x4 x1 == x5 x2 == x6 x3 == x0 x4 == x1 x5 == x2 x6 == x3 总结可得： x0 == x1 == x2 == x3 == x4 == x5 == x6 即最多分一组，且所有元素都必须相等也就是，最大组数就是 n 与 k 的最大公约数
接下来便是解决如何通过最小的操作，使得组内元素全部相等。经验证：当所有元素等于数组的中位数时，花费的操作最小：
数组长度为偶数，中位数取最中间两位中的任一位，因为他们得到的操作数相等
数组长度是奇数，中位数去最中间的一位
综上，中位数取：
nums[n/2]
# 代码
class Solution { | |
public long makeSubKSumEqual(int[] arr, int k) { | |
int n = arr.length; | |
if (k >= n) return 0; | |
// 求 n 与 k 的最大公约数，就是一共可分的组数 | |
int g = gcd(n, k); | |
long r = 0L; | |
if (g > 1) { | |
int[] tarr = new int[n / g]; | |
for(int i = 0; i < g; ++i) { | |
int c = 0; | |
for (int j = i; j < n; j += g) { | |
tarr[c++] = arr[j]; | |
} | |
r += sum(tarr); | |
} | |
} else { | |
// 只能分成一个组，那么就是 arr 中的数要全部相同 | |
r = sum(arr); | |
} | |
return r; | |
} | |
private int gcd(int a, int b) { | |
int t; | |
while (b > 0) { | |
t = a % b; | |
a = b; | |
b = t; | |
} | |
return a; | |
} | |
private long sum(int[] nums) { | |
int n = nums.length; | |
Arrays.sort(nums); | |
long r = 0; | |
int d = nums[n / 2]; | |
for (int a : nums) { | |
r += Math.abs(a - d); | |
} | |
return r; | |
} | |
} |
# 提交结果
# T4. 图中的最短环
链接：https://leetcode.cn/problems/shortest-cycle-in-a-graph/
# 思路
BFS：
图论中的环：从 a 点到 b 点有两条简单的路径
利用 BFS 枚举每个起点，第一次到达的环就是最短环
需要注意的是：在遍历过程中，可能会遍历到已经入过队的结点，此时可以使用标记
# 代码
class Solution { | |
public int findShortestCycle(int n, int[][] edges) { | |
List<Integer>[] g = new List[n]; | |
for (int i = 0; i < n; ++i) { | |
g[i] = new ArrayList<>(); | |
} | |
// 建图 | |
for (int[] e : edges) { | |
g[e[0]].add(e[1]); | |
g[e[1]].add(e[0]); | |
} | |
int ans = Integer.MAX_VALUE; | |
for (int i = 0; i < n; ++i) { | |
int len = bfs(i, g); | |
if (len != -1) { | |
ans = Math.min(ans, len); | |
} | |
} | |
return ans == Integer.MAX_VALUE ? -1 : ans; | |
} | |
private int bfs(int start, List<Integer>[] g) { | |
int n = g.length; | |
//dis [i] 表示 start 到 i 的距离 | |
int[] dis = new int[n]; | |
//-1 表示还未访问过 | |
Arrays.fill(dis, -1); | |
Queue<Integer> que = new LinkedList<>(); | |
dis[start] = 0; | |
que.offer(start); | |
while (!que.isEmpty()) { | |
for (int i = que.size(); i > 0; --i) { | |
int cur = que.poll(); | |
for (int nxt : g[cur]) { | |
if (dis[nxt] == -1) { | |
// 从未访问过，入队 | |
dis[nxt] = dis[cur] + 1; | |
que.offer(nxt); | |
} else if (dis[nxt] >= dis[cur]) { | |
// 遇到了环，因为 nxt 已经有其他的点到达过，所以可以返回 | |
return dis[nxt] + dis[cur] + 1; | |
} | |
//dis [nxt] < dis [cur]，表示当前结点是从 nxt 过来的，直接忽略 | |
} | |
} | |
} | |
// 没有任何环，即是一颗树，直接返回 -1； | |
return -1; | |
} | |
} |
# 提交结果
