[数据结构与算法]offer(1)高质量的代码

高质量的代码：

16-数值的整数次方：

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

考虑特殊输入，比如输入为负数或者0

//靠，怪不得是中等题，卡了8次。。。。
变量声明Int/double
溢出强转
class Solution {
public:
    double myPow(double x, int n) {
        double result;
        //1.判定特殊情况：
        if((x==0)&&(n<0))
            return 0.0;
        if(n==1)
            return x;
        if(n==0)
            return 1;
        //2.考虑负数情况，归二为一
        //强制转换 
        unsigned int m = (unsigned int) n;
        if(n<0){
            x=1/x;
            m=-m;
        }

        if(m/2==0) return x;
        else result = myPow(x,m/2);
        
        if(m%2==1){
            return result*result*x;
        }else{
            return result*result;
        }  
    }
};

17-打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

*(注)-考虑大数问题

18-删除链表的节点

给定单向链表的头指针和一个要删除的节点指针，定义函数在O(1)时间内删除该节点。

//删除一个节点的时候不一定要删除节点本身，可以用节点指向的下一个节点来替换这个节点
void Deletnode(ListNode* PListHead, ListNode* pToBeDelete){
    if(!pListhead||!pToBeDelte)
        return;
    //要删除的节点不是尾节点
    if(pToBeDeleted->m_pNext != nullptr)
        {
            ListNode* pNext = pToBeDeleted->m_pNext;
            pToBeDeleted->m_nValue = pNext->m_nValue;
            pToBeDeleted->m_pNext = pNext->m_pNext;

            delete pNext;
            pNext = nullptr;
        }
        // 链表只有一个结点，删除头结点（也是尾结点）
        else if(*pListHead == pToBeDeleted)
        {
            delete pToBeDeleted;
            pToBeDeleted = nullptr;
            *pListHead = nullptr;
        }
        // 链表中有多个结点，删除尾结点
        else
        {
            ListNode* pNode = *pListHead;
            while(pNode->m_pNext != pToBeDeleted)
            {
                pNode = pNode->m_pNext;            
            }

            pNode->m_pNext = nullptr;
            delete pToBeDeleted;
            pToBeDeleted = nullptr;
        }
    }
}

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

**注意：**此题对比原题有改动

常见解法1）需要双指针：使用指针Pre记录要删除节点指针指向的上一个节点
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val) return head->next;
        ListNode *pre = head, *cur = head->next;
        while(cur != nullptr && cur->val != val) {
            pre = cur;
            cur = cur->next;
        }
        if(cur != nullptr) pre->next = cur->next;
        return head;
    }
};
解法2）：class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val) return head->next;
        ListNode *cur = head->next;
        while(cur->val != val) {
            cur = cur->next;
        }
        if(cur->next!=nullptr){
            ListNode *deletenext = cur->next;
            cur->val = deletenext->val;
            cur->next = deletenext->next;
            delete deletenext;
            deletenext = nullptr; 
        }else{
            ListNode *pNode = head;
            while(pNode->next!=cur){
                pNode = pNode->next;
            }
            pNode->next = nullptr;
            delete cur;
            cur = nullptr;
        }
        return head;
    }
};

附加-删除排序链表中的重复元素

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

1)虚拟头结点
前三种方法都需要增加特殊情况判断（链表为空或者链表只有一个节点），当然也有方法可以不去判断特殊情况。这就是哑节点方法。只需要在头节点前面增加一个虚拟头节点，这样对头节点的处理就像其它 normal node 一样了。不过，在设置虚拟头节点的值的时候，可能需要设置大一点的值，因为链表是排序链表，如果这个虚拟头节点的值设置得比较小，很可能就会跟原链表头节点的值相等，如果恰好头节点后面没有其它节点值等于头节点的值，这样会将头节点也删除而出错。
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        /*创建虚拟头节点，并将节点值赋值*/
        ListNode* dummyHead = new ListNode(1000);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while(cur->next!=nullptr){
            /*当前节点值等于下一节点值*/
            if(cur->val == cur->next->val){
                cur->next = cur->next->next;
            }else{
                cur = cur->next;
            }
        }
        ListNode* retNode = dummyHead->next;
        delete dummyHead;
        return retNode;
    }
};

19-正则表达式匹配：

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。