问题:“找到前六位数字之和等于后三位数字之和的六位数数字的算法。”
我在一次采访中遇到了这个问题,想知道最好的解决方案。这就是我到目前为止所拥有的。
方法1:当然,蛮力解决方案是检查每个数字(介于100,000和999,999之间),其前三位数和后三位数的和是否相等。如果是,则增加某些计数器,该计数器保持所有此类数字的计数。
但这会检查所有900,000个数字,因此效率低下。
方法2:由于我们被问到“多少”个这样的数字,而不是“哪个数字”,我们可以做得更好。将数字分为两部分:前三位数字(从100到999)和后三位数字(从000到999)。因此,候选号码任一部分的三位数之和范围可以是1到27。
*为每个部分维护一个std::map<int, int>
,其中key是和,值是在相应部分中具有该和的数字(3位)。
*现在,对于第一部分中的每个数字,找出其总和并更新相应的 map 。
*同样,我们可以获取第二部分的更新 map 。
*现在,通过将相应的对(例如,键4的映射1中的值和键4的映射2中的值)相乘并将它们相加得出答案。
用这种方法,我们最终检查了1000个数字。
我的问题是我们如何进一步优化?有更好的解决方案吗?
最佳答案
对于0 <= s <= 18
,确切地存在10 - |s - 9|
方法来获取s
作为两位数的和。
所以,对于第一部分
int first[28] = {0};
for(int s = 0; s <= 18; ++s) {
int c = 10 - (s < 9 ? (9 - s) : (s - 9));
for(int d = 1; d <= 9; ++d) {
first[s+d] += c;
}
}
那是19 * 9 = 171次迭代,对于后半部分,也类似地执行,内部循环从0开始而不是1,即19 * 10 = 190次迭代。然后将
first[i]*second[i]
求和为1 <= i <= 27
。关于c++ - 查找满足某些属性的六位数数字的优化算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13059952/