57. 插入?yún)^(qū)間
https://leetcode.cn/problems/insert-interval/
提示：0 <= intervals.length <= 10^4intervals[i].length == 20 <= intervals[i][0] <= intervals[i][1] <= 10^5intervals 根據(jù) intervals[i][0] 按 升序 排列newInterval.length == 20 <= newInterval[0] <= newInterval[1] <= 10^5
當(dāng)前區(qū)間與要加入的新區(qū)間之間的關(guān)系只有兩種可能：相交或者不相交。
如果相交，將兩者結(jié)合即可。
如果不相交，判斷新加入的區(qū)間是否在當(dāng)前區(qū)間之前，如果是，就先加入答案。
遍歷一遍之后，如果沒有處理過新加入的區(qū)間，就說明新區(qū)間應(yīng)該加在最后。
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
if (intervals.length == 0) return new int[][]{newInterval};
List<int[]> ans = new ArrayList<>();
int s = newInterval[0], e = newInterval[1];
boolean f = false;
for (int[] interval: intervals) {
int a = interval[0], b = interval[1];
// 和 newInterval 相交
if (b >= s && a <= e) {
f = true;
a = Math.min(a, s);
b = Math.max(b, e);
}
// 不相交 newInterval 在此區(qū)間之前
if (a > e) {
if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < s) {
ans.add(newInterval);
f = true;
}
}
if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < a) ans.add(new int[]{a, b});
else ans.get(ans.size() - 1)[1] = b;
}
// 如果沒有處理過 newInterval
if (!f) ans.add(newInterval);
return ans.toArray(new int[ans.size()][2]);
}
}
823. 帶因子的二叉樹
https://leetcode.cn/problems/binary-trees-with-factors/
提示：1 <= arr.length <= 10002 <= arr[i] <= 10^9arr 中的所有值 互不相同
解法——遞推
將元素排序之后，從小到大依次處理各個(gè)數(shù)值作為根節(jié)點(diǎn)時(shí)的二叉樹數(shù)量。
class Solution {
final long MOD = (long)1e9 + 7;
public int numFactoredBinaryTrees(int[] arr) {
Arrays.sort(arr);
int n = arr.length;
long ans = 0;
Map<Integer, Long> m = new HashMap<>(); // 存儲(chǔ)每個(gè)數(shù)字作為根節(jié)點(diǎn)時(shí)的二叉樹數(shù)量
for (int i = 0; i < n; ++i) {
long cnt = 1;
for (int j = 0; j < i; ++j) { // 枚舉兒子節(jié)點(diǎn)
if (arr[i] % arr[j] == 0 && m.containsKey(arr[i] / arr[j])) {
cnt = (cnt + m.get(arr[j]) * m.get(arr[i] / arr[j])) % MOD;
}
}
ans = (ans + cnt) % MOD;
m.put(arr[i], cnt);
}
return (int)ans;
}
}
1654. 到家的最少跳躍次數(shù)(BFS，??最遠(yuǎn)距離上界的證明)
https://leetcode.cn/problems/minimum-jumps-to-reach-home/description/
提示：1 <= forbidden.length <= 10001 <= a, b, forbidden[i] <= 20000 <= x <= 2000forbidden 中所有位置互不相同。位置 x 不在 forbidden 中。
可以證明，一定可以在[0, max(f + a + b, x + b)] 的下標(biāo)范圍內(nèi)找到最優(yōu)解，其中 f 是最遠(yuǎn)進(jìn)制點(diǎn)的坐標(biāo)。
因?yàn)?f, a, b, x <= 2000，故搜索范圍不會(huì)超過 6000。（證明略，我也沒整明白）
用 bfs 計(jì)算最短路。
class Solution {
public int minimumJumps(int[] forbidden, int a, int b, int x) {
Set<Integer> s = new HashSet<>();
for (int v: forbidden) s.add(v);
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{0, 1}); // 將起點(diǎn)放入隊(duì)列
final int N = 6000;
boolean[][] vis = new boolean[N][2];
vis[0][1] = true;
for (int ans = 0; !q.isEmpty(); ++ans) {
for (int t = q.size(); t > 0; --t) {
int[] p = q.poll();
int i = p[0], k = p[1];
// 到達(dá)了目的地，直接返回答案
if (i == x) return ans;
List<int[]> nxt = new ArrayList<>();
nxt.add(new int[]{i + a, 1});
// 如果上一步 不是向后跳，那么這一步可以向后跳
if ((k & 1) == 1) nxt.add(new int[]{i - b, 0});
for (int[] e: nxt) {
int j = e[0];
k = e[1];
if (j >= 0 && j < N && !s.contains(j) && !vis[j][k]) {
q.offer(new int[]{j, k});
vis[j][k] = true;
}
}
}
}
return -1;
}
}
1761. 一個(gè)圖中連通三元組的最小度數(shù)
https://leetcode.cn/problems/minimum-degree-of-a-connected-trio-in-a-graph/
提示：2 <= n <= 400edges[i].length == 21 <= edges.length <= n * (n-1) / 21 <= ui, vi <= nui != vi圖中沒有重復(fù)的邊。
構(gòu)造鄰接表，枚舉每一個(gè)三元組。
class Solution {
public int minTrioDegree(int n, int[][] edges) {
int[] cnt = new int[n + 1];
int[][] isC = new int[n + 1][n + 1];
for (int[] edge: edges) {
int x = edge[0], y = edge[1];
isC[x][y] = 1;
isC[y][x] = 1;
cnt[x]++;
cnt[y]++;
}
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (isC[i][j] == 0) continue;
for (int k = j + 1; k <= n; ++k) {
if (isC[j][k] == 0 || isC[i][k] == 0) continue;
ans = Math.min(ans, cnt[i] + cnt[j] + cnt[k] - 6);
}
}
}
return ans != Integer.MAX_VALUE? ans: -1;
}
}
2240. 買鋼筆和鉛筆的方案數(shù)
https://leetcode.cn/problems/number-of-ways-to-buy-pens-and-pencils/
提示：1 <= total, cost1, cost2 <= 10^6
解法1——完全背包
套用完全背包模板，對(duì)dp數(shù)組求和即可。
class Solution {
public long waysToBuyPensPencils(int total, int cost1, int cost2) {
long[] dp = new long[total + 1];
dp[0] = 1;
for (int j = cost1; j <= total; ++j) dp[j] += dp[j - cost1];
for (int j = cost2; j <= total; ++j) dp[j] += dp[j - cost2];
long ans = 0;
for (long d: dp) ans += d;
return ans;
}
}
解法2——枚舉買了幾支鋼筆（推薦解法）
通過枚舉購買鋼筆的數(shù)量，計(jì)算此時(shí)可以購買鉛筆的數(shù)量，+1即是購買此時(shí)數(shù)量鋼筆時(shí)，購買鉛筆的方案數(shù)。
class Solution {
public long waysToBuyPensPencils(int total, int cost1, int cost2) {
long ans = 0;
for (int i = 0; i * cost1 <= total; ++i) {
ans += (total - i * cost1) / cost2 + 1;
}
return ans;
}
}
2511. 最多可以摧毀的敵人城堡數(shù)目
https://leetcode.cn/problems/maximum-enemy-forts-that-can-be-captured/?envType=daily-question&envId=2023-09-02
提示：1 <= forts.length <= 1000-1 <= forts[i] <= 1
解法——一次遍歷
題目要求是計(jì)算 1 和 -1 之間的 0 的最大數(shù)量。
一次遍歷，遍歷的過程中記錄上一個(gè) 1 或 -1 出現(xiàn)的位置即可。
class Solution {
public int captureForts(int[] forts) {
int lastId = 0, ans = 0;
for (int i = 0; i < forts.length; ++i) {
if (forts[i] == -1 || forts[i] == 1) {
if (forts[i] + forts[lastId] == 0) ans = Math.max(ans, i - lastId - 1);
lastId = i;
}
}
return ans;
}
}
1921. 消滅怪物的最大數(shù)量（貪心）
https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/
提示：n == dist.length == speed.length1 <= n <= 10^51 <= dist[i], speed[i] <= 10^5文章來源：http://www.zghlxwxcb.cn/news/detail-701176.html
先計(jì)算時(shí)間，再按時(shí)間排序。
貪心的先消滅快要到達(dá)城市的怪獸。文章來源地址http://www.zghlxwxcb.cn/news/detail-701176.html
class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
int n = dist.length;
int[] t = new int[n];
for (int i = 0; i < n; ++i) {
t[i] = (dist[i] + speed[i] - 1) / speed[i]; // 向上取整
}
Arrays.sort(t);
for (int i = 0; i < n; ++i) {
if (t[i] <= i) return i;
}
return n;
}
}
到了這里，關(guān)于【LeetCode每日一題合集】2023.8.28-2023.9.3（到家的最少跳躍次數(shù)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
