算法打卡
01.03 URL化。
- 编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
- 方法一， 直接用一个新数据组 将原来字符串翻译后返回。 通用性更好， 支持多个字符替换 。 空间复杂度 O(n) 时间复杂度 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);
}
- 方法二 ，双指针分别 指向当前字符串索引，跟替换后的索引， 倒序处理。 但是前提条件字符串的末尾空格足够多才行（实际使用场景较小） 空间复杂度 O(1) 时间复杂度 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 和一个 长度相同 的整数数组 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;
}
