[leetcode] 剑指 Offer 专题（二）

sinkinben 2020-10-19 原文

《剑指 Offer》专题第二部。

16 数值的整数次方

递归快速幂。如果 n 是负数，那么先求正数次幂的（取相反数），结果取倒数。因为涉及相反数，因此需要特殊考虑 n 是否为 -2147483648 .

class Solution {
public:
    double myPow(double x, int n) {
        if (n  == 0) return 1;
        else if (n == 1) return x;
        else
        {
            bool sign = (n < 0);
            bool ismin = (n == (int)0x80000000);
            if (ismin) n++;
            if (sign) n = -n;
            double k = myPow(x, n >> 1);
            k *= k;
            if (n & 1) k *= x;
            if (ismin) k *= x;
            return sign ? (1/k):k;
        }
    }
};

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

题目：剑指 Offer 17. 打印从1到最大的n位数。

Python 的话只需要一行：

return list(range(1, pow(10, n)))

C++ 无脑解法：

class Solution {
public:
    vector<int> printNumbers(int n) {
        int limit = pow(10, n);
        vector<int> v;
        for (int i=1; i<limit; i++)
            v.push_back(i);
        return v;
    }
};

但是如果面试的时候，n 给出很大呢，即 \(10^n\) 超出了一个 int 的表示范围，该怎么处理？

通过字符串模拟。

class Solution
{
public:
    vector<int> printNumbers(int n)
    {
        // 从左到右存放低位->高位
        char str[n + 1];
        memset(str, \'0\', n);
        str[n] = \'\0\';
        while (increment(str, n))
            print(str, n);
        return vector<int>();
    }

    void print(char str[], int n)
    {
        int i = n - 1;
        while (i >= 0 && str[i] == \'0\')
            i--;
        assert(i != -1);
        while (i >= 0)
            cout << str[i--];
        cout << endl;
    }
	// 模拟加法，溢出 n 位时返回 false
    bool increment(char str[], int size)
    {
        int cur = str[0] - \'0\' + 1;
        if (cur <= 9)
        {
            str[0] = cur + \'0\';
            return true;
        }
        else
        {
            int inbit = 1;
            int i = 0;
            str[i] = \'0\';
            while (inbit)
            {
                i++;
                cur = str[i] - \'0\' + inbit;
                inbit = (cur >= 10);
                str[i] = (inbit ? (\'0\') : (cur + \'0\'));
                if (i == size - 1 && inbit)
                    return false;
            }
            return true;
        }
    }
};

18 链表删除节点

水题。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (head == NULL) return NULL;
        if (head->val == val) return head->next;
        auto pre = head, p = head->next;
        while (p != NULL)
        {
            if (p->val == val)
            { pre->next = p->next; break; }
            pre = p, p = p->next;
        }
        return head;
    }
};

移除重复节点

题目：面试题 02.01. 移除重复节点。

跟书上要求不一致，这里是未排序的链表。使用集合记录是否第一次出现即可。

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if (head == nullptr) return nullptr;
        set<int> s;
        s.insert(head->val);
        auto pre = head, p = head->next;
        while (p != nullptr)
        {
            if (s.count(p->val) == 0)
            {
                s.insert(p->val);
                pre = p, p = p->next;
            }
            else
            {
                pre->next = p->next;
                p = p->next;
            }
        } 
        return head;
    }
};