2 抽象 将一个包含m个整数的数组分成n个数组,每个数组的和尽量接近 3 思路 这个问题是典型的动态规划的问题,理论上是无法找到最优解的,但是本次只是为了解决实际生产中的问题,而不是要AC,所以我们只需要找到一个相对合理的算法...输入:int数组,分组数divisionNum 对数组倒序排序 计算数组的平均值 avg 遍历数组。...如果第一个数大于等于avg,将这个数单独作为一组,因为再加下一个数也不会使得求和更接近avg;然后将剩下的数重新求平均,表示需要让剩下的数分配得更加平均,这样可以避免极值的影响,然后重新开始下一轮计算...如果第一个数num小于avg,我们将这个数加入到数组中,然后我们需要找到一(或若干)个数,使得其和更接近delta = avg-num, 继续遍历数组,若发现某个数k==delta,将k加入到数组,结束本轮寻找...22 3, sum = 53 arr 3 is : 27 10 6 5 2 2 1, sum = 53 4 实现 // 将数组分成n个数组,每个数组的和尽量接近 func GetAvgArr(numberList
2022-04-09:给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m , 数组下标 从 1 开始 计数。 初始时,你的分数为 0 。...你需要执行恰好 m 步操作。在第 i 步操作(从 1 开始 计数)中,需要: 选择数组 nums 开头处或者末尾处 的整数 x 。...你获得 multipliers[i] * x 分,并累加到你的分数中。 将 x 从数组 nums 中移除。 在执行 m 步操作后,返回 最大 分数。 力扣1770。..., M+1) } for L := M - 1; L >= 0; L-- { for j := L + 1; j <= M; j++ { R := N - M + j - 1...indexB := L + N - R - 1 dp[L][j] = getMax(A[L]*B[indexB]+dp[L+1][j], A[R]*B[indexB]+dp[L
2022-04-09:给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m , 数组下标 从 1 开始 计数。 初始时,你的分数为 0 。...你需要执行恰好 m 步操作。在第 i 步操作(从 1 开始 计数)中,需要: 选择数组 nums 开头处或者末尾处 的整数 x 。 你获得 multipliersi * x 分,并累加到你的分数中。...将 x 从数组 nums 中移除。 在执行 m 步操作后,返回 最大 分数。 力扣1770。 答案2022-04-09: 样本对应模型。 代码用golang编写。...:= len(A) M := len(B) dp := make([][]int, M+1) for i := 0; i < M+1; i++ { dp[i] = make([]int, M+...1) } for L := M - 1; L >= 0; L-- { for j := L + 1; j <= M; j++ { R := N - M + j - 1 indexB
2023-01-06:给定一个只由小写字母组成的字符串str,长度为N, 给定一个只由0、1组成的数组arr,长度为N, arr[i]等于 0 表示str中i位置的字符不许修改, arr[i] 等于...1表示str中i位置的字符允许修改, 给定一个正数m,表示在任意允许修改的位置, 可以把该位置的字符变成a~z中的任何一个, 可以修改m次。...返回在最多修改m次的情况下,全是一种字符的最长子串是多长。 1 <= N, M <= 10^5, 所有字符都是小写。 来自字节。 答案2023-01-06: 尝试全变成a一直到全变成z,遍历26次。...时间复杂度:O(N)。 空间复杂度:O(1)。 代码用rust和solidity编写。 代码用rust编写。...用完的时候 let mut change = 0; for l in 0..n { // l......r -> while
2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。...她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher : 对每个满足 0 <= i < n 的下标 i ,lower[i] = arr[i] -...给你一个由 2n 个整数组成的整数数组 nums ,其中 恰好 n 个整数出现在 lower ,剩下的出现在 higher ,还原并返回 原数组 arr 。...组合 lower 和 higher 得到 [2,6,10,4,8,12] ,这是 nums 的一个排列。 另一个有效的数组是 arr = [5,7,9] 且 k = 3 。...= nums.len() as isize; // nums[0] -> 小数组的第0个 let m = n >> 1; // 谁是大数组的第0个?
2023-01-06:给定一个只由小写字母组成的字符串str,长度为N,给定一个只由0、1组成的数组arr,长度为N,arri等于 0 表示str中i位置的字符不许修改,arri 等于 1表示str中i...位置的字符允许修改,给定一个正数m,表示在任意允许修改的位置,可以把该位置的字符变成a~z中的任何一个,可以修改m次。...返回在最多修改m次的情况下,全是一种字符的最长子串是多长。1 while r
2021-04-05:给两个长度分别为M和N的整型数组nums1和nums2,其中每个值都不大于9,再给定一个正数K。 你可以在nums1和nums2中挑选数字,要求一共挑选K个,并且要从左到右挑。...2.动态规划+选元素+双指针的DC3合并。有代码。 2.1.dpi,i是数组序号,j是0,K的数,dpi是最优位置。 2.2.从arr1和arr2中选元素。...2.3.合并arr1中的选中的元素和arr2中的选中的元素,采用dc算法。 2.4.返回最大值。 代码用golang编写。...maxPick(nums1, dp1, get1) //arr2中挑元素 pick2 := maxPick(nums2, dp2, k-get1) //和并挑的元素...~ N maxIndex := size - get // i~N-1 for i := size - get; i >= 0; i-- {
2023-12-06:用go语言,给你一个由 n 个数对组成的数对数组 pairs, 其中 pairs[i] = [lefti, righti] 且 lefti < righti 。...2.创建一个大小为 n 的整型数组 ends,用于存储当前数对链中每个数对的右边界值。 3.初始化变量 size 为 0,表示当前数对链的长度。...4.遍历排序后的数对数组 pairs: • 对于每个数对 pair,使用二分搜索找到 ends 数组中第一个大于等于 pair[0] 的索引 find。...5.返回变量 size 即为能够形成的最长数对链长度。 总的时间复杂度:在排序和遍历过程中,都需要 O(n log n) 的时间复杂度(排序花费 O(n log n),遍历花费 O(n))。...总的额外空间复杂度:除了存储输入数据之外,我们额外使用了一个大小为 n 的数组 ends 来存储数对链的右边界。因此,额外空间复杂度是 O(n)。
2023-05-12:存在一个由 n 个节点组成的无向连通图,图中的节点按从 0 到 n - 1 编号,给你一个数组 graph 表示这个图,其中,graphi 是一个列表,由所有与节点 i 直接相连的节点组成...2.在 shortestPathLength 函数中,获取图中节点的个数 n,使用 Floyd 算法计算所有节点之间的最短路径距离,并将结果保存到 distance 二维数组中,同时初始化一个 ans...3.接下来,初始化一个 dp 数组,其中 dpi 表示当前状态为 i(二进制表示),当前在节点 j 的情况下,能形成的最短路径长度。同时,对于 dp 数组进行初始化,将所有元素的值设为 -1。...如果 dp 数组中已有对应状态和当前节点的最短路径长度,则直接返回该值,避免重复计算。...空间复杂度:本算法中使用了一个距离矩阵 distance 数组来存储节点之间的最短路径距离,其空间复杂度为 O(n^2);同时,使用了一个 dp 数组来记录状态和节点的最短路径长度,其空间复杂度也是 O
2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。...她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher : 对每个满足 0 <= i < n 的下标 i ,loweri = arri - k 对每个满足...给你一个由 2n 个整数组成的整数数组 nums ,其中 恰好 n 个整数出现在 lower ,剩下的出现在 higher ,还原并返回 原数组 arr 。...组合 lower 和 higher 得到 2,6,10,4,8,12 ,这是 nums 的一个排列。 另一个有效的数组是 arr = 5,7,9 且 k = 3 。...= nums.len() as isize; // nums[0] -> 小数组的第0个 let m = n >> 1; // 谁是大数组的第0个?
2023-05-29:给你一个由 n 个正整数组成的数组 nums你可以对数组的任意元素执行任意次数的两类操作如果元素是 偶数 ,除以 2例如,如果数组是 1,2,3,4那么你可以对最后一个元素执行此操作使其变成...1,2,3,2如果元素是 奇数 ,乘上 2例如,如果数组是 1,2,3,4 ,那么你可以对第一个元素执行此操作,使其变成 2,2,3,4数组的 偏移量 是数组中任意两个元素之间的 最大差值。...该算法的时间复杂度为 O(nlogn),其中 n 是数组的长度。在最坏情况下,我们需要对所有奇数元素乘以 2,因此数组中的每个元素最多会被操作两次(一次除以 2,一次乘以 2)。...这样,我们就需要执行 2n 次操作。由于堆的插入和删除操作都需要 O(logn) 的时间,因此算法的总时间复杂度为 O(nlogn)。该算法的空间复杂度为 O(n),其中 n 是数组的长度。...我们需要使用一个堆来存储数组的所有元素,因此需要使用 O(n) 的额外空间。
By CaesarChang 合作: root121toor@gmail.com ~关注我 带你看更多精品知识 见注释 简单动态规划问题 将前面的数之和做一个更新...Solution { public int maxSubArray(int[] nums) { int Max=nums[0]; int pre=0; //记录前面的和...int cur=0; //记录当前数 for(int num:nums){ cur=num; if(pre>0){ //如果前面的和>...0,当前数字+前面的和 cur+=pre; } if(cur>Max){ Max=cur;...} pre=cur; //更新前面的和 } return Max; } } ?
2023-03-11:给定一个N*M的二维矩阵,只由字符'O'、'X'、'S'、'E'组成, 'O'表示这个地方是可通行的平地, 'X'表示这个地方是不可通行的障碍, 'S'表示这个地方有一个士兵,全图保证只有一个士兵..., 'E'表示这个地方有一个敌人,全图保证只有一个敌人, 士兵可以在上、下、左、右四个方向上移动, 走到相邻的可通行的平地上,走一步耗费a个时间单位, 士兵从初始地点行动时,不管去哪个方向,都不用耗费转向的代价...返回士兵找到敌人的最少时间。 如果因为障碍怎么都找不到敌人,返回-1, 1 <= N,M <= 1000, 1 <= a,b <= 100000, 只会有一个士兵、一个敌人。 来自华为。...} } } // 初始化 visited 数组 visited := make([][][]bool, n) for i := range visited { visited...} } } // 初始化优先队列和 visited 数组 h := &minHeap{} heap.Init(h) heap.Push(h, node{startX, startY
2023-03-16:给定一个由 0 和 1 组成的数组 arr ,将数组分成 3 个非空的部分, 使得所有这些部分表示相同的二进制值。...答案2023-03-16: 给定一个由 0 和 1 组成的数组 arr,需要将其分成三个非空部分,使得每个部分中 1 的数量相等。如果无法做到,则返回 [-1, -1]。...输入:由 0 和 1 组成的数组 arr,长度为 n(1 ≤ n ≤ 3×10^4),且只包含数字 0 和 1。...[start1 - 1, start2] // 返回第一个和第二个子数组的结束位置 } 算法分析: 该算法的时间复杂度为 O(n),其中 n 是输入数组的长度,因为需要遍历整个数组一次。...[1, 5]); ``` 总结和展望: 本文介绍了一种简单的算法,可以解决给定一个由 0 和 1 组成的数组 arr,需将其分成三个非空部分,使得每个部分中 1 的数量相等的问题。
题目 你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。 空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。...1,2,3,4] 1 / \ 2 3 / 4 输出: “1(2(4))(3)” //解释: 原本将是“1(2(4)())(3())”, //在你省略所有不必要的空括号对之后
题目:给定两个大小为 m 和 n 的数组 nums1 和 nums2。 请你找出这两个有序数组的中位数 方法:很简单的办法就是利用list的函数来实现。...0 m=0 if len(nums1)<len(nums2): lenth_all=len(nums1) n=len(nums2...=0: temp.extend(nums1[-m:]) if n!...目前我的刷题只是断断续续的开始,我感觉做这样的题目的时候呢,首先还是对基础知识的掌握,在一个就是我们用一个我们最熟悉的算法去解决。然后去寻找最优的算法。...可能后续的刷题,我将会改变到原来的方式去实现。python和java的实现代码都有。
2022-03-25:给定一个长度为 N 的字符串 S,由字符'a'和'b'组成,空隙由 '?' 表示。...你的任务是用a字符或b字符替换每个间隙, 替换完成后想让连续出现同一种字符的最长子串尽可能短。 例如,S = "aa??bbb", 如果将"??"...替换为"aa" ,即"aaaabbb",则由相等字符组成的最长子串长度为4。 如果将"??"替换为"ba" ,即"aababbb",则由相等字符组成的最长子串长度为3。...那么方案二是更好的结果,返回3。 S的长度 <= 10^6。 来自CMU入学申请考试。 答案2022-03-25: 根据S的长度 <= 10^6推断,复杂度是O(N)才能过。...= 右,中间问号长度是大于1的奇数。a???b变成abaab或者aabab。 5.左 != 右,中间问号长度等于1。a?b的问号根据ab数量决定,谁小成全谁。相等的时候,成全左边。
2023-03-11:给定一个N*M的二维矩阵,只由字符'O'、'X'、'S'、'E'组成,'O'表示这个地方是可通行的平地,'X'表示这个地方是不可通行的障碍,'S'表示这个地方有一个士兵,全图保证只有一个士兵...,'E'表示这个地方有一个敌人,全图保证只有一个敌人,士兵可以在上、下、左、右四个方向上移动,走到相邻的可通行的平地上,走一步耗费a个时间单位,士兵从初始地点行动时,不管去哪个方向,都不用耗费转向的代价...返回士兵找到敌人的最少时间。如果因为障碍怎么都找不到敌人,返回-1,1 <= N,M <= 1000,1 <= a,b <= 100000,只会有一个士兵、一个敌人。来自华为。...{return a}// 标记该位置已经被访问过visited[si][sj][d] = true// 计算从四个方向到达下一个位置所需的代价(如果可以到达的话)var p [4]intp[0] = f...j++ {if mapData[i][j] == 'S' {startX, startY = i, jbreak}}}// 初始化优先队列和 visited 数组h := &minHeap{}heap.Init
2022-09-13:给你两个整数 m 和 n ,分别表示一块矩形木块的高和宽。...同时给你一个二维整数数组 prices ,其中 pricesi = hi, wi, pricei 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。...你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。请你返回切割一块大小为 m x n 的木块后,能得到的 最多 钱数。注意你可以切割木块任意次。...输入:m = 4, n = 6, prices = [3,2,10,1,4,2,4,1,3]。输出:32。答案2022-09-13:严格位置依赖的动态规划版本 + 优化。...优化1 : 递归的形式,改成迭代形式;优化2 : prices中的单块收益直接填入dp表即可,如果有更好的分割方案,更新掉;优化3 : 分割只需要枚举一半即可。时间复杂度:O(N**3)。
2023-03-16:给定一个由 0 和 1 组成的数组 arr ,将数组分成 3 个非空的部分, 使得所有这些部分表示相同的二进制值。...答案2023-03-16: 给定一个由 0 和 1 组成的数组 arr,需要将其分成三个非空部分,使得每个部分中 1 的数量相等。如果无法做到,则返回 -1, -1。...输入:由 0 和 1 组成的数组 arr,长度为 n(1 ≤ n ≤ 3×10^4),且只包含数字 0 和 1。...[start1 - 1, start2] // 返回第一个和第二个子数组的结束位置 } 算法分析: 该算法的时间复杂度为 O(n),其中 n 是输入数组的长度,因为需要遍历整个数组一次。...[1, 5]); 总结和展望: 本文介绍了一种简单的算法,可以解决给定一个由 0 和 1 组成的数组 arr,需将其分成三个非空部分,使得每个部分中 1 的数量相等的问题。
领取专属 10元无门槛券
手把手带您无忧上云