Onat
BAN USERI've noticed that the question is demanding that the original order among groups need to stay the same whereas my above code sorts them too. So the updated version of IsSpecialSmaller() method will avoid that.
private static bool IsSpecialSmaller(char a, char b)
{
if (a.IsSmall())
{
return b.IsSpace() || b.IsUpper();
}
else if (a.IsSpace())
{
return b.IsUpper();
}
else
{
return false;
}
}
Used selection sort with a custom comparison logic which resides in the IsSpecialSmaller method.
These are my extension methods for the char.
public static class CharExtensions
{
public static bool IsSmall(this char c)
{
return c >= 97 && c <= 122;
}
public static bool IsSpace(this char c)
{
return c == 32;
}
public static bool IsUpper(this char c)
{
return c >= 65 && c <= 90;
}
}
And then the solution that uses these extension methods:
public static void Sort(char[] str)
{
for (int i = 0; i < str.Length; i++)
{
var minIndex = i;
for (int j = i + 1; j < str.Length; j++)
{
if (IsSpecialSmaller(str[j], str[minIndex]))
{
minIndex = j;
}
}
SwapChars(str, i, minIndex);
}
}
private static bool IsSpecialSmaller(char a, char b)
{
if (a.IsSmall())
{
return b.IsSpace() || b.IsUpper() || a < b;
}
else if (a.IsSpace())
{
return b.IsUpper();
}
else
{
return b.IsUpper() ? a < b : false;
}
}
private static void SwapChars(char[] str, int i, int j)
{
var tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
public static int[] GetSequence(int n)
{
var result = new int[n * 2];
var usage = new byte[n + 1];
for (int i = 1; i <= n; i++)
{
result[0] = i;
usage[i]++;
if (SetSequence(result, 1, n, usage))
{
return result;
}
else
{
usage[i]--;
}
}
return null;
}
private static bool SetSequence(int[] result, int startIndex, int n, byte[] usage)
{
if (startIndex == n * 2)
{
return true;
}
for (int i = 1; i <= n; i++)
{
if (usage[i] == 0)
{
result[startIndex] = i;
usage[i]++;
if (!SetSequence(result, startIndex + 1, n, usage))
{
usage[i]--;
}
else
{
return true;
}
}
else if (usage[i] == 1 &&
startIndex - i - 1 >= 0 &&
result[startIndex - i - 1] == i)
{
result[startIndex] = i;
usage[i]++;
if (!SetSequence(result, startIndex + 1, n, usage))
{
usage[i]--;
}
else
{
return true;
}
}
}
return false;
}
Here's a recursive approach with C#. Please feel free to highlight any areas that can be improved.
public List<string> GetPossibleIps(string ip)
{
return GetPossibleIps(ip, 4);
}
private List<string> GetPossibleIps(string ip, int sectionLeft)
{
List<string> allIps = new List<string>();
if (sectionLeft == 1)
{
if (IsValid(ip))
{
allIps.Add(ip);
return allIps;
}
else
{
return null;
}
}
for (int i = 1; i <= 3; i++)
{
if (ip.Length >= i)
{
string firstIDigit = ip.Substring(0, i);
if (IsValid(firstIDigit))
{
List<string> ipParts = GetPossibleIps(ip.Substring(i), sectionLeft - 1);
if (ipParts != null && ipParts.Count > 0)
{
PrependPartToParts(firstIDigit, ipParts);
allIps.AddRange(ipParts);
}
}
}
}
return allIps;
}
private void PrependPartToParts(string ipPart, List<string> ipParts)
{
for (int i = 0; i < ipParts.Count; i++)
{
ipParts[i] = ipPart + "." + ipParts[i];
}
}
private bool IsValid(string ipSection)
{
if (string.IsNullOrEmpty(ipSection) ||
(ipSection.Length > 1 && ipSection.Substring(0, 1).Equals("0")))
{
return false;
}
int number;
bool parsed = int.TryParse(ipSection, out number);
return parsed && (number >= 0 && number <= 255);
}
This my C# implementation for this approach, please let me know if you spot any bug with it, cheers:
public void Maximize(int[] arr, int swapsAllowed)
{
if (arr == null)
{
return;
}
int start = 0;
int swapsLeft = swapsAllowed;
int lastIndex = swapsLeft + start < arr.Length - 1 ? swapsLeft + start : arr.Length - 1;
int maxIndex = start;
while (swapsLeft > 0 &&
start < arr.Length)
{
for (int i = start + 1; i <= lastIndex; i++)
{
if (arr[i] > arr[maxIndex])
{
maxIndex = i;
}
}
if (maxIndex > start)
{
for (int i = maxIndex; i >= start + 1; i--)
{
Swap(ref arr[i], ref arr[i - 1]);
}
}
swapsLeft = swapsLeft - (maxIndex - start);
start++;
lastIndex = swapsLeft + start < arr.Length - 1 ? swapsLeft + start : arr.Length - 1;
maxIndex = start;
}
}
private void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
Can you write the code for it?
- Onat August 18, 2015