[剑指Offer] 第3章课后题详解

目录

大数加法

本题为《剑指Offer》“面试题12：打印1到最大的n位数”一节中的“相关题目”。

定义一个函数，在该函数中可以实现任意两个整数的加法。

分析

由于没有限定输入两个数的大小范围，所以需要把它当做大数问题来处理。大数无法用int，long甚至long long类型来表示，这里选择用字符串来表示。这里需要注意的一个点是，没有限制不能输入负数，还得考虑负数的情况。由于负数的加入，我们需要考虑，运算到底是做加法还是做减法，最后结果的符号问题。

解法

bigNumberPlus函数为所求函数，其余4个函数分别完成判断加减法，比较绝对值，计算，输出结果的任务。本解法采用的是顺序容器string（[C++ 面试基础知识总结] 顺序容器）。

#include <iostream>

using namespace std;

//定义3个标识符，分别表示第一个加数，第二个加数，运算结果的符号
bool flag1,flag2,flag3;

//判断运算是做加法还是做减法，并去掉负数开头的减号，方便后面比较绝对值
auto computeType(string &s1, string &s2) -> bool{

    flag1 = s1[0] == '-';
    flag2 = s2[0] == '-';

    if (flag1){
        s1.erase(s1.begin());
    }
    if (flag2){
        s2.erase(s2.begin());
    }

    //异号为真，同号为假，真表示做减法，假表示做加法
    return flag1 ^ flag2;
}

//比较两个大整数的绝对值，目的是为了便于做减法
auto judge(const string &s1, const string &s2) -> bool{

    //如果位数不等，则位数多的绝对值更大
    if(s1.size() != s2.size()){
        return  s1.size() > s2.size();
    }

    //位数相等时，从高位到低位依次比较
    auto b1 = s1.begin(), b2 = s2.begin();
    while(b1 != s1.end() && b2 != s2.end()){
        //找到第一个不相等同位数字，返回比较结果
        if (*b1 != *b2){
            return *b1 > *b2;
        }
        ++b1;
        ++b2;
    }
    //如果两个数字完全相等，返回真
    return true;
}

//计算大整数绝对值之和或差，s1为绝对值较大的加数
auto compute(const string &s1, const string &s2, bool type) -> string{
    //运算结果的字符串长度，最多比绝对值较大的加数位数多2，该情况下，两个加数都为负，且最高位有进位
    string sum(s1.size() + 2,'0');

    //takeOVer表示是否有进位或退位
    bool takeOver = 0;
    //采用逆向迭代器，由于s1，s2具备const属性，sum不具备，所以不能把3个迭代器一起定义
    auto p1 = s1.rbegin(), p2 = s2.rbegin();
    auto p3 = sum.rbegin();

    //当较小的加数还有位没有参加运算时
    while(p2 != s2.rend()){
        //如果字符串中有非数字字符则报错
        if (*p1 < '0' || *p1 > '9'|| *p2 < '0' || *p2 > '9')
        {
            throw new runtime_error("invalid");
        }
        int v1 = *p1++ - '0', v2 = *p2++ - '0', result;
        //type为真，做减法
        if (type){
            //如果不退位
            if(v1 >= v2 + takeOver){
                result = v1 - v2 - takeOver;
                *p3++ = char('0' + result % 10);
                takeOver = 0;
            }
            //如果退位
            else{
                result = v1 + 10 - v2 - takeOver;
                *p3++ = char('0' + result % 10);
                takeOver = 1;
            }
        }
        else{
            result = v1 + v2 + takeOver;
            *p3++ = char('0' + result % 10);
            takeOver = result / 10;
        }
    }

    //当s1长度大于s2时，对剩余位数进行运算，不是直接复制是因为可能有进位退位
    while(p1 != s1.rend()){
        if (*p1 < '0' || *p1 > '9')
        {
            throw new runtime_error("invalid");
        }
        int v1 = *p1++ - '0', result;
        if (type){
            if(v1 >= takeOver){
                result = v1 - takeOver;
                *p3++ = char('0' + result % 10);
                takeOver = 0;
            }
            else{
                result = v1 + 10 - takeOver;
                *p3++ = char('0' + result % 10);
                takeOver = 1;
            }
        }
        else{
            result = v1 + takeOver;
            *p3++ = char('0' + result % 10);
            takeOver = result / 10;
        }
    }

    //如果最高位有进位，再在运算结果前补上1
    if(takeOver == 1){
        *p3++ = char('0' + takeOver);
    }
    //如果运算结果为负，再在运算结果前不上负号
    if(flag3){
        *p3++ = '-';
    }

    返回运算结果字符串
    return sum;
}

//输出结果
auto printResult(const string &s) -> void{
    bool isBegin0 = true;
    for(auto begin = s.begin(), end = s.end(); begin != end; ++begin){
        //找到第一位不为0的某位，依次输出后面每一位
        if (isBegin0 && *begin != '0'){
            isBegin0 = false;
        }
        if (!isBegin0){
            cout << *begin;
        }
    }
    cout << endl;
}

auto bigNumberPlus(const string &s1, const string &s2) -> void{
    string realS1(s1), realS2(s2);
    //判断加减法，并取绝对值。
    bool type = computeType(realS1, realS2);

    //运算结果的符号位与绝对值大的加数相同
    flag3 = judge(realS1, realS2) ? flag1 : flag2;
    //计算并输出结果，将绝对值大的加数放在compute函数的第一个参数
    printResult(judge(s1, s2) ? compute(realS1, realS2, type) : compute(realS2, realS1, type));
}



int main(int argc, const char * argv[]) {

    string s1,s2;
    cin >> s1 >> s2;
    bigNumberPlus(s1, s2);

    return 0;
}

优化

本解法还有两个地方可以进一步优化：
1.在computeType函数中，对string类型容器进行删除首元素操作，这是不推荐的，可以考虑用deque<char>或者list<char>来替换string。原因详见[C++ 面试基础知识总结] 顺序容器。
2.在compute函数中，做了两步运算，第一步为s1低位与s2的运算，第二步是s1高位与s2最高位进位或退位的运算，这里可以再提取一个函数出来，用于计算两个相等长度字符串的运算，接收4个参数，分别为2个加数的引用、进位标志和运算类型，返回最高位进位标志，然后调用两次，第一次是s1低位与s2的运算，第二次是s1高位与全为’0’的字符串的运算。这样可以让代码更简洁，提升代码的拓展性。

链表的中间节点

本题为《剑指Offer》“面试题15：链表中倒数第k个结点”一节中的“相关题目”。

求链表的中间结点，如果链表中的结点总数为奇数，返回中间结点；如果结点总数为偶数，返回中间两个结点的任意一个。链表节点定义如下：

struct ListNode{
    int       m_nValue;
    ListNode*  m_pNext;
};

分析

可以定义两个指针，一个每次走两步，一个每次走一步，走两步的指针抵达链表尾部时，则走一步的指针正好在链表中间。需要注意的是空链表的情况，且走两步的指针不能连续走两步，每走一步都必须判定是否已达到链表尾部。

解法

auto findMidNode(ListNode* pListHead) -> ListNode*{

    //链表为空，返回NULL
    if(pListHead == NULL){
        return NULL;
    }

    //初始化两个指针都指向链表头部
    ListNode* pAhead = pListHead;
    ListNode* pBehind = pListHead;

    //走两步的指针没有抵达链表尾部时进行循环
    while(pAhead -> m_pNext != NULL){
        //走两步的指针向后移动一步
        pAhead = pAhead -> m_pNext;
        //走一步的指针向后移动一步，可以调整该行代码的位置来决定链表节点个数为偶数时输出哪一个，目前输出的是中间靠后的节点，如果放在下面判定语句之后，则输出中间靠前的节点
        pBehind = pBehind -> m_pNext;

        //如果走两步的指针抵达链表尾部，则直接返回走一步的指针
        if(pAhead -> m_pNext == NULL){
            return pBehind;
        }
        //走两步的指针再向后移动一步
        pAhead = pAhead -> m_pNext;
    }

    return pBehind;
}

环形链表

本题为《剑指Offer》“面试题15：链表中倒数第k个结点”一节中的“相关题目”。

判断一个单向链表是否形成了环形结构。链表节点定义如下：

struct ListNode{
    int       m_nValue;
    ListNode*  m_pNext;
};

分析

与上道题类似，定义两个指针，走两步的指针如果能追到走一步的指针，则形成了环形结构，如果走到底了，则没有形成环形结构。同样注意的也是空链表的处理和走两步之间的判定。

解法

//本题解法与上题大体一致
auto hasCircle(ListNode* pListHead) -> bool{
    if(pListHead == NULL){
        return NULL;
    }

    ListNode* pAhead = pListHead;
    ListNode* pBehind = pListHead;

    while(pAhead -> m_pNext != NULL){
        pAhead = pAhead -> m_pNext;
        pBehind = pBehind -> m_pNext;

        //走两步的指针走到链表尾部，表示没有环
        if(pAhead -> m_pNext == NULL){
            return false;
        }
        pAhead = pAhead -> m_pNext;
        //走两步的指针与走一步的指针相遇，表示有环，只在此处做判定，因为只有走两步指针额外走一步的时候才有可能追上走一步的指针。
        if(pAhead == pBehind){
            return true;
        }
    }
    return false;
}

反转链表

本题为《剑指Offer》“面试题16：反转链表”一节中的“本题拓展”。

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点，用递归的方式实现。链表节点定义如下：

struct ListNode{
    int        m_nKey;
    ListNode*  m_pNext;
};

分析

数据结构中链表插入有两种方法，头插法和尾插法，尾插法是链表尾部最后一个节点的next指针指向插入节点，头插法是用插入节点的next指针指向链表的第一个节点（非固定头节点的情况）。将链表中的节点依次用头插法的方式插入到一个新的空链表中则可以实现链表的反转。这里需要注意的是输入链表为空，输入链表只有一个节点的特例，以及链表断裂的防止。

解法

auto reverseList(ListNode* pListHead) -> ListNode*{
    //链表为空
    if(pListHead == NULL){
        return NULL;
    }

    //链表只有一个节点，直接返回头节点
    if(pListHead -> m_pNext == NULL){
        return pListHead;
    }
    //保存原链表头结点的下一个节点，防止链表断裂
    ListNode* nextNode = pListHead -> m_pNext;
    //摘下原链表的头结点，作为新链表的头结点
    pListHead -> m_pNext = NULL;
    //递归调用
    return insertHead(nextNode, pListHead);
}

auto insertHead(ListNode* pListHead, ListNode* newListHead) -> ListNode*{
    //如果原链表只剩最后一个节点了，则将该节点插入到新链表的头部，并返回该节点
    if(pListHead -> m_pNext == NULL){
        pListHead -> m_pNext = newListHead;
        return pListHead;
    }
    //保存原链表当前头结点的下一个节点，防止链表断裂
    ListNode* nextNode = pListHead -> m_pNext;
    //摘下原链表的当前头结点，插入到新链表的头部
    pListHead -> m_pNext = newListHead;
    //递归调用
    return insertHead(nextNode, pListHead);
}