面試場景題：如何設計一個紅包隨機算法

目前在阿里云的面試過程中遇到了這道算法題，今天搜了下解法，整理出來

面試官：咱來寫個算法題吧
設計一個搶紅包的隨機算法，比如一個人在群里發(fā)了100塊錢的紅包，群里有10個人一起來搶紅包，每人搶到的金額隨機分配。
1.所有人搶到的金額之和要等于紅包金額，不能多也不能少。
2.每個人至少搶到1分錢。
3.最佳手氣不超過紅包總金額的90%

解題思路1：隨機分配法

錢的單位轉換為分，每次在[1, leaveMoney]這個區(qū)間內隨機一個值，記為r；
計算一下剩余金額leaveMoney-r，剩余金額（單位：分）必須大于剩余人數，不然后面的人無法完成分配，例如10個人，有1個人搶了紅包，剩余的money至少還需要9分錢，不然剩余的9人無法分；
按照順序隨機n-1次，最后剩下的金額可以直接當做最后一個紅包，不需要隨機；

解題代碼：

 public static List<Double> generate(double totalMoney, int people) {
        // 轉換為分處理避免浮點誤差
        double totalCents = Math.round(totalMoney * 100);
        double maxLimit = (totalCents * 0.9); // 總金額的90%
        double leaveMoney = totalCents;
        List<Double> result = new ArrayList<>();
        //判斷錢不夠分,不處理
        if ((int)totalCents < people) {
            return result;
        }
        Random random = new Random();

        //每次生成隨機數
        int n = people - 1;
        while (n > 0) {
            //隨機數在[1, min(maxLimit, leaveMoney)]之間，單位是:分
            double min = Math.min(leaveMoney, maxLimit);
            double allocResult = 1 + random.nextInt((int)min);
            //判斷這次分配后，后續(xù)的總金額仍然可分，且不超過90%總金額
            if (allocResult > maxLimit || (leaveMoney - allocResult) < n) {
                continue;
            }
            leaveMoney -= allocResult;
            n--;
            result.add(allocResult / 100.0);
        }
        result.add(leaveMoney / 100.0);
        return result;
    }

以下是多次運行的結果：

[37.77, 50.76, 1.89, 7.89, 0.26, 0.24, 0.25, 0.78, 0.06, 0.1]
[89.38, 2.45, 3.5, 4.43, 0.03, 0.08, 0.06, 0.04, 0.01, 0.02]
[53.51, 40.86, 5.48, 0.04, 0.06, 0.01, 0.01, 0.01, 0.01, 0.01]
[42.71, 0.27, 38.99, 4.5, 4.02, 4.58, 2.97, 0.84, 0.21, 0.91]

通過多次運行的結果，可以看到越早搶紅包的人，搶到的金額越大，所以題目還可以變形

要求紅包金額分布均衡

面試官：繼續(xù)改進紅包生成算法，要求：
1.要保證紅包拆分的金額盡可能分布均衡，不要出現兩極分化太嚴重的情況。

解題思路2：二倍均值法

二倍均值法：假設剩余紅包金額為m元，剩余人數為n，那么有如下公式：

每次搶到的金額 = 隨機區(qū)間 [0.01，m /n × 2 - 0.01]元

這個公式，保證了每次隨機金額的平均值是相等的，不會因為搶紅包的先后順序而造成不公平。

舉個例子如下：

假設有5個人，紅包總額100元。100÷5×2 = 40，所以第1個人搶到的金額隨機范圍是[0.01，39.99]元，在正常情況下，平均可以搶到20元。
假設第1個人隨機搶到了20元，那么剩余金額是80元。80÷4×2 = 40，所以第2個人搶到的金額的隨機范圍同樣是[0.01，39.99]元，在正常的情況下，還是平均可以搶到20元。假設第2個人隨機搶到了20元，那么剩余金額是60元。60÷3×2 = 40，所以第3個人搶到的金額的隨機范圍同樣是[0.01，39.99]元，平均可以搶到20元。以此類推，每一次搶到金額隨機范圍的均值是相等的。

解題代碼：

public static List<Double> allocateRedEnvelop(double totalMoney, int people) {
        // 轉換為分處理避免浮點誤差
        double totalCents = Math.round(totalMoney * 100);
        double maxLimit = (totalCents * 0.9); // 總金額的90%
        Random random = new Random();
        double leaveMoney = totalCents;
        List<Double> result = new ArrayList<>();
        int n = people;
        //注意是大于1，最后1個人領取剩余的錢
        while (n > 1) {
            //生成隨機金額的范圍是[1, leaveMoney / n * 2 - 1]， 注意nextInt方法生成結果范圍是左閉右開的
            double allocatMoney = 1 + random.nextInt((int)leaveMoney / n * 2 - 1);
            result.add(allocatMoney / 100.0);
            n--;
            leaveMoney -= allocatMoney;
        }
        result.add(leaveMoney / 100.0);
        return result;
    }

生成結果測試如下，結果值比較隨機了，領取的紅包金額和先后順序無關了

[8.58, 4.56, 20.88, 13.83, 7.6, 3.94, 10.87, 8.66, 20.92, 0.16]
[3.31, 2.08, 15.99, 16.79, 13.13, 0.61, 17.38, 10.93, 4.93, 14.85]
[0.24, 21.86, 15.57, 16.86, 3.45, 3.18, 5.48, 13.01, 6.76, 13.59]

解題思路3：線段切割法

考慮一種新的解法，把紅包總金額想象成一條很長的線段，而每個人搶到的金額就是這條主線段上的某個子線段，如下圖：

假設有N個人一起搶紅包，紅包總金額為M，就需要確定N-1個切割點；
切割點的隨機范圍是（1，M），所有切割點確認后，子線段長度也就確定了
如果隨機切割點出現重復，則重新生成切割點

解題代碼如下：

    /**
     * 線段切割法
     */
    public static List<Double> allocateRedEnvelopNew(double totalMoney, int people) {
        // 轉換為分處理避免浮點誤差
        double totalCents = Math.round(totalMoney * 100);
        double maxLimit = (totalCents * 0.9); // 總金額的90%
        Random random = new Random();
        double leaveMoney = totalCents;
        List<Double> result = new ArrayList<>();
        Set<Integer> pointCutSet = new HashSet<>();
        int n = people;
        while (pointCutSet.size() < people - 1) {
            //生成n - 1個切割點，隨機點取值范圍是[1, totalCents]
            pointCutSet.add(random.nextInt((int) totalCents) + 1);
        }
        //接著生成對應子線段的錢數
        Integer[] points = pointCutSet.toArray(new Integer[0]);
        Arrays.sort(points);
        result.add(points[0] / 100.0);
        //子線段+ 最后那段的長度 = totalCents，注意上一步是已經加了points[0]，result中的所有元素和累加后的結果一定是totalCents,
        for (int i = 1; i < points.length; i++) {
            result.add((points[i] - points[i - 1]) / 100.0);
        }
        result.add((totalCents - points[points.length - 1]) / 100.0);
        return result;
    }

最后跑幾次看看生成的隨機效果，可以看到手氣最佳的有到37塊錢的，相比較二倍均值法，該方法手氣最佳獲取的金額可能更高

[20.24, 3.9, 7.63, 9.62, 15.41, 2.32, 0.21, 24.94, 9.66, 6.07]
[8.64, 33.55, 3.76, 15.35, 4.41, 9.85, 4.81, 15.9, 2.71, 1.02]
[11.31, 13.32, 16.53, 5.91, 8.69, 17.29, 11.09, 7.62, 7.14, 1.1]
[21.34, 8.24, 1.9, 7.98, 0.49, 0.32, 13.75, 37.27, 0.03, 8.68]

以上就是關于紅包隨機算法的所有解題方法了，面試中如果遇到考這道算法題，需要問清楚紅包隨機的情況，有沒有要求分布均衡。

如果覺得對面試有幫助的話，記得給文章點贊哦~

#軟件開發(fā)筆面經#