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

雨点打透心脏的1/2处 2022-06-12 13:08 311阅读 0赞

## **数组中的逆序对** ##

算法导论上应该有这样的课后题。

归并的思路，假设f(i,j)表示数组i到j的逆序对数，那么有：  
f(i,j)=f(i,k)\+f(k\+1,j),s(i,j,k)  
其中s(i,j,k)表示逆序对(p,q),p∈\[i,k\],q∈\[k\+1,j\]

由于归并排序，我么得到两个有序的子数组L,R，那么当出现逆序对(L\[i\],R\[j\])时，表示(L\[i\]>R\[j\]) 也可以得到L\[i..k\]>R\[j\],k为分割点

因此每次只需计算 k−i\+1

在代码中，由于归并时重置了索引，L和R都是从0开始，因此，当出现逆序时(L\[i\]>R\[j\])，先计算L的长度为n1=q−p\+1，然后减去出现逆序的位置i，得到L\[i..q\]的元素的个数。

#include <iostream>
    #include <vector>
    using namespace std;
    class Solution {
    
    private:
        int count;
        void MergeSort(vector<int>&a, int p, int r)
        {
            if (p < r)
            {
                int q = p + (r - p) / 2;
                MergeSort(a, p, q);
                MergeSort(a, q + 1, r);
                Merge(a, p, q, r);
            }
        }
        void Merge(vector<int>&a, int p, int q, int r)
        {
            int n1 = q - p + 1;
            int n2 = r - q;
            vector<int>L(n1 + 1);
            vector<int>R(n2 + 1);
            L[n1] = numeric_limits<int>::max();
            R[n2] = numeric_limits<int>::max();
            for (int i = 0; i < n1; ++i)
                L[i] = a[p + i];
            for (int i = 0; i < n2; ++i)
                R[i] = a[q + i + 1];
            int i = 0;
            int j = 0;
            for (int k = p; k <= r; ++k)
            {
                if (L[i] <= R[j])
                    a[k] = L[i++];
                else
                {
                    a[k] = R[j++];
                    count += (q - i + 1 - p);
                    if(count>1000000007)
                        count%=1000000007;
                }
            }
        }
    public:
        int InversePairs(vector<int> data) {
            vector<int>a;
            a.swap(data);
            count = 0;
            MergeSort(a, 0, a.size() - 1);
            return count;
        }
    };

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

## **两个链表的第一个公共节点** ##

两个链表最终汇聚成一股，节点串成Y字型。

class Solution {
    public:
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            ListNode*pa=pHead1;
            ListNode*pb=pHead2;
            while(pa!=pb){
                pa=pa?pa->next:pHead2;
                pb=pb?pb->next:pHead1;
            }
            return pa;
        }
    };

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

## **数字在排序数组中出现的次数** ##

统计个数就是hash，这里条件给定了排序数组，可以不必额外的空间了。用二分找到上下界即可。

由于上下界算法查找得到的是开区间，因此要对特殊情况，例如\[6,6,6\] 6这种情况进行处理。

class Solution {
    private:
        int lower(const vector<int>&a, const int &k)
        {
            if (k <= a[0])
                return -1;
            int l = 0;
            int r = a.size() - 1;
            int m = l + (r - l+1) / 2;
            while (l < r)
            {
                if (a[m] < k)
                    l = m;
                else
                    r = m - 1;  
                m = l + (r - l + 1) / 2;
            }
            return m;
        }
        int upper(const vector<int>&a, const int &k)
        {
            if (k >= a[a.size() - 1])
                return a.size();
            int l = 0;
            int r = a.size() - 1;
            int m = l + (r - l) / 2;
            while (l < r)
            {
                if (a[m] > k)
                    r = m;
                else
                    l = m + 1;
                m = l + (r - l) / 2;
            }
            return m;
        }
    public:
        int GetNumberOfK(vector<int> data, int k) {
            if (data.size() == 0)
                return 0;
            vector<int>a;
            a.swap(data);
            int l = lower(a, k);
            int r = upper(a, k);
            return r - l - 1;
        }
    };

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

## **二叉树的深度** ##

广度优先搜索和深度优先搜索都可以做。

广度优先搜索，求出层数即可：

class Solution {
    private:
        int count;
        void bfs(TreeNode * root)
        {
            queue<TreeNode *>q;
            q.push(root);
            while (!q.empty())
            {
                int len = q.size();
                ++count;
                while (len--)
                {
                    TreeNode * p = q.front();
                    q.pop();
                    if (p->left != nullptr)
                        q.push(p->left);
                    if (p->right != nullptr)
                        q.push(p->right);
                }
            }
        }
    public:
        int TreeDepth(TreeNode* pRoot)
        {
            if(pRoot==nullptr)
                return 0;
            count = 0;
            bfs(pRoot);
            return count;
        }
    };

深度优先搜索是分别递归左右子树，得到左右子树的深度，然后左右子树深度选较大者加一，表示加上根节点以后树的深度。

class Solution {
    private:
        int dfs(TreeNode *root)
        {
            if (root == nullptr)
                return 0;
            int l = dfs(root->left);
            int r = dfs(root->right);
            return max(l, r) + 1;
        }
    public:
        int TreeDepth(TreeNode* pRoot)
        {
            return dfs(pRoot);
        }
    };

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

## **数组中只出现1一次的两个数字** ##

除了出现1次的两个数字，其他数字出现2次。  
相同的数字异或为0，这样，遍历数组两两异或将得到一个结果，这个结果肯定是一个非0的数，这个数是由数组唯2出现一次的数得来，找到这个数的二进制位第一个不为0的位，将这个数组划分为两个子数组，就能分别找到这两个数。

总体来说就四步：  
step1：遍历数组，两两异或得到num1和num2异或的结果tmp  
step2：找到tmp的二进制位中第一个出现的1 bit位idx  
step3：根据这个idx位是否为1将原数组划分为两个子数组  
step4：两个子数组分别做step1操作，得到的结果为num1和num2

class Solution {
    public:
        void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
            int tmp = 0;
            //step 1
            for (auto i : data)
                tmp ^= i;
            //step 2
            int idx = 0;
            while ((tmp & 1) == 0)
            {
                tmp >>= 1;
                ++idx;
            }
            //step 3
            vector<int>v1;
            vector<int>v2;
            v1.reserve(data.size());
            v2.reserve(data.size());
    
            for (auto i : data)
            {
                if (((i >> idx) & 1) == 1)
                    v1.push_back(i);
                else
                    v2.push_back(i);
            }
            //step 4
            *num1 = 0;
            for (auto i : v1)
                *num1 ^= i;
            *num2 = 0;
            for (auto i : v2)
                *num2 ^= i;
        }
    };