Goro
BAN USERRuns in O(n) time and O(1) space:
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
public class Test
{
public static void Main()
{
var road = new Road
{
Blocks = CreateBlocks("_**_**_"),
RollarSize = 3
};
Console.WriteLine(road.CountMinRepairs());
}
public static List<Block> CreateBlocks(string blocks)
{
var model = new List<Block>();
foreach(var block in blocks)
{
model.Add(new Block { IsDamaged = block == '*' });
}
return model;
}
}
public class Block
{
public bool IsDamaged { get; set; }
public bool IsRepaired { get; private set; }
public void Repair()
{
IsRepaired = true;
}
public bool IsNew()
{
return !IsDamaged && !IsRepaired;
}
public bool NeedsRepair()
{
return IsDamaged && !IsRepaired;
}
}
public class Road
{
public List<Block> Blocks { get; set; } = new List<Block>();
public int RollarSize;
public int Repair(int pos)
{
int count = 0;
if (pos < 0 || pos + RollarSize > Blocks.Count) return 0;
for (int i = 0; i < RollarSize; i++)
{
if (!Blocks[pos + i].IsRepaired)
{
Blocks[pos + i].Repair();
count++;
}
}
return count;
}
public int CountMinRepairs()
{
int count = 0;
for (int i = 0; i < Blocks.Count; i++)
{
var block = Blocks[i];
var newBlocks = RollarSize;
int pos = 0, cur = 0;
bool wasRepaired = false;
if (!block.NeedsRepair()) continue;
for (int j = i-(RollarSize-1); j <= i; j++)
{
if (j < 0 || j + RollarSize > Blocks.Count) continue;
cur = 0;
for (int k = 0; k < RollarSize; k++)
{
if (Blocks[j+k].IsNew()) cur++;
}
if (cur <= newBlocks)
{
newBlocks = cur;
pos = j;
wasRepaired = true;
}
}
if (wasRepaired)
{
count += Repair(pos);
}
}
return count;
}
}
Runs in O(n) time.
Considering that the random strings are words, real words has a max_size of ~30 chars, or that it's random chars, but with a max of a constant, this will yield O(n * c) where c == avg number of chars in a word, thus it's constant, thus this is O(n).
- Goro May 26, 2016