Jessy.Pinkman
BAN USERWho told that the input list is allowed for changes, like "reverse second part"? Apparently it can be reversed back, but what if the collection is read-only? What if it is not thread-safe?
When we save place, we have to sacrifice performance and vice-versa. We can apply one optimization though: search chars in the right half from the middle instead of "left" or 0. C# version.
class SingleLinkedList
{
public SingleLinkedList(char item)
{
Item = item;
}
public SingleLinkedList(string data)
{
this.Item = data[0];
SingleLinkedList current = this;
for (int i = 1; i < data.Length; i++)
{
current.Next = new SingleLinkedList(data[i]);
current = current.Next;
}
}
public SingleLinkedList Next { get; private set; }
public char Item { get; private set; }
public override string ToString()
{
StringBuilder sb = new StringBuilder();
var current = this;
while (current != null)
{
sb.Append(current.Item);
current = current.Next;
}
return sb.ToString();
}
}
static SingleLinkedList GetItem(SingleLinkedList head, int index)
{
int i = 0;
while (head != null && i < index)
{
i++;
head = head.Next;
}
return head;
}
static int GetSize(SingleLinkedList list)
{
int count = 0;
while (list != null)
{
list = list.Next;
count++;
}
return count;
}
static bool isPalindrome(SingleLinkedList list)
{
SingleLinkedList head = list;
SingleLinkedList current = list;
int count = GetSize(list);
int count2 = count >> 1;
SingleLinkedList head2 = GetItem(head, count2 + count % 2);
for (int i = 0; i < count2; i++)
{
if (current.Item != GetItem(head2, count2 - i - 1).Item)
return false;
current = current.Next;
}
return true;
}
static void Main(string[] args)
{
SingleLinkedList word = new SingleLinkedList("polyPaAggAaPylop");
Console.WriteLine("IsPalindrome? " + word + ": " +isPalindrome(word));
Console.ReadKey();
}
How about this? It runs much faster (several times) than recursive algorithm.
static void run2(Dictionary<char, char[]> dict, string input, List<string> output)
{
int[] indexes = new int[input.Length];
int[] limits = new int[input.Length];
for (int i = 0; i < indexes.Length; i++)
{
indexes[i] = -1;
limits[i] = dict.ContainsKey(input[i]) ? dict[input[i]].Length-1 : -1;
}
bool stop = false;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indexes.Length; i++)
{
sb.Append(indexes[i] < 0 ? input[i] : dict[input[i]][indexes[i]]);
}
while (!stop)
{
output.Add(sb.ToString());
//Console.WriteLine(sb);
indexes[0]++;
for (int i = 0; i < indexes.Length; i++)
{
if (indexes[i] > limits[i])
{
indexes[i] = -1;
sb[i] = input[i];
if (i < indexes.Length - 1)
{
indexes[i + 1]++;
}
else
stop = true;
}
else
{
sb[i] = dict[input[i]][indexes[i]];
break;
}
}
}
}
Be careful, Anon, people can easily understand that fool is YOU.
(a+b)^2 = a^2 + 2ab + b^2.
1^2 = 1. Starting from the next line, b = 1 always => 2ab = (a+a)
2^2 = 1 + (1+1) + 1 = 4
3^2 = 4 + (2+2) + 1 = 9, etc. The complexity is sqrt(n), same as odds sum
Here is the full implementation, one based on Stack and another one on recursion approache.
class CharStream
{
int _pos = 0;
char[] _stream = new char[0];
public CharStream()
{
}
public CharStream(string stream)
{
SetStream(stream);
}
public void SetStream(string stream)
{
if (string.IsNullOrEmpty(stream))
throw new ArgumentNullException();
_stream = stream.ToCharArray();
_pos = 0;
}
public bool HasNext
{
get
{
return _pos < _stream.Length;
}
}
public char Next()
{
if (!HasNext)
throw new ArgumentException();
return _stream[_pos++];
}
public string Stream
{
get { return new string(_stream); }
set { SetStream(value); }
}
public void Reset()
{
_pos = 0;
}
}
static bool ParentesisCorrect(CharStream stream)
{
Stack<char> stack = new Stack<char>();
while (stream.HasNext)
{
char nextValue = stream.Next();
if (nextValue == '[' || nextValue == '(')
stack.Push(nextValue);
else
{
if (stack.Count == 0)
return false;
char stackValue = stack.Pop();
if (nextValue == '[' && stackValue != ']' ||
nextValue == '(' && stackValue != ')' ||
nextValue == ')' && stackValue != '(' ||
nextValue == ']' && stackValue != '[')
return false;
}
}
return stack.Count == 0 ? true : false;
}
static bool recCor(CharStream stream)
{
bool result = true;
while (stream.HasNext)
{
result &= RecursiveParentesisCorrect(stream.Next(), stream, 0);
}
return result;
}
static bool OpenBracket(char c)
{
return c == '[' || c == '(';
}
static bool CloseBracket(char c)
{
return c == ')' || c == ']';
}
static bool RecursiveParentesisCorrect(char prevChar, CharStream stream, int depth)
{
char streamValue = stream.HasNext ? stream.Next() : 'x';
if (OpenBracket(streamValue))
{
if (!RecursiveParentesisCorrect(streamValue, stream, ++depth))
return false;
else
{
return depth != 0 && stream.HasNext ?
RecursiveParentesisCorrect(prevChar, stream, --depth) : false;
}
}
else
{
return (OpenBracket(prevChar) && CloseBracket(streamValue));
}
}
and a test method
static void TestBrackets()
{
CharStream cs = new CharStream("([][()])[][()]");
Console.WriteLine("{0} is {1} correct", cs.Stream, ParentesisCorrect(cs) ? "" : "NOT");
cs.Reset();
Console.WriteLine("{0} is {1} correct", cs.Stream, recCor(cs) ? "" : "NOT");
Console.ReadKey();
}
void count(int[] a, int N)
{
int[] l = new int[N];
int[] r = new int[N];
l[0]=1;r[N-1]=1;
for (int i = 1; i < N; i++)
{
l[i] = l[i-1]*a[i-1];
r[N-i-1] = r[N-i]*a[N-i];
}
for(int i=0;i<N;i++)
Console.WriteLn(l[i]*r[i]);
Why can't we use following algorithm (haven't read comments intentionally)
1. Sort the array, complexity O(N*logN) in asc. order
2. Run through the array once (complexity is O(N)), ultimately it's gonna be O(N*logN)
void Split(int[] input, List<int> a1, List<a2>)
{
long sum1 = 0, sum2 = 0;
Sort(input);
for (int i = input.Length; i>=0; i--)
{
if (sum1 <= sum2)
{
sum1 += input[i];
a1.Add(input[i]);
}else
{
sum2 += input[i];
a2.Add(input[i]);
}
//If we're sure that sum/2 fits into long type - no problem, otherwise we need to manage it
//like if (sum1 >= Epsilon || sum2 >= Epsilon) {sum1-=Epsilon, sum2-=Epsilon}, where
//Epsilon is a bullet-proof limit that excepts overflows
}
if (sum1!= sum2)
Console.WriteLine("Average sums differ");
}
Why do u think there is a "wording problem"? If it was, they would not provide us "1" and "itself" as dividers. This means that Nth "ugly number" either Nth number in natural row (1, 2, 3...etc) OR 30*N.
- Jessy.Pinkman October 21, 2014I can't find other meanings in the task.