Asaf
BAN USERHere is a non brute force solution
public static void Print()
{
var board = new int[4, 4];
var solutions = GetSolutions(board, 0, 0);
Console.WriteLine(solutions.Count);
}
public static List<int[,]> GetSolutions(int[,] board, int x, int y)
{
var res = new List<int[,]>();
if (y > 3)
{
res.Add(board);
return res;
}
var options = GetOptions(board, x, y);
int newX = x == 3 ? 0 : x+1;
int newY = x == 3 ? y+1 : y;
foreach (var number in options)
{
var newBoard = board.Clone() as int[,];
newBoard[x, y] = number;
res.AddRange(GetSolutions(newBoard, newX, newY));
}
return res;
}
private static List<int> GetOptions(int[,] board, int x, int y)
{
var options = new List<int>() { 1, 2, 3, 4 };
for (int i = 0; i < x; i++)
{
var val = board[i, y];
if (options.Contains(val))
{
options.Remove(val);
}
}
for (int i = 0; i < y; i++)
{
var val = board[x, i];
if (options.Contains(val))
{
options.Remove(val);
}
}
var xx = x / 2;
var yy = y / 2;
for (int i = xx*2; i < xx*2+2; i++)
{
for (int j = yy*2; j < yy*2+2; j++)
{
var val = board[i, j];
if (options.Contains(val))
{
options.Remove(val);
}
}
}
return options;
}
C# solution for creating a doubly linked list using existing memory, notice the recursion will take up memory too
public static Node ConvertBstToListReturnHead(Node root)
{
return ConvertBstToList(root).Item1;
}
public static Tuple<Node, Node> ConvertBstToList(Node root)
{
if (root == null)
{
return null;
}
var left = ConvertBstToList(root.Left);
var right = ConvertBstToList(root.Right);
Node first=root;
Node last=root;
if (left != null)
{
root.Left = left.Item2;
left.Item2.Right = root;
first = left.Item1;
}
if (right != null)
{
root.Right = right.Item1;
right.Item1.Left = root;
last = right.Item2;
}
return new Tuple<Node, Node>(first, last);
}
C# implementation for a modified binary search:
public static void PrintAges(int[] ages)
{
printAges(ages, ages[0], 1, 1, ages.Length - 1, ages.Length - 1);
}
public static void printAges(int[] ages, int age, int count, int start, int end, int endIndex)
{
if (start >= end)
{
if (start == end && ages[start] == age)
{
count++;
}
Console.WriteLine(string.Format("Age:{0}, Times:{1}", age, count));
if (start == end && ages[start] != age)
{
printAges(ages, ages[start], 1, start + 1, endIndex, endIndex);
}
else if (end != endIndex)
{
printAges(ages, ages[end + 1], 0, end + 1, endIndex, endIndex);
}
}
else
{
int middleIndex = (start + end) / 2;
if (ages[middleIndex] == age)
{
printAges(ages, age, count + middleIndex - start+1, middleIndex + 1, end, endIndex);
}
else
{
printAges(ages, age, count, start, middleIndex - 1, endIndex);
}
}
}
I liked your idea but it will not work on 123145
- Asaf January 25, 2015the longest unique string is 23145,
I think the variable lastDup should be set to letters[input.charAt(i)] + 1