我昨天在算法测试中遇到了这个问题，但我无法找出答案，这让我非常疯狂，因为它占了大约40分。 我觉得大多数同学没有正确解决它，因为我过去24小时内也没有找到解决方案。
给定长度为n的任意二进制字符串，如果存在三个等间距的1，请编写一个算法在O(n*log(n))的时间内解决此问题。
像这样的字符串有三个“等间距”的1：11100000、0100100100
编辑：这是一个随机数，所以它应该适用于任何数字。 我给出的例子是为了说明“等间距”属性。 因此，1001011是一个有效的数字，其中1、4和7是等间距的1。
foreach character in the string
if the character equals 1 {
if length cache > 0 { //we can skip the first one
foreach location in the cache { //last in first out kind of order
if ((currentlocation + (currentlocation - location)) < length string)
if (string[(currentlocation + (currentlocation - location))] equals 1)
return found evenly spaced string
else
break;
}
}
remember the location of this character in a some sort of cache.
}
return didn't find evenly spaced string
C# 代码：
public static Boolean FindThreeEvenlySpacedOnes(String str) {
List<int> cache = new List<int>();
for (var x = 0; x < str.Length; x++) {
if (str[x] == '1') {
if (cache.Count > 0) {
for (var i = cache.Count - 1; i > 0; i--) {
if ((x + (x - cache[i])) >= str.Length)
break;
if (str[(x + (x - cache[i]))] == '1')
return true;
}
}
cache.Add(x);
}
}
return false;
}
它是如何工作的：
iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache
iteration 2:
x
|
101101001
iteration 3:
a x b
| | |
101101001
//we retrieve location a out of the cache and then based on a
//we calculate b and check if te string contains a 1 on location b
//and of course we store x in the cache because it's a 1
iteration 4:
axb
|||
101101001
a x b
| | |
101101001
iteration 5:
x
|
101101001
iteration 6:
a x b
| | |
101101001
a x b
| | |
101101001
//return found evenly spaced string
如何使用O(n^2)的空间来实现简单的O(n)解决方案？（假设所有位运算符都在O(1)内完成。）
该算法基本上分为四个阶段：
第一阶段：对于原始数字中的每个位，找出其中的1有多远，但只考虑一个方向。（我考虑了最不重要的位方向上的所有位。）
第二阶段：颠倒输入位的顺序；
第三阶段：在反转的输入上重新运行步骤1。
第四阶段：比较第1阶段和第3阶段的结果。如果任何位在上下等距离，则必须有一个命中。
请记住，上述算法中的任何一步都不会超过O(n)的时间。 ^_^
作为额外的好处，此算法将从每个数字中找到所有等距离的1。因此，例如，如果您得到“0x0005”的结果，则在1和3个单位处均有等距离的1
我没有真正尝试优化下面的代码，但它是可编译的C#代码，似乎可以工作。
using System;
namespace ThreeNumbers
{
class Program
{
const int uint32Length = 32;
static void Main(string[] args)
{
Console.Write("Please enter your integer: ");
uint input = UInt32.Parse(Console.ReadLine());
uint[] distancesLower = Distances(input);
uint[] distancesHigher = Distances(Reverse(input));
PrintHits(input, distancesLower, distancesHigher);
}
/// <summary>
/// Returns an array showing how far the ones away from each bit in the input. Only
/// considers ones at lower signifcant bits. Index 0 represents the least significant bit
/// in the input. Index 1 represents the second least significant bit in the input and so
/// on. If a one is 3 away from the bit in question, then the third least significant bit
/// of the value will be sit.
///
/// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.
/// (Where n is the number of bits in the input.)
/// </summary>
public static uint[] Distances(uint input)
{
uint[] distanceToOnes = new uint[uint32Length];
uint result = 0;
//Sets how far each bit is from other ones. Going in the direction of LSB to MSB
for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
distanceToOnes[arrayIndex] = result;
result <<= 1;
if ((input & bitIndex) != 0)
{
result |= 1;
}
}
return distanceToOnes;
}
/// <summary>
/// Reverses the bits in the input.
///
/// As programmed this algorithm needs O(n) time and O(n) space.
/// (Where n is the number of bits in the input.)
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static uint Reverse(uint input)
{
uint reversedInput = 0;
for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
{
reversedInput <<= 1;
reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
}
return reversedInput;
}
/// <summary>
/// Goes through each bit in the input, to check if there are any bits equally far away in
/// the distancesLower and distancesHigher
/// </summary>
public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
{
const int offset = uint32Length - 1;
for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
//hits checks if any bits are equally spaced away from our current value
bool isBitSet = (input & bitIndex) != 0;
uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];
if (isBitSet && (hits != 0))
{
Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
}
}
}
}
}
有人可能会评论说，对于足够大的任何数字，位运算无法在 O(1) 时间内完成。你是正确的。然而，我猜想每个使用加法、减法、乘法或除法（无法通过移位完成）的解决方案都会遇到这个问题。
这里没有理论答案，但我写了一个快速的Java程序来探索运行时间行为作为k和n的函数，其中n是总位长度，k是1的数量。我和一些回答者一样认为，“常规”算法检查所有比特位置对并查找第三个比特，即使在最坏情况下需要O(k^2)，但实际上由于最坏情况需要稀疏比特串，因此是O(n ln n)。
不管怎样，下面是程序。这是一个蒙特卡洛风格的程序，对于常数n运行大量的试验NTRIALS，并随机生成一系列k值的比特集合，使用指定的上下限约束在伯努利过程中的1的密度，并记录找到或未找到均匀间隔的三个1的运行时间，以步数而不是CPU时间来衡量。我对n=64, 256, 1024, 4096, 16384*（仍在运行）进行了测试运行，先进行500000次试验，以查看哪些k值需要最长的运行时间，然后进行另一次测试，进行5000000次试验，并缩小对单点密度的关注范围以查看那些数值的情况。最长的运行时间确实出现在非常稀疏的密度情况下（例如，对于n=4096，运行时间峰值在k=16-64范围内，平均运行时间在k=31时为4212步，最大运行时间在k=58时峰值为5101步）。看起来，要使最坏情况的O(k^2)步长超过扫描比特串以查找1的位置索引的O(n)步长，需要非常大的N值。
package com.example.math;
import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;
public class EvenlySpacedOnesTest {
static public class StatisticalSummary
{
private int n=0;
private double min=Double.POSITIVE_INFINITY;
private double max=Double.NEGATIVE_INFINITY;
private double mean=0;
private double S=0;
public StatisticalSummary() {}
public void add(double x) {
min = Math.min(min, x);
max = Math.max(max, x);
++n;
double newMean = mean + (x-mean)/n;
S += (x-newMean)*(x-mean);
// this algorithm for mean,std dev based on Knuth TAOCP vol 2
mean = newMean;
}
public double getMax() { return (n>0)?max:Double.NaN; }
public double getMin() { return (n>0)?min:Double.NaN; }
public int getCount() { return n; }
public double getMean() { return (n>0)?mean:Double.NaN; }
public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; }
// some may quibble and use n-1 for sample std dev vs population std dev
public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
for (int i = 0; i < statistics.length; ++i)
{
StatisticalSummary summary = statistics[i];
ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
i,
summary.getCount(),
summary.getMin(),
summary.getMax(),
summary.getMean(),
summary.getStdDev());
}
}
}
public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
{
public void setProbability(double d);
public boolean getNextBoolean();
}
static public class Bernoulli implements RandomBernoulliProcess
{
final private Random r = new Random();
private double p = 0.5;
public boolean getNextBoolean() { return r.nextDouble() < p; }
public void setProbability(double d) { p = d; }
}
static public class TestResult {
final public int k;
final public int nsteps;
public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; }
}
////////////
final private int n;
final private int ntrials;
final private double pmin;
final private double pmax;
final private Random random = new Random();
final private Bernoulli bernoulli = new Bernoulli();
final private BitSet bits;
public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
this.bits = new BitSet(n);
}
/*
* generate random bit string
*/
private int generateBits()
{
int k = 0; // # of 1's
for (int i = 0; i < n; ++i)
{
boolean b = bernoulli.getNextBoolean();
this.bits.set(i, b);
if (b) ++k;
}
return k;
}
private int findEvenlySpacedOnes(int k, int[] pos)
{
int[] bitPosition = new int[k];
for (int i = 0, j = 0; i < n; ++i)
{
if (this.bits.get(i))
{
bitPosition[j++] = i;
}
}
int nsteps = n; // first, it takes N operations to find the bit positions.
boolean found = false;
if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
{
int lastBitSetPosition = bitPosition[k-1];
for (int j1 = 0; !found && j1 < k; ++j1)
{
pos[0] = bitPosition[j1];
for (int j2 = j1+1; !found && j2 < k; ++j2)
{
pos[1] = bitPosition[j2];
++nsteps;
pos[2] = 2*pos[1]-pos[0];
// calculate 3rd bit index that might be set;
// the other two indices point to bits that are set
if (pos[2] > lastBitSetPosition)
break;
// loop inner loop until we go out of bounds
found = this.bits.get(pos[2]);
// we're done if we find a third 1!
}
}
}
if (!found)
pos[0]=-1;
return nsteps;
}
/*
* run an algorithm that finds evenly spaced ones and returns # of steps.
*/
public TestResult run()
{
bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
// probability of bernoulli process is randomly distributed between pmin and pmax
// generate bit string.
int k = generateBits();
int[] pos = new int[3];
int nsteps = findEvenlySpacedOnes(k, pos);
return new TestResult(k, nsteps);
}
public static void main(String[] args)
{
int n;
int ntrials;
double pmin = 0, pmax = 1;
try {
n = Integer.parseInt(args[0]);
ntrials = Integer.parseInt(args[1]);
if (args.length >= 3)
pmin = Double.parseDouble(args[2]);
if (args.length >= 4)
pmax = Double.parseDouble(args[3]);
}
catch (Exception e)
{
System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
System.exit(0);
return; // make the compiler happy
}
final StatisticalSummary[] statistics;
statistics=new StatisticalSummary[n+1];
for (int i = 0; i <= n; ++i)
{
statistics[i] = new StatisticalSummary();
}
EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
int printInterval=100000;
int nextPrint = printInterval;
for (int i = 0; i < ntrials; ++i)
{
TestResult result = test.run();
statistics[result.k].add(result.nsteps);
if (i == nextPrint)
{
System.err.println(i);
nextPrint += printInterval;
}
}
StatisticalSummary.printOut(System.out, statistics);
}
}
# <algorithm>
def contains_evenly_spaced?(input)
return false if input.size < 3
one_indices = []
input.each_with_index do |digit, index|
next if digit == 0
one_indices << index
end
return false if one_indices.size < 3
previous_indexes = []
one_indices.each do |index|
if !previous_indexes.empty?
previous_indexes.each do |previous_index|
multiple = index - previous_index
success_index = index + multiple
return true if input[success_index] == 1
end
end
previous_indexes << index
end
return false
end
# </algorithm>
def parse_input(input)
input.chars.map { |c| c.to_i }
end
我在处理数百万位的最坏情况时遇到了麻烦。从/dev/urandom进行模糊测试基本上会给你O(n)，但我知道最坏情况比那还要糟糕。我只是无法确定有多糟糕。对于小的n，可以轻松找到大约为3*n*log(n)的输入，但对于这个特定问题，很难将其与其他增长顺序区分开来。
有没有人在处理最坏情况输入的时候能够生成长度大于十万的字符串？
假设：
完全错误，谈论log(n)个上限的1
编辑：
现在我发现使用Cantor数（如果正确），集合密度为(2/3)^Log_3(n)（多么奇怪的函数），我同意，log(n)/n的密度太强了。
如果这是上限，那么至少有一种算法可以在O(n*(3/2)^(log(n)/log(3)))时间复杂度和O((3/2)^(log(n)/log(3)))空间复杂度内解决此问题。（请查看Justice的答案）
这仍然比O(n^2)好得多。
这个函数((3/2)^(log(n)/log(3)))在第一眼看起来真的像n*log(n)。
我如何得到这个公式？
将Cantor数应用于字符串。
假设字符串长度为3^p == n
在生成Cantor字符串的每个步骤中，您保留先前数量的2/3个1。应用p次。
这意味着 (n * ((2/3)^p)) -> (((3^p)) * ((2/3)^p)) 剩下的数字，简化后为 2^p。
这意味着在 3^p 的字符串中有 2^p 个数字 -> (3/2)^p 个数字。代入 p=log(n)/log(3) 并得到
((3/2)^(log(n)/log(3)))
我将尝试提出一种数学方法。这只是一个开始而不是结束，因此任何帮助、评论或甚至矛盾都将不胜感激。然而，如果这种方法被证明有效，则算法就是在字符串中进行直接搜索。
给定一个固定的空间数量 k 和一个字符串 S，寻找 k-间隔三元组的时间复杂度为 O(n) - 我们只需测试每个 0<=i<=(n-2k) 是否满足 S[i]==S[i+k]==S[i+2k]。测试的时间复杂度为 O(1)，我们需要进行 n-k 次测试，其中 k 是一个常数，因此总时间复杂度为 O(n-k)=O(n)。
假设 1 的数量与我们需要搜索的最大空间之间存在反比关系。也就是说，如果有很多 1，那么必须存在一个三元组，并且它必须相当密集；如果只有很少的 1，则三元组（如果存在）可以相当稀疏。换句话说，我可以证明如果我有足够的 1，这样的三元组必须存在 - 而且我拥有的 1 越多，就必须找到更密集的三元组。这可以通过Pigeonhole principle来解释 - 希望稍后详细说明。
假设我对可能需要查找的空间数量有一个上限 k。现在，对于在 S[i] 中定位到的每个 1，我们需要检查 S[i-1] 和 S[i+1]、S[i-2] 和 S[i+2]，... S[i-k] 和 S[i+k] 中是否存在 1。这需要对 S 中的每个 1 进行 O((k^2-k)/2)=O(k^2) 的检查 - 这是由于Gauss' Series Summation Formula。请注意，这与第 1 节不同 - 我将 k 视为空间的上限，而不是常数空间。
我们需要证明 O(n*log(n))。也就是说，我们需要展示 k*(1的数量) 与 log(n) 成比例。
如果我们能够做到这一点，算法就很简单了 - 对于每个索引为 i 的 S 中的 1，只需从两侧寻找距离为 k 的 1。如果在相同的距离内找到两个 1，则返回 i 和 k。再次强调，难点在于找到 k 并证明其正确性。
我非常感谢您在这里的评论 - 我一直在试图在我的白板上找到 k 和 1 的数量之间的关系，但迄今为止没有成功。
显然，我们需要同时检查许多三元组，因此我们需要以某种方式压缩这些检查。我有一个候选算法，但分析时间复杂度超出了我的能力和时间限制。
建立一棵树，每个节点有三个子节点，每个节点包含其叶子中1的总数。还要在1上建立一个链表。为每个节点分配一个允许的成本，与其覆盖范围成比例。只要我们在每个节点花费的时间在预算内，我们就会有一个O(n lg n)的算法。
--
从根节点开始。如果其下方的1的总数的平方小于其允许的成本，应用朴素算法。否则对其子节点进行递归。
现在，我们要么在预算范围内返回，要么知道没有完全包含在其中一个子节点中的有效三元组。因此，我们必须检查节点间的三元组。
现在事情变得非常混乱。我们基本上希望在限制范围的同时对可能的子节点集进行递归。一旦范围足够受限，以至于朴素算法可以在预算范围内运行，就执行它。享受实现这个吧，因为我保证这将是繁琐的。有大约十几种情况。
--
我认为该算法有效的原因是，没有有效三元组的序列似乎在1的一堆和很多0之间交替出现。它有效地分割了附近的搜索空间，并且树模拟了这种分割。
算法的运行时间并不明显。它依赖于序列的非平凡属性。如果1非常稀疏，则朴素算法将在预算范围内工作。如果1很密集，则应立即找到匹配项。但是，如果密度“恰好正确”（例如，接近~n^0.63，可以通过在没有基数3中的“2”数字的位置设置所有位来实现），我不知道它是否有效。您必须证明分裂效应足够强。
对于您来说，可能可以使用Rabin-Karp算法的改编版本。它的复杂度是0(n)，因此可以帮助您。
请查看http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm
这可能是一个解决方案吗？我不确定它是否是O(nlogn)，但在我看来，它比O(n²)更好，因为找不到三元组的唯一方法是质数分布。
还有改进的空间，第二个找到的1可以成为下一个第一个1。此外没有错误检查。
#include <iostream>
#include <string>
int findIt(std::string toCheck) {
for (int i=0; i<toCheck.length(); i++) {
if (toCheck[i]=='1') {
std::cout << i << ": " << toCheck[i];
for (int j = i+1; j<toCheck.length(); j++) {
if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << " found" << std::endl;
return 0;
}
}
}
}
return -1;
}
int main (int agrc, char* args[]) {
std::string toCheck("1001011");
findIt(toCheck);
std::cin.get();
return 0;
}
我认为这个算法的复杂度是O(n log n)（使用C++和DevStudio 2k5）。现在，我不知道如何分析算法以确定其复杂度，因此我已经向代码中添加了一些度量收集信息。该代码计算任何给定输入的1和0序列上执行的测试数量（希望我没有搞砸算法）。我们可以将实际测试次数与O值进行比较，看看是否存在相关性。
#include <iostream>
using namespace std;
bool HasEvenBits (string &sequence, int &num_compares)
{
bool
has_even_bits = false;
num_compares = 0;
for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
{
for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
{
++num_compares;
if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
{
has_even_bits = true;
// we could 'break' here, but I want to know the worst case scenario so keep going to the end
}
}
}
return has_even_bits;
}
int main ()
{
int
count;
string
input = "111";
for (int i = 3 ; i < 32 ; ++i)
{
HasEvenBits (input, count);
cout << i << ", " << count << endl;
input += "0";
}
}
这个程序输出每个字符串长度的测试次数，最多达到32个字符。以下是结果：
n Tests n log (n)
=====================
3 1 1.43
4 2 2.41
5 4 3.49
6 6 4.67
7 9 5.92
8 12 7.22
9 16 8.59
10 20 10.00
11 25 11.46
12 30 12.95
13 36 14.48
14 42 16.05
15 49 17.64
16 56 19.27
17 64 20.92
18 72 22.59
19 81 24.30
20 90 26.02
21 100 27.77
22 110 29.53
23 121 31.32
24 132 33.13
25 144 34.95
26 156 36.79
27 169 38.65
28 182 40.52
29 196 42.41
30 210 44.31
31 225 46.23
我也添加了“n log n”值。使用您选择的绘图工具绘制这些值，以查看两个结果之间的相关性。这种分析是否适用于所有n值？我不知道。