我昨天在算法测试中遇到了这个问题,我无法找到答案.它让我绝对疯狂,因为它值得大约40分.我认为大多数课程都没有正确解决,因为我在过去24小时内没有提出解决方案.
给定长度为n的任意二进制字符串,如果存在,则在字符串中找到三个均匀间隔的字符串.编写一个在O(n*log(n))时间内解决此问题的算法.
所以像这样的字符串有三个"均匀间隔"的字符串:11100000,0100100100
编辑:这是一个随机数,所以它应该可以适用于任何数字.我给出的例子是为了说明"均匀间隔"的属性.所以1001011是一个有效的数字.1,4和7是均匀间隔的.
给定一个整数数组,A 1,A 2,...,A n,包括负数和正数,以及另一个整数S.现在我们需要在数组中找到三个不同的整数,其总和最接近给定的整数S如果存在多个解决方案,则其中任何一个都可以.
您可以假设所有整数都在int32_t范围内,并且计算总和时不会发生算术溢出.S没什么特别的,只是随机挑选的数字.
有没有比强力搜索更有效的算法来找到三个整数？