不同数出现在大小为k的n个不同数的子集中的概率是多少？ - 腾讯云开发者社区

2022-01-13：K 个不同整数的子数组。给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。...（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）返回 A 中好子数组的数目。来自力扣992。答案2022-01-13：两个窗口的滑动窗口。k-1窗口，k窗口。...时间复杂度：O(N)。空间复杂度：O(N)。代码用golang编写。...:= subarraysWithKDistinct2(arr, 2) fmt.Println(ret) } func subarraysWithKDistinct2(arr []int, k...int) int { return numsMostK(arr, k) - numsMostK(arr, k-1) } func numsMostK(arr []int, k int) int

3023 0

K 个不同整数的子数组（双指针）

题目给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。...（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）返回 A 中好子数组的数目。...示例 1：输入：A = [1,2,1,2,3], K = 2 输出：7 解释：恰好由 2 个不同整数组成的子数组： [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2...示例 2：输入：A = [1,2,1,3,4], K = 3 输出：3 解释：恰好由 3 个不同整数组成的子数组： [1,2,1,3], [2,1,3], [1,3,4]....解题参考官方思路每次遍历一个右端点 r，以该右端点为结束的满足题意的子数组有多少个左端点有两个极限位置 l1, l2，[l1, r]刚好有 k 个不同数字，[l2, r] 刚好有 k-1 个不同数字

6522 0

您找到你想要的搜索结果了吗？

是的

没有找到

golang刷leetcode 滑动窗口（2）K 个不同整数的子数组

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。...（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）返回 A 中好子数组的数目。...示例 1：输出：A = [1,2,1,2,3], K = 2 输入：7 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2...示例 2：输入：A = [1,2,1,3,4], K = 3 输出：3 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4]....2,窗口内部问题可以拆分出两个子问题 A，K种不同值组成的子数组 B，A所得子数组中，移动左指针仍然满足题目要求的子数组 3，定义两个左指针start，start2 A，移动start和end，直到k

3411 0

K 个不同整数的子数组（困难）

题目描述给定一个正整数数组 nums。如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为好子数组。...例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。返回 nums 中好子数组的数目。...nums 的每一个位置 i 而言：找到其左边「最远」满足出现 k 个不同字符的下标，记为 p。...这时候形成的区间为 [p, i] 找到其左边「最远」满足出现 k - 1 个不同字符的下标，记为 j。...这时候形成的区间为 [j, i] 「那么对于 j - p 其实就是代表以 nums[i] 为右边界（必须包含 num[i]），不同字符数量「恰好」为 k 的子数组数量」 ?

5052 0

每日算法系列【LeetCode 992】K个不同整数的子数组

题目描述给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。...（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）返回 A 中好子数组的数目。...现在考虑右边界为 j 的情况，左边界 i 有什么规律呢？我们可以证明，满足 [i, j] 正好包含 K 个不同整数的 i 的取值是一段连续的区间。...假设 [i, j]包含 K 个不同整数，同时 [i', j] 也包含 K 个不同整数（i 的数量是非增的，所以这过程中没有增加新的数，也没有任何一个数的数量降到了...而 j 右移一个数之后， l 需要右移，直到 [l, j] 中正好有 K 个不同整数， r 也继续右移，直到[r + 1, j] 中正好有 K - 1 个不同整数。

5301 0

K 个不同整数的子数组(双指针)（滑动窗口）

题目给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。...（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）返回 A 中好子数组的数目。...示例 2：输入：A = [1,2,1,3,4], K = 3 输出：3 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4]....而「最多存在 KK 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1K−1 个不同整数的子区间的个数」。...因为原问题就转换成为求解「最多存在 KK 个不同整数的子区间的个数」与「最多存在 K - 1K−1 个不同整数的子区间的个数」，它们其实是一个问题。

3611 0

编程题分享：有⼀堆糖果，其数量为n,现将糖果分成不同数量的堆数

题目：编程题：有⼀堆糖果，其数量为n，现将糖果分成不同数量的堆数（每堆数量均为整数，最少为1），请算出糖果堆对应数量的最⼤乘积是多少，并给出对应的分配⽅案；举例：糖果数量为8，可以得到的乘积最...⼤为18，对应的分配⽅案为【2，3，3】；思路分析：初始测试数据比较小，可以在草稿纸上穷举分配方案，寻找规律，发现：当数量小于5时，最大的乘积就是本身，无需分配其次注意到分配后的数目如果是...，for 循环处理,并得到每个分配数字分析 mod 变量的影响，使得分配数尽可能靠近数字 3 最后，简单测试数量 n，验证分配方案是否符合实际要求 ....编码如下： ** * 有⼀堆糖果，其数量为n，现将糖果分成不同数量的堆数 * @param int $z_number 糖果数量 * @return string 检测结果 */ public...$arr_option[] = 3; } }elseif ($mod == 1){ //对其中的一个分配数加

2331 0

2022-01-13：K 个不同整数的子数组。给定一个正整数数组

2022-01-13：K 个不同整数的子数组。给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。...（例如，1,2,3,1,2 中有 3 个不同的整数：1，2，以及 3。）返回 A 中好子数组的数目。来自力扣992。答案2022-01-13：两个窗口的滑动窗口。k-1窗口，k窗口。...时间复杂度：O(N)。空间复杂度：O(N)。代码用golang编写。...:= subarraysWithKDistinct2(arr, 2) fmt.Println(ret) } func subarraysWithKDistinct2(arr []int, k...int) int { return numsMostK(arr, k) - numsMostK(arr, k-1) } func numsMostK(arr []int, k int) int

2641 0

2024-12-30：所有球里面不同颜色的数目。用go语言，给定一个整数 limit 和一个大小为 n x 2 的二维数组 qu

2024-12-30：所有球里面不同颜色的数目。用go语言，给定一个整数 limit 和一个大小为 n x 2 的二维数组 queries，其中包含若干操作。...在每次操作后，我们需要计算并返回所有球中不同颜色的数量。请返回一个长度为 n 的数组 result，该数组的第 i 个元素表示第 i 次操作后不同颜色的总数。...需要注意的是，没有染色的球不计入不同颜色的统计。 1 <= limit <= 1000000000。 1 n == queries.length <= 100000。...大体步骤如下： 1.初始化一个空的结果数组 ans，用于存储每次操作后的不同颜色总数。 2.初始化两个空的映射表：color 用于记录球的颜色，cnt 用于记录每种颜色的球数量。...总的时间复杂度取决于操作次数n和limit的数量，程序中需要遍历所有的操作，故时间复杂度为O(n)。

622 0

2025-02-20：子数组按位与值为 K 的数目。用go语言，给定一个整数数组 nums 和一个整数 k，请计算满足条件的子数

2025-02-20：子数组按位与值为 K 的数目。用go语言，给定一个整数数组 nums 和一个整数 k，请计算满足条件的子数组数量：这些子数组的所有元素经过按位与运算后的结果等于 k。...2.对于输入的数组 nums 中的每个元素，遍历其索引 i 和元素 x： 2.1.如果 x 与 k 的按位与结果小于 k，则更新 border 和 lastK 为当前索引 i，表示单独的元素满足条件。...2.3.如果 x 大于 k，则从 i-1 开始逆向遍历到上次遇到 k 的位置之间的元素： 2.3.1.计算 nums[j] 和 x 的按位与结果为 y。...2.3.4.否则，更新 nums[j] 为 y。 3.在每次迭代中，累加符合条件的子数组数量，即 lastK - border。 4.返回最终的 ans 作为结果。...总的时间复杂度：O(n)，其中 n 为数组 nums 的长度。总的额外空间复杂度：O(1)，除了几个整型变量外，没有使用额外的空间。

451 0

2024-06-26：用go语言，给定一个长度为n的数组nums和一个正整数k，找到数组中所有相差绝对值恰好为k的子数组，并

2024-06-26：用go语言，给定一个长度为n的数组nums和一个正整数k，找到数组中所有相差绝对值恰好为k的子数组，并返回这些子数组中元素之和的最大值。如果找不到这样的子数组，返回0。...输入：nums = [-1,3,2,4,5], k = 3。输出：11。解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 3 。好子数组有 [-1,3,2] 和 [2,4,5] 。...最大子数组和为 11 ，对应的子数组为 [2,4,5] 。答案2024-06-26： chatgpt 题目来自leetcode3026。...3.最终判断 ans 是否仍为负无穷大，如果是，则返回 0，否则将 ans 转换为 int64 类型后返回。总的时间复杂度为 O(n)，其中 n 为输入数组的长度。...总的额外空间复杂度也是 O(n)，因为使用了一个 map 来存储元素之和为特定值的最小下标，当输入数组中所有元素都不相差绝对值恰好为 k 时，map 中最多会存储 n 个元素。

642 0

2022-07-27：小红拿到了一个长度为N的数组arr，她准备只进行一次修改，可以将数组中任意一个数arr，修改为不大于P的正数（修改后的数必须和原数不同)

2022-07-27：小红拿到了一个长度为N的数组arr，她准备只进行一次修改，可以将数组中任意一个数arri，修改为不大于P的正数（修改后的数必须和原数不同)，并使得所有数之和为X的倍数。...小红想知道，一共有多少种不同的修改方案。 1 N, X <= 10^5。 1 <= arri, P <= 10^9。来自网易。答案2022-07-27：求所有数字的累加和sum。...时间复杂度：O(N)。代码用rust编写。...("测试开始"); for _ in 0..test_time { let n = rand::thread_rng().gen_range(0, len) + 1;...1 : 0 // 在不考虑变出来的数，是不是num的情况下，算一下有几个数，符合要求 let ans = p / x + if (p % x) >= mod0 { 1 } else {

1.4K3 0

初识JAVA：华为面试写一个程序：要求出用1，2，5这三个数不同个数组合的和为100的组合个数

要求出用1，2，5这三个数不同个数组合的和为100的组合个数因为x+2y+5z=100 所以x+2y=100-5z，且z<=20 x<=100 y<=50 所以(x+2y)的可能值如下： z=0, x=100, 98, 96, … 0 z=1, x=95, 93, …, 1 z=2, x=90, 88, …, 0 z=3, x=85, 83, …..., 1 z=4, x=80, 78, …, 0 … z=19, x=5, 3, 1 z=20, x=0 因此，组合总数为100以内的偶数+95以内的奇数+90以内的偶数+…+5以内的奇数+1，...即为： (51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)+(11+8)+(6+3)+1** 某个偶数m以内的偶数个数（包括...0）可以表示为m/2+1=(m+2)/2 某个奇数m以内的奇数个数也可以表示为(m+2)/2 import java.util.zip.DeflaterOutputStream; /** * Created

5313 0

2023-06-04：你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复，请你为她按如下规则创建一个播放列

2023-06-04：你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复，请你为她按如下规则创建一个播放列表，每首歌至少播放一次，一首歌只有在其他 K...该函数中定义三个int64类型变量：cur、ans和sign。cur用于保存当前循环中需要累加到答案中的部分，ans则是最终结果。sign初始为1，在每次循环结束时将其乘以-1来实现交替相加或相减。...6.numMusicPlaylists函数中使用一个for循环遍历i从0到n-k。在每次循环中，首先计算cur = sign * pow(n-k-i, l-k) % MOD。...在numMusicPlaylists函数中使用了一个for循环，循环次数为n-k，每次循环中调用了power函数，时间复杂度为$O(logMOD)$，然后进行了常数次乘、除和取模运算，时间复杂度为O(1...因此总时间复杂度为$O(n(n-k)logMOD)=O(n^2*logMOD)$。空间复杂度：O(n)，主要是用来存储阶乘表和阶乘结果的乘法逆元表。

2650 0

华为面试题：写一个程序要求出用1，2，5这三个数不同个数组合的和为100的组合个数(Java实现）

因为x+2y+5z=100 所以x+2y=100-5z，且z<=20 x<=100 y<=50 所以(x+2y)<=100，且(x+5z)是偶数对z作循环，求x的可能值如下： z=0, x=100,...2, x=90, 88, …, 0 z=3, x=85, 83, …, 1 z=4, x=80, 78, …, 0 … z=19, x=5, 3, 1 z=20, x=0 因此，组合总数为100...以内的偶数+95以内的奇数+90以内的偶数+…+5以内的奇数+1，即为： (51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)...+(11+8)+(6+3)+1 某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2 某个奇数m以内的奇数个数也可以表示为(m+2)/2 import java.util.zip.DeflaterOutputStream

1.2K3 0

【面经1】算法工程师实习校招面经 (上篇)

n-1个后门是羊，你先选一个，如果面试官告诉你其余n-1个中某个是羊，你会重新选择么（假设n为3）你先选一个，概率1/n；面试官告诉你某个不是，你在剩余中选的概率为两部分：（1）你选的那个是，则概率...一人随机选了一个盒子，并摸出一个红球，请问这个盒子里另外一个也是红球的概率是多少 2/3，2/3概率选了第一个盒子六、算法基础该部分主要是手写代码，也是面试的重要组成部分可能因为我本科非计算机，面试官大都比较宽容...的排序算法快排，归并，堆排序 5.8 二叉树路径和为给定值 5.9 一个数组，其他数出现两次，另一个出现一次，找出改进：另外两个数出现一次 5.10 链表中倒数第k个结点 5.11 判断链表对称/链表回文...；给定c，找到a，b，满足 a属于A b属于B a+b=c 三个数呢 5.25 一维数组最大和二维数组求最大和矩阵 5.26 二维数组有多少个子数组包含一行的，第一行为例，一个的n个，两个的n-1个...0.5，要求设计如下等概率生成器： 5.42 给定n个数的数组，找到所有长度大于等于k的连续子数组中平均值最大的那个。

7843 0

2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少

2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？...2.遍历矩阵 grid，对于每个位置上的值，如果当前位置上的值为非零正整数，则更新答案为当前岛屿的大小。...3.遍历矩阵 grid，当当前位置上的值为 0 时，分别查看该位置上、下、左、右四个方向是否有与其相邻且已经被访问过的岛屿，并将它们的大小累加起来。...如果这些岛屿的大小之和加上当前位置上自身的大小可以更新最大岛屿面积，则更新答案。4.返回答案。时间复杂度：$O(n^2)$ ，遍历了三次矩阵，每次遍历的时间复杂度均为 $O(n^2)$。...空间复杂度：$O(n^2)$，使用了两个二维数组，每个数组都是 $n \times n$ 的大小。

3621 0

算法面试太难？反手就是一波面经

二、数据结构算法题 1、K个有序数组，找一个长度最小的区间，在这个区间里至少包含每个数组各一个数 2、n个[0,n)的数，求每个数的出现次数（不能开辟额外空间） 3、数组的全排列（空间复杂度O（1））...） 9、一个数组，所有数组都出现了两次，只有一个数出现了一次，返回这个数（位运算） 10、一个数组，一个数出现了超过一半次数，返回这个数 11、将除法的结果用字符串返回，如果能够除尽，则返回相除的结果，...12、数组排序，假设数组排序后的位次和排序前的位次绝对值差值小于K，有什么比快排好的算法？ 13、树中两个节点的第一个的公共祖先。...7、如何预测一家店分品类的销量 8、信息流采样，有n份数据，但是n的长度并不知道，设计一个采样算法，使得每份被选择的概率是相同的。...，平均点击率应该是多少？

1.8K3 0

八个意想不到的数学事实

我们可以这样想，每一个自然数都对应一个它两倍大的数，而每一个偶数都有都有一个大小为它一半的自然数：也就是说，对于每一个自然数都有一个偶数与之一一对应，因此这两个无穷大的数列集合大小一致，被称为可数无穷集...、阶乘、2的n次幂。 5. 生日悖论假如你所在的办公室共有23个员工，那么其中两个人生日在同一天的概率是多少？答案是50%！是不是远远高过你的猜想？...两个人生日不同的概率是：三个人都不同则是：四个人都不同为： ……....我在1号箱子里放置了两个金条，2号箱子放了两个银条，3号箱子放有一金条一银条。现在你打开任意一只箱子其中的一个隔间，假如看到的是一个金条，那么这只箱子中另外一个隔间里同样是金条的概率是多少？...我们将调和数级与一个明显比它小的数级相比较可以看到在这两个不同的数级中，相同位置的项在上图显示的数级中明显比在调和数级中小，而这个较小数级也可以写作：也就是发散到无穷。

1.3K1 0

面试题精选:数据伪造

大致需求是已知一批数和每个数出现的次数，然后写个接口，每次调用都能返回已知数据中的某个数，且返回的概率和原始数据中每个数出现的概率一致，题目描述起来有些绕口，我们来举个实际的例子。 ?...以上面的输入为例，要求实现的接口必须以11.96%的概率返回5、18.10%的概率返回91……16.55%的概率返回98，当然我的要求不仅仅是这几个数，而是可能有10^5个数。...借助已有的random()，我们很简单就可以生成0-n之间的一个随机数i，但是如果直接返回num[i]的话，每个数返回的概率是一致的，明显不满足我们的需求。...其实解决方案也很简单，我们按照每个数出现的频次大小，将其映射成不同的区间大小，出现的概率越大，区间越大。...想象下，这些数据按不同的区间大小把一个飞镖盘分成不同的部分，我们生成数的时候就是拿个飞镖随机扎，扎到哪个算哪个。 ? 当然我们可以直接用一位直线区间描述上面的二维飞镖盘模型。

3142 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

2022-01-13：K 个不同整数的子数组。

K 个不同整数的子数组（双指针）

golang刷leetcode 滑动窗口（2）K 个不同整数的子数组

K 个不同整数的子数组（困难）

每日算法系列【LeetCode 992】K个不同整数的子数组

K 个不同整数的子数组(双指针)（滑动窗口）

编程题分享：有⼀堆糖果，其数量为n,现将糖果分成不同数量的堆数

2022-01-13：K 个不同整数的子数组。给定一个正整数数组

2024-12-30：所有球里面不同颜色的数目。用go语言，给定一个整数 limit 和一个大小为 n x 2 的二维数组 qu

2025-02-20：子数组按位与值为 K 的数目。用go语言，给定一个整数数组 nums 和一个整数 k，请计算满足条件的子数

2024-06-26：用go语言，给定一个长度为n的数组nums和一个正整数k，找到数组中所有相差绝对值恰好为k的子数组，并

2022-07-27：小红拿到了一个长度为N的数组arr，她准备只进行一次修改，可以将数组中任意一个数arr，修改为不大于P的正数（修改后的数必须和原数不同)

初识JAVA：华为面试写一个程序：要求出用1，2，5这三个数不同个数组合的和为100的组合个数

2023-06-04：你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复，请你为她按如下规则创建一个播放列

华为面试题：写一个程序要求出用1，2，5这三个数不同个数组合的和为100的组合个数(Java实现）

【面经1】算法工程师实习校招面经 (上篇)

2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少

算法面试太难？反手就是一波面经

八个意想不到的数学事实

面试题精选:数据伪造

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐