ZuZu
BAN USER@ Miguel ,
Answer to "ccc" is 294
Answer to "ddd" is 945
Answer to "abbc" is 27 (use pencil and piece of paper)
Answer to "zzzzz" is 797
And there are some my tests:
Answer to "ab" is 1
Answer to "ba" is 26
Answer to "abab" is 1
Answer to "abccba" is 757
And here is my working code/solution:
static int MOD = 1009;
static int CalcSstring(string s)
{
int[] a = new int[s.Length];
a[0] = 1;
for (int i = 1; i < a.Length; i++)
{
a[i] = (a[i - 1] * 25) % MOD;
}
int result = 0;
for (int i = 0; i < s.Length; i++)
{
for (char ch = 'a'; ch < s[i]; ch++)
{
if (i > 0 && s[i - 1] == ch) continue;
result = (result + a[s.Length - i - 1]) % MOD;
}
}
return (result + 1) % MOD;
}
Simple recursive solution :
static bool PatternMatchString(string pattern, string s)
{
return PatternMatchString(pattern, s, pattern.Length - 1, s.Length - 1);
}
static bool PatternMatchString(string pattern, string s, int i, int j)
{
if (i < 0)
{
return j < 0;
}
bool result = false;
if (char.IsLetter(pattern[i]))
{
result |= j >= 0 && pattern[i] == s[j] && PatternMatchString(pattern, s, i - 1, j - 1);
}
else
{
result |= pattern[i] == '+' && PatternMatchString(pattern, s, i - 1, j);
result |= pattern[i] == '*' && PatternMatchString(pattern, s, i - 2, j);
result |= j >= 0 && pattern[i - 1] == s[j] && PatternMatchString(pattern, s, i, j - 1);
}
return result;
}
And then we can simplify the above implementation to:
static int FindInRotatedArray2(int[] a, int k)
{
int l = 0;
int r = a.Length - 1;
while (l <= r)
{
int m = l + (r - l) / 2;
if (k == a[m]) return m;
if (a[l] <= a[m]) // 1, 2
{
if (a[l] <= k && k < a[m]) r = m - 1;
else l = m + 1;
}
else // 3, 4
{
if (a[m] < k && k <= a[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}
// 1. L < M < R (1,2,3) - regular QuickSort
// 2. L < M > R (2,5,1)
// 3. L > M < R (5,1,3)
// 4. L > M > R (3,2,1) - reverse QuickSort
static int FindInRotatedArray(int[] a, int k)
{
int l = 0;
int r = a.Length - 1;
while (l < r)
{
int m = l + (r - l) / 2;
if (k == a[m]) return m;
if (a[l] <= a[m] && a[m] <= a[r]) // 1
{
if (a[m] > k) r = m - 1;
else l = m + 1;
}
else if (a[l] <= a[m] && a[m] >= a[r]) // 2
{
if (a[l] <= k && k < a[m]) r = m - 1;
else l = m + 1;
}
else if (a[l] >= a[m] && a[m] <= a[r]) // 3
{
if (a[m] < k && k <= a[r]) l = m + 1;
else r = m - 1;
}
else // 4
{
if (a[m] > k) l = m + 1;
else r = m - 1;
}
}
return a[l] == k ? l : -1;
}
static List<int[]> AllSets(int[] a)
{
return AllSets(a, 0, new List<int>()).ToList();
}
static IEnumerable<int[]> AllSets(int[] a, int i, List<int> curr)
{
if (i == a.Length)
{
yield return curr.ToArray();
}
else
{
foreach(var s in AllSets(a, i + 1, curr))
{
yield return s;
}
curr.Add(a[i]);
foreach(var s in AllSets(a, i + 1, curr))
{
yield return s;
}
curr.RemoveAt(curr.Count - 1);
}
}
O(N logN):
static bool IsExistsPairThatThierSumIsK(int[] a, int k)
{
for (int i = 0; i < a.Length; i++)
{
int j = FindLeftmost(a, k - a[i]);
if (j == -1) continue;
if (i != j || (i + 1 < a.Length && a[i] == a[i + 1])) return true;
}
return false;
}
static int FindLeftmost(int[] a, int k)
{
int l = 0;
int r = a.Length - 1;
while (l < r)
{
int m = l + (r - l) / 2;
if (a[m] >= k) r = m;
else l = m + 1;
}
return a[l] == k ? l : -1;
}
O(N):
static bool IsExistsPairThatThierSumIsK2(int[] a, int k)
{
int l = 0;
int r = a.Length - 1;
while (l < r)
{
if (a[l] + a[r] == k) return true;
else if (a[l] + a[r] > k) r--;
else l++;
}
return false;
}
Brute force :
static bool IsWinner(int n)
{
bool result = false;
for (int i = 0; i < 31 && n > 1 << i; i++)
{
if ((n & (1 << i)) == 0 && (n & (1 << (i + 1))) != 0) // detect this one "10"
result |= !IsWinner(n - (1 << i));
}
return result;
}
The best solution :
static bool IsWinner2(int n)
{
int sum = 0;
int zeros = 0;
while (n > 0)
{
if ((n & 1) != 0) sum += zeros;
else zeros++;
n >>= 1;
}
return (sum & 1) != 0 ? true : false; // true - first player win, false - second player win
}
static void Merge(int[] a, int[] b) // assumption: length of b is twice bigger than length of a
{
int i = a.Length - 1;
int j = a.Length - 1;
for (int p = b.Length - 1; p >=0; p--)
{
if (i >= 0 && (j < 0 || a[i] > b[j]))
{
b[p] = a[i--];
}
else
{
b[p] = b[j--];
}
}
}
static int CountDistinctNodesFromSourceToDestination(List<int>[] graph, int n, int source, int dest)
{
bool[] inPath = new bool[n];
DFS(source, dest, graph, new bool[n], inPath);
return inPath.Where(_ => _).Count();
}
static bool DFS(int v, int dest, List<int>[] g, bool[] used, bool[] inPath)
{
bool pathFound = false;
if (v == dest)
{
pathFound = true;
}
else
{
used[v] = true;
foreach (int u in g[v])
{
if (!used[u])
{
pathFound |= DFS(u, dest, g, used, inPath);
}
}
used[v] = false;
}
inPath[v] |= pathFound;
return pathFound;
}
static void PrintAllPaths(List<int>[] graph, int n, int source, int dest)
{
DFS(source, dest, graph, new List<int>(), new bool[n]);
}
static void DFS(int v, int dest, List<int>[] g, List<int> path, bool[] used)
{
path.Add(v);
used[v] = true;
if (v == dest)
{
Print(path);
}
else
{
foreach(int u in g[v])
{
if (!used[u]) DFS(u, dest, g, path, used);
}
}
path.RemoveAt(path.Count - 1);
used[v] = false;
}
Simple one via C#:
static List<List<string>> GroupAnagrams(string[] words)
{
Dictionary<string, List<string>> d = new Dictionary<string, List<string>>();
foreach (var word in words)
{
string key = new string(word.ToCharArray().OrderBy(_ => _).ToArray());
if (!d.ContainsKey(key))
{
d.Add(key, new List<string>());
}
d[key].Add(word);
}
return d.Values.ToList();
}
Simple recursive approach :
static bool isMatch(string regex, string s)
{
return IsMatch(regex, s, regex.Length - 1, s.Length - 1);
}
static bool IsMatch(string regex, string s, int i, int j)
{
if (i < 0)
{
return j < 0;
}
bool result = false;
if (j >= 0)
{
if (regex[i] == '.' || regex[i] == s[j]) result |= IsMatch(regex, s, i - 1, j - 1);
}
if (regex[i] == '*') result |= IsMatch(regex, s, i - 2, j) || IsMatch(regex, s, i - 1, j);
return result;
}
Simple implementation for described idea :
static Node Clone(Node head)
{
if (head == null) return null;
Node doubledHead = head;
// double original list
while (head != null)
{
Node next = head.Next;
Node copy = new Node { Value = head.Value, Next = head.Next };
head.Next = copy;
head = next;
}
// set random link
Node originalRunner = doubledHead;
while (originalRunner != null)
{
originalRunner.Next.Random = originalRunner.Random == null ? null : originalRunner.Random.Next;
originalRunner = originalRunner.Next.Next;
}
// seperate lists
Node copyHead = doubledHead.Next;
Node copyTail = null;
while (doubledHead != null)
{
Node copyNode = doubledHead.Next;
if (copyTail != null) copyTail.Next = copyNode;
copyTail = copyNode;
doubledHead = doubledHead.Next.Next;
}
return copyHead;
}
You can solve this problem by writing your own comparer for numbers.
You must sort the list using this comparer. And then just concatenate all the elements.
The main idea of comparer :
1. X > Y <=> XY > YX
2. X < Y <=> XY < YX
3. X = Y <=> XY = YX
Don't forget to take care of the overflowing. (In my implementation below I've assumed that overflowing is impossible)
Implementation using custom created comparer class:
class SpecialComparer : IComparer<int>
{
public int Compare(int x, int y)
{
string xstr = x.ToString();
string ystr = y.ToString();
string XY = xstr + ystr;
string YX = ystr + xstr;
// returns
// positive number, when YX > XY
// zero, when YX = XY
// negative number, when YX < XY
return YX.CompareTo(XY);
}
}
static int ComposeTheMaxNumbers(int[] numbers)
{
SpecialComparer comparer = new SpecialComparer();
Array.Sort(numbers, comparer);
StringBuilder result = new StringBuilder();
foreach (int number in numbers)
{
result.Append(number.ToString());
}
return int.Parse(result.ToString());
}
However, in C# we may just write a lambda and LINQs expressions:
static int ComposeTheMaxNumbers(int[] numbers)
{
Array.Sort(numbers, new Comparison<int>((x, y) => (y.ToString() + x.ToString()).CompareTo(x.ToString() + y.ToString())));
return int.Parse(numbers.Select(_ => _.ToString()).Aggregate((x, y) => x + y));
}
P.S. The second approach is ineffective because all the time we create string's objects. But I think you've got the idea.
- ZuZu June 26, 2013static Node GetTheKthFromTailNode(Node head, int k)
{
Node runner = head;
while (--k != 0 && runner != null)
{
runner = runner.Next;
}
if (runner == null) return null;
Node result = head;
while (runner.Next != null)
{
runner = runner.Next;
result = result.Next;
}
return result;
}
void Sort(int[] array)
{
int below = -1;
int above = array.Length;
for (int i = 0; i < above; )
{
if (array[i] == 1)
{
// below
Swap(array, i, ++below);
i++;
}
else if (array[i] == 3)
{
// above
Swap(array, i, --above);
}
else
{
// middle
i++;
}
}
}
void Swap(int[] array, int i, int j)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
Actually we can solve the problem in another way:
1. Assume that in the current step of iteration you have three variables of string : previous, current, next
2. Check on each iteration :
2.1. if (previous == current) do noting
2.2. if (previous != current)
2.2.1. if (current == next) return previous
2.2.2. if (current != next) return current
Complexity : O(N * L) where L - max length of line
Auxiliary Memory : O(1)
Xor-solution.
Complexity : O(N * L) , where L - max length of line
Auxiliary Memory : O(L)
Here is an implementation of your idea on C#:
const int MAX_LINE_LENGTH = 100;
static string GetUniqueLine(string[] lines)
{
if (lines.Length < 3) return null; // or handle it in another way
char[] result = new char[MAX_LINE_LENGTH];
foreach (string line in lines)
{
XorString(result, line);
}
if ((lines.Length & 1) == 0)
{
if (lines[0] == lines[1])
{
XorString(result, lines[0]);
}
else
{
XorString(result, lines[2]);
}
}
return new string(result.TakeWhile(ch => ch != '\0').ToArray());
}
private static void XorString(char[] result, string line)
{
for (int i = 0; i < line.Length; i++)
{
result[i] ^= line[i];
}
}
You may use a LinkedList.
For example, you have two linked lists - A and B.
Split data into lists : read first 10000 elements to A while remaining numbers insert into list B.
Then you can easily insert numbers after 10000th with constant time.
After reading stuff you can merge A and B.
Complexity O(N) (every insertion costs O(1) )
public static string Parse(string s)
{
int index = 0;
return "(" + Parse(s, ref index).ToString() + ")";
}
private static StringBuilder Parse(string s, ref int index)
{
StringBuilder result = new StringBuilder();
while (index < s.Length && s[index] != ')')
{
if (s[index] == '(')
{
index++;
result.Append(Parse(s, ref index));
}
else result.Append(s[index]);
index++;
}
return result;
}
public static int RomanToInteger(string s)
{
int result = 0;
int d = 1;
int prev = -1;
for(int i = s.Length - 1; i >= 0; i--)
{
int curr = 0;
switch(s[i])
{
case 'I':
curr = 1;
break;
case 'V':
curr = 5;
break;
case 'X':
curr = 10;
break;
case 'L':
curr = 50;
break;
case 'C':
curr = 100;
break;
case 'D':
curr = 500;
break;
case 'M':
curr = 1000;
break;
default:
throw new Exception("Invalid roman numeral");
}
if (prev == -1 || curr > prev) d = 1;
else if (curr < prev) d= -1;
result += d * curr;
prev = curr;
}
return result;
}
public class Node
{
public char Value { get; set; }
public Node Next { get; set; }
}
public static Node Shift(Node head)
{
Func<char, bool> isVowel = c => c == 'a' || c == 'o' || c == 'e' || c == 'u' || c == 'i' || c == 'y';
Func<char, bool> isConsonant = c => c >= 'a' && c <= 'z' && !isVowel(c);
Node vowelHead = null;
Node vowelTail = null;
Node consonantHead = null;
Node consonantTail = null;
while (head != null)
{
if (isVowel(head.Value))
{
Add(ref vowelHead, ref vowelTail, head.Value);
}
else if (isConsonant(head.Value))
{
Add(ref consonantHead, ref consonantTail, head.Value);
}
else
{
// value is not in a range 'a'..'z'
// throw exception or handle this case in another way
}
head = head.Next;
}
if (vowelTail != null)
{
vowelTail.Next = consonantHead;
return vowelHead;
}
else
{
return consonantHead;
}
}
private static void Add(ref Node head, ref Node tail, char val)
{
Node n = new Node { Value = val };
if (tail != null) tail.Next = n;
if (head == null) head = n;
tail = n;
}
Use stack :
public static bool IsBalanced(string s)
{
Stack<char> s = new Stack<char>();
foreach(var ch in s)
{
if (ch == '(' || ch == '[' || ch == '{') s.Push(ch);
else
{
if (stack.Count == 0) return false;
int top = s.Pop();
if ((ch == ')' && top != '(') ||
(ch == ']' && top != '[') ||
(ch == '}' && top != '{')) return false;
}
}
return s.Count == 0;
}
The output should be the following matrix :
3 11 14
2 10 13
1 9 12
And here is simple code on C#:
public static void Rotate(int[,] a, int size, int key)
{
for (int first = 0; first < size / 2; first++)
{
int last = size - 1 - first;
for (int i = first; i < last; i++)
{
int offset = i - first;
int tmp = a[first, i];
a[first, i] = a[i, last];
a[i, last] = a[last, last - offset];
a[last, last - offset] = a[last - offset, first];
a[last - offset, first] = tmp;
}
}
for (int j = 0; j < size; j++)
{
if (IsPrime(j + 1))
{
for(int i = 0; i< size;i++)
{
a[i,j] += key;
}
}
}
}
private static bool IsPrime(int n)
{
if(n<2) return false;
for(int i = 2; i <= (int)Math.Sqrt(n); i++)
{
if(n%i==0) return false;
}
return true;
}
Just implement a min-heap with 1 million of size.
In any time in the heap you will have the first million of max numbers
private class Heap
{
private int[] array;
private int currentSize = 0;
public Heap(int size)
{
this.array = new int[size];
this.currentSize = 0;
}
public bool IsFull
{
get
{
return this.currentSize == array.Length;
}
}
private void Swap(int first, int second)
{
int tmp = array[first];
array[first] = array[second];
array[second] = tmp;
}
public bool Insert(int value)
{
if (!IsFull)
{
array[currentSize++] = value;
HeapifyUp(currentSize - 1);
return true;
}
return false;
}
public void HeapifyUp(int curr)
{
while (curr != 0)
{
int parent = curr % 2 == 0 ? (curr >> 1) - 1 : curr >> 1;
if (array[curr] < array[parent])
{
Swap(curr, parent);
curr = parent;
}
else
{
return;
}
}
}
public int GetRoot()
{
if (currentSize > 0)
{
return array[0];
}
throw new Exception("Heap is empty");
}
public void UpdateRoot(int value)
{
if (currentSize > 0)
{
array[0] = value;
HeapifyDown(0);
}
}
public void HeapifyDown(int curr)
{
while (true)
{
int left = (curr << 1) + 1;
int right = (curr << 1) + 2;
if (left >= currentSize)
{
break;
}
int optimal = left;
if (right < currentSize && array[right] < array[left])
{
optimal = right;
}
if (array[curr] > array[optimal])
{
Swap(curr, optimal);
curr = optimal;
}
else
{
break;
}
}
}
}
public void ProcessNumbers(IEnumerable<int> numbers)
{
Heap h = new Heap(5);
foreach (int number in numbers)
{
if (!h.IsFull)
{
h.Insert(number);
}
else
{
int min = h.GetRoot(); // it will be the minimum value of heap
if (number > min)
{
h.UpdateRoot(number);
}
}
}
}
BFS via C# :
class Point
{
public int X { get; set; }
public int Y { get; set; }
}
public int FindTheShortestExit(byte[,] matrix, int n, int x, int y)
{
if (!(x >= 0 && y >= 0 && x < n && y < n))
{
throw new Exception("Invalid input data");
}
int[] dx = { 1, 0, 0, -1 };
int[] dy = { 0, 1, -1, 0 };
int[,] a = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
a[i, j] = int.MaxValue;
}
}
a[x, y] = 0;
int result = int.MaxValue;
Queue<Point> q = new Queue<Point>();
q.Enqueue(new Point { X = x, Y = y });
while (q.Count != 0)
{
Point curr = q.Dequeue();
if ((curr.X == 0 || curr.Y == 0 || curr.X == n - 1 || curr.Y == n - 1) && a[curr.X, curr.Y] + 1 < result)
{
result = a[curr.X, curr.Y] + 1;
}
for (int i = 0; i < 4; i++)
{
if (
curr.X + dx[i] >= 0 && curr.X + dx[i] < n &&
curr.Y + dy[i] >= 0 && curr.Y + dy[i] < n &&
matrix[curr.X + dx[i], curr.Y + dy[i]] == 1 &&
a[curr.X + dx[i], curr.Y + dy[i]] > a[curr.X, curr.Y] + 1)
{
q.Enqueue(new Point { X = curr.X + dx[i], Y = curr.Y + dy[i] });
a[curr.X + dx[i], curr.Y + dy[i]] = a[curr.X, curr.Y] + 1;
}
}
}
if (result == int.MaxValue)
{
return -1; // can't find exit
}
return result;
}
public class Node
{
public int Key { get; set; }
public Node Next { get; set; }
}
public bool SwapKthFirstAndKthLastNode(Node head, int k)
{
k--;
Node kthFirstPrev = null;
Node kthFirst = head;
int i = 0;
while (i < k && kthFirst != null)
{
kthFirstPrev = kthFirst;
kthFirst = kthFirst.Next;
i++;
}
if (kthFirst == null)
{
return false;
}
Node kthLastPrev = null;
Node kthLast = head;
Node current = kthFirst;
while (current.Next != null)
{
kthLastPrev = kthLast;
kthLast = kthLast.Next;
current = current.Next;
}
Node oldKthFirst = kthFirst.Next;
if (kthFirstPrev != null)
{
kthFirstPrev.Next = kthLast;
}
kthFirst.Next = kthLast.Next;
if (kthLastPrev != null)
{
kthLastPrev.Next = kthFirst;
}
kthLast.Next = oldKthFirst;
return true;
}
}
DP here is redundant.
You can just calculate the result in this way:
- ZuZu October 28, 2013