算法笔记-数学/采样

主要用于记录刷题过程中遇到的一些数学题型的求解方法

排列组合

1、从n个不同元素中取出m（m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A（n,m）表示。

2、从n个不同元素中，任取m（m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m（m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C（n,m） 表示。

等差等比求和

小技巧，字符串转整数

1
2
int x = 0;
for(int i=0;i<size;i++)x=x*10+str.charAt(i)-'0';

变量交换

如何不使用第三个变量来交换两个数的值 ？

  1. 数学
1
2
3
4
a=10,b=20
a=a+b=30
b=a-b=30-20=10
a=a-b=30-10=20
  1. 位运算(异或)
1
2
3
4
a=10,b=20
a=a^b
b=a^b
a=a^b

最小公倍

1
2
3
4
5
6
7
8
9
10
11
public  int commonMultiple(int n, int m) {// 求两个数的最小公倍数
    return n * m / commonDivisor(n, m);
}
public  int commonDivisor(int n, int m) {// 求两个数的最大公约数
    while (n % m != 0) {
        int t = n % m;
        n = m;
        m = t;
    }
    return m;
}

相关题目

Sqrt(x)（easy）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    //二分查找
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
    //牛顿迭代法求平方根
    public int mySqrt(int x) {
        if (x == 0) return 0;
        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) break;
            x0 = xi;
        }
        return (int) x0;
    }
}

指数幂

1

剑指 Offer 64. 求1+2+…+n

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    //递归
    public int sumNums(int n) {
        boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
        return n;
    }
    //等差数列求和
    public int sumNums(int n) {
        return (int) (Math.pow(n, 2) + n) >> 1;
    }
}

用 Rand7() 实现 Rand10()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//1.如何利用一个小范围随机数，得到一个大范围等概率随机数？
//采用随机数的 k 进制，对于 randN，采用 N 进制，即：(randN - 1) * N + randN 得到了一个 N*N 范围的等概率随机数，如果还不够大，可以继续在 randN 或生成的 randN*N 上使用这个

//思路：
class Solution extends SolBase {
    public int rand10() {
        int row, col, idx;
        do {
            row = rand7();
            col = rand7();
            idx = col + (row - 1) * 7;//(randN - 1) * N + randN 得到 N*N范围的数 即7*7=49
        } while (idx > 40);//大于40拒绝采样
        return 1 + (idx - 1) % 10;
    }
}

字符串相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public String multiply(String num1, String num2) {
    if("0".equals(num1)||"0".equals(num2))return "0";
    int m = num1.length();
    int n = num2.length();
    int[] ans = new int[m+n];
    //计算
    for(int i=n-1,k = m+n-1;i>=0;i--,k--){
        int nc = num2.charAt(i)-48;//乘数
        int multiplyCarry = 0;//相乘的进位
        int addCarry = 0;//相加的进位
        int l=k;
        for(int j=m-1;j>=0;j--,l--){
            int mc = num1.charAt(j)-48;//被乘数
            int value = nc*mc + multiplyCarry;
            multiplyCarry = 0;
            if(value>9){
                multiplyCarry = value/10;
                value = value%10;
            }
            int out = ans[l]+value+addCarry;
            addCarry=0;
            if(out>9){
                addCarry = 1;
                out = out-10;
            }
            ans[l]= out;
        }
        if(multiplyCarry!=0)ans[l]=multiplyCarry;
        if(addCarry!=0)ans[l]+=addCarry;
    }
    //构建返回值
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < ans.length; i++) sb.append(ans[i]);
    if (sb.charAt(0)=='0')sb.deleteCharAt(0);
    return sb.toString();
}

36进制加法/字符串相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
		//十进制
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int n1Index = num1.length()-1;
        int n2Index = num2.length()-1;
        int carry = 0;
        while(n1Index>=0||n2Index>=0){
            int n1 = n1Index >= 0 ? num1.charAt(n1Index)-'0' : 0;
            int n2 = n2Index >= 0 ? num2.charAt(n2Index)-'0' : 0;
            int sum = n1 + n2 + carry;
            carry = 0;
            if(sum>9){
                sum = sum - 10;
                carry = 1;
            }
            sb.insert(0,sum);
            n1Index--;
            n2Index--;
        }
        if(carry==1)sb.insert(0,carry);
        return sb.toString();
    }
    //三十六进制
    //36进制由0-9，a-z，共36个字符表示。
		//要求按照加法规则计算出任意两个36进制正整数的和，如1b + 2x = 48  （解释：47+105=152）
		//要求：不允许使用先将36进制数字整体转为10进制，相加后再转回为36进制的做法
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int n1Index = num1.length()-1;
        int n2Index = num2.length()-1;
        int carry = 0;
        while(n1Index>=0||n2Index>=0){
            int n1 = n1Index >= 0 ? getInt(num1.charAt(n1Index)) : 0;
            int n2 = n2Index >= 0 ? getInt(num2.charAt(n2Index)) : 0;
            int sum = n1 + n2 + carry;
            carry = 0;
            if(sum>35){
                carry = sum / 36;
                sum = sum % 36;
            }
            char aChar = getChar(sum);
            sb.insert(0,aChar);
            n1Index--;
            n2Index--;
        }
        if(carry!=0)sb.insert(0,getChar(carry));
        return sb.toString();
    }

    private char getChar(int sum) {
        if (sum<10)return (char) (sum+'0');
        return (char) (sum - 10 + 'a');
    }

    private int getInt(char charAt) {
        if (charAt<='9')return charAt-'0';
        return charAt-'a'+10;
    }
}

多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    //思路：摩尔投票(相同+1，不同-1，为0替换)
    public int majorityElement(int[] nums) {
        int ans = nums[0],count = 1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]==ans)count++;
            else count--;
            if(count==0){
                ans=nums[i];
                count=1;
            }
        }
        return ans;
    }
}

求最大公约数

1.欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式 **gcd(a,b) = gcd(b,a mod b) **。

以除数和余数反复做除法运算，当**余数为 0** 时，取当前算式**除数**为最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution{
		//递归
		public int gcd(int num1,int num2){
    		int mod = num1 % num2;
        return mod == 0 ? num2 : gcd(num2,mod);
    }
    //迭代
    public int gcd(int num1,int num2){
    		int mod = num1 % num2;
        while(mod!=0){
        		num1 = num2;
            num2 = mod;
            mod = num1 % num2;
        }
        return num2;
    }
}

2.更相减损术（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public int gcd(int num1, int num2) {
        int max = Math.max(num1, num2);
        int min = Math.min(num1, num2);
        int count = 0;
        while (max % 2 == 0 && min % 2 == 0) {
            max /= 2;
            min /= 2;
            count++;
        }
        int reduce = max - min;
        while (reduce != min && reduce > 0) {
            max = Math.max(min, reduce);
            min = Math.min(min, reduce);
            reduce = max - min;
        }
        return (int) (min * Math.pow(2, count));
    }
}

数组中出现次数超过一半的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    //摩尔投票:遇到和当前统计的num则count++,否则count--,当count==0,更新num
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int num = nums[0];
        int count = 1;
        for(int i=1;i<n;i++){
            if(nums[i]==num)count++;
            else count--;
            if(count == 0){
                num = nums[i];
                count++;
            }
        }
        return num;
    }
}

Excel表列名称

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    //思路:类似进制转换26进制（可以参考10进制的方式来做)
    public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        while (columnNumber != 0) {
            int cur = columnNumber % 26;
            columnNumber /= 26;//除以26获取下一位
            if (cur == 0) {//余数是0则为Z
                sb.append('Z');
                columnNumber--;//因为没有0是从1开始的所以需要--
            } else {
                sb.append((char)('A' + cur - 1));//否则是A-Y
            }
        }
        return sb.reverse().toString();//翻转
    }
}

求n边形周长的k等分点坐标

https://www.jianshu.com/p/430b22307d1e

https://blog.csdn.net/sky302761277/article/details/88838593

有一个n边形(P0, P1, …, Pn)， 每一条边皆为垂直或水平线段。现给定数值k，以P0为起点将n边形的周长分为k段，每段的长度相等，请打印出k等分点的坐标(T0, T1, …, Tk）的坐标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution{
    //思路：计算多边形的周长，得出每个等分点长度，再确定每个点的坐标
    //两点间距离公式:√￣(x1-x2)^2+(y1-y2)^2
    public int[][] m(int[][] points,int k){
        int[][] ret = new int[k][];
        int len = points.length;
        int perimeter = 0;
        int[] pointDistance = new int[len];
        //计算多边形周长
        for(int i=1;i<len;i++){
            int x = points[i][0] - points[i-1][0];
            int y = points[i][1] - points[i-1][1];
            double sideLen = Math.abs(Math.sqrt((x*x)-(y*y)));
            pointDistance[i] = (int) sideLen;
            perimeter+=sideLen;
            if(i==len-1){//首尾那段
                int ex = points[len-1][0] - points[0][0];
                int ey = points[len-1][1] - points[0][1];
                perimeter+= Math.abs(Math.sqrt((ex*ex)-(ey*ey)));
            }
        }
        //每段的长度
        int sideLen = perimeter / k;
        //跟着线走计算坐标
        ret[0] = points[0];
        int[] lenArr = new int[k];
        for (int i = 1; i < k; i++) lenArr[i] = i * sideLen;
        int index = 1;
        for (int i = 1; i < len; i++) {
            int target = lenArr[i];//目标节点的长度距离
            int[] prePoint = points[0];//前一个节点
            for (int j = 0; j < len; j++) {
                if (pointDistance[j]>target){//说明目标节点在prePoint和points[j]之间

                }else prePoint = points[j];
            }
        }
        return ret;
    }
}

5253. 找到指定长度的回文数（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    //找规律,发现前面两个数呈递增
    //101
    //111
    //121
    //131
    //可以知道长度为3的回文数最小值是(10)1, 最大值是(99)9。取值范围就是[101,999]。
    public long[] kthPalindrome(int[] queries, int intLength) {
        int n = queries.length;
        //前面两个数最小值10
        long min = (long)Math.pow(10, (intLength - 2 + 1)/2);
        //前面两个数最大值99
        long max = (long)Math.pow(10, (intLength + 1)/2) - 1;
        long[] ans = new long[n];
        for (int i = 0; i <  n; i++){
            int q = queries[i];
            //queries[i]超出设置为-1,intLength=3,共有90个回文串
            if ((long)q > (long)9*Math.pow(10, (intLength-1)/2)){
                ans[i] = -1;
                continue;
            }
            //因为前面两个数呈递增状态，q-1+min即为该数的前缀
            long cur  = q - 1 + min;
            String str = String.valueOf(cur);
            //如果intLength是偶数,直接拼接自己的翻转
            if (intLength % 2 == 0){
                StringBuilder sb = new StringBuilder(str);
                str += sb.reverse().toString();
            }else{//如果是intLength奇数，则去掉第一位在翻转追加
                StringBuilder sb = new StringBuilder(str);
                str += sb.reverse().toString().substring(1);
            }
            ans[i] = Long.parseLong(str);
        }
        return ans;
    }
}

479. 最大回文数乘积（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    //直接枚举,枚举前
    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        int upper = (int) Math.pow(10, n) - 1;//取一部分upper=99,上界9999
        int ans = 0;
        for (int left = upper; ans == 0; --left) { // 枚举回文数的左半部分
            long p = left;//99 98 97 ...
            for (int x = left; x > 0; x /= 10) {
                //p = 99 * 10 + 99 % 10 = 990 + 9 = 999   x=9
                //p = 999 * 10 + 9 % 10 = 9990 + 9 = 9999   x=0
                p = p * 10 + x % 10; // 翻转左半部分到其自身末尾，构造回文数 p
            }
            //枚举获取两个相乘==p
            for (long x = upper; x * x >= p; --x) {
                if (p % x == 0) { // x 是 p 的因子
                    ans = (int) (p % 1337);
                    break;
                }
            }
        }
        return ans;
    }
}

497. 非重叠矩形中的随机点（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Solution {

    Random rand;
    List<Integer> arr;//累计每个矩阵点数[rect(1)Points,rect(1)Points+rect(2)Points,....,rect(N-1)Points+rect(N)Points]
    int[][] rects;
    //预处理
    public Solution(int[][] rects) {
        rand = new Random();//随机种子
        arr = new ArrayList<>();
        arr.add(0);//默认添加0,数据从下标1开始
        this.rects = rects;
        //预处理
        for (int[] rect : rects) {
            int a = rect[0], b = rect[1], x = rect[2], y = rect[3];
            //当前矩阵的点数
            int totalPoints = (x - a + 1) * (y - b + 1);
            //前一个点的矩阵总共有的点数
            Integer prevRectPoints = arr.get(arr.size() - 1);
            //当前总共有的点
            arr.add(prevRectPoints + totalPoints);
        }
    }

    public int[] pick() {
        //1.在[0,所有点数]区间获取一个随机整数（保证了所有的点等概率获取）
        int k = rand.nextInt(arr.get(arr.size() - 1));
        //2.在arr数组中获取点数为k所在矩阵数组的下标（k+1是因为rand是会取0的，但是我们points不可能为0）
        int rectIndex = binarySearch(arr, k + 1) - 1;
        //3.k=k-arr.get(rectIndex)得到当前k点是在矩阵中的第几个点（注意这里的rectIndex是当前矩阵的前面一个矩阵的下标，因为我们上面存的时候是从下标1开始）
        k -= arr.get(rectIndex);
        //当前随机获取的矩阵
        int[] rect = rects[rectIndex];//因为已经减一了，所以当前rectIndex就是对应数组的矩阵
        //还原坐标
        int a = rect[0], b = rect[1], y = rect[3];
        int col = y - b + 1;//列上有多少个点，算上边框
        int da = k / col;//x上的增量
        int db = k - col * da;//y上的增量
        //左下角坐标加上增量da、db即可
        return new int[]{a + da, b + db};
    }

    //查找一下target所属矩阵的下标
    private int binarySearch(List<Integer> arr, int target) {
        int low = 0, high = arr.size() - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = arr.get(mid);
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

478. 在圆内随机生成点（mid）

拒绝采样：先采集大范围的数据，存在满足的直接返回，否则继续采样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    double radius;
    double x_center;
    double y_center;
    //(x-a)²+(y-b)²=r² (ab为圆心坐标,r为半径)
    public Solution(double radius, double x_center, double y_center) {
        //(x-x_center)²+(y-y_center)²=r²
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
    }
    //拒绝采样
    public double[] randPoint() {
        double radPow = radius * radius;
        while(true){
            //[0,2 * radius)
            double x = Math.random() * (2 * radius) - radius;
            double y = Math.random() * (2 * radius) - radius;
            //满足直接返回
            if(x * x + y * y <= radPow){
                return new double[]{x_center + x,y_center + y};
            }
        }
    }
}

528. 按权重随机选择（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int[] w;
int n;
long[] prefixSum;
long total;
public Solution(int[] w) {
    this.w = w;
    this.n = w.length;
    total = w[0];
    prefixSum = new long[n];
    for (int i = 1; i < n; i++) {
        total+=w[i];
        prefixSum[i]+=prefixSum[i-1];
    }
}
//[20, 34, 160, 2]
//[20, 54, 210, 212]
//[1,20],[21,54],[55,210],[211,212]
public int pickIndex() {
    //[1,total]
    int index = (int) (Math.random() * total) + 1;
    //获取当前随机数所属区间的下标
    int ret = binarySearch(index);
    return ret;
}

private int binarySearch(int index) {
    int left = 0,right = prefixSum.length - 1;
    while (left<right){
        int mid = left + (right-left)/2;
        if (prefixSum[mid]>=index)right = mid;
        else if (prefixSum[mid]<index){
            left = mid + 1;
        }
    }
    return left;
}

710. 黑名单中的随机数（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private Map<Integer,Integer> map;
    private Random random;
    int m;
    //总共n个数，m个黑名单数，那么可选数就是n-m个
    //0 1 2 3 4 5 6 7 8 9 blacklist=[3,6,7]
    //0 1 2 3(8) 4 5 6(9) 7 8 9 blacklist=[3,6,7]（将黑名单的数映射到非黑名单数上）
    public Solution(int n, int[] blacklist) {
        this.map = new HashMap<>();
        this.random = new Random();
        int m = blacklist.length;
        int last = n - m;//9-3=6
        this.m = last;
        //记录比last大的黑名单数
        Set<Integer> bls = new HashSet<>();
        for(int black:blacklist){
            if(black>=last)bls.add(black);
        }
        //映射黑名单数到非黑名单数上
        int w = last;
        for(int black:blacklist){
            if(black<last){
                while(bls.contains(w))w++;
                map.put(black,w);
                w++;
            }
        }
    }
    
    public int pick() {
        int rdm = random.nextInt(m);
        return map.getOrDefault(rdm,rdm);//如果map中有，那说明是映射的，否则就是随机数
    }
}

204. 计数质数（mid）

埃氏筛

  • 要得到自然数n以内的全部素数，必须把不大于 根号n 的所有素数的倍数剔除，剩下的就是素数。
  • 给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；
  • 再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去……。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        // 从 2 开始枚举到 sqrt(n)。
        for (int i = 2; i * i < n; i++) {
            // 如果当前是素数
            if (isPrim[i]) {
                // 就把从 i*i 开始，i 的所有倍数都设置为 false。
                for (int j = i * i; j < n; j += i) {
                    isPrim[j] = false;
                }
            }
        }
        //计数
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrim[i]) cnt++;
        }
        return cnt;
    }
}

积分抽奖

我们做了一个活动，根据用户的积分来抽奖，用户的积分都保存在一个数组里面

arr = [20, 34, 160, 2…]，数组下标就是用户的 ID，则这里：

ID 为 0 的用户的积分是 arr[0] 等于 20 分。

ID 为 1 的用户的积分是 arr[1] 等于 34 分。

请你设计一个抽奖算法，随机抽出一位中奖用户，要求积分越高中奖概率越高。

返回值是中奖用户的 ID

PS: 1<= arr.length <= 50000 且 1<= arr[i] <= 50000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
    /**
     * arr = [20, 34, 160, 2…]，数组下标就是用户的 ID，则这里：
     * ID 为 0 的用户的积分是 arr[0] 等于 20 分。
     * ID 为 1 的用户的积分是 arr[1] 等于 34 分。
     * 请你设计一个抽奖算法，随机抽出一位中奖用户，要求积分越高中奖概率越高。
     * 返回值是中奖用户的 ID
     * PS: 1<= arr.length <= 50000 且 1<= arr[i] <= 50000
     */
    //时间复杂度O(n)+O(log(n))
    //空间复杂度O(n)
    int[] w;
    int n;
    long[] prefixSum;
    long total;
    public Solution(){}
    public Solution(int[] w) {
        this.w = w;
        this.n = w.length;
        total = w[0];
        prefixSum = new long[n];
        for (int i = 1; i < n; i++) {
            total+=w[i];
            prefixSum[i]+=prefixSum[i-1];
        }
    }
    //[20, 34, 160, 2]
    //[20, 54, 210, 212]
    //[1,20],[21,54],[55,210],[211,212]
    public int pickIndex() {
        //[1,total]
        int index = (int) (Math.random() * total) + 1;
        //获取当前随机数所属区间的下标
        int ret = binarySearch(index);
        return ret;
    }

    private int binarySearch(int index) {
        int left = 0,right = prefixSum.length - 1;
        while (left<right){
            int mid = left + (right-left)/2;
            if (prefixSum[mid]>=index)right = mid;
            else if (prefixSum[mid]<index){
                left = mid + 1;
            }
        }
        return left;
    }
}

172. 阶乘后的零（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    //分析
    // 5!=[5]*4*3*[2]*1=120 1个0
    //10!=[10]*9*8*7*6*[5]*4*3*[2]*1=3628800 2个0
    //15!=[15](拆分3*5然后5*2又组成一个0)*14*13*12*11*[10]*9*8*7*6*[5]*4*3*[2]*1=1307674368000 3个0
    //结论：能出现0的情况只有2*5的倍数(25*4=100可拆解为2*5*2*5同样是两个0)，所以只需要求出其乘法因子有多少个5即可
    public int trailingZeroes(int n) {
        int ret = 0;
        if(n<5)return 0;
        while(n>=5){
            ret+=n/5;
            n/=5;
        }
        return ret;
    }
}

793. 阶乘函数后 K 个零（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    // 5!=[5]*4*3*[2]*1=120 1个0
    //10!=[10]*9*8*7*6*[5]*4*3*[2]*1=3628800 2个0
    //0个数为的k的数共有 = 阶乘0个数为的k+1的数 - 阶乘0个数为的k的数
    public int preimageSizeFZF(int k) {
        return (int) (binarySearch(k + 1) - binarySearch(k));
    }
    //求出阶乘0个数为k的数值
    private long binarySearch(int k){
        //定义左右边界 最大不会超过5倍的k因为乘以5相当于多了一个0了
        long l = 0, r = 5L * k;
        while(l<=r){
            long mid = l + (r-l)/2;
            if(trailingZeroes(mid)>=k){
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return r+1;
    }
    //n的尾部0个数（参考上一题）
    public int trailingZeroes(long n) {
        int ret = 0;
        if(n<5)return 0;
        while(n>=5){
            ret+=n/5;
            n/=5;
        }
        return ret;
    }
}

相关资料

基础算法 > 刷题记录
算法笔记-数学/采样
https://mikeygithub.github.io/2021/10/20/yuque/算法笔记-数学!采样!概率/
作者
Mikey
发布于
2021年10月20日
许可协议