第二十七篇，C++面经之手写代码（一）

前几篇整理、记录了面试遇到的问答题目，接下来再开几篇，写一写手写代码环节的题目，尽量加上注释或者讲解，并把代码写完整，达到复制粘贴后可立即编译执行的程度。
语言还是C++，有一点需要说明一下，有些面试官要求做安全检查，比如传入的指针是否为空，传入的int值是否超出设定的范围，但大部分不强制要求，关键看设计思路，所以我贴上的代码里有的做这种检查有的没做，知晓这层意思就好。
每篇的数量就先不做限制了，主要控制篇幅吧，毕竟这种题目长短差别很大。

一、判断回文字符串

bool func(const char* str) // 回文
{
    if (str == nullptr || strlen(str) == 0)
        return false;
 
    int nLen = strlen(str);
    for (int i = 0, j = nLen - 1; i <= j; ++i, --j)
    {
        if (str[i] == str[j])
            continue;
        else
            return false;
    }
 
    return true;
}

这个没啥太多好说的，也是比较经典的题目，两头双向奔赴就好。

二、合并两个有序数组

void func1(int a[], int b[], const int m, const int n) // 合并两个有序数组
{
    int i = m-1, j = n-1;
    int k = m + n - 1;
 
    while (i >= 0 && j >= 0)
    {
        a[k--] = (a[i] > b[j]) ? a[i--] : b[j--];
    }
 
    while (j >= 0)
    {
        a[k--] = b[j--];
    }
}

数组a和b是已经排好序了的并且排序方式相同，m、n分别是a、b中的元素个数，但互相大小未知，不过m不是数组a的全部length，因为要把合并后的结果放在a中，认为a的长度足够大。
这道题有几个注意点：

1. 覆盖问题，索引k的设计要找好位置，不能让合并后的新数据覆盖了原a中尚未参与合并排序的元素；
2. 第一个while()循环结束后，假如i未减到0，即原a未遍历完，此时b已遍历完并完成合并，由于合并结果仍然写到a中，a剩余的元素也是符合排序规则的，因此它们就不用动了，无需增加额外操作；
3. 第一个while()循环结束后，假如j未减到0，则a遍历完了b没遍历完，说明b的剩余元素应放到合并后的末尾，所以增加了一道while()循环把它们放到a里去。

三、用两个栈结构实现FIFO队列

#include <stack>
using namespace std;
 
void push(int num) // 用两个栈结构实现FIFO队列
{
    stack1.push(num);
}
 
int pop()
{
    if (stack2.empty() == true)
    {
        while (stack1.empty() == false)
        {
            stack2.push(stack1.top());
            stack1.pop();
        }            
    }
 
    int ret = stack2.top();
    stack2.pop();
    return ret;
}

FIFO即先入先出，First In First Out；队列要实现入队和出对两个方法，我们把它定义为push()和pop()；栈结构直接用C++标准的stack，两个栈结构简单起名stack1、stack2。
栈是典型的FILO先入后出数据结构，题干的立意是用两个栈结构实现FIFO，自然想到这就免不了要在两个栈之间倒换数据。
入队push()操作就比较简单了，没有太多要求，只管加入即可，因此我们用stack1承接push()方法，如代码中所示，很简单不再赘述；关键的是出队pop()，得准确无误地找到最先入队的那个，并在栈中删除它的记录，而且不能扰乱其它元素的顺序，这时第二个栈结构的重要作用就显现出来了。
先设想只有一个栈结构该怎么做pop()呢？把所有元素弹出来，放到一个vector或者什么里，然后舍弃最早的那个把剩余的再按原顺序压栈回去，这样做是能做，但一方面违背了题目对可用数据结构的约束，即只能用栈；另一方面方法太笨，体现不出软件设计的精妙。
而再用一个栈就完美解决了，就像左手倒右手一样，把stack1里的弹出压栈到stack2里，正好反转了stack1中的整体顺序但又保持了元素间的相对顺序，stack2栈顶元素即为最早入队者，直接把它返回并pop()即可；pop()之后不用再倒回stack1，留在stack2里供后续继续pop()；仅在pop()时发现stack2为空需要把stack1全部倒入stack2。
简便、巧妙！

四、斐波那契数列问题

// 递归写法
int fibonacci(const int n)
{
    if (n <= 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n-1) + fibonacci(n-2);
}
 
// 非递归写法
int fibonacci(const int n)
{
    if (n <= 0)
        return 0;
    else if (n == 1)
        return 1;
    else
    {
        int add1=0, add2=1, result=1;
        int i = 2;
        while (i <= n)
        {
            result = add1 + add2;
            add1 = add2;
            add2 = result;
            ++i;
        }
 
        return result;
    }
}

兔子繁衍问题、青蛙跳台阶问题，均可归纳抽象为斐波那契数列问题，斐波那契数列与自然之美吻合，即黄金分割。
斐波那契数列问题一般有递归写法和非递归写法。

五、走棋盘格问题

int func(const int n, const int m) // n横向，m纵向
{
    if (n <= 0 || m <= 0)
        return 1;
    else if (n == 1 || m == 1)                         //单边的
        return n + m;
    else
    {
        return func(n - 1, m) + func(n, m - 1);   //常规，递归，横向减一个纵向减一个
    }
}

走棋盘格问题和斐波那契数列有点儿相似，但难度更大一点。
问题描述是这样的：围棋的棋盘是有行列的，我们将其坐标化，假定某一个角为原点(0, 0)，每走一行或一列为一步，不许往回走，问走到(n, m)有多少种走法？
这道题的思路也是递归，考虑每个点从其前一个点的到达方式即可。分析题干约束，每个点的到达方式其实只会有两种，一是前一个点与其行数相同列数减1，一是前一个点与其列数相同行数减1，然后一步到达；如此递归地往回推导，最终可回到显而易见的初始位置或者易得出结果的特殊位置。
特殊位置比如代码中第二个条件分支，即棋盘行或列坐标为1的点，从原点到达的走法为n+m种，草稿纸上一画便知。
递归题一般会有非递归解法，可尝试动手写一写。