不能掩饰的快乐 (转载)# pets - 心有所宠
m*e
1 楼
今天重做leetcode：String Reorder Distance Apart。发现1337c0d3r给出的答案（http://discuss.leetcode.com/questions/31/string-reorder-distance-apart）有较大改进的地方："used" array and the while loop inside the for loop are not needed. I wrote one with C#:
// String Reorder Distance Apart
public string ReorderDistanceApart(string str, int distance)
{
int[] freq = new int[256];
int[] used = new int[256];
bool[] except = new bool[256];
int n = str.Length;
int i,j;
char[] results = new char[n];
for (i = 0; i < n; ++i)
{
freq[str[i]]++;
}
for (i = 0; i < n; ++i)
{
int indexCur = GetLargestFreq(freq, used);
results[i] = (char)indexCur;
used[indexCur] = distance;
freq[indexCur]--;
for (j = 0; j < 256; ++j)
{
if (used[j] > 0)
used[j]--;
}
}
return new string(results);
}
private int GetLargestFreq(int[] freq, int[] used)
{
int maxFreq = INT_MIN;
int maxInd = -1;
for (int i=0; i<256; i++)
{
if (freq[i] > maxFreq && used[i] <= 0)
{
maxFreq = freq[i];
maxInd = i;
}
}
return maxInd;
}
// String Reorder Distance Apart
public string ReorderDistanceApart(string str, int distance)
{
int[] freq = new int[256];
int[] used = new int[256];
bool[] except = new bool[256];
int n = str.Length;
int i,j;
char[] results = new char[n];
for (i = 0; i < n; ++i)
{
freq[str[i]]++;
}
for (i = 0; i < n; ++i)
{
int indexCur = GetLargestFreq(freq, used);
results[i] = (char)indexCur;
used[indexCur] = distance;
freq[indexCur]--;
for (j = 0; j < 256; ++j)
{
if (used[j] > 0)
used[j]--;
}
}
return new string(results);
}
private int GetLargestFreq(int[] freq, int[] used)
{
int maxFreq = INT_MIN;
int maxInd = -1;
for (int i=0; i<256; i++)
{
if (freq[i] > maxFreq && used[i] <= 0)
{
maxFreq = freq[i];
maxInd = i;
}
}
return maxInd;
}
