模拟微面试之去空格

RemoveMultipleSpaces.cs

//请实现下面的函数，输入参数baseStr是一个（可以更改的）字符串，请将其中所有连续出现的多个空格都替换成一个空格，单一空格需保留。
//请直接使用baseStr的空间，如需开辟新的存储空间，不能超过o(N)（注意是小o，N是字符串的长度）。返回值是替换后的字符串的长度。
//样例代码为C#，但可以使用任何语言。如需使用任何库函数，必须同时给出库函数的实现。
class Program
{
    public static int RemoveMultipleSpaces(char[] baseStr)
    {
        // TODO
    }
}

//样例测试程序（请自行补充更多的测试案例）
[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));
    }
}

    public static int RemoveMultipleSpaces(char[] baseStr)
    {
        if (baseStr == null)
            return 0;
        int write = 0,read = 0;
        while(read < baseStr.Length) 
        {
            if (baseStr[read] == ' ' &&
                read + 1 < baseStr.Length &&
                baseStr[read + 1] == ' ')
                ++read;
            else 
                baseStr[write++] = baseStr[read++];
        }
        return write;
    }

偷懒，既然能用额外空间还是搞个额外空间比较省事，就是个状态翻转，对C#不熟悉

public static int RemoveMultipleSpaces(char[] baseStr)
{
  char[] temp = new char[baseStr.Length];
        int status = 0;
        int i=0;
        foreach (char c in baseStr)
        {
            if (c != ' ')
            {
                status = 0;
                temp[i++] = c;
            }
            else
            {
                if (status == 0)
                {
                    temp[i++] = c;
                    status = 1;
                }
            }
        }
        Array.Copy(temp, baseStr, baseStr.Length);
        return i;
        // TODO
    }
}

    public static int RemoveMultipleSpaces(char[] baseStr)
    {
        var result = new char[baseStr.Length];
        var count = 0;
        for (var i = 1; i < baseStr.Length; i++)
        {
            if (baseStr[i] == ' ' && baseStr[i - 1] == ' ') continue;
            result[count++] = baseStr[i-1];
        }
        result[count++] = baseStr[baseStr.Length - 1];
        Array.Copy(result, baseStr, baseStr.Length);
        return count;
    }

public static int RemoveMultipleSpaces(char[] baseStr)
{
    if (baseStr == null){
        return 0;
    }
    int p = 0, spaces = 0;
    for (var i = 0; i < baseStr.length; i++) {
       if((baseStr[i]!=" "||spaces<1)&&p!=i){
           baseStr[p++] = baseStr[i];
       }
       if(baseStr[i]==" "){
           spaces++;
       }else{
           spaces=0;
       }
    }
    return p;
}

public class Program {
    public static int RemoveMultipleSpaces(char[] baseStr){
        if(baseStr == null || baseStr.length == 0){
            return 0;
        }
        int i = 0, lastIndex = 0, length = baseStr.length;
        boolean removing = false;
        for(; i < length; i++){
            if(removing){
                if(baseStr[i] != ' '){
                    baseStr[lastIndex] = baseStr[i];
                    removing = false;
                    lastIndex++;
                }
            }else{
                if(baseStr[i] == ' '){
                    removing = true;
                }
                baseStr[lastIndex] = baseStr[i];
                lastIndex++;
            }
        }
        return lastIndex;
    }
}

C/C++ version

Assume str is null terminated, otherwise overrun

Passed test cases in https://gist.github.com/2232954

1. base on adjacent comparing, with double cursors

size_t remove_multiple_spaces(__inout char* str)
{
    if (str == 0)
        return -1;  // represent error

    //if (str[0] == 0)  // optimise for ""
    //    return 0;

    char* i = str;
    char* w = str;

    while (*i != 0) {
        if (*i == ' ' && *(i + 1) == ' ')
            ++i;
        else
            *++w = *++i;
    }
    return (w - str);
}

2. former variant, base on adjacent comparing, with double cursors

size_t remove_multiple_spaces(__inout char* str)
{
    if (str == 0)
        return -1;  // represent error

    char* i = str;
    char* w = str;

    while (*i != 0) {
        if (*++i == ' ' && *(i - 1) == ' ');
        else
            *++w = *i;
    }
    return (w - str);
}

3. base on state machine, with double cursors.
   less memory access, but more branches

size_t remove_multiple_spaces(__inout char* str)
{
    if (str == 0)
        return -1;  // represent error

    char* i = str;
    char* w = str;
    register bool space = false;    // space had appeared

    while (*i != 0) {
        if (*i == ' ') {
            if (space) {
                ++i;
                continue;
            }
            space = true;
        }
        else
            space = false;
        *w++ = *i++;
    }
    *w = 0;
    return (w - str);
}

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;

}

C++ 版 https://gist.github.com/2232954

C https://gist.github.com/2233688

<script src="https://gist.github.com/2233688.js?file=remove_multiple_space.c"></script>

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) 时间）

C https://gist.github.com/2232989

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=|