算法打卡
01.03 URL化。
- 編寫一種方法，將字符串中的空格全部替換為%20最蕾。假定該字符串尾部有足夠的空間存放新增字符，并且知道字符串的“真實”長度老厌。（注：用Java實現(xiàn)的話瘟则，請使用字符數(shù)組實現(xiàn)，以便直接在數(shù)組上操作枝秤。）
- 方法一醋拧， 直接用一個新數(shù)據(jù)組 將原來字符串翻譯后返回。 通用性更好淀弹， 支持多個字符替換 趁仙。 空間復(fù)雜度 O(n) 時間復(fù)雜度 O(n)
public string ReplaceSpaces(string S, int length)
{
var charLength = S.Count(x => x != ' ');
var chars = new char[charLength + (length - charLength) * 3];
var k = 0;
for (int i = 0; i < length; i++)
{
if (S[i] == ' ')
{
chars[k++] = '%';
chars[k++] = '2';
chars[k++] = '0';
}
else
{
chars[k++] = S[i];
}
}
return new string(chars);
}
- 方法二 ，雙指針分別 指向當(dāng)前字符串索引垦页，跟替換后的索引， 倒序處理干奢。 但是前提條件字符串的末尾空格足夠多才行（實際使用場景較腥浮） 空間復(fù)雜度 O(1) 時間復(fù)雜度 O(n)
public string ReplaceSpaces(string S, int length)
{
var chars = S.ToCharArray();
var charLength = S.Count(x => x != ' ');
var realLength = charLength + (length - charLength) * 3;
var k = realLength - 1;
for (int i = length - 1; i != k; i--)
{
if (chars[i] == ' ')
{
chars[k--] = '0';
chars[k--] = '2';
chars[k--] = '%';
}
else
{
chars[k--] = chars[i];
}
}
new string(chars, 0, realLength - 1);
}
1528. 重新排列字符串
- 給你一個字符串 s 和一個 長度相同 的整數(shù)數(shù)組 indices 。請你重新排列字符串 s 忿峻，其中第 i 個字符需要移動到 indices[i] 指示的位置薄啥。返回重新排列后的字符串。
- 簡單方案
public string RestoreString(string s, int[] indices)
{
var chars = s.ToCharArray();
for(var i = 0; i < indices.Length; i++)
{
chars[indices[i]] = s[i];
}
return new string(chars);
}
- 原址交換
public string RestoreString(string s, int[] indices)
{
var chars = s.ToCharArray();
for(var i = 0; i < indices.Length; i++)
{
while(indices[i] != i)
{
Swap(chars, i,indices[i]);
Swap(indices, i,indices[i]);
}
}
return new string(chars);
}
private void Swap<T>(T[] arr逛尚， int a, int b)where T :struct
{
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
