Java实现微信抢红包
抢红包的这个问题，最最开始关注是因为阿里的场景面试题提到过的
当时的代码处理还很简单，先从普通场景探索下红包问题
- 拼手气红包--线性切割法
场景: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.003.等值红包
场景:红包总额为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 抢红包算法本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-02-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读