本文首发于微信公众号「玉刚说」

原文链接：面试必备：数组和字符串

数据结构和算法有多重要？

我想有追求的程序员都不会放过它的。 打个比方，在金庸的武侠世界里，数据结构和算法它就像一门上乘的内功心法，一旦掌握了它，各种武功信手拈来，毫无压力（张无忌就是一个典型的例子），对于程序员来说，它能决定你在技术这条道路上能走多远。

本文主要涉及数组、字符串这几个数据结构，然后通过解答和分析几道常见的面试题，从中分享一些我的学习心得和解题套路，希望对你有帮助。

题目1：翻转句子

题目： 给定一个英文句子，每个单词之间都是由一个或多个空格隔开，请翻转句子中的单词顺序（包括空格的顺序），但单词内字符的顺序保持不变。例如输入"www google com "，则应输出" com google www"。

如果你经常关注算法相关文章，这道题应该会比较熟悉，各种博客和书籍上都有出现，不熟悉也没关系，现在我们就一起来尝试解答下。这里要注意题意和网上流传的题目有个不同点：网上基本都是单词间有且只有一个空格，而此题需要考虑一个或多个空格的情况。

解题思路

试想一下，如果将整个字符串翻转，结果是句子是反转了，但单词内的字符顺序也翻转了。如果要保证单词内顺序不变，只需要再将每个单词翻转一下就满足要求了。

由于题中“www google com ”字符串较长，我就以" hello world"为例分析下这个过程，请看下图。

图 1.0 翻转句子，但保证句子中单词内部字符顺序。

注：（1）字符串" hello world"初始状态，注意首字符是空格。 （2）将" hello world"整个句子翻转后的样子。可以看出不仅翻转了句子中单词的顺序(包括空格)，连单词内的字符顺序也翻转了。(3) 定义两个指针p1、p2都指向句子的首字符。 （4）首字符d，不是空格，此时p1指针不动，p2指针向右移动1位，指向字符 l。（移动p2指针目的：检查单词的结束位置。） （5）由于第二个字符为 l ，也不是空格，p2继续向右移动1位。（6）多次移动后，p2指针在第一个空格处停下来，此时就能得知p2-1为该单词的结束位置。（7）反转两个指针（p1、p2-1）中间的字符串。（8）交换后，重置两个指针位置p1=p2++。以此类推，继续寻找下一个单词并翻转，直到指针移动到句子末尾就结束循环。

此思路的关键是：1. 实现一个函数/方法，翻转字符串中的一段。 2. 判断并获取句子中的单词，注意空格。

测试用例

• 功能测试：多个单词、1个单词、单词间只有一个空格、单词间有多个空格。
• 特殊输入测试：空字符、字符串中只有空格、null对象（指针）。

编码实现

• Java代码

/**
 * @param chars 原字符串
 * @param start 大于等于0
 * @param end   小于 length
 * @return
 */
private char[] v1_0_reverse(char[] chars, int start, int end) {

    // str 判断null， 索引有效值判断
    if (chars == null || start < 0 || end >= chars.length || start >= end) {
        return chars;
    }

    while (start < end) {
        // 收尾字符互换，直到替换完成。
        char temp = chars[start];
        chars[start] = chars[end];
        chars[end] = temp;
        start++;
        end--;
    }
    return chars;
}

private String v1_0_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        return sentence;
    }

    int length = sentence.length();
    // 第一步翻转所有字符
    char[] chars = v1_0_reverse(sentence.toCharArray(), 0, length - 1);
    System.out.println(new String(chars));

    // 第二步翻转每个单词（重点：怎么找到单词）
    int start = 0, end = 0;
    while (start < length) {
        if (chars[start] == ' ') {
            // 遇到空格就向右边继续查找
            start++;
            end++;
        } else if (end == length || chars[end] == ' ') {
            // 遇到空格或者已经到了字符串末尾，此时翻转找到的单词内部字符，这里需要注意end-1
            chars = v1_0_reverse(chars, start, end - 1);
            System.out.println(new String(chars));
            // 重新制定检查索引start
            start = end++;
        } else {
            // end加1，为了检查单词是否结束
            end++;
        }
    }
    return new String(chars);
}

• C++ 代码实现

// 反转字符串
void Reverse(char *pBegin, char *pEnd)
{
    if(pBegin == NULL || pEnd == NULL)
        return;

    while(pBegin < pEnd)
    {
        char temp = *pBegin;
        *pBegin = *pEnd;
        *pEnd = temp;

        pBegin ++, pEnd --;
    }
}

// 翻转句子中单词顺序，但保证单词内字符顺序不变。
char* ReverseSentence(char *pData)
{
    if(pData == NULL)
        return NULL;

    char *pBegin = pData;

    char *pEnd = pData;
    while(*pEnd != '\0')
        pEnd ++;
    pEnd--;

    // 翻转整个句子
    Reverse(pBegin, pEnd);

    // 翻转句子中的每个单词
    pBegin = pEnd = pData;
    while(*pBegin != '\0')
    {
        if(*pBegin == ' ')
        {
            pBegin ++;
            pEnd ++;
        }
        else if(*pEnd == ' ' || *pEnd == '\0')
        {
            Reverse(pBegin, --pEnd);
            pBegin = ++pEnd;
        }
        else
        {
            pEnd ++;
        }
    }
    return pData;
}

如果你在面试的时候遇到这道题，并且很容易就想到了这个算法，有经验的面试官就会在这道题基础上加点难度，继续考查面试者。so，第二道题来了：

题目：接上题，面试官继续提问，我们得到的" com google www"需要被用作一个URL的参数，所以这里需要的处理是去掉开头结尾的无效空格，并将两个单词中间的每一个空格都替换为"%20"。例如" com google www"应被转换为"com%20%20google%20www"，请给出转换函数。

解题思路

• 第一步去掉收尾的无效空格；比如" com google www"去掉后得到"com google www"。
• 第二步将两个单词中间的每一个空格都替换为"%20"。

还是以" hello world"为例，简单分析下解题过程，请看下图。

图 1.1 剔除收尾无效空格，并将单词间的每一个空格都替换为"%20"。

注：（1）字符串" hello world"，这里注意首字符是空格。 （2）剔除首尾空格后。 （3）对原字符串进行扩容。newLen = len + 2 x blackCount；这里解释下新数组的长度是如何计算的，由于是将每一个空格都替换为"%20",就相当于原来占一个字符替换后要占三个字符，换言之，每一个空格就会多出两个字符长度，所以就有前面的表达式。 （4） 定义两个指针p1、p2，分别指向len-1和newLen-1位置。 （5）判断p1指针是否指向空格，如果是则在p2处开始插入字符“%20”，不是则将p1指向的值复制给p2并将两个指针往左移动一位。这里将p1指向的字符 d 赋值给p2，并将两个指针向左移动一位。 （6）将p1指向的字符 l 赋值给p2，并移动指针。 （7）多次赋值和移动后，p1指向了第一个空格。 （8）在p2处依次插入字符 0 、 2 、 % ，并指针p2向左移动三位，结束后将p1向左移动一位，此时p1、p2重合结束循环。

测试用例

• 功能测试：前后有无空格情况、中间一个或多个空格情况。
• 特殊输入测试：空字符、字符串中只有空格、null对象（指针）。

编码实现

• Java代码

private String v1_1_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        return sentence;
    }

    // 去掉字符串收尾的空格
    sentence = trim(sentence);
    int len = sentence.length();
    char[] chars = sentence.toCharArray();
    int count = getSpaceCount(sentence);
    int newLen = 2 * count + len;
    // 扩容，内部使用System.arraycopy 方法实现。
    chars = Arrays.copyOf(chars, newLen);

    int index = len - 1;
    int newIndex = newLen - 1;
    while (index >= 0 && newIndex > index) {
        if (chars[index] == ' ') {
            chars[newIndex--] = '0';
            chars[newIndex--] = '2';
            chars[newIndex--] = '%';
        } else {
            chars[newIndex--] = chars[index];
        }
        index--;
    }

    return new String(chars);
}

/**
 * 剔除字符串收尾的空格
 *
 * @param origin
 * @return
 */
private String trim(String origin) {
    char[] chars = origin.toCharArray();
    int length = chars.length;
    int st = 0;
    while (st < length && chars[st] == ' ') {
        st++;
    }

    while (st < length && chars[length - 1] == ' ') {
        length--;
    }

    // 如果收尾有空格，就截取生成新的字符串
    if (st > 0 || length < chars.length) {
        origin = new String(chars, st, (length - st));
    }
    return origin;
}

private int getSpaceCount(String sentence) {
    char[] chars = sentence.toCharArray();
    int count = 0;
    for (char c : chars) {
        if (c == ' ') {
            count++;
        }
    }
    return count;
}

• C++实现

/* 去掉收尾空格:将原字符串截取后返回新字符串 */
void trim(char *strIn, char *strOut){
    int i = 0;
    int j = strlen(strIn) - 1;

    while(strIn[i] == ' ')
        ++i;

    while(strIn[j] == ' ')
        --j;
    strncpy(strOut, strIn + i , j - i + 1);
    strOut[j - i + 1] = '\0';
}

/*length 为字符数组string的总容量*/
void replaceBlank(char string[], int length)
{
    if(string == NULL && length <= 0)
        return;

    /*originalLength 为字符串string的实际长度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;

        if(string[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    /*newLength 为把空格替换成'%20'之后的长度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}

题目2：调整数组中元素顺序

题目： 给定一个整数数组，请实现一个函数来调整数组中数字的顺序，使得所有奇数都位于偶数之前。

解题思路

此题比较简单，我最先想到的解法是这样：我们维护两个指针(索引)，一个指针指向数组的第一个数字，称之为头指针，向右移动；一个指针指向最后一个数字，称之为尾指针，向左移动。

图2.0 调整数组{2，1，3，6，4，7，8，5}使得奇数位于偶数前面的过程。

注：（1）初始化两个指针P1、P2，分别指向数组的头部和尾部。（2）由上一步得知，指针P1指向的数字是偶数2，而P2指向的数字是奇数5，满足条件，我们交换这两个数字。（3） P1继续向右移动直到指向偶数6，P2继续向左移动直到指向奇数7。（4）交换两个指针指向的数字。（5）P1，P2继续移动后重叠，表明所有奇数已位于偶数前面了。

循环结束条件：两个指针重叠时或P2指针移动到了P1指针的前面，此时退出循环。 可以看出此算法，一次循环搞定，所以时间复杂度O(n), 由于在原数组上操作，所以空间复杂度O(1)。

测试用例

• 功能测试：全是奇数、全是偶数、奇偶数存在但已排好序/未排好序。
• 特殊输入测试： null对象、数组元素为0、有负数情况。

编码

• Java实现

private int[] v2_0_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }
     int st = 0;
     int end = nums.length - 1;

     while (st < end) {
         // find even number
         if (isOdd(nums[st])) {
             st++;// 奇数，索引右移
         } else if (!isOdd(nums[end])) {
             end--;// 偶数，索引左移
         } else {
             // 奇偶数互换
             int temp = nums[st];
             nums[st] = nums[end];
             nums[end] = temp;
             st++;
             end--;
         }
     }
     return nums;
 }

 // 与1做按位运算，不为0就是奇数，反之为偶数
 private boolean isOdd(int n) {
     return (n & 1) != 0;
 }

• C++实现

// 互换
void swap(int* num1, int* num2) {
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

//判断是否为奇数
bool isOdd(int data) {
    return (data & 1) != 0;
}

//奇偶互换
void oddEvenSort(int *pData, unsigned int length) {
    if (pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while (pBegin < pEnd)
    {
        //如果pBegin指针指向的是奇数，正常，向右移
        if (isOdd(*pBegin))  
        {
            pBegin++;
        }
        //如果pEnd指针指向的是偶数，正常，向左移
        else if (!isOdd(*pEnd))
        {
            pEnd--;
        }
        else
        {
            //否则都不正常，交换
            swap(pBegin, pEnd);
        }
    }
}

有经验的面试官又来了，题目难度需要升下级，😶~

题目： 接上题，面试官会继续要求改造此函数使其能够保证原先输入数组的奇数内部顺序以及偶数内部顺序，即如果输入为{2，1，3，6，4，7，8，5}，则输出应为{1，3，7，5，2，6，4，8}，奇数之间的相互顺序和偶数之间的相互顺序不得被改变。

解题思路

要想保证原数组内元素的顺序，可使用O(n)的temp数组空间按顺序缓存偶数，奇数依次放到原数组前面，最后将temp中偶数取出放在原数组后面。

图 2.1 借助O(n)的temp数组缓存偶数，进而保证原数组顺序。

注： 变量解释：st为即将插入的奇数在原数组中的索引，evenCount为缓存的偶数个数。（1）初始化和原数组相同长度的数组temp，指针p1指向首个元素，st=eventCount=0。 （2）将p1指向的偶数 2 放入在temp中，evenCount自加1。 （3）由于p1指针向右移动一位指向的是奇数 1 ，所以将p1指向的值赋值给Array[st]，此时还st=0，赋值完成后st自加1。 （8）依次逻辑，直到循环结束时，已完成原数组中奇数元素按顺序插入到了头部，偶数按顺序缓存在了temp数组中，即图中状态。

**上图展示了偶数按顺序缓存到temp数组中，奇数按顺序放到原数组前面。**最后将temp数组中的偶数依次按序放在原数组后面，这个过程较简单，就没体现到图中，具体请看下面代码实现。

测试用例

同上一题。这里就省略了。

编码

• Java实现

private int[] v2_1_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }

     int st = 0;
     int evenCount = 0;
     int[] temp = new int[nums.length];
     for (int i = 0; i < nums.length; i++) {
         if (!isOdd(nums[i])) {
             evenCount += 1;
             temp[evenCount - 1] = nums[i];
         } else {
             if (st < i) {
                 // 将奇数依次放在原数组前面
                 nums[st] = nums[i];
             }
             st++;
         }
     }

     if (evenCount > 0) {
         for (int i = st; i < nums.length; i++) {
             nums[i] = temp[i - st];
         }
     }
     return nums;
}

• C++实现

void v2_1_solution(int* nums,unsigned int len)
{
     if (!nums || len <= 1) {
         return;
     }
     int st = 0;
     int evenCount = 0;
     // 申请的内存空间temp
     int temp[len];
     for (int i = 0; i < len; i++) {
         if (!isOdd(nums[i])) {
             evenCount += 1;
             temp[evenCount - 1] = nums[i];
         } else {
             if (st < i) {
                 // 将奇数依次放在原数组前面
                 nums[st] = nums[i];
             }
            st++;
         }
     }
     // 将temp中偶数取出放在原数组后面
     if (evenCount > 0) {
         for (int i = st; i < len; i++) {
             nums[i] = temp[i - st];
         }
     }
 }

学习心得&解题套路

细心的读者可能发现了，文中解题过程大致是这样的：分析思路->测试用例->编码->调试并通过测试。你可能会问怎样才能很好的掌握算法编程呢？我的建议是：有事没事刷道题吧。勤加练习，终成大神。哈哈，请轻拍。

关于解题思路（详见剑指offer）

• 画图让抽象问题形象化
• 举例让抽象问题具体化
• 分解让复杂问题简单化

​各种数据结构及算法书籍： 大话数据结构、剑指offer、算法导论等等。 在线编程：LeetCode、牛客网、七月在线 菜鸟练手推荐：C++在线工具

总结

现在去大公司面试，都会有算法题，所以不是你想不想掌握它，而是公司会通过它把一部分人淘汰掉，说的可能有点吓人，但现实就是这样操作的。文中所有代码均编译运行并通过测试用例检查，由于篇幅限制，代码没有贴全，完整的可运行代码请点击链接获取： github.com/yangjiantao…。 由于作者水平有限，文中错误之处在所难免，敬请读者指正。