8_其他.md

其他

1、洗牌算法

基本思想是：每次从一组数中随机选出一个数，然后与最后一个数交换位置，并且不再考虑最后一个数。

public class Shuffle {

    public void shuffle(int[] nums){
        Random random=new Random();
        for(int i=nums.length-1;i>=0;i--){
            //[0,i] 之中随机选择一个数
            int j=random.nextInt(i+1); // j 为[0,i] 中随机的下标
            swap(nums,i,j); // i 始终指向 [0,i] 的最后位置
        }
    }

    public void swap(int[] nums,int i,int j) {
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }

    @Test
    public void test(){
        int[] nums={1,2,3,4,5,6,7,8,9,10};
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        System.out.println();
        shuffle(nums);
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        System.out.println();
    }
}

1 2 3 4 5 6 7 8 9 10 
7 3 8 5 10 2 1 6 4 9

2、抢红包算法

线段切割法：在一条线段上找 (N-1) 个随机点，就可以将该线段随机且公平地切割成 N 段。

public class RedPacket {
    /**
     * @param n 抢红包人数
     * @param money 派发红包的金额
     *              如果是小数的话先转化为整数,相应的结果除以 100 即可
     * @return List 存储 n 个红包的金额
     */
    public List<Double> generatePocketByLineCutting(int n,double money){
        Random random=new Random();

        //如果是小数的话先转化为整数
        int newMoney=(int)money*100;

        //存储线段的的 (n-1) 个随机点，线段长度为 newMoney
        Set<Integer> set=new TreeSet<>();

        while(set.size()<n-1){ //当 set.size()==n-1 时,循环终止
            int point=random.nextInt(newMoney);
            set.add(point);
        }
        //TODO:加上终点
        set.add(newMoney);

        //存放是个红包的金额
        List<Double> res=new ArrayList<>();

        int pre=0;
        for(Integer p:set) {
            res.add((p - pre) * 1.0 / 100);
            pre = p;
        }
        return res;
    }

    @Test
    public void test(){
        int n=10;
        int money=100;
        List<Double> res=generatePocketByLineCutting(n,money);
        System.out.println(res);
        double sum=0.0;
        for(double d:res){
            sum+=d;
        }
        System.out.println(sum);
    }
}

[21.53, 10.59, 7.63, 24.2, 1.5, 3.7, 0.03, 18.49, 10.38, 1.95]
100.0