墨の折腾小屋

[leetcode 1611][Go][位运算][记忆化搜索]使整数变为 0 的最少操作次数

荐

[leetcode 1986][状压DP]完成任务的最少工作时间段

荐

[leetcode 2197][Go][栈][模拟]替换数组中的非质数

荐

[leetcode 2318][三维DP][二维DP]不同骰子序列的数目

Github主页

inkOrCloud

首页

Java

算法

前端

Android

后端

[leetcode 3171][备忘录][Go]关于LogTrick解法的个人理解

算法

Created2026-11-142026-03-08 golang 位运算 LogTrick

题目连接 leetcode 3171 参考链接灵茶山艾府 - leetcode 3171题解解题思路主要目的就是算出所有子数组的按位运算值并算出与k的绝对差，暴力解法时间复杂度为且题目中nums.length最大值为肯定会超时为了更好理解，设一对指针l/r和一个数组dp[]，dp[l]表示nums[r]|nums[r-1]|nums[r-2]...nums[l]的值，即子数组r至l的按位与运算值(当r后移时dp[0]至dp[r]中的值会被覆盖) LogTrick的思路就是利用当a|b=b时a|b|c|d|e == b|c|d|e的特点省去大量的重复计算(最终时间复杂度能达到)，即当(nums[r]|dp[l]) == dp[l]就可以直接跳过dp[l-1]到dp[0]的计算，因为此时dp[l],dp[l-1],dp[l-2]…dp[0]与上一个r边界的值完全相同 123456789var dp = make([]int, len(nums))var ret = abs(nums[0]-k)for r := range nums { //当(nums[r]|dp[l])== ...

算法

未读

[leetcode 3347][Go][答案二分]万能的二分法

Created2026-11-142026-03-08 golang 二分查找

力扣随机五道题三道都是二分题目链接 leetcode 3347 执行操作后元素的最高频率 II ## 解题思路超时方案:暴力枚举+二分查找枚举所有可能的n，再通过二分查找n的数量、n-k至n+k的范围，结合操作上限得出，在3346 执行操作后元素的最高频率 I中能通过，但在此题中能超时 123456789101112131415161718192021222324252627282930313233343536373839404142434445func findLeftIndex(nums []int, n int) int { var l, r = 0, len(nums) - 1 if nums[0] >= n { return -1 } for l < r { m := (l + r + 1) / 2 if nums[m] >= n { r = m - 1 } else { l = m } } return l}func findRightIndex(nums []int, n int) int { var l, r = 0, len( ...

[leetcode 3321][Go][有序集合]计算子数组的 x-sum II

算法

未读

[leetcode 3321][Go][有序集合]计算子数组的 x-sum II

Created2026-11-142026-03-08 golang 滑动窗口有序集合

题目链接 leetcode 3321 计算子数组的 x-sum II 前置题目 leetcode 3318 计算子数组的 x-sum I 解题思路根据题目，首先可以定义一个键值对绑定数值以及该数值在当前子数组中出现的频率 12345//也可以用长度为2的数组，根据个人喜好即可type pair struct { freq int //频率 num int //数值} 然后需要实现以下功能: 根据数值快速查询到子数组频率并修改修改后的键值对应该保持有序性能够快速查询子数组前x个频繁出现的数值的和要实现以上三个功能，可以使用一个滑动窗口加两个有序集合和一个哈希表来实现。滑动窗口用于表示当前子数组两个有序集合分别存储当前子数组下前x个频繁出现的数和剩余的数哈希表用于存储当前子数组下每个数的出现频率定义比较器 123456func comparator(a pair, b pair) int { if a.freq != b.freq { return a.freq - b.freq } return a.num - b.num} 定义集合结构 1234567891 ...

算法

未读

[leetcode 2589][Go][贪心]完成所有任务的最少时间

Created2025-11-212026-03-08 golang 贪心

题目链接 leetcode 2589 完成所有任务的最少时间解题思路将tasks根据右端点排序，只考虑右端点的情况，那么就只有三种: 没有交集后n个数组的前缀与当前数组的后缀重合与相邻的数组完全包含对于这三种情况，只要尽量将时间点靠近右端点就能尽量重合 1234567891011121314151617181920212223func findMinimumTime(tasks [][]int) int { var run = make([]bool, 2001) sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] }) var ret = 0 for i := range tasks { s, e, d := tasks[i][0], tasks[i][1], tasks[i][2] for j := s; j <= e; j++ { if run[j] { d-- } } for j := e; j >= s ...

算法

未读

[leetcode 3234][Go]统计1显著的字符串的数量

Created2025-11-152026-03-08 golang

题目链接 leetcode 3234 统计1显著的字符串的数量解题思路设i为右边界，并记录每个0的坐标，pos0[0]为-1，pos0[n]为第n个0的坐标，每当i右移时进行以下操作: 记录0下标，记录1的数量若s[i]为0，记录i并追加到pos0，设oneSum当前[0,i]内1的数量 12345if s[i] == '1' { oneSum++} else { pos0 = append(pos0, i)} 计算以i结尾符合要求的子串数量获取最近的0的坐标p，此时(p，i]内没有0，任意子串都符合要求，计算(p,i]内以i结尾的子串数量ret+=p-i 123//zeroSum表示[0,i]内0的数量zeroSum := len(pos0)ret += i - pos0[zeroSum-1] 从后往前遍历i之前的所有0下标j，计算[pos0[j],i]内0的数量cnt0=zeroSum-j，计算(pos0[j-1],i]内1的数量cnt1=i-pos[j-1]-cnt0，若k为pos0[j-1]+1，不断右移k，此时每右移一次就会减少一个1，只要[k,i]之前1 ...

[leetcode 1611][Go][位运算][记忆化搜索]使整数变为 0 的最少操作次数

算法

未读

[leetcode 1611][Go][位运算][记忆化搜索]使整数变为 0 的最少操作次数

Created2025-11-082026-03-08 golang 记忆化搜索位运算

题目链接 leetcode 1611 使整数变为 0 的最少操作次数解题思路递归(超时) 根据题目得知，要将数n变为0，那只能从左往右将所有为1的位数翻转。设i为下标从左往右遍历，若第i为为1则进行翻转，翻转时无论第i位为1还是0都需要分为以下三种情况处理: 若i为0则直接翻转若i大于0且i-1为0则先递归处理将i-1翻转为1，翻转后再按照下面的情况处理若i大于0且i-1为1则设j = [i-2, 0]，遍历j，若第j位为1则先递归翻转第j位根据以上子问题就可以初步构建递归函数: 1234567891011121314151617181920212223242526272829303132333435363738//判断第i位是否为0var isZero = func(n int, i int) bool { return 1<<i|n != n}//翻转第i位，返回操作次数和进行翻转后得到的数字var reverse func(n int, i int) (int, int)reverse = func(n, i int) (int, int) { / ...

[leetcode 2528][Go][二分答案][差分数组][前缀和]最大化城市的最小电量

算法

未读

[leetcode 2528][Go][二分答案][差分数组][前缀和]最大化城市的最小电量

Created2025-11-072026-03-08 golang 贪心算法差分数组前缀和二分查找

题目链接 leetcode 2528 最大化城市的最小电量解题思路二分查找首先最大问题最小化第一个先尝试使用二分查找，那就把大问题转化成了小问题:设一个值low，能否在新建供电站数量小于等于k的情况下使城市电量的最小值大于等于low。然后对low进行二分查找即可。 1234567891011func maxPower(stations []int, r int, k int) int64 { //预处理TODO //minP为所有城市初始电量的最小值 //power[i]表示第i个城市的初始电量 //sub为子问题 ret := sort.Search(k+1, func(i int) bool { return !sub(i+minP, r, k, power) }) - 1 + minP return int64(ret)} 二分查找复杂度为预处理每个城市的初始电量(前缀和) 每个城市的初始电量即当前城市左右范围r内的电站数量和，那么就可以求出电站数量的前缀和sum[]，再求出每个城市的初始电量power[] 12345678910111213 ...

算法

未读

[leetcode 2846][LCA]边权重均等查询

Created2025-11-042026-03-08 golang lca 树

题目链接 leetcode 边权重均等查询前置概念 LCA倍增树算法链接解题思路根据LCA的的性质，要确定两个节点的最短路径只需要确定两个节点与根节点的最短路径以及两个节点最近公共祖先与根节点的最短路径即可，所以只需要初始化一个树，再预处理计算出每个节点到根节点经过的边权为x的边的数量就能得出答案先将节点进行预处理，随机选择一个节点作为根节点，再计算出每个节点的父节点和子节点 123456789101112131415161718192021222324252627282930 //e[i]代表与节点i连接的节点以及边权(状态压缩)var e = make([][]int, n)for _, v := range edges { i, j, w := v[0], v[1], v[2] e[i] = append(e[i], j*27+w) e[j] = append(e[j], i*27+w)} //父节点，parent[i]表示i的父节点以及边权var parent = make([][]int, n)var child = make([][]int, n)//子节 ...

算法

未读

[模板]LCA倍增树算法

Created2025-11-032026-03-08 golang 树 LCA

参考 oi-wiki-LCA 定义最近公共祖先简称LCA(Lowest Common Ancestor)，指一棵树下两个节点公共祖先中离根最远的那个。下面用LCA({v1, v2, v3, v4..})表示节点的公共祖先性质若u是v的祖先，相反不为两者中的值，那么说明u,v不在同一棵子树中前序遍历中，出现在所有S中元素之前，后序遍历中则出现在所有𝑆中元素之后；两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即必定出现在u到v的最短路径上 d(u,v)代表u到v的距离,h代表节点到根的距离求法朴素求法过程将其中一个节点上跳至根并记录经过的节点，第二个节点上跳时第一个经过的已记录节点就是最近公共计算出冷个节点的高度差，将深度较大的那个节点上跳至两个节点深度一致，再同时上跳两个节点，当两个节点相遇时即可得出最近公共祖先时间复杂度预处理时时间复杂度为，单次查询时间复杂度为倍增算法过程倍增算法由朴素算法的第二种方案优化而来，先对所有节点进行预处理，pa[i][x]表示节点i的第个祖先节点 123456789101112131415/ ...

算法

未读

[leetcode 3479][线段树]水果成蓝 III

Created2025-10-302026-03-08 golang 线段树

题目链接 leetcode 3479 水果成蓝 III 前置概念线段树主要用于区间查找和区间更新，本质是一种完美二叉树，尤其适用于区间统计操作，例如区间求和，区间最值，区间最大公约数等线段树将一个数组递归划分为若干个子数组，每个节点代表一个区间，节点值即为该区间的统计数据(最值、求和、最大公约数)，所以叶子即对应每个元素结构特点节点数量:对于n个元素的数组，节点数量通常不超过4n 时间复杂度: - 建树: - 单点/区间更新(区间更新配合懒标记): - 区间查询: 建树(区间最大值) 1234567891011121314151617var n = len(arr)var tree = make([]int, 4*n)var build func(int, int, int) //i代表当前节点在tree中的对应下标，l/r表示i锁代表arr区间的左右边界build = func(i int, l int, r int) { //当l == r时说明当前节点是叶子节点(区间长度为1) if l == r { tree[i] = arr[l] retu ...