牛客剑指offer刷题记录（五）

刺骨的言语ヽ痛彻心扉 2022-06-12 03:53 196阅读 0赞

## **复杂链表复制** ##

链表的指针域中，除了有指向下一个节点的链表以外，还有一个指向随机节点的指针。

struct ListNode
    {
        int val;
        ListNode * next;
        ListNode * random;
    };

### 思路一 ###

常规做法，空间换时间。  
先常规的将拷贝的节点用next串起来，遍历一遍原始链表，然后尾插法即可。  
在尾插的同时，建立一个由原始节点指针P到拷贝节点指针C的一个map。

再次遍历原始指针，如果指针p指向节点的random域不为NULL，那么通过`m[p]->random=m[p->random]`来达到赋值random的目的：

class Solution {
    public:
        RandomListNode* Clone(RandomListNode* pHead)
        {
            if (nullptr == pHead)
                return nullptr;
            RandomListNode * p = pHead;
            unordered_map<RandomListNode*, RandomListNode*>m;
            RandomListNode *newHead = new RandomListNode(0);
            RandomListNode*tail = newHead;
            while (nullptr != p)
            {
                RandomListNode * r = new RandomListNode(p->label);
                //if (nullptr != p->random)
                m[p] = r;
                tail->next = r;
                tail = r;
                p = p->next;
            }
            tail->next = nullptr;
            p = pHead;
            while (nullptr != p)
            {
                if (nullptr != p->random)
                {
                    m[p]->random = m[p->random];
                }
                p = p->next;
            }
            return newHead->next;
        }
    };

### 思路二 ###

相当聪明的做法，看了书才能知道，就是把clone的节点接到原节点的后面  
例如：  
l1->l2->l3  
变成  
l1->l1’->l2->l2’->l3->l3’->NULL

然后有`p->next->random=p->random->next`

最后再把这个链表拆成两个链表即可。

class Solution {
    public:
        RandomListNode* Clone(RandomListNode* pHead)
        {
            if (nullptr == pHead)
                return nullptr;
            RandomListNode * p = pHead;
            while (nullptr != p)
            {
                RandomListNode*r = new RandomListNode(p->label);
                r->next = p->next;
                p->next = r;
                p = r->next;
            }
            p = pHead;
            while (nullptr != p)
            {
                if (nullptr != p->random)
                {
                    p->next->random = p->random->next;
                }
                p = p->next->next;
            }
            RandomListNode * newHead = new RandomListNode(0);//新链表的头结点
            RandomListNode *k = newHead;
    
            RandomListNode* o = pHead;//这里还需要保证原链表的形状
            p = pHead->next;
            while (nullptr != p)
            {
                o->next = o->next->next;
                k->next = p;
                k = p;
                if (nullptr != p->next)
                    p = p->next->next;
                else
                    break;
                o = o->next;
            }
            return newHead->next;
    
        }
    };

--------------------

## **二叉搜索树与双向链表** ##

将二叉搜索树转成双向链表：  
原先指向左子树的指针调整为指向双向链表中前一个节点的的指针pre，原先指向右子树的指针调整为指向双向链表后一个节点的指针next.

由于二叉搜索树中序遍历的序列是有序的，而题目要求双向链表也是有序的，因此，我们以中序的方式进行递归。

这里，我们还需要一个辅助的指针，指向当前已经排好的双向链表的最后一个节点。

所以，递归的顺序是，先排左子树，再排当前节点，再排右子树。

排好以后，list指针需要往回溯，找到双向链表的头结点。

class Solution {
    private:
        void inorder(TreeNode *root,TreeNode *&list)
        {
            if(nullptr==root)
                return;
            inorder(root->left,list);
            root->left = list;
            if (nullptr != list)
                list->right = root;
            list = root;
            inorder(root->right,list);
        }
    public:
        TreeNode* Convert(TreeNode* pRootOfTree)
        {
            if (nullptr == pRootOfTree)
                return nullptr;
            TreeNode *list = nullptr;
            inorder(pRootOfTree, list);
            while (nullptr!=list&&nullptr != list->left)
            {
                list = list->left;
            }
            return list;
        }
    };

--------------------

## **字符串全排列** ##

把字串分成两部分，一部分是字符串的第一个字符，一部分是第一个字符后面所有的字符，将第一个字符分别与后面所有的字符交换：  
比如abc，a与b、c分别交换，得到序列bac和cba。

对于子序列，再递归地完成该操作即可。

不过牛客上面有个两个要求：  
1.要求字符串出现重复字符，即可能有aac这样的序列  
2.要求字符串是字典序的。

对于第2个要求，我们很容易实现，只要将第一个字符后面所有的字符sort一下即可，对于第1个要求，如果出现重复字符，则不执行swap操作，这里需要维护一个visit容器。

class Solution {
    private:
        void dfs(vector<string>&result, string str, int start)
        {
            if (start == str.size())
            {
                result.push_back(str);
                //cout << str << endl;
            }
            sort(str.begin() + start, str.end());//保证字典序
            unordered_set<char>visit;//保证重复不交换
            for (int i = start; i < str.size(); ++i)
            {
                if (visit.find(str[i]) == visit.end())
                {
                    visit.insert(str[i]);
                    swap(str[start], str[i]);
                    dfs(result, str, start + 1);
                    swap(str[start], str[i]);
                }
            }
        }
    public:
        vector<string> Permutation(string str) {
            if (0 == str.size())
                return vector<string>(0);
            vector<string>result;
            dfs(result, str, 0);
            return result;
        }
    };

--------------------

## **数组中出现次数超过一半的数字** ##

最简单的办法莫过于排序取中间的数，这样时间效率就不高了，另外可以采用hash的方式统计一下，这样用额外的空间换取时间倒是可以将时间复杂度控制在线性。最后有一个很牛逼的算法交筛选法。

详细参考：[LeetCode169—MajorityElements][LeetCode169_MajorityElements]

class Solution {
    public:
        int MoreThanHalfNum_Solution(vector<int> numbers) {
            int candidates = numbers[0];
            int count = 0;
            for (int i = 0; i < numbers.size(); ++i)
            {
                if (count == 0)
                {
                    count = 1;
                    candidates = numbers[i];
                }
                else
                {
                    count = (candidates == numbers[i]) ? (count + 1) : (count - 1);
                }
            }
            //下面代码排除没有多数派情况
            count = 0;
            for (int i = 0; i<numbers.size(); i++)
            {
                if (numbers[i] == candidates)
                    count++;
            }
            if (count <= (numbers.size() ) / 2)
                return 0;
    
            return candidates;
        }
    };

--------------------

## **最小的k个数** ##

借助容器了。  
能想象到，最小的k个数和最大的k个数可以用堆这种结构来保存。这里我用一个优先级队列。事实上红黑树也是可以的，用一个set也是可以的。

### 优先级队列 ###

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            if (k == 0 || input.size() == 0||k>input.size())
                return vector<int>();
            priority_queue<int>q;
            for (int i = 0; i < input.size(); ++i)
            {
                q.push(input[i]);
                if (q.size()>k)
                    q.pop();
            }
            vector<int>v;
            v.reserve(q.size());
            while (!q.empty())
            {
                v.push_back(q.top());
                q.pop();
            }
            reverse(v.begin(), v.end());
            return v;
        }
    };

### 有序集合 ###

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            if (k == 0 || input.size() == 0||k>input.size())
                return vector<int>();
            set<int>s;
            for (int i = 0; i < input.size(); ++i)
            {
                s.insert(input[i]);
                if (s.size()>k)
                {
                    s.erase(std::prev(s.end()));
                }
            }
            vector<int>v;
            v.reserve(s.size());
            for (auto it = s.begin(); it != s.end(); ++it)
            {
                v.push_back(*it);
            }
    
            return v;
        }
    };

第二种思路是用partition函数来解决问题，可以想见，快排的思路是比基准小的在左边，比基准pivot大的再右边，先回顾一下快排和partition函数。

int Partition(vector<int>&v, int p, int r)
    {
        int x = v[r];//pivot
        int i = p-1;
        for (int j = p; j < r; ++j)
        {
            if (v[j] <= x)
            {
                swap(v[j], v[++i]);
            }
        }
        swap(v[r], v[i+1]);
        return i +1;
    }
    void QuickSort(vector<int>&v, int p, int r)
    {
        if (p < r)
        {
            int q = Partition(v, p, r);
            QuickSort(v, p, q - 1);
            QuickSort(v, q + 1, r);
        }
    }

如果基于数组的第k个数字来调整，使得比第k个数字小的在数组左边，比第k个数字大的都在右边，这样左边的k个数字就是k个最小数字。基于这种思路的代码如下：

int Partition(vector<int>&v, int p, int r)
    {
        int x = v[r];//pivot
        int i = p-1;
        for (int j = p; j < r; ++j)
        {
            if (v[j] <= x)
            {
                swap(v[j], v[++i]);
            }
        }
        swap(v[r], v[i+1]);
        return i +1;
    }
    class Solution {
    public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            if (k == 0 || input.size() == 0||k>input.size())
                return vector<int>();
            int p, r;
            p = 0;
            r = input.size() - 1;
            int i = Partition(input, p, r);
            while (i != k - 1)
            {
                if (i > k - 1)
                {
                    r = i - 1;
                    i = Partition(input, p, r);
                }
                else
                {
                    p = i + 1;
                    i = Partition(input, p, r);
                }
            }//end while
            vector<int>res(input.begin(), input.begin() + k);
            return res;
        }
    };

[LeetCode169_MajorityElements]: http://blog.csdn.net/zhangxiao93/article/details/51957845