本文最后更新于2022年3月20日，已超过 2 个月没更新！
LeetCode weekly 285
统计道路上的碰撞次数
// 解法 by灵茶山艾府
func countCollisions(s string) int {
s = strings.TrimLeft(s, "L") // 前缀向左的车不会发生碰撞
s = strings.TrimRight(s, "R") // 后缀向右的车不会发生碰撞
return len(s) - strings.Count(s, "S") // 剩下非停止的车必然会碰撞
}
射箭比赛中的最大得分
⚡ 位枚举
func maximumBobPoints(numArrows int, aliceArrows []int) (ans []int) {
n := 1 << 12
maxScore := 0
for i := 0; i < n; i++ {
cnt := 0
score := 0
arr := make([]int, 12)
for j := 0; j < 12; j++ {
if (i>>j)&1 == 1 {
cnt += aliceArrows[j] + 1
score += j
arr[j] = aliceArrows[j] + 1
}
}
if cnt > numArrows {
continue
}
arr[0] += numArrows - cnt
if maxScore < score {
maxScore = score
ans = arr
}
}
return
}
LeetCode biweekly 74
用地毯覆盖后的最少白色砖块
⚡ dp
func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
n := len(floor)
f := make([][]int, numCarpets+1)
for i := range f {
f[i] = make([]int, n)
}
f[0][0] = int(floor[0] & 1)
for i := 1; i < n; i++ {
f[0][i] = f[0][i-1] + int(floor[i]&1)
}
for i := 1; i <= numCarpets; i++ {
for j := carpetLen; j < n; j++ {
f[i][j] = min(f[i][j-1]+int(floor[j]&1), f[i-1][j-carpetLen])
}
}
return f[numCarpets][n-1]
}
LeetCode weekly 284
得到要求路径的最小带权子图
⚡ dijkstra
type edge struct{ to, wt int }
func dijkstra(g [][]edge, start int) []int {
n := len(g)
dis := make([]int, n)
for i := range dis {
dis[i] = 1e18
}
dis[start] = 0
h := hp{{start, 0}}
for len(h) > 0 {
p := heap.Pop(&h).(pair)
v := p.v
if dis[v] < p.dis {
continue
}
for _, e := range g[v] {
w := e.to
if dis[w] > dis[v]+e.wt {
dis[w] = dis[v] + e.wt
heap.Push(&h, pair{w, dis[w]})
}
}
}
return dis
}
func minimumWeight(n int, edges [][]int, src1 int, src2 int, dest int) int64 {
g := make([][]edge, n)
rg := make([][]edge, n)
for _, e := range edges {
v, w, wt := e[0], e[1], e[2]
g[v] = append(g[v], edge{w, wt})
rg[w] = append(rg[w], edge{v, wt})
}
d1 := dijkstra(g, src1)
d2 := dijkstra(g, src2)
d3 := dijkstra(rg, dest)
ans := int(1e18)
for x := 0; x < n; x++ {
ans = min(ans, d1[x]+d2[x]+d3[x])
}
if ans < 1e18 {
return int64(ans)
}
return -1
}
type pair struct{ v, dis int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
LeetCode weekly 283
根据描述创建二叉树
func createBinaryTree(descriptions [][]int) (root *TreeNode) {
m := map[int]*TreeNode{}
in := map[int]int{}
for _, d := range descriptions {
x, y := d[0], d[1]
if m[x] == nil {
m[x] = &TreeNode{Val:x}
}
if m[y] == nil {
m[y] = &TreeNode{Val:y}
}
if d[2] == 1 {
m[x].Left = m[y]
} else {
m[x].Right = m[y]
}
in[y]++
}
for k, _ := range m {
if in[k] == 0 {
root = m[k]
break
}
}
return root
}
替换数组中的非互质数
⚡ 栈
func replaceNonCoprimes(nums []int) []int {
st := []int{nums[0]}
for _, v := range nums[1:] {
st = append(st, v)
for len(st) >= 2 {
x, y := st[len(st)-1], st[len(st)-2]
if gcd(x,y) > 1 {
st = append(st[:len(st)-2], lcm(x,y))
} else {
break
}
}
}
return st
}
// 最大公约数
func gcd(x, y int) int{
if y == 0 {
return x
}
return gcd(y, x%y)
}
// 最小公倍数
func lcm(x, y int) int{
return x*y/gcd(x,y)
}
LeetCode weekly 273
还原原数组
⚡ 枚举+双指针
func recoverArray(nums []int) (ans []int) {
sort.Ints(nums)
n := len(nums)
ans = make([]int, n)
// 枚举所有k的可能情况
for i := 1; i < n; i++ {
k := nums[i] - nums[0]
if k == 0 || k % 2 == 1 {
continue
}
t := 0
vis := make([]bool, n)
l, r := 0, i
for r < n {
for l < n && vis[l] {
l++
}
for r < n && nums[r] - nums[l] != k {
r++
}
if r == n {
break
}
vis[r] = true
ans[t] = nums[l] + k / 2
t++; l++; r++
}
if t == n / 2 {
return ans
}
}
return
}
LeetCode weekly 270
合法重新排列数对
⚡ 欧拉路径(模板题)
func validArrangement(pairs [][]int) (ans [][]int) {
adj := map[int][]int{}
cnt := map[int]int{}
for _, p := range pairs {
adj[p[0]] = append(adj[p[0]], p[1])
cnt[p[0]]++
cnt[p[1]]--
}
start := pairs[0][0]
for k, v := range cnt {
if v == 1 {
start = k
break
}
}
// Hierholzer 算法
var dfs func(int)
dfs = func(u int) {
for len(adj[u]) != 0 {
v := adj[u][0]
adj[u] = adj[u][1:]
dfs(v)
ans = append(ans, []int{u, v})
}
}
dfs(start)
n := len(ans)
for i := 0; i < n/2; i++ {
ans[i], ans[n-i-1] = ans[n-i-1], ans[i]
}
return
}
class Solution {
Map<Integer, List<Integer>> adj = new HashMap<>();
Map<Integer, Integer> deg = new HashMap<>();
List<int[]> ans = new ArrayList<>();
public int[][] validArrangement(int[][] pairs) {
for (int[] pair : pairs) {
adj.computeIfAbsent(pair[0], v -> new ArrayList<>()).add(pair[1]);
deg.put(pair[0], deg.getOrDefault(pair[0], 0) + 1);
deg.put(pair[1], deg.getOrDefault(pair[1], 0) - 1);
}
int start = pairs[0][0];
for (Map.Entry<Integer, Integer> en : deg.entrySet()) {
if (en.getValue() == 1) {
start = en.getKey();
break;
}
}
dfs(start);
Collections.reverse(ans);
return ans.toArray(new int[0][0]);
}
// Hierholzer 算法
private void dfs(int u) {
if (!adj.containsKey(u)) return;
while (!adj.get(u).isEmpty()) {
int v = adj.get(u).remove(0);
dfs(v);
ans.add(new int[]{u, v});
}
}
}
类似题型: 重新安排行程
LeetCode weekly 269
找出知晓秘密的所有专家
⚡ 并查集
class Solution {
int[] p;
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
this.p = new int[n];
Arrays.sort(meetings, (x, y) -> x[2] - y[2]);
for (int i = 0; i < n; ++ i) p[i] = i;
p[firstPerson] = find(0);
int time = -1;
Set<Integer> persons = new HashSet<>();
for (int[] m : meetings) {
if (m[2] != time) {
for (int person : persons) {
if (find(person) != p[0]) { // 断开不知道秘密的专家之间联系
p[person] = person;
}
}
persons = new HashSet<>();
time = m[2];
}
persons.add(m[0]);
persons.add(m[1]);
if (find(m[0]) == find(0)) {
p[find(m[1])] = find(0);
} else if (find(m[1]) == find(0)) {
p[find(m[0])] = find(0);
} else {
p[find(m[1])] = find(m[0]);
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; ++ i) {
if (find(i) == find(0)) {
ans.add(i);
}
}
return ans;
}
private int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
}
第66场双周赛
统计农场中肥沃金字塔的数目
⚡ dp
func countPyramids(grid [][]int) (ans int) {
ans += work(grid) // 正金字塔
m := len(grid)
for i := 0; i < m/2; i++ {
grid[i], grid[m-i-1] = grid[m-i-1], grid[i]
}
ans += work(grid) // 倒金字塔
return
}
func work(g [][]int) (ans int) {
m, n := len(g), len(g[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
for i := range g[m-1] {
dp[m-1][i] = g[m-1][i]
}
for i := m - 2; i >= 0; i-- {
dp[i][0], dp[i][n-1] = g[i][0], g[i][n-1]
for j := 1; j < n-1; j++ {
if g[i][j] == 1 {
dp[i][j] = min(dp[i+1][j-1], min(dp[i+1][j], dp[i+1][j+1])) + 1
} else {
dp[i][j] = 0
}
ans += max(0, dp[i][j]-1)
}
}
return
}
LeetCode weekly 268
k 镜像数字的和
⚡ 打表
class Solution {
long[][] table= {
{1, 4, 9, 16, 25, 58, 157, 470, 1055, 1772, 9219, 18228, 33579, 65802, 105795, 159030, 212865, 286602, 872187, 2630758, 4565149, 6544940, 9674153, 14745858, 20005383, 25846868, 39347399, 759196316, 1669569335, 2609044274L},
{1, 3, 7, 15, 136, 287, 499, 741, 1225, 1881, 2638, 31730, 80614, 155261, 230718, 306985, 399914, 493653, 1342501, 2863752, 5849644, 9871848, 14090972, 18342496, 22630320, 28367695, 36243482, 44192979, 71904751, 155059889},
{1, 3, 6, 11, 66, 439, 832, 1498, 2285, 3224, 11221, 64456, 119711, 175366, 233041, 739646, 2540727, 4755849, 8582132, 12448815, 17500320, 22726545, 27986070, 33283995, 38898160, 44577925, 98400760, 721411086, 1676067545, 53393239260L},
{1, 3, 6, 10, 16, 104, 356, 638, 1264, 1940, 3161, 18912, 37793, 10125794, 20526195, 48237967, 78560270, 126193944, 192171900, 1000828708, 1832161846, 2664029984L, 3500161622L, 4336343260L, 6849225412L, 9446112364L, 12339666346L, 19101218022L, 31215959143L, 43401017264L},
{1, 3, 6, 10, 15, 22, 77, 188, 329, 520, 863, 1297, 2074, 2942, 4383, 12050, 19827, 41849, 81742, 156389, 325250, 1134058, 2043967, 3911648, 7009551, 11241875, 15507499, 19806423, 24322577, 28888231},
{1, 3, 6, 10, 15, 21, 29, 150, 321, 563, 855, 17416, 83072, 2220384, 6822448, 13420404, 20379000, 29849749, 91104965, 321578997, 788407661, 1273902245, 1912731081, 2570225837L, 3428700695L, 29128200347L, 69258903451L, 115121130305L, 176576075721L, 241030621167L},
{1, 3, 6, 10, 15, 21, 28, 37, 158, 450, 783, 1156, 1570, 2155, 5818, 14596, 27727, 41058, 67520, 94182, 124285, 154588, 362290, 991116, 1651182, 3148123, 5083514, 7054305, 11253219, 66619574},
{1, 3, 6, 10, 15, 21, 28, 36, 227, 509, 882, 1346, 1901, 2547, 3203, 10089, 35841, 63313, 105637, 156242, 782868, 2323319, 4036490, 5757761, 7586042, 9463823, 11349704, 13750746, 16185088, 18627530}
};
public long kMirror(int k, int n) {
return table[k - 2][n - 1];
}
}
LeetCode weekly 267
反转偶数长度组的节点⭐
class Solution {
public ListNode reverseEvenLengthGroups(ListNode head) {
ListNode dummyNode = new ListNode();
ListNode pre = dummyNode;
dummyNode.next = head;
ListNode tail = head;
int k = 0;
while (tail != null) {
k ++;
int i;
for (i = 1; i < k && tail.next != null; ++ i) {
tail = tail.next;
}
if (i % 2 == 1) {
pre = tail;
head = tail = tail.next;
continue;
}
ListNode tmpNode = tail.next;
// 反转链表
ListNode[] nodes = reverse(head, tail);
// 接入原链表中
pre.next = nodes[0];
nodes[1].next = tmpNode;
pre = nodes[1];
head = tail = tmpNode;
}
return dummyNode.next;
}
// 反转链表
public ListNode[] reverse (ListNode head, ListNode tail) {
ListNode prev = tail.next, p = head;
while (p != tail) {
ListNode tmp = p.next;
p.next = prev;
tail.next = p;
prev = p;
p = tmp;
}
return new ListNode[]{tail, head};
}
}
相似题型：K个一组翻转链表
处理含限制条件的好友请求
⚡ 并查集
func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
p := make([]int, n)
for i := range p {
p[i] = i
}
// 并查集
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
// 预处理
cant := make([]map[int]bool, n)
for i := range cant {
cant[i] = map[int]bool{}
}
for _, r := range restrictions {
cant[r[0]][r[1]] = true
cant[r[1]][r[0]] = true
}
// 求解
ans := make([]bool, len(requests))
for i, r := range requests {
v, w := find(r[0]), find(r[1])
ans[i] = true
if v == w { // 已是朋友
continue
}
if cant[v][w] { // 无法成为朋友
ans[i] = false
continue
}
if len(cant[v]) > len(cant[w]) { // 优化: 小的集合合并到大的集合
v, w = w, v
}
// 合并集合
for x := range cant[v] {
x = find(x)
cant[x][w] = true
cant[w][x] = true
}
p[v] = p[w]
}
return ans
}
第65场双周赛
模拟行走机器人 II
⚡ 千万不要去模拟
class Robot {
int w, h, dis;
boolean state;
int mod;
public Robot(int width, int height) {
w = width;
h = height;
dis = 0;
state = true;
mod = 2 * (w + h - 2);
}
public void move(int num) {
dis = (dis + num) % mod;
state = false;
}
public int[] getPos() {
if (state)
return new int[]{0, 0};
if (dis < w)
return new int[]{dis, 0};
if (dis < w + h - 1)
return new int[]{w - 1, dis - w + 1};
if (dis < 2*w + h - 2)
return new int[]{2*w + h - 3 - dis, h - 1};
return new int[]{0, mod - dis};
}
public String getDir() {
if (state) return "East";
if (dis == 0) return "South";
if (dis < w) return "East";
if (dis < w + h - 1) return "North";
if (dis < 2*w + h - 2) return "West";
return "South";
}
}
LeetCode weekly 266
最大化一张图中的路径价值
⚡ 回溯
class Solution {
int[] values;
Map<Integer, List<int[]>> adjvex;
boolean[] vis;
int maxPrice = 0;
int maxTime;
public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
this.maxTime = maxTime;
this.values = values;
this.vis = new boolean[values.length];
adjvex = new HashMap<>();
for (int[] e : edges) {
adjvex.computeIfAbsent(e[0], k -> new ArrayList<int[]>()).add(new int[]{e[1], e[2]});
adjvex.computeIfAbsent(e[1], k -> new ArrayList<int[]>()).add(new int[]{e[0], e[2]});
}
vis[0] = true;
backTrack(0, 0, values[0]);
return maxPrice;
}
private void backTrack(int x, int time, int price) {
if (time > maxTime) return;
if (x == 0) {
maxPrice = Math.max(price, maxPrice);
}
for (int[] e : adjvex.getOrDefault(x, new ArrayList<>())) {
if (!vis[e[0]]) {
vis[e[0]] = true;
backTrack(e[0], time + e[1], price + values[e[0]]);
vis[e[0]] = false;
} else {
backTrack(e[0], time + e[1], price);
}
}
}
}
第64场双周赛
两个最好的不重叠活动
⚡ 预处理+二分
class Solution {
public int maxTwoEvents(int[][] events) {
int n = events.length;
Arrays.sort(events, (x, y) -> x[1] - y[1]);
int[] f = new int[n];
f[0] = events[0][2];
for (int i = 1; i < n; ++ i) {
f[i] = Math.max(f[i - 1], events[i][2]);
}
int res = 0;
for (int[] e : events) {
int i = 0, j = n - 1;
while (i < j) {
int mid = (i + j + 1) / 2;
if (events[mid][1] < e[0]) i = mid;
else j = mid - 1;
}
int s = e[2];
if (events[i][1] < e[0]) s += f[i];
res = Math.max(res, s);
}
return res;
}
}
蜡烛之间的盘子⭐
⚡ 前缀和
class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
int n = s.length();
int[] pre = new int[n + 1];
int[] l = new int[n + 1];
int[] r = new int[n + 2];
for (int i = 1; i <= n; ++ i) {
pre[i] = pre[i - 1];
if (s.charAt(i - 1) == '*') {
pre[i] ++;
l[i] = l[i - 1];
} else {
l[i] = i;
}
}
for (int i = n; i >= 1; -- i) {
if (s.charAt(i - 1) == '*') r[i] = r[i + 1];
else r[i] = i;
}
// 枚举所有请求
int[] ans = new int[queries.length];
int idx = 0;
for (int[] q : queries) {
int a = l[q[1] + 1], b = r[q[0] + 1];
ans[idx ++] = a > b ? pre[a] - pre[b - 1] : 0;
}
return ans;
}
}
LeetCode Weekly 264
统计最高分的节点数目⭐
class Solution {
public int countHighestScoreNodes(int[] parents) {
// 预处理
Map<Integer, List<Integer>> tree = new HashMap<>();
for (int i = 0; i < parents.length; ++ i) {
tree.putIfAbsent(parents[i], new ArrayList<>());
tree.get(parents[i]).add(i);
}
// 递归求出每个子树结点数
int[] count = new int[parents.length];
dfs(0, tree, count);
// 求最高分的节点数目
int ans = 0;
long maxScore = 0;
for (int i = 0; i < parents.length; ++ i) {
long score = 1;
int parNum = count[0];
for (int node : tree.getOrDefault(i, new ArrayList<>())) {
score *= count[node];
parNum -= count[node];
}
score *= parNum == 1 ? 1 : parNum - 1;
if (score > maxScore) {
maxScore = score;
ans = 0;
}
if (score == maxScore) ++ ans;
}
return ans;
}
private int dfs (int node, Map<Integer, List<Integer>> tree, int[] count) {
List<Integer> subList = tree.getOrDefault(node, new ArrayList<>());
int cnt = 1;
for (int sub : subList) {
cnt += dfs(sub, tree, count);
}
count[node] = cnt;
return cnt;
}
}
并行课程 III
⚡ 拓扑排序
class Solution {
public int minimumTime(int n, int[][] relations, int[] time) {
// 初始化图
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] r : relations) {
map.putIfAbsent(r[0], new ArrayList<>());
map.get(r[0]).add(r[1]);
}
// 统计入度
int[] indeg = new int[n + 1];
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
for (int e : entry.getValue()) {
indeg[e] ++;
}
}
Queue<Integer> q = new LinkedList<>();
int[] f = new int[n + 1]; // f[i]表示完成第i个课程的时间
for (int i = 1; i <= n; ++ i) {
if (indeg[i] == 0) {
q.offer(i);
f[i] = time[i - 1];
}
}
while (!q.isEmpty()) {
int u = q.poll();
for (int e : map.getOrDefault(u, new ArrayList<>())) {
f[e] = Math.max(f[e], f[u] + time[e - 1]);
if (-- indeg[e] == 0) q.offer(e);
}
}
return Arrays.stream(f).max().getAsInt();
}
}
LeetCode Weekly 263
统计按位或能得到最大值的子集数目
⚡ DFS + 剪枝
class Solution {
int ans = 0;
public int countMaxOrSubsets(int[] nums) {
int sum = 0; // 按位或是不减的操作，全部 | 起来即为最大值
for (int num : nums) {
sum |= num;
}
dfs(nums, sum, 0, 0);
return ans;
}
private void dfs(int[] nums, int sum, int idx, int cur) {
if (cur == sum) { // 达到最大值即可剪枝
ans += 1 << (nums.length - idx);
return;
}
if (idx == nums.length) return;
dfs(nums, sum, idx + 1, cur | nums[idx]);
dfs(nums, sum, idx + 1, cur);
}
}
到达目的地的第二短时间⭐
⚡ BFS次短路
class Solution {
public int secondMinimum(int n, int[][] edges, int time, int change) {
// 预处理: 邻接表建图
Map<Integer, List<Integer>> adjvex = new HashMap<>();
for (int[] edge : edges) {
adjvex.putIfAbsent(edge[0], new ArrayList());
adjvex.putIfAbsent(edge[1], new ArrayList());
adjvex.get(edge[0]).add(edge[1]);
adjvex.get(edge[1]).add(edge[0]);
}
Queue<int[]> q = new LinkedList<>();
// 记录最短和次短到达的时间
int[][] minTimes = new int[n + 1][2];
for (int[] minTime : minTimes) {
Arrays.fill(minTime, Integer.MAX_VALUE);
}
q.offer(new int[]{1, 0}); // 存放编号和到达该编号的时间
while (!q.isEmpty()) {
int[] cur = q.poll();
int tmp = cur[1] % (2 * change);
int extra = tmp >= 0 && tmp < change ? 0 : 2 * change - tmp;
int nextTime = cur[1] + extra + time; // 该点到达下一个连接点的时间
// 更新连接点的时间
for (int next : adjvex.getOrDefault(cur[0], new ArrayList<>())) {
if (nextTime < minTimes[next][0]) {
minTimes[next][1] = minTimes[next][0];
minTimes[next][0] = nextTime;
} else if (nextTime > minTimes[next][0] && nextTime < minTimes[next][1]) {
minTimes[next][1] = nextTime;
} else {
continue;
}
// 入队: 更新的点及其新的到达时间
q.offer(new int[]{next, nextTime});
}
}
return minTimes[n][1];
}
}
