2022-07-09:总长度为n的数组中,所有长度为k的子序列里,有多少子序列的和为偶数?答案2022-07-09:方法一:递归,要i还是不要i。方法二:动态规划。需要两张dp表。代码用rust编写。...k = rand::thread_rng().gen_range(0, n) + 1; let mut arr = random_array(n, vv); let ans1...= arr.len() as i32; // even[i][j] : 在前i个数的范围上(0...i-1),一定选j个数,加起来是偶数的子序列个数 // odd[i][j] : 在前i个数的范围上...(0...i-1),一定选j个数,加起来是奇数的子序列个数 let mut even: Vec> = vec!...=n { for j in 1..
2021-07-27:给定一个数组arr,长度为N,arr中的值只有1,2,3三种。...那么arr整体就代表汉诺塔游戏过程中的一个状况。如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1。如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况。...福大大 答案2021-07-27: 1-7的汉诺塔问题。 1-6左→中。 7左→右。 1-6中→右。 单决策递归。 k层汉诺塔问题,是2的k次方-1步。 时间复杂度:O(N)。...true { ret := kth2(arr) fmt.Println("迭代:", ret) } } func kth(arr []int) int { N...:= len(arr) return step(arr, N-1, 1, 3, 2) } // 0...index这些圆盘,arr[0..index] index+1层塔 // 在哪?
2022-03-18:arr数组长度为n, magic数组长度为m 比如 arr = { 3, 1, 4, 5, 7 },如果完全不改变arr中的值, 那么收益就是累加和 = 3 + 1 + 4 + 5...+ 7 = 20 magicsi = {a,b,c} 表示arra~b中的任何一个值都能改成c 并且每一种操作,都可以执行任意次,其中 0 <= a <= b < n 那么经过若干次的魔法操作,你当然可能得到...arr的更大的累加和 返回arr尽可能大的累加和 n <= 10^7 m <= 10^6 arr中的值和c的范围 <= 10^12 答案2022-03-18: 线段树。...arr[i]) } return ans } // 为方法三特别定制的线段树 // 区间上维持最大值的线段树 // 支持区间值更新 // 为本道题定制了一个方法: // 假设全是单点查询,请统一返回所有单点的结果...:= size + 1 ans.max = make([]int, N<<2) ans.change = make([]int, N<<2) ans.update = make([]bool, N
2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复比如,arr = 4, 2, 0, 3, 10 1 2 3 4把0想象成洞,任何非0数字都可以来到这个洞里,然后在原本的位置留下洞比如...对于第二种有序情况,我们可以先倒序遍历数组,找出每个数需要移动的最小距离,从而计算出需要移动的次数。最后比较这两种情况下的最小搬动次数,返回较小值即可。...数字只能搬家到洞里,并且走后留下洞,因此在交换过程中需要记录其中一个数字所在的位置作为洞的位置。...golang代码如下:package mainimport "fmt"func sortArray(nums []int) int {// 长度n// ans1 : 0 1 2 3 4 .......这种样子,至少交换几次// ans2 : 1 2 3 4 .... 0 这种样子,至少交换几次// m : 每个环里有几个数// next : 往下跳的位置n := len(nums)ans1, ans2
2022-12-22:给定一个数字n,代表数组的长度,给定一个数字m,代表数组每个位置都可以在1~m之间选择数字,所有长度为n的数组中,最长递增子序列长度为3的数组,叫做达标数组。返回达标数组的数量。...1 i32 { //repeat(vec!
题目:从长度为m的int数组中随机取出n个元素,每次取的元素都是之前未取过的 Fisher-Yates洗牌算法是由 Ronald A.Fisher和Frank Yates于1938年发明的,后来被Knuth...用洗牌算法思路从1、2、3、4、5这5个数中,随机取一个数 4被抽中的概率是1/5 5被抽中的概率是1/4 * 4/5 = 1/5 2被抽中的概率是1/3 * 3/4 *...O(n^2), 空间复杂度为O(n) 代码如下: //O(N^2)time //O(N)space void test(int n, int m) { List list...该算法的基本思想和 Fisher 类似,每次从未处理的数据中随机取出一个数字,然后把该数字放在数组的尾部,即数组尾部存放的是已经处理过的数字。...时间复杂度为O(n), 空间复杂度为O(n) //O(N)time //O(N)space void knuth(int n, int m) { int[] arr = new int[n];
2023-01-06:给定一个只由小写字母组成的字符串str,长度为N,给定一个只由0、1组成的数组arr,长度为N,arri等于 0 表示str中i位置的字符不许修改,arri 等于 1表示str中i...位置的字符允许修改,给定一个正数m,表示在任意允许修改的位置,可以把该位置的字符变成a~z中的任何一个,可以修改m次。...返回在最多修改m次的情况下,全是一种字符的最长子串是多长。1 <= N, M <= 10^5,所有字符都是小写。来自字节。答案2023-01-06:尝试全变成a一直到全变成z,遍历26次。...change += 1; r += 1; } // l....r-1 r // X...= aim && arr[r] == 1 && change < mchange++;r++;}// l....r-1 r// X l+1ans = getMax(ans, r - l);if (s[uint32
2024-01-03:用go语言,给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time, 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。...一位 免费 的油漆匠,刷 任意 一堵墙的时间为 1 单位,开销为 0, 但是必须在付费油漆匠 工作 时,免费油漆匠才会工作。 请你返回刷完 n 堵墙最少开销为多少?...2.在 process1 函数中,通过递归方式将每种情况下的最小开销计算出来。 3.递归调用时考虑两种情况,选择当前墙刷或者不刷,计算出最小开销。...• paintWalls2 和 paintWalls3 使用了记忆化搜索和动态规划,时间复杂度都为 O(n^2),其中 n 为墙的数量。...• paintWalls3 的额外空间复杂度为 O(n),因为它只用了一个一维数组保存中间结果。
2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复 比如,arr = [4, 2, 0, 3, 1] 0 1 2 3 4 把0想象成洞...对于第二种有序情况,我们可以先倒序遍历数组,找出每个数需要移动的最小距离,从而计算出需要移动的次数。 3. 最后比较这两种情况下的最小搬动次数,返回较小值即可。 注意事项: 1....数字只能搬家到洞里,并且走后留下洞,因此在交换过程中需要记录其中一个数字所在的位置作为洞的位置。...# golang代码如下: package main import "fmt" func sortArray(nums []int) int { // 长度n // ans1 : 0 1 2...这种样子,至少交换几次 // ans2 : 1 2 3 4 .... 0 这种样子,至少交换几次 // m : 每个环里有几个数 // next : 往下跳的位置 n := len(nums
2023-06-20:给定一个长度为N的数组arr,arr[i]表示宝石的价值 你在某天遇到X价值的宝石, X价值如果是所有剩余宝石价值中的最小值,你会将该宝石送人 X价值如果不是所有剩余宝石价值中的最小值...具体步骤如下: 2.1.初始化累加和数据结构(it)和最小值数据结构(st)。 2.2.设定起始位置(start)为1,找到剩余宝石中的最小值(find)。...2.3.计算从起始位置到最小值之间的宝石总数(daysCount)。 2.4.将最小值送出,更新累加和数据结构(it)和最小值数据结构(st)。 2.5.更新起始位置(start)为最小值。...方法2(days2): • 时间复杂度:O(N * (logN)^2),其中N是宝石数组的长度。构建IndexTree和SegmentTree所需的时间复杂度为O(N * logN)。...每次查询最小值的时间复杂度为O(logN),总共进行N次查询。因此,总的时间复杂度为O(N * (logN)^2)。
2022-06-11:注意本文件中,graph不是邻接矩阵的含义,而是一个二部图。...在长度为N的邻接矩阵matrix中,所有的点有N个,matrixi表示点i到点j的距离或者权重,而在二部图graph中,所有的点有2*N个,行所对应的点有N个,列所对应的点有N个。...[]; // dfs过程中,碰过的点! let mut x: Vec = vec![]; let mut y: Vec = vec!...[]; // 降低的预期! // 公主上,打一个,降低预期的值,只维持最小! let mut slack: Vec = vec!...// 需要拿到,公主的slack里面,预期下降幅度的最小值!
2021-07-27:给定一个数组arr,长度为N,arr中的值只有1,2,3三种。...那么arr整体就代表汉诺塔游戏过程中的一个状况。如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1。如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况。...福大大 答案2021-07-27: 1-7的汉诺塔问题。 1. 1-6左→中。 2. 7左→右。 3. 1-6中→右。 单决策递归。 k层汉诺塔问题,是[2的k次方-1]步。 时间复杂度:O(N)。...true { ret := kth2(arr) fmt.Println("迭代:", ret) } } func kth(arr []int) int { N...:= len(arr) return step(arr, N-1, 1, 3, 2) } // 0...index这些圆盘,arr[0..index] index+1层塔 // 在哪?
2022-08-06:给定一个数组arr,长度为N,arr中所有的值都在1~K范围上,你可以删除数字,目的是让arr的最长递增子序列长度小于K。返回至少删除几个数字能达到目的。...N <= 10^4,K <= 10^2。来自京东。4.2笔试。答案2022-08-06:动态规划。时间复杂度:O(N*K)。额外空间复杂度:O(N*K)。rust和typescript的代码都有。...// len长度了!len = 3 : 1 2 3// arr[index....]是能够决定的,之前的,已经不能再决定了// 返回:让最终保留的数字,凑不足k长度的情况下,至少要删几个!...// len长度了!len = 3 : 1 2 3// arr[index....]是能够决定的,之前的,已经不能再决定了// 返回:让最终保留的数字,凑不足k长度的情况下,至少要删几个!...(arr: number[], k: number): number { var n: number = arr.length; var dp: number[][] = new Array(n);
2022-12-16:给你一个长度为n的数组,并询问q次 每次询问区间[l,r]之间是否存在小于等于k个数的和大于等于x 每条查询返回true或者false。...1 <= n, q <= 10^5 k <= 10 1 <= x <= 10^8。 答案2022-12-16: 线段树。 代码用go语言编写。...:= rand.Intn(N) + 1 k := rand.Intn(K) + 1 arr := randomArray(n, V) st := NewSegmentTree(arr...:= len(arr) k := K max := make([][]int, (n+1)<<2) query := make([][]int, (n+1)<<2) for i := 0...right = this.query[rt<<1|1] } this.merge(this.query[rt], left, right) } } // // 暴力实现的结构
2022-06-11:注意本文件中,graph不是邻接矩阵的含义,而是一个二部图。...在长度为N的邻接矩阵matrix中,所有的点有N个,matrix[i][j]表示点i到点j的距离或者权重, 而在二部图graph中,所有的点有2*N个,行所对应的点有N个,列所对应的点有N个。...[]; // dfs过程中,碰过的点! let mut x: Vec = vec![]; let mut y: Vec = vec!...[]; // 降低的预期! // 公主上,打一个,降低预期的值,只维持最小! let mut slack: Vec = vec!...// 需要拿到,公主的slack里面,预期下降幅度的最小值!
2022-12-16:给你一个长度为n的数组,并询问q次 每次询问区间l,r之间是否存在小于等于k个数的和大于等于x 每条查询返回true或者false。...1 <= n, q <= 10^5 k <= 10 1 <= x <= 10^8。 答案2022-12-16: 线段树。 代码用go语言编写。...:= rand.Intn(N) + 1 k := rand.Intn(K) + 1 arr := randomArray(n, V) st := NewSegmentTree(arr, k)...:= len(arr) k := K max := make([][]int, (n+1)<<2) query := make([][]int, (n+1)<<2) for i := 0; i...rightUpdate { right = this.query[rt<<1|1] } this.merge(this.query[rt], left, right) } } // // 暴力实现的结构
给定一个长度为n的数组arr, 现在你有一次机会, 将其中连续的K个数全修改成任意一个值, 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出这个最长的长度。...这些数组和变量将用于存储计算过程中的中间结果和输入数据。 2.在main函数中设置给定的输入数据:n表示数组的长度为5,k表示连续的k个数需要修改,arr存储具体的数组元素。...4.否则,调用rightFn函数计算修改后的数组中以每个元素为结尾的最长不下降子序列的长度,并将结果存储在数组right和ends中。...6.将arr[i]赋值给ends[find],更新当前的最长不下降子序列的长度为max(len, find),并将结果存储在right[i]中。...7.将arr[j]赋值给ends[find],更新当前的最长不下降子序列的长度为max(len, find)。 8.循环结束后,ans存储了修改后的数组的最长不下降子序列的长度。
2023-05-03:给你一棵 二叉树 的根节点 root ,树中有 n 个节点每个节点都可以被分配一个从 1 到 n 且互不相同的值另给你一个长度为 m 的数组 queries你必须在树上执行 m 个...返回一个长度为 m 的数组 answer ,其中 answeri 是执行第 i 个查询后树的高度。注意:查询之间是独立的,所以在每个查询执行后,树会回到其 初始 状态。...将该范围内所有节点的深度保存到数组 maxl 中,并计算其前缀最大值。将该范围内所有节点的深度保存到数组 maxr 中,并计算其后缀最大值。...计算左右子树的最大深度,取其中的较大值作为删除子树后树的高度。将结果保存到答案数组 ans 中。5.返回答案数组。注意:在每次查询中,需要重新计算左右子树的最大深度,因为每次查询都会修改树的结构。...时间复杂度:在 dfs 函数中,对于每个节点最多访问一次,因此该函数的时间复杂度为 O(n),其中 n 是二叉树的节点数。
num和它的下标放置一个字典中,在循环这个列表,用目标结果target减正在循环的这个数,并判断结果是否在字典中(即是否循已经遍历过),如果结果存在如字典中,即找到相加等于结果的两个值,如果不存在,即把值和对应下标存入字典中...我们可以假设新列表的长度为0,然后我们就能同时得到列表中第一个元素的值,在循环中我们可以用下一个与之比较,如果不一样,就将假设的新列表的长度+1,同时,由于有元素不一样,我们需要将新元素赋给之前相同的元素...首先,我们声明两个变量,一个为循环当前的最大值,一个为我们需要的最大值,初始都将他们赋为列表的第一个元素(需要对为列表单独讨论)。...这部的作用其实就是将重复的元素都跳过。 在外循环中将当前结点的下一个结点赋值给当前结点,最后返回单链表的头结点即可。...的n-1的值赋值给nums1[m-n-1],然后将n减一。
为了不直接操作头指针,这里我们将两个链表的头结点赋给两个变量pa和pb。在两个变量不相等的时候,开始循环。...如果pa等于空了,那么就把另一个单链表的头节点headB赋给pa,反之,当pa不等于空的时候,将pa的下一个节点赋值给pa。pb的操作也一样。...判断pb是否为空来选择将headA赋给它还是将下一个节点赋给自己 所以我们可以有以下解法 方法一 class Solution: def getIntersectionNode(self, headA...在这里我们使用字典将遍历过的值和下标记录下来,循环列表中每一个值,在每一次循环中判断目标值减去遍历的值等于的结果是否在存有已经遍历过的元素字典中,如果存在那就返回这两个下标,由于下标不是从0开始,所以我们需要将下标...在这里我们使用字典将遍历过的值和下标记录下来,循环列表中每一个值,在每一次循环中判断目标值减去遍历的值等于的结果是否在存有已经遍历过的元素字典中,如果存在那就返回这两个下标,由于下标不是从0开始,所以我们需要将下标
领取专属 10元无门槛券
手把手带您无忧上云