-
-
Save Ninputer/2227226 to your computer and use it in GitHub Desktop.
| //请实现下面的函数，输入参数baseStr是一个（可以更改的）字符串，请将其中所有连续出现的多个空格都替换成一个空格，单一空格需保留。 | |
| //请直接使用baseStr的空间，如需开辟新的存储空间，不能超过o(N)（注意是小o，N是字符串的长度）。返回值是替换后的字符串的长度。 | |
| //样例代码为C#，但可以使用任何语言。如需使用任何库函数，必须同时给出库函数的实现。 | |
| class Program | |
| { | |
| public static int RemoveMultipleSpaces(char[] baseStr) | |
| { | |
| if (baseStr == null) | |
| { | |
| throw new ArgumentNullException("baseStr"); | |
| } | |
| int writeCursor = 0; | |
| bool isLastCharSpace = false; | |
| for (int i = 0; i < baseStr.Length; i++) | |
| { | |
| char current = baseStr[i]; | |
| if (current == ' ') | |
| { | |
| if (!isLastCharSpace) | |
| { | |
| isLastCharSpace = true; | |
| baseStr[writeCursor++] = current; | |
| } | |
| } | |
| else | |
| { | |
| isLastCharSpace = false; | |
| baseStr[writeCursor++] = current; | |
| } | |
| } | |
| return writeCursor; | |
| } | |
| } | |
| //样例测试程序（请自行补充更多的测试案例） | |
| [TestFixture] | |
| public class ScannersTest | |
| { | |
| [Test] | |
| public void RemoveOneInnterSpaceBlockTest() | |
| { | |
| char[] input = "abc def".ToCharArray(); | |
| int resultLength = Program.RemoveMultipleSpaces(input); | |
| Assert.AreEqual(7, resultLength); | |
| Assert.AreEqual("abc def", new string(input, 0, resultLength)); | |
| } | |
| [Test] | |
| public void RemoveTwoInnterSpaceBlocksTest() | |
| { | |
| char[] input = "abc def ghi".ToCharArray(); | |
| int resultLength = Program.RemoveMultipleSpaces(input); | |
| Assert.AreEqual(11, resultLength); | |
| Assert.AreEqual("abc def ghi", new string(input, 0, resultLength)); | |
| } | |
| [Test] | |
| public void KeepSingleSpaceTest() | |
| { | |
| char[] input = " a b d e ".ToCharArray(); | |
| int resultLength = Program.RemoveMultipleSpaces(input); | |
| Assert.AreEqual(9, resultLength); | |
| Assert.AreEqual(" a b d e ", new string(input, 0, resultLength)); | |
| } | |
| [Test] | |
| public void AllSpacesTest() | |
| { | |
| char[] input = " ".ToCharArray(); | |
| int resultLength = Program.RemoveMultipleSpaces(input); | |
| Assert.AreEqual(1, resultLength); | |
| Assert.AreEqual(" ", new string(input, 0, resultLength)); | |
| } | |
| } |
enum State
{
kStateStart,
kStatePreviousIsSpace,
kStatePreviousIsNotSpace,
};
char* remove_redundant_spaces(char* str)
{
enum State state= kStateStart;
char* old_str= str;
char* new_str= str;
while(*old_str)
{
int is_space= (*old_str== '\x20');
switch(state)
{
case kStateStart:
{
if(is_space)
{
state= kStatePreviousIsSpace;
}
else
{
state= kStatePreviousIsNotSpace;
}
new_str++;
}
break;
case kStatePreviousIsSpace:
{
if(!is_space)
{
*new_str= *old_str;
new_str++;
state= kStatePreviousIsNotSpace;
}
else
{// do nothing.
}
}
break;
case kStatePreviousIsNotSpace:
{
*new_str= *old_str;
new_str++;
if(is_space)
{
state= kStatePreviousIsSpace;
}
else
{
//state= kStatePreviousIsNotSpace;
}
}
break;
default:
{
//must not happen.
assert(0);
}
}
old_str++;
}
*new_str= '\0';
return str;
}
//我这样的实现是被灭了呢还是被灭了呢？
define SWAP(a, b) \
({\
(a) ^= (b);\
(b) ^= (a);\
(a) ^= (b);\
})
static char *del_space(char *p_str)
{
int i = 0, j = 0;
for (j = 0, i = j; '\0' != p_str[j]; ++j) {
while ('\x20' != p_str[i]) {
++i;
}
j = (i > j) ? i : j;
assert('\x20' == p_str[i]);
if ('\x20' != p_str[j]) {
(void)SWAP(p_str[i], p_str[j]);
++i;
}
}
p_str[i] = '\0';
return p_str;
}
char* remove_redundant_spaces(char* str)
{
if(str[0]== '\0')
return str;
char* src= str+1;
char* dst= str+1;
bool prev_is_space= (str[0]== '\x20');
while(*src)
{
if(*src== '\x20') //current is space
{
if(!prev_is_space) //prev char is not space
{
*dst++= *src;
prev_is_space= true;
}
}
else //current is not space.
{
*dst++ = *src;
prev_is_space= false;
}
src++;
}
*dst= '\0';
return str;
}
int main(int argc, char** argv)
{
char buffer[256];
strcpy(buffer, " hello world ");
printf( "%s____len=%d\n", buffer, (int)strlen(buffer) );
remove_redundant_spaces(buffer);
printf( "%s____len=%d\n",buffer, (int)strlen(buffer) );
strcpy(buffer, "where there is a will, there is a way .");
printf( "%s____len=%d\n", buffer, (int)strlen(buffer) );
remove_redundant_spaces(buffer);
printf( "%s____len=%d\n",buffer, (int)strlen(buffer) );
strcpy(buffer, "1 2 3 4 5 6 8 9");
printf( "%s____len=%d\n", buffer, (int)strlen(buffer) );
remove_redundant_spaces(buffer);
printf( "%s____len=%d\n",buffer, (int)strlen(buffer) );
return 0;
}
char* remove_redundant_spaces(char* str)
{
if(str[0]== '\0')
return str;
char* src= str+1;
char* dst= str+1;
while(*src)
{
if(*src== '\x20') //current is space
{
if(! (*(src-1)== '\x20' )) //prev char is not space
*dst++= *src;
}
else //current is not space.
{
*dst++ = *src;
}
src++;
}
*dst= '\0';
return str;
}
char* remove_redundant_spaces(char* str)
{
if(str[0]== '\0')
return str;
char* src= str+1;
char* dst= str+1;
while(*src)
{
if( (*src!= '\x20') || ( (*src== '\x20') && !(*(src-1)== '\x20') ) )
*dst++= *src;
src++;
}
*dst= '\0';
return str;
}
public static int RemoveMultipleSpaces(char[] baseStr)
{
int length = 0;
bool skipSpace = false;
int lastIndex = 0;
for (int i = 0; i < baseStr.Length; i++)
{
if (skipSpace && baseStr[i] == ' ')
continue;
skipSpace = baseStr[i] == ' ';
baseStr[lastIndex++] = baseStr[i];
length++;
}
return length;
}
public static int RemoveMultipleSpaces(char[] baseStr)
{
var preChar = '\0';
var length = 0;
var space = ' ';
foreach (var c in baseStr)
{
if (c == space && preChar == space)
{
continue;
}
preChar = c;
baseStr[length] = c;
length++;
}
return length;
}
这样虽然能跑通测试，但baseStr的长度没变。不知道怎么解决，如果是ref就好了- -
public static int RemoveMultipleSpaces(char[] baseStr)
{
// TODO
int length = 0;
char tmp = new char();
for (int i = 0; i < baseStr.Length; i++)
{
if (baseStr[i] == ' ')
{
if (tmp != baseStr[i])
{
length++;
}
}
else
{
length++;
}
tmp = baseStr[i];
}
return length;
}
这样对吧~ 测试了应该是说的这个问题吧，有的把简单的搞复杂了！
http://gist.github.com/2236963
看谁的短！（在 C++ 上用原位修改 + DFA 可以做到 Θ(1) 额外空间，Θ(n) 时间）
Time O(n)
Space O(1)
public static char[] RemoveMultipleSpaces(char[] baseStr)
{
if (baseStr == null)
{
throw new ArgumentNullException("baseStr");
}
if (baseStr.Length == 1)
{
return baseStr;
}
int currentIndex = 0;
int nextIndex = 0;
bool handing = false;
while (nextIndex < baseStr.Length - 1)
{
if (baseStr[nextIndex] == ' ')
{
if (handing)
{
nextIndex++;
continue;
}
else
{
nextIndex++;
baseStr[currentIndex++] = ' ';
handing = true;
}
}
else
{
handing = false;
baseStr[currentIndex++] = baseStr[nextIndex++];
}
}
unsafe
{
fixed (char* c = baseStr)
{
int* i = (int*)c;
*(i - 1) = currentIndex;
}
}
return baseStr;
}
//Test Code
static void Main(string[] args)
{
char[] input = "abc def".ToCharArray();
var output = RemoveMultipleSpaces(input);
input = "abc def ghi".ToCharArray();
output = RemoveMultipleSpaces(input);
input = " a b d e ".ToCharArray();
output = RemoveMultipleSpaces(input);
input = " ".ToCharArray();
output = RemoveMultipleSpaces(input);
input = " ".ToCharArray();
output = RemoveMultipleSpaces(input);
input = "a".ToCharArray();
output = RemoveMultipleSpaces(input);
}
新手特来取经的（俺写的跟大家没法比啊，忒长了），C语言 https://gist.github.com/2238742
$str ='a bc d e f g';
RemoveSpace($str);
function RemoveSpace($str){
/* 获取字符串长度/转为循环次数 /
$l=strlen($str);
for($i=0;$i<$l;$i++){
/ 判断如果当前字符和下一个字符为空格，则当前字符为NUll /
if($str[$i] == ' ' and $str[$i+1] == ' '){
$str[$i] = '';
/ 若不满足条件则认为该字符不是空格，输出该字符串 */
}else{
echo $str[$i];
}
}
}
怎么我的回复没有缩进呢？
public static int RemoteMultipleSpaces(char[] baseStr)
{
if (baseStr == null || baseStr.Length == 0) return 0;
bool previousIsSpace = false;
const char space = ' ';
int originalLength = baseStr.Length;
// how many times have been moved
int movedTimes = 0;
for (int i = 0; i < originalLength - movedTimes; ++i)
{
if (baseStr[i] == space)
{
if (previousIsSpace)
{
// move the following chars to its previous position
for (int j = i; j < originalLength - 1 - movedTimes; j++)
{
baseStr[j] = baseStr[j + 1];
}
// moved once
++movedTimes;
// need to recalculate the index
--i;
}
else
previousIsSpace = true;
}
else
previousIsSpace = false;
}
Array.Copy(baseStr, baseStr, originalLength - movedTimes);
return originalLength - movedTimes;
}
static int RemoveMultipleSpaces(char[] baseStr)
{
int cnt = 0;
bool flag = false;
for (var i = 0; i < baseStr.Length; i++)
{
if (baseStr[i] == ' ')
{
if (flag)
{
cnt++;
}
else
{
flag = true;
if (cnt > 0)
{
baseStr[i - cnt] = baseStr[i];
}
}
}
else
{
if (cnt > 0)
{
baseStr[i - cnt] = baseStr[i];
}
if (flag)
{
flag = false;
}
}
}
return baseStr.Length - cnt;
}
不知道脑袋这个题目的用意。
传递的传输一个对象的引用，而很多写的版本是传的指针，有的甚至连测试代码都改了，方法的定义也改了。
数组对象本身已经在堆上了，如何更改其长度？如果不能修改baseStr的长度，这种替换也没有意义啊，而且测试里也没有测试 替换后的长度是否和返回的长度一致？
因为baseStr是参数啊，所以就等同指针认为了吧，怎么都不能改啊，再说返回的长度不就可以从新截取了吗？当然如果在返回前将baseStr[p]='\0'的话有些情况还是有用的。可惜不会C#，所以不知道它应该怎么处理字符串和字符数组的。。。
可以直接返回一个char[]或 这参数和返回都是string 或者用ref
在c#里 引用类型是地址这和指针不同，方法调用会拷贝对象的引用，这样如果重新给引用地址赋值是没用的。如果是ref 就是指针的效果
public static int RemoveMultipleSpaces(char[] baseStr)
{
int l = 0;
int spaceCount = 0;
int totalSpaceCount = 0;
for (int i = 0; i < baseStr.Length; i++)
{
if (baseStr[i] == ' ')
{
spaceCount++;
}
else
{
l++;
if (spaceCount > 0)
{
l++;
totalSpaceCount += spaceCount - 1;
spaceCount = 0;
}
if (totalSpaceCount > 0)
{
baseStr[i - totalSpaceCount] = baseStr[i];
baseStr[i] = ' ';
}
}
}
if (spaceCount > 0)
{
l++;
}
return l;
}
//请实现下面的函数，输入参数baseStr是一个（可以更改的）字符串，请将其中所有连续出现的多个空格都替换成一个空格，单一空格需保留。
//请直接使用baseStr的空间，如需开辟新的存储空间，不能超过o(N)（注意是小o，N是字符串的长度）。返回值是替换后的字符串的长度。
//样例代码为C#，但可以使用任何语言。如需使用任何库函数，必须同时给出库函数的实现。
class Program
{
public static int RemoveMultipleSpaces(char[] baseStr)
{
// TODO
bool lastisspace=false;
int lastnospace=0;
if(basestr==null ||basestr.length==0){
return 0;
}
int i=0;
for(i=0;i<basestr.length;i++){
if(lastisspace && basestr[i]==' '){
int t=i;
//不使用额外空间，就多花掉时间吧
while(t<basestr.length){
if(basestr[t++]!=' '){
basestr[i]=basestr[t];
basestr[t]=' ';
break;
}
}
if(t+1=basestr.length){
break;
}
lastisspace=false;
}
else if(basestr[i]==' '){
lastisspace=true;
}
else{
lastisspace=false;
}
}
//字符数组的多余空格已经被移到了末尾，从数组index 0开始截取 i个字符即为处理后的字符串数组。
return i;
}
}
// 纯手写，不保证通过，嘿嘿，我是想不到更好的办法，不多申请空间来处理这个了。另外申请个空间处理效率会高一些吧。
include "stdio.h"
include "stdbool.h"
int RemoveMultipleSpaces(char* baseStr)
{
char* s=baseStr;
char* d=baseStr;
if(baseStr==NULL)
return -1;
if(*baseStr=='\0')
return 0;
do{
if(*d==' ')
{
if(s==d || *s==' ')
{
s++;
}
else
{
d++;
*d=*s;
s++;
}
}
else
{
if(d < s)
{
d++;
*d=*s;
s++;
}
else
{
s++;
d++;
}
}
}while((*d)!='\0');
return d-baseStr;
}
int main(int argc,char\* argv[])
{
int i=0;
int len=0;
char test[7][30]={
{"abc def"},
{"abc def"},
{ "abc def ghi"},
{ " a b d e "},
{ " a b d e "},
{ " "},
{ ""},
};
```
for(i=0;i<7;i++)
{
printf("test[%d]:%s|\t",i,test[i]);
len=RemoveMultipleSpaces(test[i]);
printf("after:len=%d,test=%s|\n",len,test[i]);
}
return 0;
```
}
===结果===
test[0]:abc def| after:len=7,test=abc def|
test[1]:abc def| after:len=7,test=abc def|
test[2]:abc def ghi| after:len=11,test=abc def ghi|
test[3]: a b d e | after:len=9,test= a b d e |
test[4]: a b d e | after:len=9,test= a b d e |
test[5]: | after:len=1,test= |
test[6]:| after:len=0,test=|
C/C++ version
Assume str is null terminated, otherwise overrun
Passed test cases in https://gist.github.com/2232954
less memory access, but more branches