WarriorOfLight
BAN USERInstead of Array.IndexOf I should have used Hashtable to make the complexity O(n).
Otherwise this is sorting based on the first array and adding extra elements(whose order is unknown) to the end.
Any improvements?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace SortArrayUsingDiffRule
{
class Program
{
static char[] arr = new char[] {'B','A','C'};
static char[] Sort = new char[] {'D', 'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A' };
static int[] Count = new int[arr.Length];
static List<char> Extras = new List<char>();
static void Main(string[] args)
{
for (int i = 0; i < Sort.Length; i++)
{
int index = Array.IndexOf(arr, Sort[i]);
if (index != -1)
{
Count[index]++;
}
else
{
Extras.Add(Sort[i]);
}
}
int j = 0;
int k = 0;
while(j<Count.Length)
{
while (Count[j] > 0)
{
Sort[k]=arr[j];
Count[j]-- ;
k++;
}
j++;
}
for (int i = 0; i < Extras.Count; i++)
{
Sort[k++] = Extras[i];
}
}
}
}
DP Solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace pathsinmesh
{
class Program
{
static void Main(string[] args)
{
int a = 1, b = 1;
int rows=2,cols=2;
rows++;//rows and columns are in terms of number of boxes. Converting them to edges
cols++;
int[,] arr=new int[rows,cols];
for (int i = 0; i < rows; i++)
{
for (int j = 0; j <cols; j++)
{
if (i < a && cols - j-1 < b)
{
arr[i, j] = -1;
}
else if (i == 0 || j == 0)
{
arr[i, j] = 1;
}
else
{
if (arr[i - 1, j] == -1)
{
arr[i, j] = arr[i, j - 1];
}
else
{
arr[i, j] = arr[i - 1, j] + arr[i, j - 1];
}
}
}
}
}
}
}
same as Aste's solution but I am using backtracking to print all the maximum paths.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SnakeSequence
{
class Program
{
static void reconstruct(int maxlength,int curr,int x,int y,int[,] arr,Stack<Tuple<int,int>> s)
{
s.Push(new Tuple<int, int>(x , y));
if (s.Count == maxlength)
{
while (s.Count > 0)
{
Console.Write(s.Pop()+" ");
}
Console.WriteLine();
return;
}
if (x - 1 >= 0 && Math.Abs(arr[x - 1, y] - arr[x, y]) == 1)
{
reconstruct(maxlength, curr - 1, x - 1, y, arr, s);
}
else if (y - 1 >= 0 && Math.Abs(arr[x, y - 1] - arr[x, y]) == 1)
{
reconstruct(maxlength, curr - 1, x, y - 1, arr, s);
}
else
{
Tuple<int,int> top=s.Pop();
arr[top.Item1, top.Item2] = 999;
top = s.Peek();
reconstruct(maxlength, curr - 1, top.Item1, top.Item2, arr, s);
}
}
static void Main(string[] args)
{
int[,] arr = new int[,] { { 2, 3, 2, 3, 8 }, { -9, 4, 1, -1, 2 }, { 2, 3, 5, 1, 9 } };
int[,] dyn = new int[arr.GetLength(0), arr.GetLength(1)];
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
{
dyn[i, j] = 1;
}
}
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
{
int val1 = 1, val2 = 1;
if (i-1>=0 && Math.Abs(arr[i, j] - arr[i - 1, j]) == 1)
{
val1 = dyn[i - 1,j]+1;
}
if (j - 1 >= 0 && Math.Abs(arr[i, j] - arr[i, j - 1]) == 1)
{
val2 = dyn[i, j - 1]+1;
}
dyn[i, j] = Math.Max(val1, val2);
}
}
int max = 0;
int maxx=0,maxy=0;
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
{
if(dyn[i,j]>max)
{
max=dyn[i,j];
maxx=i;
maxy=j;
}
}
}
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
{
if (dyn[i, j] == max)
{
reconstruct(max, 0, i, j, arr, new Stack<Tuple<int, int>>());
}
}
}
}
}
}
No, it clearly says 'the number to the right or below' right?
- WarriorOfLight December 07, 2012using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PhoneKeyPad
{
/// <summary>
/// Mobile phone's keypad where "2" is mapped to ABC, "3" to DEF and so on.
/// Given any sequence of integers, find all the (matching) combinations in your phone book
/// </summary>
class PhoneKeyPad
{
static void Find(string input, int index, string[] list,char[] output)
{
if (index == input.Length)
{
Console.WriteLine(output);
return;
}
int p = input[index] - '0';
for (int i = 0; i < list[p].Length; i++)
{
output[index]= list[p][i];
Find(input,index+1,list,output);
output.Initialize() ;
}
}
//output cant be string because overwriting has to be done in several cases not just appending.
static void Main(string[] args)
{
string[] list = { "_",".","ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
string input = "21304";
char[] output=new char[5];
Find(input,0,list,output);
Console.ReadLine();
}
}
}
using System;
using System.Collections.Generic;
using System.Text;
namespace putparenthprod
{
class Program
{
static void Main(string[] args)
{
int[,] prodmatrix = new int[,] { { 1, 1, 3 }, { 1, 2, 2 }, { 3, 2, 1 } };
int[] sequence = new int[] { 1, 1, 2, 3, 3, 3, 2, 2, 2, 1, 1, 1 };
for (int i = 1; i < sequence.Length; i++)
{
sequence[i] = prodmatrix[sequence[i],sequence[i - 1]];
}
if (sequence.Last() == 1)
{
Console.WriteLine("Product is 1");
}
else
{
Console.WriteLine("Product is not 1");
}
}
}
}
For any value of special characters in between (not just 2):
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void PlaceBetween(int n,int index,string a,string punc,List<string> output)
{
if (index == n)
{
return;
}
for (int i = 0; i < punc.Length; i++)
{
for (int j = 0; j <= a.Length; j++)
{
if (!a.Contains(punc[i]))
{
string pre = a.Substring(0, j);
string post = a.Substring(j);
string newstring = pre + punc[i] + post;
output.Add(newstring);
PlaceBetween(n, index + 1, newstring, punc, output);
}
}
}
}
static void Main(string[] args)
{
int n=2;
string a = "test";
string punc = "0123456789%#&!";
List<string> output = new List<string>();
output.Add(a);
PlaceBetween(n,0,a,punc,output);
}
}
}
link
- WarriorOfLight December 08, 2012