0720学习

agile Posted on Jul 20 2023

面试 leetcode学习

-   剑指 Offer 49. 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:  
1 是丑数。
n 不超过1690。

---

![WX20230720-1529202x.png](https://tools.nxcloud.club:12500/images/2023/07/20/WX20230720-1529202x.png)

---

```C#
public int NthUglyNumber(int n)
{
    var priorityQueue = new PriorityQueue<long, long>();
    priorityQueue.Enqueue(1, 1);
    var set = new HashSet<long> { 1 };
    var field = new int[] { 2, 3, 5 };
    int ugly = 1;
    for (var i = 0; i < n; i++)
    {
        var longUgly = priorityQueue.Dequeue();
        ugly = (int)longUgly;
        foreach (var t in field)
        {
            var v2 = longUgly * t;
            if (!set.Contains(v2))
            {
                priorityQueue.Enqueue(v2, v2);
            }

set.Add(v2);
        }
    }

return ugly;
}

public int NthUglyNumber2(int n)
{
    var dp = new int[n];
    dp[0] = 1;
    var d2 = 0;
    var d3 = 0;
    var d5 = 0;
    for (int i = 1; i < n; i++)
    {
        var d2V = dp[d2] * 2;
        var d3V = dp[d3] * 3;
        var d5V = dp[d5] * 5;
        var minDp = Math.Min(d2V, Math.Min(d3V, d5V));
        if (minDp == d2V)
        {
            d2++;
        }

if (minDp == d3V)
        {
            d3++;
        }

if (minDp == d5V)
        {
            d5++;
        }

dp[i] = minDp;
    }

return dp[n-1];
}
```

-   剑指 Offer 60. n 个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
限制：
1 <= n <= 11

---

投掷 n 个骰子，一共会有 6 的 n 次方 种结果，且每种结果都是等可能事件。
投掷 n 个骰子，那么就会有 n 个面朝上，这 n 个朝上的面的点数之和 s 的最大值是 6n，最小值是 n。故投掷 n 个骰子，s 一共有 6n - n + 1 个可能的值（所以题目所要我们返回的浮点数组的大小就是 n * 6 - n + 1。

---

```C#
public double[] DicesProbability(int n)
{
    var dp = new double[6];
    Array.Fill(dp, 1.0 / 6.0); // 这是第一轮掷骰子的结果
    for (var i = 2; i <= n; i++) // 开始计算第2轮至第n轮掷骰子的结果
    {
        var temp = new double[i * 5 + 1]; // 初始化一个容器存储本轮的全部概率，容器大小按照5*i+1计算
        for (int j = 0; j < dp.Length; j++) //遍历上一次dp
        {
            for (int k = j; k < j + 6; k++) // 上一轮容器的每个和值，都可对本轮的6个和值产生影响，位置范围为[j,j+5]
            {
                temp[k] += dp[j] / 6.0; // 这里除以6.0的意思是，基于上一轮的和值，在本轮投出1-6中某个点数的概率应该是：上一轮概率*(1/6)
            }
        }

dp = temp;
    }

return dp;
}
```