做垂直平台网站,30天网站建设 视频教程,校园网站建设重要性,佛山专业做淘宝网站推广文章目录 竞赛链接Q1#xff1a;8015. 距离原点最远的点#xff08;贪心#xff09;Q2#xff1a;8022. 找出美丽数组的最小和#xff08;贪心#xff09;Q3#xff1a;2835. 使子序列的和等于目标的最少操作次数#xff08;贪心#xff09;思路竞赛时丑陋代码#x… 文章目录 竞赛链接Q18015. 距离原点最远的点贪心Q28022. 找出美丽数组的最小和贪心Q32835. 使子序列的和等于目标的最少操作次数贪心思路竞赛时丑陋代码有一说一没眼看现在已经忘了当时是怎么想的了优雅代码 Q42836. 在传球游戏中最大化函数值⭐⭐⭐⭐⭐树上倍增解法——利用倍增算法模板题——1483. 树节点的第 K 个祖先 成绩记录 竞赛链接
https://leetcode.cn/contest/weekly-contest-360
Q18015. 距离原点最远的点贪心
https://leetcode.cn/problems/furthest-point-from-origin/ 提示 1 moves.length n 50 moves 仅由字符 L、R 和 _ 组成
抓住本质R 和 L 是不能改变的而 _ 是可以随意选择的因此可以在最后决定 _ 往哪个方向走。
class Solution {public int furthestDistanceFromOrigin(String moves) {int ans 0, cnt 0, pos 0;for (char ch: moves.toCharArray()) {if (ch R) pos;else if (ch L) pos--;else cnt;}return Math.abs(pos) cnt;}
}Q28022. 找出美丽数组的最小和贪心
https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/ 提示 1 n 10^5 1 target 10^5
这道题目和 第 359 场周赛 中的 6450. k-avoiding 数组的最小总和 几乎一样。
我们还是用贪心来解决从小到大能选就选。
class Solution {public long minimumPossibleSum(int n, int target) {long ans 0;SetInteger s new HashSet();for (int i 1; s.size() n; i) {if (!s.contains(target - i)) {s.add(i);ans i;}}return ans;}
}Q32835. 使子序列的和等于目标的最少操作次数贪心
https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/ 提示 1 nums.length 1000 1 nums[i] 2^30 nums 只包含非负整数且均为 2 的幂。 1 target 2^31
思路
首先确定 sum target 则一定有解否则一定无解。
竞赛时丑陋代码有一说一没眼看现在已经忘了当时是怎么想的了
class Solution {static MapInteger, Integer m new HashMap(), m2 new HashMap();static {for (int i 0, v 1; i 30; i, v * 2) {m.put(v, i);m2.put(i, v);}}public int minOperations(ListInteger nums, int target) {long sum 0;int[] cnt new int[31], cnt2 new int[31];for (int num: nums) {sum num;cnt[m.get(num)];}if (sum target) return -1;for (int i 30; i 0; --i) {if (target m2.get(i)) {cnt2[i];target - m2.get(i);}}int v 0, ans 0, last -1;for (int i 0; i 30; i) {if (cnt[i] cnt2[i]) {if (last ! -1) {ans i - last;last -1;v (cnt[i] - cnt2[i] - 1) * m2.get(i);} else {v (cnt[i] - cnt2[i]) * m2.get(i);}} else if (cnt[i] cnt2[i]) {if (v (cnt2[i] - cnt[i]) * m2.get(i)) {v - (cnt2[i] - cnt[i]) * m2.get(i);}else if (last -1) last i;}}return ans;}
}优雅代码
https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/solutions/2413344/tan-xin-by-endlesscheng-immn/
class Solution {public int minOperations(ListInteger nums, int target) {long s 0; // 求和long[] cnt new long[31]; // 统计2^i的数量for (int x: nums) {s x;cnt[Integer.numberOfTrailingZeros(x)];}if (s target) return -1; // 无解的情况int ans 0, i 0;s 0;// 注意这里是1L因为i 最大是 30这是可以进循环的但是加一后就变成 31 了虽然一定不会进入循环但是要在 while 那里判断一下。while ((1L i) target) {s cnt[i] i;int mask (int) ((1L i) - 1);if (s (target mask)) continue; // 检查当前和能否填补target部分ans; // 否则需要分解更大的数字while (cnt[i] 0) {ans;i;}}return ans;}
}Q42836. 在传球游戏中最大化函数值⭐⭐⭐⭐⭐树上倍增
https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/ 提示 1 receiver.length n 10^5 0 receiver[i] n - 1 1 k 10^10
解法——利用倍增算法
利用倍增算法预处理每个节点 x 的第 2^i个祖先节点以及从 x 的父节点到 x 的第 2^i 个祖先节点的节点编号之和。最后枚举起点 x一边向上跳一边累加节点编号。
可以从代码模板中修改过来多了要维护节点之间的和。
class Solution {public long getMaxFunctionValue(ListInteger receiver, long k) {int n receiver.size(); // 节点的个数int m 64 - Long.numberOfLeadingZeros(k); // k的二进制长度int[][] pa new int[n][m]; // 节点x的第2^i个祖宗节点的变好long[][] sum new long[n][m]; // 节点x的父节点到x的第2^i个祖宗节点的节点编号之和// 初始化dp数组for (int i 0; i n; i) {pa[i][0] receiver.get(i);sum[i][0] receiver.get(i);}// 递推dp数组先枚举i再枚举xfor (int i 0; i m - 1; i) { // 注意这里的条件是 i m - 1for (int x 0; x n; x) {int p pa[x][i];pa[x][i 1] p 0? -1: pa[p][i];// 合并节点的和 sum[x][i 1] sum[x][i] sum[p][i]; }}long ans 0;// 枚举各个节点作为起始节点for (int i 0; i n; i) {long s i;int x i;for (long t k; t 0; t t - 1) {int ctz Long.numberOfTrailingZeros(t);// 要先处理求和再处理节点的变化s sum[x][ctz]; x pa[x][ctz];}ans Math.max(ans, s);}return ans;}
}受 cpu 缓存的影响倍增的二维数组开成 log*n 会比 n*log 快很多。 二维数组开成 logn * n 的形状会比开成 n * logn 的形状快很多是因为在计算机中连续的内存访问比随机的内存访问更快。当我们按行访问一个二维数组时我们可以利用缓存行的概念即将一行的数据读入缓存中这样下一次访问时就可以直接从缓存中读取数据而不需要再次从内存中读取。如果我们按列访问二维数组则每次访问都需要跨越多个缓存行这样会导致缓存失效从而降低程序的性能。因此将二维数组按行存储可以提高程序的性能。
所以可以将代码修改成如下
class Solution {public long getMaxFunctionValue(ListInteger receiver, long k) {int n receiver.size(); // 节点的个数int m 64 - Long.numberOfLeadingZeros(k); // k的二进制长度int[][] pa new int[m][n]; // 节点x的第2^i个祖宗节点的变好long[][] sum new long[m][n]; // 节点x的父节点到x的第2^i个祖宗节点的节点编号之和// 初始化dp数组for (int i 0; i n; i) {pa[0][i] receiver.get(i);sum[0][i] receiver.get(i);}// 递推dp数组先枚举i再枚举xfor (int i 0; i m - 1; i) { // 注意这里的条件是 i m - 1for (int x 0; x n; x) {int p pa[i][x];pa[i 1][x] p 0? -1: pa[i][p];// 合并节点的和 sum[i 1][x] sum[i][x] sum[i][p]; }}long ans 0;// 枚举各个节点作为起始节点for (int i 0; i n; i) {long s i;int x i;for (long t k; t 0; t t - 1) {int ctz Long.numberOfTrailingZeros(t);// 要先处理求和再处理节点的变化s sum[ctz][x]; x pa[ctz][x];}ans Math.max(ans, s);}return ans;}
}执行用时从 237ms 加速到了 65ms 。
模板题——1483. 树节点的第 K 个祖先
https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/description/ 提示 1 k n 5 * 10^4 parent[0] -1 表示编号为 0 的节点是根节点。 对于所有的 0 i n 0 parent[i] n 总成立 0 node n 至多查询 5 * 10^4 次
https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solutions/2305895/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/
本质上是动态规划记 pa[x][i] 为每个节点 x 的第 2^i 个祖先节点。如果不存在则为 -1。
计算方式如下 pa[x][1] pa[pa[x][0]][0] 的意思是x 节点的爷爷是 x 节点的父亲的父亲。 一般的有 pa[x][i 1] pa[pa[x][i]][i]。
class TreeAncestor {int[][] pa;// 使用原始数据将整个 pa 数组预处理出来public TreeAncestor(int n, int[] parent) {int m 32 - Integer.numberOfLeadingZeros(n); // n的二进制长度pa new int[n][m]; // 表示节点i的2^j个祖宗节点// 初始化dp数组即填充每个节点的父亲节点for (int i 0; i n; i) {pa[i][0] parent[i];}// 先枚举i再枚举x// 相当于先算出所有爷爷节点再算出所有爷爷的爷爷节点for (int i 0; i m - 1; i) {for (int x 0; x n; x) {int p pa[x][i]; // 取出x的第2^i个祖宗节点// x的第2^(i1)个祖宗节点 等于 x的第2^i个祖宗节点的第2^i个祖宗节点pa[x][i 1] p 0? -1: pa[p][i]; }}}// 取出node节点的第k个祖宗节点public int getKthAncestor(int node, int k) {// 写法1 从低位到高位枚举// int m 32 - Integer.numberOfLeadingZeros(k); // k的二进制长度// for (int i 0; i m; i) {// if ((k i 1) 1) { // k的二进制当前位为1// node pa[node][i];// if (node 0) break;// }// }// return node;// 写法2 不断去掉k末尾的1for (; k ! 0 node ! -1; k k - 1) {node pa[node][Integer.numberOfTrailingZeros(k)];}return node;}
}/*** Your TreeAncestor object will be instantiated and called as such:* TreeAncestor obj new TreeAncestor(n, parent);* int param_1 obj.getKthAncestor(node,k);*/成绩记录 最后一题实在是写不出来了。(不过还好好像大家也都写不出来
