头像

Delayeddesire




离线:22天前



转载常见的几种概率面试题

常见的几种概率面试题




题目描述

  1. 给定数组A,大小为N,数字元素为1~N的int数,但是有些数字出现多次,有些数字没出现,统计出哪些数字出现了多次,哪些数字没有出现,要求额外空间使用O(1),时间O(N)。

解题思路

  1. 第一次遍历:对于每一个A[i] = A[i] * n。
  2. 第二次遍历:对于每一个i,A[A[i]/n]++。
  3. 第三次遍历:对于每一个i,A[i] % n就是出现次数。
#include <iostream>
#include <vector>
using namespace std;

// 模拟的数组
vector<int> arr = {1, 3, 1, 1, 3, 5, 4, 2, 6, 7};

int main()
{
    int n = arr.size();

    // 第一步:为每个元素乘上 n
    for(auto& e : arr) e *= n;      // 10 30 10 10 30 50 40 20 60 70 

    // 第二步:a[a[i] / n]++
    for(int i = 0; i < n; ++i)
    {
        arr[arr[i] / n]++;
    }                               // 10 33 11 12 31 51 41 21 60 70

    // 第三步:扫描数组,得出结果
    for(int i = 0; i < n; ++i)
    {
        int num = arr[i] % n;
        cout << i << " 出现的次数为 " << num << endl;
    }                               // 0 3 1 2 1 1 1 1 0 0


    return 0;
}



截屏2021-03-03 下午11.09.50.png
参考了其他同学的理解:itdef
截屏2021-03-03 下午11.24.46.png

// 动态规划
// 注意:注意表中的下标与字符串中的下标它们是不一样的,因为空串的存在,导致表中的下标
// 每次多一个单位。
class Solution {
public:
    bool isMatch(string s, string p) {
        // 定义状态
        // dp[n][m]表示 s 串的前 n 个字符和 p 串的前 m 个字符是否匹配
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));

        // 状态初始化
        // s 和 p 都是空串的时候能够匹配
        dp[0][0] = true;

        // s 串为空串的时候,p 串只有偶数位为 * 的时候才能够匹配。
        // 比如:.* / a* / a*b*d* 等(题目中说明了没有连续的 *)
        for(int i = 2; i <= m; i += 2)
            dp[0][i] = dp[0][i - 2] && p[i - 1] == '*';

        // 状态转移
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                // 由于空串占据了下标 0,因此在找字符的时候
                // 需要在填表的下标上减去一个单位,即dp中的j -> 字符串中的 j - 1
                if(p[j - 1] == '*')
                {
                    // ab / abc*
                    if(dp[i][j - 2])
                        dp[i][j] = true;
                    // abb / ab*
                    else if(dp[i - 1][j] && s[i - 1] == p[j - 2])
                        dp[i][j] = true;
                    // abb / a.*
                    else if(dp[i - 1][j] && p[j - 2] == '.')
                        dp[i][j] = true;
                }
                else 
                {
                    if(dp[i - 1][j - 1] && s[i - 1] == p[j - 1])
                        dp[i][j] = true;
                    else if(dp[i - 1][j - 1] && p[j - 1] == '.')
                        dp[i][j] = true;
                }
            }
        }

        // 返回最后一个状态
        return dp[n][m];
    }
};



class MaxQueue {
public:
    queue<int> que;         // 保存队列中所有的数子
    deque<int> maxque;      // 保存队列中最大的数字(两端操作为O(1))
    MaxQueue() {
    }

    int max_value() {
        return maxque.size() ? maxque.front() : -1;
    }

    void push_back(int value) {
        que.push(value);

        // 维护 maxque 为递减序列,每次可以输出当前队列中最大的数
        while(!maxque.empty() && maxque.back() < value)
            maxque.pop_back();

        maxque.push_back(value);
    }

    int pop_front() {
        if(que.empty())
            return -1;

        int result = que.front();
        que.pop();
        if(result == maxque.front())
            maxque.pop_front();

        return result;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */



8CCEF07FB09228E0CEB642F48DE67DAD.jpg

class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n == 1) return 0;

        return (lastRemaining(n - 1, m) + m) % n;
    }
};



// 动态规划
class Solution {
public:
    vector<double> dicesProbability(int n) {
        // 保存概率结果
        vector<double> result;

        // 判断边界条件
        if(n == 0)  return result;

        // 计算所有可能出现的情况
        double sum = pow(6, n);

        // 定义状态(dp[n][s]: 当有 n 个骰子的时候,和为 s 的情况的个数)
        vector<vector<int>> dp(n + 1, vector<int>(6 * n + 1, 0));

        // 状态初始化(dp[1][1] = 1, dp[1][2] = 1, ...)
        for(int i = 1; i <= 6; ++i)
            dp[1][i] = 1;

        // 状态转移(当有 2 个以上骰子的时候)
        // 枚举骰子的个数
        for(int i = 2; i <= n; ++i)
        {
            // 枚举各个骰子的总和
            for(int j = i; j <= 6 * n; ++j)     
            {
                // 枚举当前骰子所出现的数字
                for(int k = 1; k <= 6; ++k)
                {
                    if(j - k < 0) break;
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }

        // 计算和为 i 时所出现的情况占总情况的概率
        for(int i = n; i <= 6 * n; ++i)
            result.push_back(dp[n][i] * 1.0 / sum);

        return result;
    }
};



// 二分
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] != mid) r = mid;
            else l = mid + 1;
        }

        if(l == nums[l]) l++;

        return l;
    }
};
// 间隔法
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 第一个元素不是 0 的情况
        if(nums[0]) return 0;

        // 一般情况
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] - nums[i - 1] > 1)
            {
                return nums[i] - 1;
            }
        }

        return nums.size();
    }
};



// 三指针方法:2, 3, 5
class Solution {
public:
    int nthUglyNumber(int n) {
        // 判断边界条件
        if(n == 0)  return 0;

        // 保存所有结果集
        vector<int> result;
        result.push_back(1);

        // 三个指针从头开始遍历
        int i = 0, j = 0, k = 0;
        int index = n;
        while(n--)
        {
            int num = min(result[i] * 2, min(result[j] * 3, result[k] * 5));
            if(num == result[i] * 2) i++;
            if(num == result[j] * 3) j++;
            if(num == result[k] * 5) k++;

            result.push_back(num);
        }

        // 返回数组中最后一个元素
        return result[index - 1];
    }
};



// 哈希表法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 哈希表统计次数
        unordered_map<int, int> hash;
        for(auto& e : nums)
            hash[e]++;

        // 遍历哈希表
        int len = nums.size() / 2;
        for(auto& e : hash)
        {
            if(e.second > len)
                return e.first;
        }

        return 0;
    }
};
// 排序法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 对数组进行排序
        sort(nums.begin(), nums.end());

        // 返回最中间的数
        return nums[nums.size() / 2];
    }
};
// 摩尔投票法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 遍历数组中的元素
        int count = 0;
        int result = 0;
        for(auto& e : nums)
        {
            if(count <= 0)
                result = e;

            if(result == e)
                count++;
            else
                count--;
        }

        return result;
    }
};



// 暴力搜索
class Solution {
public:
    vector<string> result;
    string str;
    vector<int> flag;  // 记录已经使用过的字符
    vector<string> permutation(string s) {
        // 判断边界条件
        if(s == "")
            return result;

        // 是相同的元素在一起
        sort(s.begin(), s.end());

        // 初始化标记数组
        flag.resize(s.size(), 1);

        // 暴力搜索
        dfs(s, 0, s.size());

        // 返回所有结果集
        return result;
    }

    void dfs(string s, int start, int len)
    {
        // 当前搜索的长度已经满足要求
        if(start == len)
        {
            result.push_back(str);
            return;
        }

        for(int i = 0; i < len; ++i)
        {
            // 前一个相同的元素没有使用时,当前元素不能先使用
            // 等下一轮递归进行的时候从头遍历开始进行使用
            if(i && s[i] == s[i - 1] && flag[i - 1] == 1)
            {
                continue;
            }

            if(flag[i] == 1)
            {
                str += s[i];
                flag[i] = 0;
                dfs(s, start + 1, len);

                // 恢复原有状态
                flag[i] = 1;
                str.pop_back();
            }
        }

        return ;
    }
};