我如何优化这个代码来寻找一个数字X，它的数字之和等于n？ - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

它适用于哪些问题？这篇文章给你答案

近似算法是一种处理优化问题 NP 完全性的方式，它无法确保最优解。近似算法的目标是在多项式时间内尽可能地接近最优值。它虽然无法给出精确最优解，但可以将问题收敛到最终解的近似值。...方法和决定步骤现在，我们开始分析这个问题，把它分解成数个单独的标准问题。...这里，我们想要找出多重集的元素之和相等的子集，那么该问题就可以分解成以下两个问题：子集和问题：子集 X 的元素之和等于数字 W。...适用性：该算法通过构建二叉树来假设分区。每一级表示一对数字，左侧的分支表示用差值替换数字，右侧的分支表示将差值放置在同一个子集中。该算法先通过最大差分求得解，然后继续寻找更好的近似解。...这个问题就可以通过装箱问题来解决，帮助当局决定 x 量的垃圾需要多少个垃圾箱。集装箱船：装箱问题的现实应用。在计算机科学领域中，该问题可用于多种内存管理技术。

1.5K6 0

这个远古的算法竟然可以！

这不是巧合；我们构造半列的方式意味着这个2的幂之和表达式中的指数，恰好总是奇数值的行号。把这些行对应的倍列值相加，其实就是18乘以2的幂之和，这个幂之和刚好等于89，即18和89。...其实，RPM实际上是算法的算法。半列本身是一种算法实现，即寻找与第一个数相等的2的幂之和。2的幂之和也称89的二进制展开（binary expansion）。...二进制是只用0和1表示数字的一种方法，近几十年来它变得极其重要，因为计算机以二进制存储信息。...现在，我们需要删除半列值是偶数的行。使用Python的%（取模）运算符测试奇偶性，返回除法的余数。如果数字x是奇数，那么x%2等于1。...你将看到很多很有意思的算法，包括：搜索、排序和最优化算法；以人为本的算法，帮助人们确定如何接球；先进的高级算法，比如机器学习和人工智能相关算法；以及古代文明时期的算法，比如数字相乘、寻找最大公约数以及幻方生成算法

1.5K3 0

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

是的

没有找到

【c++算法篇】双指针（下）

有效三角形的个数题目描述：这道题当然可以暴力求解，三层循环枚举所有情况，来进行判断，但是可以进行优化：我们知道，三角形的满足条件是任意的两边之和大于第三边，但是如果我们已经判断了较小的两个边大于第三边...，同时跳过 pre 指针的连续重复数字，并将 pre 指针向右移动同样地，跳过 las 指针的连续重复数字，并将 las 指针向左移动寻找条件：三数之和等于零。...我们还可以进一步优化，当i对应的数字大于零，意味着无论如何结果都大于零，就可以直接break了： for(int i=0;i<nums.size()-2;i++) { if(i>0&&nums[...它提供的值不一定是整形，所以上面函数中我们使用长整型来避免溢出总代码如下： class Solution { public: vector> fourSum(vector...，以及一些可以通过前后关系来优化问题的场景：有序数组的对撞指针：两数之和：在有序数组中找到两个数，使它们的和为特定的目标值三数之和/四数之和：与两数之和类似，但需要找到三个或四个数的组合移除元素

731 0

它适用于哪些问题？这篇文章给你答案

近似算法是一种处理优化问题 NP 完全性的方式，它无法确保最优解。近似算法的目标是在多项式时间内尽可能地接近最优值。它虽然无法给出精确最优解，但可以将问题收敛到最终解的近似值。...方法和决定步骤现在，我们开始分析这个问题，把它分解成数个单独的标准问题。...这里，我们想要找出多重集的元素之和相等的子集，那么该问题就可以分解成以下两个问题：子集和问题：子集 X 的元素之和等于数字 W。...适用性：该算法通过构建二叉树来假设分区。每一级表示一对数字，左侧的分支表示用差值替换数字，右侧的分支表示将差值放置在同一个子集中。该算法先通过最大差分求得解，然后继续寻找更好的近似解。...这个问题就可以通过装箱问题来解决，帮助当局决定 x 量的垃圾需要多少个垃圾箱。集装箱船：装箱问题的现实应用。在计算机科学领域中，该问题可用于多种内存管理技术。

4291 0

算法题也有升级版，两数之和的进阶问题——三数之和

今天我们来看一道它的变形题：LeetCode15，三数之和。...而数据当中是有重复数字的，这样一来势必造成出现大量的重复结果。我们当然可以先寻找答案再进行去重，但考虑到复杂度，这是不可行的。比如极端情况下，所有数字全都是0时，会导致大量的重复。...，等于剩下的元素套用两数之和寻找答案。...但其实元素排序，枚举了第一个数之后，我们也有其他的方法寻找答案，比如说如果熟悉两指针的话，也可以使用两指针来寻找元素组合。...它的解法和思考的细节基本上本题类似，甚至直接枚举一个数，剩下的直接调用三数之和都可以通过，实在是没什么意思，就不展开赘述了，感兴趣的同学可以去试一试。

5033 0

leetcode 907子数组的最小值之和题解

最小值为 3，1，2，4，1，1，2，1，1，1，和为 17 思路分析：这里是求出子数组的最小值之和，其实并不需要知道这个子数组的除了最大值之外其它数值。...假设当前数字下标为a，该数字往前的第一个小于该数的下标为x（也就是最小数组最大边界）、往后第一个小于等于该数的下标为y，那么次数就是y-x+1+(y-a)*(y-b)。...例如以[3,1,2,4]的2为例子，则a=2 x=2 y=3，所以次数3-2+1+(3-2)*(2-2) = 2 所以这个题目就变成了，找出对于数组中每一个值，它的前继小于自己的下标/后继小于等于自己的下标...那么如何寻找呢。解法 1: 常规解法。就是遍历数组，每个数字往前往后继续找边界。这样时间复杂度为o(n)。在第 87 个 case 就超时了。...仔细观察，其实优化版本只对部分 case 简化，其实它还是o(n2)的时间复杂度。要通过这里肯定不能o(n2)。

1.4K1 0

颜色空间系列1: RGB和CIEXYZ颜色空间的转换及相关优化

XYZ 色彩空间（也叫做 CIE 1931 色彩空间）是其中一个最先采用数学方式来定义的色彩空间，它由国际照明委员会（CIE）于1931年创立。...更过具体的关于XYZ空间的理论解释可见：点击打开链接本文的重点是如何优化这个RGBXYZ相互转换的过程。...优化的原理基本就是用整数的乘除法来替代浮点运算，比如，对各系数乘以一个很大的数，计算出结果在整除这个数，则得到的数字和之前的浮点算式取整结果是一致的。...，如果我们能够整除一个2的N次幂数，则可以用整数的移位来代替整除。...我对这个N的取值建议是在保证整个算式的每个部分的计算结果不超过int（对于64位CPU，则是long类型）类型的最大范围时，N越大越好。

3.2K2 0

惊呆了，LeetCode居然挂了……LeetCode周赛第281场解析

统计各位数之和为偶数的整数个数难度：零星给你一个正整数 num ，请你统计并返回小于或等于 num 且各位数字之和为偶数的正整数的数目。...正整数的各位数字之和是其所有位上的对应数字相加的结果。解法题目范围很小，题意也简单，典型的热身题，对于这样的题目秒切是基本要求。...但这里涉及一个问题，我们不能保证一定可以找到这样的字符。比如极端情况zzzzzzzzzz，我们就找不到可以用来分隔的字符。所以我们还需要通过枚举来寻找，如果找不到直接退出循环。...a : gcd(b, a % b); } 求完最大公约数之后，我们进一步可以想到，对于k的某个约数x而言，如果我们希望它乘上y能够整除k，y必然包含k/x这个因数。...(); vector mods(n, 0); // 求出每个数和k的最大公约数，可以知道，这个结果一定小于等于k for (int

5961 0

零基础学Python之42：水仙花数

今天解决Python初学者经常会遇到的一道练习题：请打印所有的水仙花数，所谓水仙花数，是指这样的3位数，它的每个位上的数字的3次方之和等于它本身，例如：153就是一个水仙花数，因为：1^3 + 5^...3次方之和列出所有的三位数第一步，求一个3位数在个位、十位和百位上的数，可以用除法和取余解决。...1问题，可以用这个代码验证结果： print(list(range(100, 1000, 1))) 加上逻辑判断语句，最后的代码： for m in range(100, 1000, 1): s...153, 370, 371, 407] 再再进一步三位数的情况叫水仙花数，对于n位数，每个位上的数字的 n 次幂之和如果等于它本身，这种数在数学上还有一个统一的称呼：自幂数。...我这里给出一个简单优化的思路，程序中求取n次方的数学运算比较花时间，可以把这些数值提前保存在字典中，以后直接查表即可，这样程序从110秒优化到55秒，快了一倍。

2.3K2 1

四数之和

三数之和是，我们首先确定一个数，然后利用双指针去找另外的两个数，我们在这个题目里面的解题思路是需要首先确定两个数然后利用双指针去找另外两个数，和三数之和思路基本一致很容易理解。...n 我把剪枝分为了 4 类，括号内的是用什么完成剪枝 1.如果剩余可选的数字数量少于 n，则剪掉（递归返回）； 2.每层递归的 for 循环中，从第二轮循环开始，如果数组中当前数字和前一个相同...，则剪掉（进行下一次循环，这条的任务就是去重）； 3.如果当前数字 + 已确定数字的和 + (n - 1) * 排序后数组中当前数字的下一个数字 > target，则说明后面的数无论怎么选，加起来都一定大于...target，所以剪掉（递归返回）； 4.如果当前数字 + 已确定数字的和 + (n - 1) * 排序后数组最后一个数字 < target，则说明后面的数无论怎么选，加起来都一定小于 target...为了避免无用功，在加入之前先瞅一眼，如果 nums[i] 加上它右边数字的三倍之后大于目标值，说明就算后面所有数字都相等，也不可能在 nums[i] 的右边找到另外三个数加上 nums[i]的和等于目标值

2813 0

算法——（转）动态规划入门

2、例题解析首先，我们看一下这道题（此题目来源于北大POJ）：数字三角形(POJ1163) ? 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。... 然后我们用D( r, j) 来表示第r行第 j 个数字(r,j从1开始算) 我们用MaxSum(r, j)表示从D(r,j)到底边的各条路径中，最佳路径的数字之和。 ...因为三角形的数字总数是 n(n+1)/2 2.3 递归转动态规划根据这个思路，我们就可以将上面的代码进行改进，使之成为记忆递归型的动态规划程序： #include ...但是，我们并不能满足于这样的代码，因为递归总是需要使用大量堆栈上的空间，很容易造成栈溢出，我们现在就要考虑如何把递归转换为递推，让我们一步一步来完成这个过程。 ...当然不是，我们仍然可以继续优化，而这个优化当然是对于空间进行优化，其实完全没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组maxSum[100]即可

6141 0

【leetcode刷题】T216-回文素数

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。例如，2，3，5，7，11 以及 13 是素数。...回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。例如，12321 是回文数。...刷了两天，我也投降了，看了网上的解答，牛逼主要使用了两个技巧一是排除了除11外的所有偶数。...想想，能被11整除的数有什么特点呢，奇数位数字之和 - 偶数位数字之和等于11的倍数；偶数素数有什么特点呢，奇数位数字之和 = 偶数位数字之和。那么，除11外，偶数位数字，不存在回文素数。...二是只判断6x-1和6x+1的数。怎么来的呢？大于6的数，6x能被2整除，6x+2能被2整除，6x+3能被3整除，6x+4能被2整除，只有6x+1和6x-1可能素数。

5552 0

C语言杨辉三角的实现

想必大家在初高中就听过和学过杨辉三角，那么用C语言如何实现呢？...要实现杨辉三角首先得先知道它的特征，以下是我找到的杨辉三角的特点： 1.每行端点与结尾的数为1 2.每行数字左右对称，由1开始逐渐变大 3.第n行的数字有n项 4.每个数字等于上一行的左右两个数字之和...即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。...即 C(n+1,i)=C(n,i)+C(n,i-1) 根据这些特点，我们便可以写出杨辉三角的代码：（代码虽长了点，但是步骤清晰） #define _CRT_SECURE_NO_WARNINGS #...，读者可自主进行优化 { arr[1][0] = 1; arr[1][1] = 1; } else { for (j = 1; j < i;

4322 0

机器人的运动范围

一、题目地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。...一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。...<= 100 • 0 <= k <= 20 三、解题思路根据题目描述，我们需要在m行n列的矩阵中寻找行坐标和列坐标的数位之和不大于k的格子数量。...确定了具体的解题步骤，我们首先来看如何计算一个数字的数位之和。...常用的方式是，通过与10取余（%10）的方式来获得最后一位的数字，那么获取到个位之后，再通过与10取整（/10）的方式来移除最后一位，那么再次通过与10取余计算后，就取得了原数字的十位数字了，依次类推，

1812 0

【面试高频题】难度 25，回溯 + 高精度的经典结合

题目描述这是 LeetCode 上的「306. 累加数」，难度为「中等」。 Tag : 「回溯算法」、「高精度」累加数是一个字符串，组成它的数字可以形成累加序列。...一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。...给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。如果是，返回 true ；否则，返回 false 。...， x 可以被直接到 list 并继续爆搜； list 长度大于等于 2 ，即 x 需要满足「其值大小为前两数之和」要求，以此条件作为剪枝，满足要求的 x 才能追加到 list...在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

1932 0

用人脑生成等概率随机数，困扰人类30万年的问题解决了 | 附“源代码”

因为人类是有情感的：1和10分别位于两端，选择这样两个数是否会太刻意？7是不是我的幸运数字？潜意识里的想法都会左右你最终的选择。那该怎么办？...现在，我们来定义这样一个变量xi,j，它表示我们把数字i调整到数字j的样本占数字i总样本中的比例。因为选7的人比较多，我们希望把部分7调整到1，如果把20%的7变成1，那么x7,1=0.2。...同时，我们还必须确保原始分布中的所有概率质量（probability mass）都是守恒的。所以每个i调整到1到10的总概率应该等于1（注：原文如此，应等于原本选择数字i的概率Pi）。 ?...另外，我们还希望尽可能保留原始的分布，也就是让xi,i（保持不动的部分）之和最大，即不调整的部分尽可能多。 ? 现在这个问题就变成了一个线性规划问题，在这20个约束条件下，令对角元素之和最大。...人脑随机数生成器现在你明白人类随机数生成器的工作原理了，下面就是这套程序的“源代码向一个人问得1~10之间的随机整数n1； if n1=5 then 再向另一个人问得一个随机整数n2；

6282 0

JS算法_知识点精讲

针对非正数的数组，我们换一个思路来求子数组之和。假设整个数组的长度为n,它的某个「子数组」的第一个数字的下标是i;最后一个数字的下标是j。...」，并将和「保存」下来将数组的前i个数字之和记为x 如果存在一个j (j<i) 即，j在x前面，且数组的前j个数字之和为x-target（「很重要」）那么数组中从第j+1个数字开始到第i个数字结束的子数组之和为...当扫描到数组第i个数字并求得前i个数字之和是x时，需要知道在i之前存在「多少」个j并且前j个数字之和等于x-target 所以，对于每个i,不但要保存前i个数字之和，还要保存每个和出现的次数所以，我们用一个...它「左边的子数组」的数字之和就是从第一个数字开始累加到第i-1个数字的和它「右边的子数组」的数字之和就是从第i+1个数字开始累加到最后一个数字的和,这个和等于数组中「所有数字」之和减去从第一个数字累加到第...（只包含该字符）分割出长度为2的字符串（包含该字符及它后面的一个字符）分割出长度为x的字符串 (x<n) 分割出长度为n的字符串解决这个问题需要很多步，每一步分割出一个回文字符串。

2.1K1 0

从零开始学习PYTHON3讲义（六）for循环跟斐波那契数列

斐波那契数列指的是这样一个数列： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...，这个数列从第3项开始，每一项都等于前两项之和。...这个数列从第3项开始，每一项都等于前两项之和。...这个数列从第3项开始，每一项都等于前两项之和。...这个过程一般只能进行数学上的分析和经验的积累。所以这里我直接说答案：在第一版的时候，我们使用了3个数字的“窗口”，因为第三个数字是前两个数字之和。...第二版的优化，我们知道了第三个数字其实可以省略不保存，所以只使用了2个数字的“窗口”，因为队列中第三个数字需要前两个数字之和，所以这2个数字的窗口，实际无法继续省略。

1.3K1 0

漫画：位运算技巧整理汇总+一道被嫌弃的题目

好了，废话就到这里，今天将分享一道很简单，并且总被Diss的题目： 01 PART 两数之和这个题很老了，拿出来给不会的同学看一看，会的直接跳过。...（值得一说的是，这个题目在国外上，有2000个dislike，可以看到大家的嫌弃！）第268题：不使用运算符 + 和 - ，计算两整数 a 、b 之和。 ?...（注意，一些编辑器底层会把用%判断奇偶数的代码，自动优化成位运算） 2、不使用第三个数，交换两个数。x = x ^ y ， y = x ^ y ， x = x ^ y。...（这个技巧可以用来检测 2的幂，或者检测一个整数二进制中 1 的个数，又或者别人问你一个数变成另一个数其中改变了多少个bit位，统统都是它） 5、i+(~i)=-1，i 取反再与 i 相加，相当于把所有二进制位设为...若n为负数，n >> 31 的所有位等于1，其值等于-1） 7、使用 (x ^ y) >= 0 来判断符号是否相同。

4351 0

JS算法探险之数组

针对非正数的数组，我们换一个思路来求子数组之和。假设整个数组的长度为n,它的某个「子数组」的第一个数字的下标是i;最后一个数字的下标是j。...将数组的前i个数字之和记为x 如果存在一个j (j<i) 即，j在x前面，且数组的前j个数字之和为x-target（「很重要」）那么数组中从第j+1个数字开始到第i个数字结束的子数组之和为target...当扫描到数组第i个数字并求得前i个数字之和是x时，需要知道在i之前存在「多少」个j并且前j个数字之和等于x-target 所以，对于每个i,不但要保存前i个数字之和，还要保存每个和出现的次数所以，我们用一个...6），下标为3的数字(值为6)的左边3个数1,7,3的和与右边两个数字2,9的和相等 ❞ 分析当扫描到第i个数字时它「左边的子数组」的数字之和就是从第一个数字开始累加到第i-1个数字的和它「右边的子数组...」的数字之和就是从第i+1个数字开始累加到最后一个数字的和,这个和等于数组中「所有数字」之和减去从第一个数字累加到第i个数字的和代码实现 function pivotIndex(nums){ let

8341 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭