网站正在备案中模板,营销型网站建设jm3q,建设网站的公司广州,网站开发公司管理模式#x1f31f;欢迎来到 我的博客 —— 探索技术的无限可能#xff01; #x1f31f;博客的简介#xff08;文章目录#xff09; 【题解】—— 每日一道题目栏 上接#xff1a;【题解】—— LeetCode一周小结43
28.冗余连接 II
题目链接#xff1a;685. 冗余连接 II
在… 欢迎来到 我的博客 —— 探索技术的无限可能 博客的简介文章目录 【题解】—— 每日一道题目栏 上接【题解】—— LeetCode一周小结43
28.冗余连接 II
题目链接685. 冗余连接 II
在本问题中有根树指满足以下条件的 有向 图。该树只有一个根节点所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点而根节点没有父节点。
输入一个有向图该图由一个有着 n 个节点节点值不重复从 1 到 n的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]用以表示 有向 图中连接顶点 ui 和顶点 vi 的边其中 ui 是 vi 的一个父节点。
返回一条能删除的边使得剩下的图是有 n 个节点的有根树。若有多个答案返回最后出现在给定二维数组的答案。
示例 1 输入edges [[1,2],[1,3],[2,3]] 输出[2,3] 示例 2 输入edges [[1,2],[2,3],[3,4],[4,1],[1,5]] 输出[4,1] 提示 n edges.length 3 n 1000 edges[i].length 2 1 ui, vi n 题解 方法并查集
class Solution {private int[] p;public int[] findRedundantDirectedConnection(int[][] edges) {int n edges.length;int[] ind new int[n];for (var e : edges) {ind[e[1] - 1];}ListInteger dup new ArrayList();p new int[n];for (int i 0; i n; i) {if (ind[edges[i][1] - 1] 2) {dup.add(i);}p[i] i;}if (!dup.isEmpty()) {for (int i 0; i n; i) {if (i dup.get(1)) {continue;}int pu find(edges[i][0] - 1);int pv find(edges[i][1] - 1);if (pu pv) {return edges[dup.get(0)];}p[pu] pv;}return edges[dup.get(1)];}for (int i 0;; i) {int pu find(edges[i][0] - 1);int pv find(edges[i][1] - 1);if (pu pv) {return edges[i];}p[pu] pv;}}private int find(int x) {if (p[x] ! x) {p[x] find(p[x]);}return p[x];}
}29.生成不含相邻零的二进制字符串
题目链接3211. 生成不含相邻零的二进制字符串
给你一个正整数 n。
如果一个二进制字符串 x 的所有长度为 2 的 子字符串 中包含 至少 一个 “1”则称 x 是一个 有效 字符串。
返回所有长度为 n 的 有效 字符串可以以任意顺序排列。
示例 1 输入 n 3 输出 [“010”,“011”,“101”,“110”,“111”] 解释 长度为 3 的有效字符串有“010”、“011”、“101”、“110” 和 “111”。 示例 2 输入 n 1 输出 [“0”,“1”] 解释 长度为 1 的有效字符串有“0” 和 “1”。 提示 1 n 18 题解 方法回溯爆搜
class Solution {public ListString validStrings(int n) {ListString ans new ArrayList();char[] path new char[n];dfs(0, n, path, ans);return ans;}private void dfs(int i, int n, char[] path, ListString ans) {if (i n) {ans.add(new String(path));return;}// 填 1path[i] 1;dfs(i 1, n, path, ans);// 填 0if (i 0 || path[i - 1] 1) {path[i] 0; // 直接覆盖dfs(i 1, n, path, ans);}}
}30.交换后字典序最小的字符串
题目链接3216. 交换后字典序最小的字符串
给你一个仅由数字组成的字符串 s在最多交换一次 相邻 且具有相同 奇偶性 的数字后返回可以得到的 字典序最小的字符串 。
如果两个数字都是奇数或都是偶数则它们具有相同的奇偶性。例如5 和 9、2 和 4 奇偶性相同而 6 和 9 奇偶性不同。
示例 1 输入 s “45320” 输出 “43520” 解释 s[1] ‘5’ 和 s[2] ‘3’ 都具有相同的奇偶性交换它们可以得到字典序最小的字符串。 示例 2 输入 s “001” 输出 “001” 解释 无需进行交换因为 s 已经是字典序最小的。 提示 2 s.length 100 s 仅由数字组成。 题解 方法贪心
class Solution {public String getSmallestString(String s) {char[] t s.toCharArray();for (int i 1; i t.length; i) {char x t[i - 1];char y t[i];if (x y x % 2 y % 2) {t[i - 1] y;t[i] x;break;}}return new String(t);}
}31.不包含相邻元素的子序列的最大和
题目链接3165. 不包含相邻元素的子序列的最大和
给你一个整数数组 nums 和一个二维数组 queries其中 queries[i] [posi, xi]。
对于每个查询 i首先将 nums[posi] 设置为 xi然后计算查询 i 的答案该答案为 nums 中 不包含相邻元素 的 子序列 的 最大 和。
返回所有查询的答案之和。
由于最终答案可能非常大返回其对 109 7 取余 的结果。
子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。
示例 1 输入nums [3,5,9], queries [[1,-2],[0,-3]] 输出21 解释 执行第 1 个查询后nums [3,-2,9]不包含相邻元素的子序列的最大和为 3 9 12。 执行第 2 个查询后nums [-3,-2,9]不包含相邻元素的子序列的最大和为 9 。 示例 2 输入nums [0,-1], queries [[0,-5]] 输出0 解释 执行第 1 个查询后nums [-5,-1]不包含相邻元素的子序列的最大和为 0选择空子序列。 提示 1 nums.length 5 * 104 -105 nums[i] 105 1 queries.length 5 * 104 queries[i] [posi, xi] 0 posi nums.length - 1 -105 xi 105 题解 方法分治思想线段树
class Solution {public int maximumSumSubsequence(int[] nums, int[][] queries) {int n nums.length;// 4 个数分别保存 f00, f01, f10, f11long[][] t new long[2 (32 - Integer.numberOfLeadingZeros(n))][4];build(t, nums, 1, 0, n - 1);long ans 0;for (int[] q : queries) {update(t, 1, 0, n - 1, q[0], q[1]);ans t[1][3]; // 注意 f11 没有任何限制也就是整个数组的打家劫舍}return (int) (ans % 1_000_000_007);}// 合并左右儿子private void maintain(long[][] t, int o) {long[] a t[o * 2];long[] b t[o * 2 1];t[o][0] Math.max(a[0] b[2], a[1] b[0]);t[o][1] Math.max(a[0] b[3], a[1] b[1]);t[o][2] Math.max(a[2] b[2], a[3] b[0]);t[o][3] Math.max(a[2] b[3], a[3] b[1]);}// 用 nums 初始化线段树private void build(long[][] t, int[] nums, int o, int l, int r) {if (l r) {t[o][3] Math.max(nums[l], 0);return;}int m (l r) / 2;build(t, nums, o * 2, l, m);build(t, nums, o * 2 1, m 1, r);maintain(t, o);}// 把 nums[i] 改成 valprivate void update(long[][] t, int o, int l, int r, int i, int val) {if (l r) {t[o][3] Math.max(val, 0);return;}int m (l r) / 2;if (i m) {update(t, o * 2, l, m, i, val);} else {update(t, o * 2 1, m 1, r, i, val);}maintain(t, o);}
} 2024.11
1.超级饮料的最大强化能量
题目链接3259. 超级饮料的最大强化能量
来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。
你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而如果从一种能量饮料切换到另一种你需要等待一小时来梳理身体的能量体系在那个小时里你将不会获得任何强化能量。
返回在接下来的 n 小时内你能获得的 最大 总强化能量。
注意 你可以选择从饮用任意一种能量饮料开始。
示例 1 输入energyDrinkA [1,3,1], energyDrinkB [3,1,1] 输出5 解释 要想获得 5 点强化能量需要选择只饮用能量饮料 A或者只饮用 B。 示例 2 输入energyDrinkA [4,1,1], energyDrinkB [1,1,3] 输出7 解释 第一个小时饮用能量饮料 A。 切换到能量饮料 B 在第二个小时无法获得强化能量。 第三个小时饮用能量饮料 B 并获得强化能量。 提示 n energyDrinkA.length energyDrinkB.length 3 n 105 1 energyDrinkA[i], energyDrinkB[i] 105 题解 方法递归搜索 保存递归返回值 记忆化搜索
class Solution {public long maxEnergyBoost(int[] a, int[] b) {int n a.length;int[][] c {a, b};long[][] memo new long[n][2];return Math.max(dfs(n - 1, 0, c, memo), dfs(n - 1, 1, c, memo));}private long dfs(int i, int j, int[][] c, long[][] memo) {if (i 0) {return 0;}if (memo[i][j] 0) { // 之前计算过return memo[i][j];}return memo[i][j] Math.max(dfs(i - 1, j, c, memo), dfs(i - 2, j ^ 1, c, memo)) c[j][i];}
}2.使两个整数相等的位更改次数
题目链接3226. 使两个整数相等的位更改次数
给你两个正整数 n 和 k。
你可以选择 n 的 二进制表示 中任意一个值为 1 的位并将其改为 0。
返回使得 n 等于 k 所需要的更改次数。如果无法实现返回 -1。
示例 1 输入 n 13, k 4 输出 2 解释 最初n 和 k 的二进制表示分别为 n (1101)2 和 k (0100)2 我们可以改变 n 的第一位和第四位。结果整数为 n (0100)2 k。 示例 2 输入 n 21, k 21 输出 0 解释 n 和 k 已经相等因此不需要更改。 示例 3 输入 n 14, k 13 输出 -1 解释 无法使 n 等于 k。 提示 1 n, k 106 题解 方法O(1) 位运算做法
class Solution {public int minChanges(int n, int k) {return (n k) ! k ? -1 : Integer.bitCount(n ^ k);}
}3.大礼包
题目链接638. 大礼包
在 LeetCode 商店中 有 n 件在售的物品。每件物品都有对应的价格。然而也有一些大礼包每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 price 表示物品价格其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单其中 needs[i] 是需要购买第 i 件物品的数量。
还有一个数组 special 表示大礼包special[i] 的长度为 n 1 其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量且 special[i][n] 也就是数组中的最后一个整数为第 i 个大礼包的价格。
返回 确切 满足购物清单所需花费的最低价格你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品即使那样会降低整体价格。任意大礼包可无限次购买。
示例 1 输入price [2,5], special [[3,0,5],[1,2,10]], needs [3,2] 输出14 解释有 A 和 B 两种物品价格分别为 ¥2 和 ¥5 。 大礼包 1 你可以以 ¥5 的价格购买 3A 和 0B 。 大礼包 2 你可以以 ¥10 的价格购买 1A 和 2B 。 需要购买 3 个 A 和 2 个 B 所以付 ¥10 购买 1A 和 2B大礼包 2以及 ¥4 购买 2A 。 示例 2 输入price [2,3,4], special [[1,1,0,4],[2,2,1,9]], needs [1,2,1] 输出11 解释A B C 的价格分别为 ¥2 ¥3 ¥4 。 可以用 ¥4 购买 1A 和 1B 也可以用 ¥9 购买 2A 2B 和 1C 。 需要买 1A 2B 和 1C 所以付 ¥4 买 1A 和 1B大礼包 1以及 ¥3 购买 1B ¥4 购买 1C 。 不可以购买超出待购清单的物品尽管购买大礼包 2 更加便宜。 提示 n price.length needs.length 1 n 6 0 price[i], needs[i] 10 1 special.length 100 special[i].length n 1 0 special[i][j] 50 生成的输入对于 0 j n - 1 至少有一个 special[i][j] 非零。 题解 方法状态压缩 记忆化搜索
class Solution {private final int bits 4;private int n;private ListInteger price;private ListListInteger special;private MapInteger, Integer f new HashMap();public int shoppingOffers(ListInteger price, ListListInteger special, ListInteger needs) {n needs.size();this.price price;this.special special;int mask 0;for (int i 0; i n; i) {mask | needs.get(i) (i * bits);}return dfs(mask);}private int dfs(int cur) {if (f.containsKey(cur)) {return f.get(cur);}int ans 0;for (int i 0; i n; i) {ans price.get(i) * (cur (i * bits) 0xf);}for (ListInteger offer : special) {int nxt cur;boolean ok true;for (int j 0; j n; j) {if ((cur (j * bits) 0xf) offer.get(j)) {ok false;break;}nxt - offer.get(j) (j * bits);}if (ok) {ans Math.min(ans, offer.get(n) dfs(nxt));}}f.put(cur, ans);return ans;}
}下接【题解】—— LeetCode一周小结45
