跳转至

5. 书写高质量的代码

书写, 布局, 命名

代码完整性

面试题16: 数值的整数次方

Question

实现函数double power(double base, int expoent), 求base的exponent次方, 不得使用库函数, 同时不需要考虑大数问题

Answer

参考代码: 数值的整数次方

面试题17: 打印从1到最大的n位数

Question

Answer

参考代码: 打印从1到最大的n位数

可以优化

面试题18: 删除链表的节点

Question

Answer

struct Node
{
    int value;
    Node* next;
};

void DeleteNode(Node** pHead, Node* pToBeDelete)
{
    if (pHead == nullptr || *pHead == nullptr || pToBeDelete == nullptr)
        return;

    Node* head = *pHead;
    // 只有一个节点
    if (head->next == nullptr)
    {
        delete pToBeDelete;
        *pHead = nullptr;
    }
    // 有多个节点
    else 
    {
        // 删除尾节点
        if (pToBeDelete->next == nullptr)
        {
            delete pToBeDelete;
            head->next = nullptr;
        }
        // 删除头节点
        else if (pToBeDelete == head)
        {
            *pHead = head->next;
            delete head;
        }
        else
        {
            Node* p = pToBeDelete->next;
            pToBeDelete->value = pToBeDelete->next->value;
            pToBeDelete->next = pToBeDelete->next->next;
            delete p;
        }
    }
}
参考代码: 删除链表的节点

题目二: 删除链表中重复的节点

Question

Answer

struct Node
{
    int value;
    Node* next = nullptr;
};

void deleteDuplication(Node** pHead)
{
    if (pHead == nullptr || *pHead == nullptr)
        return;

    Node* head = *pHead;
    // 只有一个节点
    if (head->next == nullptr)
        return;

    // 两个节点
    Node* preNode = head;
    Node* curNode = head->next;

    if (curNode->next == nullptr)
    {
        if (curNode->value == preNode->value)
        {
            head->next = nullptr;
            delete curNode;
            return;
        }
    }

    // 多个节点
    while (curNode->next != nullptr)
    {
        if (preNode->value == curNode->value)
        {
            Node* waitDelete = curNode->next;
            curNode->value = curNode->next->value;
            curNode->next = curNode->next->next;
            delete waitDelete;
        }
        else 
        {
            preNode = preNode->next;
            curNode = preNode->next;
        }
    }

    if (preNode->value == curNode->value)
    {
        preNode->next = nullptr;
        delete curNode;
    }
}
参考代码: 删除有序链表里重复的节点

面试题19: 正则表达式匹配

面试题20: 表示数值的字符串

面试题21: 调整数组顺序使奇数位于偶数前面

代码的鲁棒性

面试题22: 链表中倒数第k个节点

struct Node
{
    int value;
    Node* next = nullptr;
};

Node* tailKNode(Node **pHead, int k)
{
    if (pHead == nullptr || *pHead == nullptr || k <= 0)
        return nullptr;

    Node* head = *pHead;
    Node* preNode = head;
    Node* kNode = preNode;

    for (int i = 0; i < k - 1; ++i)
    {
        kNode = kNode->next;
        if (kNode == nullptr)
            return nullptr;
    }

    while (kNode->next != nullptr)
    {
        preNode = preNode->next;
        kNode = kNode->next;
    }
    return preNode;
}
参考代码: 链表中倒数第k个节点

面试题23: 链表中环的入口节点

struct Node
{
    int value;
    Node* next = nullptr;
};

Node* linkListCircleStartNode(Node** pHead)
{
    if (pHead == nullptr || *pHead == nullptr)
        return nullptr;

    Node* head = *pHead;

    if (head->next == nullptr || head->next->next == nullptr)
        return nullptr;

    // 判断是否存在环
    Node* p1 = head->next;
    Node* p2 = head->next->next;

    while (p1 != nullptr && p2 != nullptr && p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next->next;
    }
    if (p1 == nullptr)  // 不存在环
        return nullptr;

    // 判断环的长度
    int circleLength = 1;
    p1 = p1->next;
    while (p1 != p2)
    {
        p1 = p1->next;
        circleLength++;
    }

    // 再利用两个指针找到环的入口
    Node* pBefore = head;
    Node* pAfter = head;
    for (int i = 0; i < circleLength; ++i)
        pAfter = pAfter->next;

    while (pBefore != pAfter)
    {
        pBefore = pBefore->next;
        pAfter = pAfter->next;
    }
    return pBefore;
}

完整代码: 链表中环的入口节点

面试题24: 反转链表

struct Node
{
    int value;
    Node* next = nullptr;
};

Node * LinkListReversed(Node** pHead)
{
    if (pHead == nullptr || *pHead == nullptr)
        return nullptr;

    Node* head = *pHead;
    // 只有一个头节点,直接返回
    if (head->next == nullptr)  
        return head;

    Node* preNode = head;
    Node* curNode = head->next;
    Node* tempNode = curNode->next;
    // 只有两个节点
    if (curNode -> next == nullptr)
    {
        curNode->next = head;
        head->next = nullptr;
        return curNode;
    }

    while (curNode != nullptr)
    {
        curNode->next = preNode;
        if (preNode == head) preNode->next = nullptr;
        preNode = curNode;
        curNode = tempNode;
        if (curNode == nullptr) return preNode;
        tempNode = curNode->next;
    }
    return nullptr;
}

完整代码: 反转链表

面试题25: 合并两个排序链表

struct Node
{
    int value;
    Node* next = nullptr;
};


Node* mergeSortedLinkList(Node** pHead1, Node** pHead2)
{
    if (pHead1 == nullptr && pHead2 == nullptr)
        return nullptr;

    if (*pHead1 == nullptr)
        return *pHead2;

    if (*pHead2 == nullptr)
        return *pHead1;

    Node* head1 = *pHead1;
    Node* head2 = *pHead2;
    Node* resultHead = nullptr;
    Node* resultCurNode = nullptr;

    while (head1 != nullptr && head2 != nullptr)
    {
        Node* node = new Node;

        if (head1->value < head2->value)
        {
            node->value = head1->value;
            head1 = head1->next;
        }
        else
        {
            node->value = head2->value;
            head2 = head2->next;
        }

        if (resultHead == nullptr)
        {
            resultHead = node;
            resultCurNode = node;
        }
        else
        {
            resultCurNode->next = node;
            resultCurNode = node;
        }
    }

    while (head1 != nullptr)
    {
        Node* node = new Node;
        node->value = head1->value;
        resultCurNode->next = node;
        resultCurNode = node;
        head1 = head1->next;
    }

    while (head2 != nullptr)
    {
        Node* node = new Node;
        node->value = head2->value;
        resultCurNode->next = node;
        resultCurNode = node;
        head2 = head1->next;
    }
    return resultHead;
}

参考代码: 合并两个排序链表

面试题26: 树的子结构

struct Node
{
    double value;
    Node* left = nullptr;
    Node* right = nullptr;
};

bool equal(double num1, double num2)


bool hasSubTree(Node* pRoot1, Node* pRoot2)
{
    bool result = false;

    if (pRoot1 != nullptr && pRoot2 != nullptr)
    {
        if (equal(pRoot1->value, pRoot2->value))
            result = doesTree1HaveTree2(pRoot1, pRoot2)

        if (!result)
            result = hasSubTree(pRoot1->left, pRoot2);

        if (!result)
            result = hasSubTree(pRoot1->right, pRoot2);
    }

    return result;
}


bool doesTree1HaveTree2(Node* pNode1, Node* pNode2)
{
    if (pNode2 == nullptr)
        return true;

    if (pNode1 == nullptr)
        return false;

    if (!equal(pNode1->value, pNode2->value))
        return false

    return doesTree1HaveTree2(pNode1->left, pRoot2->left) && doesTree1HaveTree2(pNode1->right, pRoot2->right)
}

bool equal(double num1, double num2)
{
    if (num1 - num2 > -0.000001 && num1 - num2 < 0.000001)
        return true;
    return false;
}

参考代码: 树的子结构