男男床上爱做 网站,最近一星期的新闻,中国商标官方网站,python在线运行#x1f31f;欢迎来到 我的博客 —— 探索技术的无限可能#xff01; #x1f31f;博客的简介#xff08;文章目录#xff09; 【题解】—— 每日一道题目栏 上接#xff1a;【题解】—— LeetCode一周小结45 11.切棍子的最小成本
题目链接#xff1a;1547. 切棍子的最… 欢迎来到 我的博客 —— 探索技术的无限可能 博客的简介文章目录 【题解】—— 每日一道题目栏 上接【题解】—— LeetCode一周小结45 11.切棍子的最小成本
题目链接1547. 切棍子的最小成本
有一根长度为 n 个单位的木棍棍上从 0 到 n 标记了若干位置。例如长度为 6 的棍子可以标记如下 给你一个整数数组 cuts 其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍这两根木棍的长度和就是切割前木棍的长度。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1 输入n 7, cuts [1,3,4,5] 输出16 解释按 [1, 3, 4, 5] 的顺序切割的情况如下所示 第一次切割长度为 7 的棍子成本为 7 。第二次切割长度为 6 的棍子即第一次切割得到的第二根棍子第三次切割为长度 4 的棍子最后切割长度为 3 的棍子。总成本为 7 6 4 3 20 。 而将切割顺序重新排列为 [3, 5, 1, 4] 后总成本 16如示例图中 7 4 3 2 16。 示例 2 输入n 9, cuts [5,6,1,4,2] 输出22 解释如果按给定的顺序切割则总成本为 25 。总成本 25 的切割顺序很多例如[4, 6, 5, 2, 1] 的总成本 22是所有可能方案中成本最小的。 提示 2 n 10^6 1 cuts.length min(n - 1, 100) 1 cuts[i] n - 1 cuts 数组中的所有整数都 互不相同 题解 方法记忆化搜索
class Solution {public int minCost(int n, int[] cuts) {Arrays.sort(cuts);int m cuts.length 2;int[] newCuts new int[m];System.arraycopy(cuts, 0, newCuts, 1, m - 2);newCuts[m - 1] n;int[][] memo new int[m][m];return dfs(0, m - 1, newCuts, memo);}private int dfs(int i, int j, int[] cuts, int[][] memo) {if (i 1 j) { // 无需切割return 0;}if (memo[i][j] 0) { // 之前计算过return memo[i][j];}int res Integer.MAX_VALUE;for (int k i 1; k j; k) {res Math.min(res, dfs(i, k, cuts, memo) dfs(k, j, cuts, memo));}return memo[i][j] res cuts[j] - cuts[i];}
}12.统计满足 K 约束的子字符串数量 I
题目链接3258. 统计满足 K 约束的子字符串数量 I
给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件则认为该字符串满足 k 约束
字符串中 0 的数量最多为 k。 字符串中 1 的数量最多为 k。 返回一个整数表示 s 的所有满足 k 约束 的 子字符串 的数量。
示例 1 输入s “10101”, k 1 输出12 解释 s 的所有子字符串中除了 “1010”、“10101” 和 “0101” 外其余子字符串都满足 k 约束。 示例 2 输入s “1010101”, k 2 输出25 解释 s 的所有子字符串中除了长度大于 5 的子字符串外其余子字符串都满足 k 约束。 示例 3 输入s “11111”, k 1 输出15 解释 s 的所有子字符串都满足 k 约束。 提示 1 s.length 50 1 k s.length s[i] 是 ‘0’ 或 ‘1’。 题解 方法滑动窗口
class Solution {public int countKConstraintSubstrings(String S, int k) {char[] s S.toCharArray();int ans 0;int left 0;int[] cnt new int[2];for (int i 0; i s.length; i) {cnt[s[i] 1];while (cnt[0] k cnt[1] k) {cnt[s[left] 1]--;left;}ans i - left 1;}return ans;}
}13.统计满足 K 约束的子字符串数量 II
题目链接3261. 统计满足 K 约束的子字符串数量 II
给你一个 二进制 字符串 s 和一个整数 k。
另给你一个二维整数数组 queries 其中 queries[i] [li, ri] 。
如果一个 二进制字符串 满足以下任一条件则认为该字符串满足 k 约束
字符串中 0 的数量最多为 k。 字符串中 1 的数量最多为 k。 返回一个整数数组 answer 其中 answer[i] 表示 s[li…ri] 中满足 k 约束 的 子字符串 的数量。
示例 1 输入s “0001111”, k 2, queries [[0,6]] 输出[26] 解释 对于查询 [0, 6] s[0…6] “0001111” 的所有子字符串中除 s[0…5] “000111” 和 s[0…6] “0001111” 外其余子字符串都满足 k 约束。 示例 2 输入s “010101”, k 1, queries [[0,5],[1,4],[2,3]] 输出[15,9,3] 解释 s 的所有子字符串中长度大于 3 的子字符串都不满足 k 约束。 提示 1 s.length 105 s[i] 是 ‘0’ 或 ‘1’ 1 k s.length 1 queries.length 105 queries[i] [li, ri] 0 li ri s.length 所有查询互不相同 题解 方法滑动窗口前缀和二分查找
class Solution {public long[] countKConstraintSubstrings(String S, int k, int[][] queries) {char[] s S.toCharArray();int n s.length;int[] left new int[n];long[] sum new long[n 1];int[] cnt new int[2];int l 0;for (int i 0; i n; i) {cnt[s[i] 1];while (cnt[0] k cnt[1] k) {cnt[s[l] 1]--;}left[i] l; // 记录合法子串右端点 i 对应的最小左端点 l// 计算 i-left[i]1 的前缀和sum[i 1] sum[i] i - l 1;}long[] ans new long[queries.length];for (int i 0; i queries.length; i) {int ql queries[i][0];int qr queries[i][1];// 如果区间内所有数都小于 ql结果是 jqr1int j lowerBound(left, ql - 1, qr 1, ql);ans[i] sum[qr 1] - sum[j] (long) (j - ql 1) * (j - ql) / 2;}return ans;}// 返回在开区间 (left, right) 中的最小的 j满足 nums[j] target// 如果没有这样的数返回 right// 原理见 https://www.bilibili.com/video/BV1AP41137w7/private int lowerBound(int[] nums, int left, int right, int target) {while (left 1 right) { // 区间不为空// 循环不变量// nums[left] target// nums[right] targetint mid left (right - left) / 2;if (nums[mid] target) {left mid; // 范围缩小到 (mid, right)} else {right mid; // 范围缩小到 (left, mid)}}return right;}
}
方法预处理
class Solution {public long[] countKConstraintSubstrings(String S, int k, int[][] queries) {char[] s S.toCharArray();int n s.length;int[] left new int[n];long[] sum new long[n 1];int[] cnt new int[2];int l 0;for (int i 0; i n; i) {cnt[s[i] 1];while (cnt[0] k cnt[1] k) {cnt[s[l] 1]--;}left[i] l;sum[i 1] sum[i] i - l 1;}int[] right new int[n];l 0;for (int i 0; i n; i) {while (l n left[l] i) {l;}right[i] l;}long[] ans new long[queries.length];for (int i 0; i queries.length; i) {int ql queries[i][0];int qr queries[i][1];int j Math.min(right[ql], qr 1);ans[i] sum[qr 1] - sum[j] (long) (j - ql 1) * (j - ql) / 2;}return ans;}
}14.统计好节点的数目
题目链接3249. 统计好节点的数目
现有一棵 无向 树树中包含 n 个节点按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges其中 edges[i] [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。
如果一个节点的所有子节点为根的 子树 包含的节点数相同则认为该节点是一个 好节点。
返回给定树中 好节点 的数量。
子树 指的是一个节点以及它所有后代节点构成的一棵树。
示例 1 输入edges [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] 输出7 说明 树的所有节点都是好节点。 示例 2 输入edges [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]] 输出6 说明 树中有 6 个好节点。上图中已将这些节点着色。 示例 3 输入edges [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]] 输出12 解释 除了节点 9 以外其他所有节点都是好节点。 提示 2 n 105 edges.length n - 1 edges[i].length 2 0 ai, bi n 输入确保 edges 总表示一棵有效的树。 题解 方法深度优先搜索
class Solution {public int countGoodNodes(int[][] edges) {int n edges.length 1;ListInteger[] g new ArrayList[n];Arrays.setAll(g, i - new ArrayList());for (int[] e : edges) {int x e[0];int y e[1];g[x].add(y);g[y].add(x);}dfs(0, -1, g);return ans;}private int ans;private int dfs(int x, int fa, ListInteger[] g) {int size 1;int sz0 0;boolean ok true;for (int y : g[x]) {if (y fa) {continue; // 不能递归到父节点}int sz dfs(y, x, g);if (sz0 0) {sz0 sz; // 记录第一个儿子子树的大小} else if (sz ! sz0) { // 存在大小不一样的儿子子树ok false; // 注意不能 break其他子树 y 仍然要递归}size sz;}ans ok ? 1 : 0;return size;}
}15.最少翻转次数使二进制矩阵回文 I
题目链接3239. 最少翻转次数使二进制矩阵回文 I
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 也就是将格子里的值从 0 变成 1 或者从 1 变成 0 。
请你返回 最少 翻转次数使得矩阵 要么 所有行是 回文的 要么所有列是 回文的 。
示例 1 输入grid [[1,0,0],[0,0,0],[0,0,1]] 输出2 解释 将高亮的格子翻转得到所有行都是回文的。 示例 2 输入grid [[0,1],[0,1],[0,0]] 输出1 解释 将高亮的格子翻转得到所有列都是回文的。 示例 3 输入grid [[1],[0]] 输出0 解释 所有行已经是回文的。 提示 m grid.length n grid[i].length 1 m * n 2 * 105 0 grid[i][j] 1 题解 方法回文
class Solution {public int minFlips(int[][] grid) {int m grid.length;int n grid[0].length;int diffRow 0;for (int[] row : grid) {for (int j 0; j n / 2; j) {if (row[j] ! row[n - 1 - j]) {diffRow;}}}int diffCol 0;for (int j 0; j n; j) {for (int i 0; i m / 2; i) {if (grid[i][j] ! grid[m - 1 - i][j]) {diffCol;}}}return Math.min(diffRow, diffCol);}
}16.最少翻转次数使二进制矩阵回文 II
题目链接3240. 最少翻转次数使二进制矩阵回文 II
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 也就是将格子里的值从 0 变成 1 或者从 1 变成 0 。
请你返回 最少 翻转次数使得矩阵中 所有 行和列都是 回文的 且矩阵中 1 的数目可以被 4 整除 。
示例 1 输入grid [[1,0,0],[0,1,0],[0,0,1]] 输出3 解释 示例 2 输入grid [[0,1],[0,1],[0,0]] 输出2 解释 示例 3 输入grid [[1],[1]] 输出2 解释 提示 m grid.length n grid[i].length 1 m * n 2 * 105 0 grid[i][j] 1 题解 方法贪心
class Solution {public int minFlips(int[][] a) {int m a.length;int n a[0].length;int ans 0;for (int i 0; i m / 2; i) {for (int j 0; j n / 2; j) {int cnt1 a[i][j] a[i][n - 1 - j] a[m - 1 - i][j] a[m - 1 - i][n - 1 - j];ans Math.min(cnt1, 4 - cnt1); // 全为 1 或全为 0}}if (m % 2 0 n % 2 0) {// 正中间的数必须是 0ans a[m / 2][n / 2];}int diff 0;int cnt1 0;if (m % 2 0) {// 统计正中间这一排for (int j 0; j n / 2; j) {if (a[m / 2][j] ! a[m / 2][n - 1 - j]) {diff;} else {cnt1 a[m / 2][j] * 2;}}}if (n % 2 0) {// 统计正中间这一列for (int i 0; i m / 2; i) {if (a[i][n / 2] ! a[m - 1 - i][n / 2]) {diff;} else {cnt1 a[i][n / 2] * 2;}}}return ans (diff 0 ? diff : cnt1 % 4);}
}17.适龄的朋友
题目链接825. 适龄的朋友
在社交媒体网站上有 n 个用户。给你一个整数数组 ages 其中 ages[i] 是第 i 个用户的年龄。
如果下述任意一个条件为真那么用户 x 将不会向用户 yx ! y发送好友请求
ages[y] 0.5 * ages[x] 7 ages[y] ages[x] ages[y] 100 ages[x] 100 否则x 将会向 y 发送一条好友请求。
注意如果 x 向 y 发送一条好友请求y 不必也向 x 发送一条好友请求。另外用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
示例 1 输入ages [16,16] 输出2 解释2 人互发好友请求。 示例 2 输入ages [16,17,18] 输出2 解释产生的好友请求为 17 - 16 18 - 17 。 示例 3 输入ages [20,30,100,110,120] 输出3 解释产生的好友请求为 110 - 100 120 - 110 120 - 100 。 提示 n ages.length 1 n 2 * 104 1 ages[i] 120 题解 方法计数滑动窗口
class Solution {public int numFriendRequests(int[] ages) {int[] cnt new int[121];for (int age : ages) {cnt[age];}int ans 0;int ageY 0;int cntWindow 0;for (int ageX 0; ageX cnt.length; ageX) {cntWindow cnt[ageX];if (ageY * 2 ageX 14) { // 不能发送好友请求cntWindow - cnt[ageY];ageY;}if (cntWindow 0) { // 存在可以发送好友请求的用户ans cnt[ageX] * cntWindow - cnt[ageX];}}return ans;}
}下接【题解】—— LeetCode一周小结47
