肖老师总算是发了个派上用场的文件咯，虽然还在忙适合自己，属于自己的快速框架的搭建工作，但始终不忘对面试题的一些巩固与练习，特别是数据结构、算法的一些题，即使对于自己所在的求职岗位可能对这方面考察相对较弱，但自己还是觉得，对于一个合格的开发工程师，应该对这些底层结构有一定的理解掌握，当然这一点更是印证了自己的“强迫症”（执着）的特点，对背后原理的“渴望”，正所谓那个什么，对~~就是知己知彼，方得百战百胜！

由于平时一直处于开发的状态中，大多数功能的实现，都是得益于系统自带的类库，或者第三方库，要么也是别人直接写好的帮助类，大大的提高了开发效率，却使自己逻辑算法能力慢慢淡化，正好借此机会，好好看看这本剑指的书，巩固自己的逻辑能力同时，理解底层数据结构！

    书中有提到这样一个算法题：【替换空格】

问题描述：请实现一个函数，把字符串中每个空格替换成“%20”。例如输入“We are happy”，则输出“We%20are%20happy”.

这个问题是解决web开发中url地址特殊字符传递到服务器无法识别，当然此问题考察的重点并不是去解决服务器无法识别特殊字符的问题，考查点在于，时间效率上，也就是时间复杂度！

书中是针对c/c++来分析这个问题的，从一个先决条件，两个方向来分析解决：

先决条件——从原有字符串中替换（看到这，我就纳闷了，鉴于自己对学c#语言的理解，string字符串具有不可变性（只读），也就是如果要替换，注定是对于一个新字符串来说的，先暂且往下看）

方向一——从头到尾依次扫描字符串，每发现空格字符替换之（对于我来说，这是正向思维方式解决问题）

这时候，假设字符串的长度为n，对于每个空格字符，需要移动其后面O（n）个字符，那对于O（n）个空格字符的字符串而言时间复杂度为O（n^2）。

方向二——先统计字符串中空格总数，由此计算出替换后的字符串长度，然后从字符串后面依次向替换后的长度移动。

这时候，会发现，不管有多少空格，都保证了每个字符只移动一次，所以时间复杂度为O（n）。

看完之后确实蛮有道理的，但是也存在一些疑惑，方法二虽然时间效率要高，但在某种特殊情况，我觉得方法一应该还快一些，比如空格比较少，且比较靠后，这样，对于方法一需要移动字符相对会缩小，方法二这时依然还是要对每个字符进行移动操作！

想到这里，还是用c#来试试吧，由于c#字符串具有不可变性，那就不能向上面c/c++那样分析在原有基础上做文章了，通过Stopwatch测量自己实现的替换，与.net自带的Replace替换耗时是相等的，没有看.net源代码，也不清楚Replace具体是怎么实现替换，当然也有字符串本身的原有在里面（request所占的空间太小，不足以与Replace区分个上下）：

 class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            string request = "  my pjax codescript";
            sw.Start();
            string temp = repStr(request);
            sw.Stop();
            sw.Restart();
            string temp1 = request.Replace(" ", "%20");
            sw.Stop();
            Console.WriteLine("自己耗时{0}--{1}\r\n系统耗时{2}--{3}",sw.Elapsed,repStr(request),sw.Elapsed,temp1);
            Console.WriteLine(temp==temp1);
        }
        static string repStr(string s)
        {
            int oldLength = s.Length;
            int newLength =oldLength+ (s.Split(' ').Length - 1)*2;
            char[] c = new char[newLength];
            int indexOfchar=0;
            for (int i = 0; i < oldLength; i++)
            {
                if (s[i] == ' ')
                {
                    c[indexOfchar] = '%';
                    c[++indexOfchar] = '2';
                    c[++indexOfchar] = '0';
                }
                else
                {
                    c[indexOfchar] = s[i];
                }
                indexOfchar++;
            }
            return string.Concat(c);
            
        }
    }
}

耗时对比：

很好，这本书不错，后面继续研究学习啦，正是弥补自己薄弱的一面！

发表吐槽