ahmad.m.hagag
BAN USER- Dynamic Programming
public static int Minimum(int[] N, int amount)
{
List<int> subAmount = new List<int>();
for (int i = 0; i < N.Length; i++)
{
if (N[i] == amount)
return 1;
else if (amount > N[i])
{
subAmount.Add(Minimum(N, amount - N[i]));
}
}
subAmount.Sort();
foreach (int count in subAmount)
{
if (count > 0)
return 1 + count;
}
return -1;
}
well, obviously this is subset sum for positive integers,
I just thought about it like this, we try to find the minimum subset of coins that sum to the target amount.
try to find one coin that matches the amount. if not, try to find two, then three, till u find a subset or you fail
public static Queue<int> SubSetSum_Major(int[] input, int amount)
{
Queue<int> result = null;
for (int resultCount = 1; resultCount < input.Length; resultCount++)
//try with seubsets with length 1, then 2 ...
for (int i = 0; i < input.Length; i++)
{
SubsetSum(input, i, resultCount, amount, ref result);
if (result != null)
{
//whenever you find a result, will be with minimum length
return result;
}
}
return null;
}
public static void SubsetSum(int[] input, int startIndex, int subsetLength, int amount, ref Queue<int> result)
{
for (int i = startIndex; i <= input.Length - subsetLength; i++)
{
if (subsetLength == 1)
{
if (amount == input[i])
{
result = new Queue<int>(new int[] { input[i] });
}
}
else
{
SubsetSum(input, i + 1, subsetLength - 1, amount - input[i], ref result);
if (result != null)
{
result.Enqueue(input[i]);
if (result.Count == subsetLength)
return;
}
}
}
}
traverse the input array, when you find the start of the target arrray, start comparing,
If you found the whole target array, return the currentindex - target.Length as the starting index.
At any time If the input array has fewer letters than those in the target array, return -1
public static int IsSubstring(string input, string target)
{
if (input.Length < target.Length || target.Length ==0)
return -1;
int targetPointer = 0;
for (int inputIndex = 0; inputIndex < input.Length; inputIndex++)
{
// you finished matching all the target array characters against the input , and it worked
if (targetPointer == target.Length)
{
return inputIndex - target.Length;
}
if (input[inputIndex] == target[targetPointer])
{
targetPointer++;
}
else
{
// reset the target pointer for next matching chance (when you find the first letter again)
targetPointer = 0;
}
}
return -1;
}
Same Idea, but more simple code - I guess -
private static void PrintAlternating(TreeNode<int> root)
{
if (root == null)
return;
Queue<TreeNode<int>> level = new Queue<TreeNode<int>>();
level.Enqueue(root);
bool left = true;
TreeNode<int> element2Print;
while (level.Count > 0)
{
Queue<TreeNode<int>> newLevel = new Queue<TreeNode<int>>();
element2Print = level.Peek();
while (level.Count > 0)
{
if (!left)
element2Print = level.Peek();
TreeNode<int> current = level.Dequeue();
if (current.left != null)
newLevel.Enqueue(current.left);
if (current.right != null)
newLevel.Enqueue(current.right);
}
Console.WriteLine(element2Print.value);
level = new Queue<TreeNode<int>>(newLevel.ToArray());
left = !left;
}
}
I think it is better to think about it as BFS. I got the level in each iteration in a queue.
I use alternating "left" variable to view the first element in the leve; queue one time(left most), and last element the other time ( right most)
private static void PrintAlternating(TreeNode<int> root)
{
if (root == null)
return;
Queue<TreeNode<int>> level = new Queue<TreeNode<int>>();
level.Enqueue(root);
bool left = true;
TreeNode<int> element2Print;
while (level.Count > 0)
{
Queue<TreeNode<int>> newLevel = new Queue<TreeNode<int>>();
element2Print = level.Peek();
while (level.Count > 0)
{
if (!left)
element2Print = level.Peek();
TreeNode<int> current = level.Dequeue();
if (current.left != null)
newLevel.Enqueue(current.left);
if (current.right != null)
newLevel.Enqueue(current.right);
}
Console.WriteLine(element2Print.value);
level = new Queue<TreeNode<int>>(newLevel.ToArray());
left = !left;
}
}
TESTING
static void Main(string[] args)
{
TreeNode<int> root = InitiateTree();
PrintAlternating(root);
Console.ReadKey();
}
public class TreeNode<T>
{
public TreeNode(T value, TreeNode<T> left, TreeNode<T> right)
{
this.value = value;
this.left = left;
this.right = right;
}
public T value;
public TreeNode<T> left;
public TreeNode<T> right;
}
private static TreeNode<int> InitiateTree()
{
return new TreeNode<int>(1,
new TreeNode<int>(2,
null,
new TreeNode<int>(4,
null,
null)),
new TreeNode<int>(3,
new TreeNode<int>(5,
new TreeNode<int>(7,
null,
null),
null
),
new TreeNode<int>(6,
null,
null)
)
);
}
Dynamic programming with Memoization
- ahmad.m.hagag June 21, 2013