Java实现微信抢红包
【摘要】 抢红包的这个问题，最最开始关注是因为阿里的场景面试题提到过的当时的代码处理还很简单，先从普通场景探索下红包问题拼手气红包–线性切割法场景:100块钱红包，群内50人，红包数量为20个，30个人将抢不到红包这个算法可以把总金额想象成一条线段，每个人都有机会切一刀，前面的人切完(有失公平性，会出现第一个切一大段的情况，后面需要改造)，剩下的后面的人再接着切剩下的，这样越是前面的人截取的长度（理解...
抢红包的这个问题，最最开始关注是因为阿里的场景面试题提到过的
当时的代码处理还很简单，先从普通场景探索下红包问题
拼手气红包–线性切割法
场景:100块钱红包，群内50人，红包数量为20个，30个人将抢不到红包
这个算法可以把总金额想象成一条线段，每个人都有机会切一刀，前面的人切完(有失公平性，会出现第一个切一大段的情况，后面需要改造)，剩下的后面的人再接着切剩下的，这样越是前面的人截取的长度（理解成领取到的红包金额）越大的概率就越大。
//线段切割法
public static void lineSegmentCutting(double money, int number) {
if (money < 0 && number < 1) System.out.println("输入错误！");
double begin = 0, end = money;
double y = 0;
List<Double> list = new ArrayList<>();
for (int i = 0; i < number - 1; i++) {
double nn = 0;
double amount = nextDouble(begin, end);
nn = amount - begin;
System.out.println("第" + (i + 1) + "个人领取的红包金额为：" + format(nn));
y += nn;
begin = amount;
list.add(nn);
}
System.out.println("第" + number + "个人领取的红包金额为：" + format(end - begin));
Double max = Collections.max(list);
System.out.println("线段切割法手气最佳！！！" + format(max));
y += (end - begin);
System.out.println("验证发出的红包总金额为：" + format(y));
}
第1个人领取的红包金额为：148.49
第2个人领取的红包金额为：1.16
第3个人领取的红包金额为：12.14
第4个人领取的红包金额为：27.32
第5个人领取的红包金额为：3.76
第6个人领取的红包金额为：5.34
第7个人领取的红包金额为：1.28
第8个人领取的红包金额为：0.39
第9个人领取的红包金额为：0.09
第10个人领取的红包金额为：0.01
第11个人领取的红包金额为：0.01
第12个人领取的红包金额为：0.00
第13个人领取的红包金额为：0.00
第14个人领取的红包金额为：0.00
第15个人领取的红包金额为：0.00
第16个人领取的红包金额为：0.00
第17个人领取的红包金额为：0.00
第18个人领取的红包金额为：0.00
第19个人领取的红包金额为：0.00
第20个人领取的红包金额为：0.00
线段切割法手气最佳！！！148.49
验证发出的红包总金额为：200.00
问题:如何保证20个人都能抢到红包？
2.二倍均值法
这是一种很合理很公平的抢红包算法了
在此我们假设
红包剩余金额为 M
红包剩余数量为 N
这种算法就是每次都在区间[0,M/N×2] 随机取一个数
假设100元红包发10个人，那么合理的做法应该是每个人领到10元的概率相同。
第一个人随机金额的范围为[0,100/10×2] ,也就是[0,20],这样平均可以领到10元，此时剩余金额为100-10=90。
第二个人随机金额的范围为[0,90/9×2] ,也就是[0,20],这样平均也可以领到10元，此时剩余金额为90-10=80。
第三个人随机金额的范围为[0,80/8×2] ,也就是[0,20],这样平均也可以领到10元。
//二倍均值法
public static List doubleMeanMethod(double money, int number) {
List result = new ArrayList();
if (money < 0 && number < 1)
return null;
double amount, sum = 0;
int remainingNumber = number;
int i = 1;
List<Double> list = new ArrayList<>();
while (remainingNumber > 1) {
amount = nextDouble(0.01, 2 * (money / remainingNumber));
sum += amount;
System.out.println("第" + i + "个人领取的红包金额为：" + format(amount));
money -= amount;
remainingNumber--;
result.add(amount);
i++;
list.add(amount);
}
result.add(money);
System.out.println("第" + i + "个人领取的红包金额为：" + format(money));
Double max = Collections.max(list);
System.out.println("二倍均值法手气最佳！！！" + format(max));
sum += money;
System.out.println("验证发出的红包总金额为：" + format(sum));
return result;
}
运行结果:
请输入红包总金额：200
请输入红包数量：20
第1个人领取的红包金额为：0.48
第2个人领取的红包金额为：16.39
第3个人领取的红包金额为：7.44
第4个人领取的红包金额为：15.50
第5个人领取的红包金额为：15.48
第6个人领取的红包金额为：0.82
第7个人领取的红包金额为：0.05
第8个人领取的红包金额为：19.11
第9个人领取的红包金额为：2.67
第10个人领取的红包金额为：0.55
第11个人领取的红包金额为：13.09
第12个人领取的红包金额为：23.05
第13个人领取的红包金额为：7.78
第14个人领取的红包金额为：10.44
第15个人领取的红包金额为：19.88
第16个人领取的红包金额为：0.92
第17个人领取的红包金额为：12.22
第18个人领取的红包金额为：12.73
第19个人领取的红包金额为：3.06
第20个人领取的红包金额为：18.33
二倍均值法手气最佳！！！23.05
验证发出的红包总金额为：200.00
3.等值红包
场景:红包总额为100，群内人数为20人，需要每个人都为5块钱
/*
* 等值红包
* */
public static void average(double money, int number) {
BigDecimal count = BigDecimal.valueOf(money);
if (money < 0 && number < 1) System.out.println("输入错误！");
BigDecimal y =new BigDecimal(0) ;
BigDecimal num = BigDecimal.valueOf(number);
for (int i = 0; i < number ; i++) {
BigDecimal divide = count.divide(num,2,BigDecimal.ROUND_HALF_UP);
System.out.println("第" + (i + 1) + "个人领取的红包金额为：" + divide);
y=y.add(divide);
}
System.out.println("等值红包验证发出的红包总金额为：" + y);
}
运行结果:
第1个人领取的红包金额为：5.00
第2个人领取的红包金额为：5.00
第3个人领取的红包金额为：5.00
第4个人领取的红包金额为：5.00
第5个人领取的红包金额为：5.00
第6个人领取的红包金额为：5.00
第7个人领取的红包金额为：5.00
第8个人领取的红包金额为：5.00
第9个人领取的红包金额为：5.00
第10个人领取的红包金额为：5.00
第11个人领取的红包金额为：5.00
第12个人领取的红包金额为：5.00
第13个人领取的红包金额为：5.00
第14个人领取的红包金额为：5.00
第15个人领取的红包金额为：5.00
第16个人领取的红包金额为：5.00
第17个人领取的红包金额为：5.00
第18个人领取的红包金额为：5.00
第19个人领取的红包金额为：5.00
第20个人领取的红包金额为：5.00
等值红包验证发出的红包总金额为：100.00
但问题是如果200块，发214人，出现小数时需要保留2位小数出现精度损失导致总额不够200块如何解决？
ps:报错
BigDecimal divide = count.divide(num);
java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result
原因:JAVA中如果用BigDecimal做除法的时候一定要在divide方法中传递第二个参数，定义精确到小数点后几位，否则在不整除的情况下，结果是无限循环小数时，就会抛出以上异常
改为以上的
BigDecimal divide = count.divide(num,2,BigDecimal.ROUND_HALF_UP);
第212个人领取的红包金额为：0.93
第213个人领取的红包金额为：0.93
第214个人领取的红包金额为：0.93
等值红包验证发出的红包总金额为：199.02
那么出现不能整除的小数时，即便是BigDecimal 进行计算，保留2位小数后仍有精度损失，那么微信是如何解决的？
微信直接变更场景
将每个红包的金额由用户定义
public static void averageByCustom(double money, int number) {
System.out.println("红包总金额为：" + format(money*number));
}
此处加format，不加的话需要转为BigDecimal进行计算，精度计算会保留超过既定金额
完整代码
import java.math.BigDecimal;
import java.util.*;
/**
* 生成min到max范围的浮点数
**/
public class redEnvelope {
public static double nextDouble(final double min, final double max) {
return min + ((max - min) * new Random().nextDouble());
}
public static String format(double value) {
return new java.text.DecimalFormat("0.00").format(value); // 保留两位小数
}
//二倍均值法
public static List doubleMeanMethod(double money, int number) {
List result = new ArrayList();
if (money < 0 && number < 1)
return null;
double amount, sum = 0;
int remainingNumber = number;
int i = 1;
List<Double> list = new ArrayList<>();
while (remainingNumber > 1) {
amount = nextDouble(0.01, 2 * (money / remainingNumber));
sum += amount;
System.out.println("第" + i + "个人领取的红包金额为：" + format(amount));
money -= amount;
remainingNumber--;
result.add(amount);
i++;
list.add(amount);
}
result.add(money);
System.out.println("第" + i + "个人领取的红包金额为：" + format(money));
Double max = Collections.max(list);
System.out.println("二倍均值法手气最佳！！！" + format(max));
sum += money;
System.out.println("验证发出的红包总金额为：" + format(sum));
return result;
}
//线段切割法
public static void lineSegmentCutting(double money, int number) {
if (money < 0 && number < 1) System.out.println("输入错误！");
double begin = 0, end = money;
double y = 0;
List<Double> list = new ArrayList<>();
for (int i = 0; i < number - 1; i++) {
double nn = 0;
double amount = nextDouble(begin, end);
nn = amount - begin;
System.out.println("第" + (i + 1) + "个人领取的红包金额为：" + format(nn));
y += nn;
begin = amount;
list.add(nn);
}
System.out.println("第" + number + "个人领取的红包金额为：" + format(end - begin));
Double max = Collections.max(list);
System.out.println("线段切割法手气最佳！！！" + format(max));
y += (end - begin);
System.out.println("验证发出的红包总金额为：" + format(y));
}
/*
* 等值红包
* */
public static void average(double money, int number) {
BigDecimal count = BigDecimal.valueOf(money);
if (money < 0 && number < 1) System.out.println("输入错误！");
BigDecimal y =new BigDecimal(0) ;
BigDecimal num = BigDecimal.valueOf(number);
for (int i = 0; i < number ; i++) {
BigDecimal divide = count.divide(num,2,BigDecimal.ROUND_HALF_UP);
System.out.println("第" + (i + 1) + "个人领取的红包金额为：" + divide);
y=y.add(divide);
}
System.out.println("等值红包验证发出的红包总金额为：" + y);
}
/*
* 等值红包用户定义单个金额大小
* */
/**
* 功能描述:
* @Param: [money:单个金额, number：红包个数]
* @Return: void
* @Author: zhaozhenkun
* @Date: 2021/2/22 11:27
*/
public static void averageByCustom(double money, int number) {
System.out.println("红包总金额为：" + format(money*number));
}
/**
* 拆红包
* @param price 红包总金额
* @param person 红包个数
*/
public static void grapRed(int price,int person){
List<BigDecimal> moneys = math(BigDecimal.valueOf(price), person);
if (moneys != null) {
BigDecimal b = new BigDecimal(0);
int num = 1;
for (BigDecimal bigDecimal : moneys) {
System.out.println("第" + num + "个人抢到：" + bigDecimal + "元 ");
b = b.add(bigDecimal);
num++;
}
for (int i = 0;i < moneys.size(); i++) {
BigDecimal bigDecimal = moneys.get(i);
if (bigDecimal.equals(Collections.max(moneys))) {
System.out.println("最大金额是第"+(i + 1)+"个人，" + "最佳手气:" + Collections.max(moneys));
}
}
//验证红包总值
System.out.println("红包总额:" + b + "元 ");
}
}
/**
* 单个红包0.01
* @param redPrice 红包总额
* 人数
* @return
*/
public static List<BigDecimal> math(BigDecimal redPrice, int personNumber) {
//发红包最少0.01*personNumber
if (redPrice.doubleValue() < personNumber * 0.01) {
return null;
}
Random random = new Random();
int money = redPrice.multiply(BigDecimal.valueOf(100)).intValue();
double count = 0;
double[] arrRandom = new double[personNumber];
List<BigDecimal> arrMoney = new ArrayList<BigDecimal>(personNumber);
for (int i = 0; i < arrRandom.length; i++) {
int r = random.nextInt((personNumber) * 99) + 1;
count += r;
arrRandom[i] = r;
}
int c = 0;
for (int i = 0; i < arrRandom.length; i++) {
Double x = new Double(arrRandom[i] / count);
int m = (int) Math.floor(x * money);
if (m == 0) {
m = 1;
}
c += m;
if (i < arrRandom.length - 1) {
arrMoney.add(new BigDecimal(m).divide(new BigDecimal(100)));
} else {
arrMoney.add(new BigDecimal(money - c + m).divide(new BigDecimal(100)));
}
}
Collections.shuffle(arrMoney);
return arrMoney;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("这是一段模拟抢红包的代码。");
/* int number;
double money;
System.out.print("请输入红包总金额：");
money = sc.nextDouble();
System.out.print("请输入红包数量：");
number = sc.nextInt();*/
//System.out.println(money + " " + number);
/* //二倍均值法
doubleMeanMethod(money, number);
//System.out.println(doubleMeanMethod(money,number).toString());
System.out.println();
//线段切割法
lineSegmentCutting(money, number);
System.out.println();
average(money,number);*/
// averageByCustom(money, number);
grapRed(100,20);
}
}
抢红包的实际面试题，本公众号的阿里面试题
题目：写一个发红包程序，连续发N次红包（每次红包总金额相同），每个红包随机分给M个人
要求
（1）最大红包金额不能超过红包总金额的90%；
（2）连续N次发红包，获得最佳手气（红包金额最高）的人，得到最佳手气的次数不超过总次数的30%；
（3）单个红包最小1分钱；
1.控制最大红包金额
2.控制最佳手气人次数
3.最小包1分钱
抢红包数据线性分析
可以参考下抢红包的大数据分析，根据抢红包的线性分布来参考下最公平的算法
1最公平的算法是二倍均值算法，能够避免第N个过大或过小问题
或者算出平均值，在平均值上加钱
2.如果出现两个相同大小金额如何处理？
如果存在相同最大金额则重新计算
3.如果全部处理完还剩余钱怎么办？
将钱加到小红包里
4.如果钱是负数怎么办？
从小红包里将钱抽取出来
/**
* 拆红包
* @param price 红包总金额
* @param person 红包个数
*/
public static void grapRed(int price,int person){
List<BigDecimal> moneys = math(BigDecimal.valueOf(price), person);
if (moneys != null) {
BigDecimal b = new BigDecimal(0);
int num = 1;
for (BigDecimal bigDecimal : moneys) {
System.out.println("第" + num + "个人抢到：" + bigDecimal + "元 ");
b = b.add(bigDecimal);
num++;
}
for (int i = 0;i < moneys.size(); i++) {
BigDecimal bigDecimal = moneys.get(i);
if (bigDecimal.equals(Collections.max(moneys))) {
System.out.println("最大金额是第"+(i + 1)+"个人，" + "最佳手气:" + Collections.max(moneys));
}
}
//验证红包总值
System.out.println("红包总额:" + b + "元 ");
}
}
/**
* 单个红包0.01
* @param redPrice 红包总额
* 人数
* @return
*/
public static List<BigDecimal> math(BigDecimal redPrice, int personNumber) {
//发红包最少0.01*personNumber
if (redPrice.doubleValue() < personNumber * 0.01) {
return null;
}
Random random = new Random();
int money = redPrice.multiply(BigDecimal.valueOf(100)).intValue();
double count = 0;
double[] arrRandom = new double[personNumber];
List<BigDecimal> arrMoney = new ArrayList<BigDecimal>(personNumber);
for (int i = 0; i < arrRandom.length; i++) {
int r = random.nextInt((personNumber) * 99) + 1;
count += r;
arrRandom[i] = r;
}
int c = 0;
for (int i = 0; i < arrRandom.length; i++) {
Double x = new Double(arrRandom[i] / count);
int m = (int) Math.floor(x * money);
if (m == 0) {
m = 1;
}
c += m;
if (i < arrRandom.length - 1) {
arrMoney.add(new BigDecimal(m).divide(new BigDecimal(100)));
} else {
arrMoney.add(new BigDecimal(money - c + m).divide(new BigDecimal(100)));
}
}
Collections.shuffle(arrMoney);
return arrMoney;
}
运行结果:100块.20个人抢
第1个人抢到：5.76元
第2个人抢到：3.89元
第3个人抢到：6.7元
第4个人抢到：6.35元
第5个人抢到：4.03元
第6个人抢到：2.55元
第7个人抢到：3元
第8个人抢到：8.13元
第9个人抢到：4.07元
第10个人抢到：0.4元
第11个人抢到：8.08元
第12个人抢到：3.91元
第13个人抢到：1.65元
第14个人抢到：8.92元
第15个人抢到：6.5元
第16个人抢到：4.69元
第17个人抢到：4.26元
第18个人抢到：1.56元
第19个人抢到：8.86元
第20个人抢到：6.69元
最大金额是第14个人，最佳手气:8.92
红包总额:100.00元
找大佬请教的代码
import org.apache.commons.lang3.RandomUtils;
import java.util.*;
public class SimpleRedRnvelopes {
private Map<Integer, Integer[]> mPriceMapper = new HashMap<>();
private Map<Integer, Integer> top = new HashMap<>();
private Map<Integer,Integer> everyTop = new HashMap<>();
public int getRandomForIntegerBounded(int min, int max) {
int intBounded = RandomUtils.nextInt(min, max);
return intBounded;
}
public SimpleRedRnvelopes(double mRedRnvelopesPrice, int m, int n) {
if (m <= 0 || n <= 0 || m < 2 || (mRedRnvelopesPrice * 100 < m)) {
throw new IllegalArgumentException();
}
//总抢红包金额(分)，每个人默认已经抢到了1分 一定为整数
int price = (int) (mRedRnvelopesPrice * 100 - m);
//剩余金额、按分取整。保留整数部分 如果超过了整数部分 那么一定是超额了
int maxPrice = (int) (mRedRnvelopesPrice * 100 * 0.9);
System.out.println("可抢总金额：" + price + " 单人最大金额: " + maxPrice);
for (int i = 0; i < n;) {
Integer priceList[] = new Integer[m];
int surplus = price; //剩余
for (int j = 0; j < m - 1; ) {
if (surplus == 0) {
priceList[j] = 1;
} else {
int snagging = genPrice(surplus, m, maxPrice).get(getRandomForIntegerBounded(0, m));
// int snagging = getRandomForIntegerBounded(0,surplus + 1);
if (snagging > (maxPrice - 1)) {
continue;
}
surplus -= snagging;
priceList[j] = snagging + 1;
}
j++;
}
priceList[m - 1] = surplus + 1;
//获取手气最佳
int max = Arrays.asList(priceList).stream().mapToInt(x -> x).max().getAsInt();
int passengerIndex = getMaxIndex(priceList,max);
if(top.containsKey(passengerIndex)){
if((top.get(passengerIndex) + 1) > n * 0.3){
continue;
}
Integer topCount = top.get(passengerIndex);
topCount = new Integer(topCount + 1);
}else {
top.put(passengerIndex,1);
}
i++;
mPriceMapper.put(i, priceList);
everyTop.put(i,passengerIndex);
}
}
public int getMaxIndex(Integer[] list,int max){
for(int i = 0;i < list.length;i++){
if(list[i] == max){
return i;
}
}
throw new RuntimeException();
}
/**
* 考虑到第一个人抢到到金额概率永远大于后面的人(金额大小结果随着人数依次递减)，简单的随机数算法
* @return
*/
public List<Integer> genPrice(int price, int m, int maxPrice) {
List<Integer> priceList = new ArrayList();
int surplus = price;
int max = 0; //不能同时存在那个相同的最大值,存在相同的最大值需要重算
for (int j = 0; j < m;) {
int snagging = getRandomForIntegerBounded(0, surplus + 1);
if (snagging > (maxPrice - 1)) {
continue;
}
surplus -= snagging;
priceList.add(snagging);
j++;
}
Collections.shuffle(priceList);
return priceList;
}
public void print() {
for (Map.Entry<Integer, Integer[]> c : mPriceMapper.entrySet()) {
int sum = Arrays.asList(c.getValue()).stream().mapToInt(x -> x).sum();
Integer key = c.getKey();
System.out.println(c.getKey() + " 金额数据:" + Arrays.asList(c.getValue()) + " Sum: " + sum + " 手气最佳为第:" + everyTop.get(c.getKey())+"人");
}
}
public static void main(String[] args) {
//金额，人数，次数
new SimpleRedRnvelopes(100, 10, 1).print();
}
}
运行结果:
1 金额数据:[2, 4, 13, 1, 14, 2793, 1, 120, 1, 7051] Sum: 10000 手气最佳为第:9人
2 金额数据:[2488, 495, 22, 2, 5493, 663, 8, 1, 7, 821] Sum: 10000 手气最佳为第:4人
3 金额数据:[2240, 5, 40, 110, 1, 4695, 2451, 9, 1, 448] Sum: 10000 手气最佳为第:5人
4 金额数据:[18, 773, 2535, 1, 4, 2376, 15, 111, 1710, 2457] Sum: 10000 手气最佳为第:2人
5 金额数据:[1153, 5333, 169, 4, 364, 159, 3, 98, 204, 2513] Sum: 10000 手气最佳为第:1人
参考文章
https://www.meipian.cn/cea2ksx 抢红包大数据分析
https://www.zhihu.com/question/22625187?sort=created 微信的红包算法
https://blog.csdn.net/paincupid/article/details/82054647 带红包上下限的算法
https://www.cnblogs.com/rutaha/p/14054156.html 抢红包算法
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）