6.数学（六）

题目汇总https://leetcode-cn.com/tag/math/

423. 从英文中重建数字中等[✔]

441. 排列硬币简单[✔]

453. 最小移动次数使数组元素相等简单[✔]

458. 可怜的小猪困难（不做了吧）

462. 最少移动次数使数组元素相等 II中等[✔]

478. 在圆内随机生成点中等（不做了吧，题解只有20）

483. 最小好进制困难（不做了吧，题解只有20）

507. 完美数简单[✔]

517. 超级洗衣机困难（不做了吧，题解只有16）

423. 从英文中重建数字中等

给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。
注意:

1. 输入只包含小写英文字母。
2. 输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
3. 输入字符串的长度小于 50,000。
   示例 1:
   输入: "owoztneoer"
   输出: "012" (zeroonetwo)
   示例 2:
   输入: "fviefuro"
   输出: "45" (fourfive)

思路：

https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/solution/cong-ying-wen-zhong-zhong-jian-shu-zi-by-leetcode/

class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了99.20%的用户，2020/07/26
    public String originalDigits(String s) {
        char[] count = new char[26 + (int)'a'];
        for(char letter: s.toCharArray()){
            count[letter]++;
        }

        int[] out = new int[10];
        out[0] = count['z'];  //'z'只出现在数字 0 中
        out[2] = count['w'];  //'w'只出现在数字 2 中
        out[4] = count['u'];  //'u'只出现在数字 4 中
        out[6] = count['x'];  //'x'只出现在数字 6 中
        out[8] = count['g'];  //'g'只出现在数字 8 中
        out[3] = count['h'] - out[8]; //'h'只出现在数字 8 和 3 中
        out[5] = count['f'] - out[4]; //'f'只出现在数字 4 和 5 中
        out[7] = count['s'] - out[6]; //'s'只出现在数字 6 和 7 中
        out[9] = count['i'] - out[5] - out[6] - out[8];//'i'只出现在数字 5、6 和 8 中
        out[1] = count['n'] - out[7] - 2 * out[9];

        StringBuilder output = new StringBuilder();
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < out[i]; j++){
                 output.append(i); 
            }
        }       
    return output.toString();
    }
}

441. 排列硬币简单

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内
（-2,147,483,648 到 2,147,483,647 ）
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
示例 2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.

思路一：迭代

class Solution {//执行用时：13 ms, 在所有 Java 提交中击败了9.61%的用户，2020/07/26
    public int arrangeCoins(int n) {
        if(n == 1)  return 1;
        long sum = 0;//如果是int存储sum并且n很大的话，会溢出的，所以用long存储sum
        int i;
        for(i = 1; i < n; i++){
            sum += i;
            if(sum > n){
                break;
            }
        }
    return i - 1;
    }
}

思路二：等差数列

利用前 n 项和公式 sum = n(n+1)/2
对于这道题而言，是x(x+1)/2 = n,x²+x-2n=0，对一元二次方程的结果取整。

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户，2020/07/26
    public int arrangeCoins(int n) {
        double res = (-1 + Math.sqrt(1 + 8 * (long)n)) / 2;
        return (int) res;
    }
}

思路三：二分查找

453. 最小移动次数使数组元素相等简单

给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。
示例:
输入:[1,2,3]
输出:3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

思路：

典型的数学题，还是看了评论区的解答：假设目前数组总和为sum，我们需要移动次数为m，那么整体数组总和将会增加m × (n - 1)，这里的n为数组长度，最后数组所有元素都相等为x，于是有：
sum + m × (n - 1) = x × n (1)
我们再设数组最小的元素为min_val，m = x - min_val​，即 ​x = m + min_val​带入(1)得：m = sum - min_val * n​

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户,2020/07/26
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            if(min > nums[i]){
                min = nums[i];
            }
        }
        int res = 0;
        for(int i=0;i<nums.length;i++){
            res += nums[i] - min;
        }
    return res;
    }
}

462. 最少移动次数使数组元素相等 II中等

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
例如:
输入:
[1,2,3]
输出:
2
说明： 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：
[1,2,3] => [2,2,3] => [2,2,2]

思路：排序找中位数

其实就是求中位数，证明过程评论区很多大佬讲到了，很清楚。

class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了37.79%的用户,2020/07/27
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for(int num : nums){
            sum += Math.abs(nums[nums.length / 2] - num);
        }
    return sum;
    }
}

507. 完美数简单

对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。
给定一个 **整数 **n， 如果他是完美数，返回 True，否则返回 False
示例：
输入: 28
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14
提示：
输入的数字 n 不会超过 100,000,000. (1e8)

思路一：暴力法，会超时 !

class Solution {
    public boolean checkPerfectNumber(int num) {
        int sum = 0;
        for(int i=1;i<num;i++){
            if(num % i == 0){
                sum += i;
            }
        }
    return sum == num;
    }
}

思路二：优化的暴力法

正因子必然是成对出现的，故而我们只需要遍历到 num 的平方根即可

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了90.51%的用户,2020/07/27
    public boolean checkPerfectNumber(int num) {
        if(num == 1)
            return false;
        int sum = 1;
        for(int i = 2; i * i < num; i++){
            if(num % i == 0){
                sum += i;
                sum += num / i;//成对出现的因子
            }
        }
        return sum == num;
    }
}

思路三：投机取巧

完美数只有 6, 28, 496, 8128, 33550336 这几个，可以通过判断该数字是否为以下几个来解决

class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户,2020/07/27
    public boolean checkPerfectNumber(int num) {
        switch(num){
            case 6:
            case 28:
            case 496:
            case 8128:
            case 33550336:
                return true;
        }
    return false;
    }
}