江门网站制作流程,楚雄网站设计,上海网络营销外包服务公司,广告推广图片文章目录 57. 插入区间823. 带因子的二叉树解法——递推 1654. 到家的最少跳跃次数(BFS#xff0c;#x1f6b9;最远距离上界的证明)1761. 一个图中连通三元组的最小度数2240. 买钢笔和铅笔的方案数解法1——完全背包解法2——枚举买了几支钢笔#xff08;推荐解法#xff… 文章目录 57. 插入区间823. 带因子的二叉树解法——递推 1654. 到家的最少跳跃次数(BFS最远距离上界的证明)1761. 一个图中连通三元组的最小度数2240. 买钢笔和铅笔的方案数解法1——完全背包解法2——枚举买了几支钢笔推荐解法 2511. 最多可以摧毁的敌人城堡数目解法——一次遍历 1921. 消灭怪物的最大数量贪心 57. 插入区间
https://leetcode.cn/problems/insert-interval/ 提示 0 intervals.length 10^4 intervals[i].length 2 0 intervals[i][0] intervals[i][1] 10^5 intervals 根据 intervals[i][0] 按 升序 排列 newInterval.length 2 0 newInterval[0] newInterval[1] 10^5
当前区间与要加入的新区间之间的关系只有两种可能相交或者不相交。
如果相交将两者结合即可。 如果不相交判断新加入的区间是否在当前区间之前如果是就先加入答案。
遍历一遍之后如果没有处理过新加入的区间就说明新区间应该加在最后。
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {if (intervals.length 0) return new int[][]{newInterval};Listint[] 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 在此区间之前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;}// 如果没有处理过 newIntervalif (!f) ans.add(newInterval);return ans.toArray(new int[ans.size()][2]);}
}823. 带因子的二叉树
https://leetcode.cn/problems/binary-trees-with-factors/ 提示 1 arr.length 1000 2 arr[i] 10^9 arr 中的所有值 互不相同
解法——递推
将元素排序之后从小到大依次处理各个数值作为根节点时的二叉树数量。
class Solution {final long MOD (long)1e9 7;public int numFactoredBinaryTrees(int[] arr) {Arrays.sort(arr);int n arr.length;long ans 0;MapInteger, Long m new HashMap(); // 存储每个数字作为根节点时的二叉树数量for (int i 0; i n; i) {long cnt 1;for (int j 0; j i; j) { // 枚举儿子节点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. 到家的最少跳跃次数(BFS最远距离上界的证明)
https://leetcode.cn/problems/minimum-jumps-to-reach-home/description/
提示 1 forbidden.length 1000 1 a, b, forbidden[i] 2000 0 x 2000 forbidden 中所有位置互不相同。 位置 x 不在 forbidden 中。
可以证明一定可以在[0, max(f a b, x b)] 的下标范围内找到最优解其中 f 是最远进制点的坐标。 因为 f, a, b, x 2000故搜索范围不会超过 6000。证明略我也没整明白
用 bfs 计算最短路。
class Solution {public int minimumJumps(int[] forbidden, int a, int b, int x) {SetInteger s new HashSet();for (int v: forbidden) s.add(v);Dequeint[] q new ArrayDeque();q.offer(new int[]{0, 1}); // 将起点放入队列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];// 到达了目的地直接返回答案if (i x) return ans;Listint[] 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. 一个图中连通三元组的最小度数
https://leetcode.cn/problems/minimum-degree-of-a-connected-trio-in-a-graph/ 提示 2 n 400 edges[i].length 2 1 edges.length n * (n-1) / 2 1 ui, vi n ui ! vi 图中没有重复的边。
构造邻接表枚举每一个三元组。
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. 买钢笔和铅笔的方案数
https://leetcode.cn/problems/number-of-ways-to-buy-pens-and-pencils/ 提示 1 total, cost1, cost2 10^6
解法1——完全背包
套用完全背包模板对dp数组求和即可。
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——枚举买了几支钢笔推荐解法
通过枚举购买钢笔的数量计算此时可以购买铅笔的数量1即是购买此时数量钢笔时购买铅笔的方案数。
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. 最多可以摧毁的敌人城堡数目
https://leetcode.cn/problems/maximum-enemy-forts-that-can-be-captured/?envTypedaily-questionenvId2023-09-02 提示 1 forts.length 1000 -1 forts[i] 1
解法——一次遍历
题目要求是计算 1 和 -1 之间的 0 的最大数量。
一次遍历遍历的过程中记录上一个 1 或 -1 出现的位置即可。
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. 消灭怪物的最大数量贪心
https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/ 提示 n dist.length speed.length 1 n 10^5 1 dist[i], speed[i] 10^5
先计算时间再按时间排序。 贪心的先消灭快要到达城市的怪兽。
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;}
}
