nemestnyi
BAN USER1. In-order traverse binary tree, and get array of predecessors
2. Fill matrix using the array obtained in step 1
Complexity is O(2n).
Memory is O(n).
public class BinaryTreeNode
{
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public int Data;
}
public class BinaryTree
{
public int Size;
public BinaryTreeNode Root;
}
public static int[,] FinPredecessorsMatrix(BinaryTree binaryTree)
{
var size = binaryTree.Size;
var arr = new int[size];
InOrderTraverse(binaryTree.Root, arr, 0);
var matrix = new int[size, size];
for (var i = 1; i < size; i++)
{
matrix[arr[i - 1], arr[i]] = 1;
}
return matrix;
}
private static int InOrderTraverse(BinaryTreeNode node, int[] arr, int index)
{
if (node == null)
return index;
index = InOrderTraverse(node.Left, arr, index);
arr[index] = node.Data;
index++;
return InOrderTraverse(node.Right, arr, index);
}
This solution is similar to quicksort algorithm in part of partition of array, but simplier. Complexity is O(n).
public static int BringNzeToLeft(int[] arr)
{
int i = 0;
int j = arr.Length - 1;
while (true)
{
while (i < arr.Length && arr[i] != 0)
i++;
while (j >= 0 && arr[j] == 0)
j--;
if (i < j)
Swap(arr, i, j);
else
return i;
i++;
j--;
}
}
private static void Swap(int[] arr, int left, int right)
{
var tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
I think if it's not forbidden, we can simply change data in tree nodes, traverse at first left and right nodes, then swap them.
i.e. in order traverse for left node and in order traverse for right node recursively.
Complexity is O(n).
public class TreeNode
{
public TreeNode Left;
public TreeNode Right;
public string Data;
}
public static void ReverseNodes(TreeNode root)
{
ReverseNodesInternal(root.Left, root.Right);
}
private static void ReverseNodesInternal(TreeNode left, TreeNode right)
{
if (left == null || right == null)
return;
ReverseNodesInternal(left.Left, right.Right);
ReverseNodesInternal(left.Right, right.Left);
var tmp = left.Data;
left.Data = right.Data;
right.Data = tmp;
}
C#, NUnit
// Algorithm:
// 1. Get item and check if it is in right position
// 2. If so move to next item
// 3. Else, start to swap items sequentially, until find item in the right position
// O(n)
public static void Permutation(int[] x, int[] a)
{
for (var i = 0; i < a.Length; i++)
{
var ind = a[i] - 1;
var val = x[i];
while (a[ind] - 1 != ind)
{
var tmpInd = a[ind] - 1;
var tmpVal = x[ind];
x[ind] = val;
a[ind] = ind + 1;
ind = tmpInd;
val = tmpVal;
}
}
}
[Test]
public static void PermutationTest()
{
var x = new[] {17, 5, 1, 9};
var a = new[] {3, 2, 4, 1};
Permutation(x, a);
Assert.AreEqual(new int[]{9, 5, 17, 1}, x);
x = new int[] { 10, 15, 20, 25, 30 };
a = new int[] { 1, 2, 3, 4, 5 };
Permutation(x, a);
Assert.AreEqual(new int[] { 10, 15, 20, 25, 30 }, x);
x = new int[] { 10, 15, 20, 25 };
a = new int[] { 4, 3, 2, 1 };
Permutation(x, a);
Assert.AreEqual(new int[] { 25, 20, 15, 10 }, x);
x = new int[] {10, 15, 20, 25, 30};
a = new int[] {5, 4, 3, 2, 1};
Permutation(x, a);
Assert.AreEqual(new int[] { 30, 25, 20, 15, 10 }, x);
}
// C#
// O(n + m + m/n = 2m)
public static bool IsAnagram(string a, string b)
{
if (string.IsNullOrEmpty(a) || string.IsNullOrEmpty(b))
return false;
if (a.Length > b.Length)
return false;
var dicA = new Dictionary<char, int>();
// O(n)
foreach (var ch in a)
{
if (dicA.ContainsKey(ch))
dicA[ch]++;
else
dicA.Add(ch, 1);
}
var i = 0;
while (i <= b.Length - a.Length)
{
var j = i;
var dicB = new Dictionary<char, int>();
// O(m)
while (j < i + a.Length)
{
if (dicB.ContainsKey(b[j]))
{
dicB[b[j]]++;
}
else
{
if (dicA.ContainsKey(b[j]))
dicB.Add(b[j], 1);
else
break;
}
j++;
}
if (j == i + a.Length)
{
if (dicA.Count == dicB.Count)
{
// O(n), can get into O(m/n) times
if (dicA.All(kvp => kvp.Value == dicB[kvp.Key]))
return true;
}
i = j;
}
else
{
i++;
}
}
return false;
}
1. Get sum all elements
2. Until the right combination will not be found, iterate over all combinations, which start from 1st element (because 1st element always will be in left combination) and stop when count of elements less than array length - 1 (because result array must have two parts)
3. If such combination found, rearrange the elements in array
O(2^(n-1) - 1)
- nemestnyi July 02, 2014