4.数学（四）

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

268. 缺失数字简单[✔]

273. 整数转换英文表示困难（不做了）

279. 完全平方数中等[✔]

313. 超级丑数中等（理解不深）

319. 灯泡开关中等（不做了）

326. 3的幂简单

343. 整数拆分中等[✔]

335. 路径交叉困难（不做了）

268. 缺失数字简单

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]，输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]，输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

思路：位运算的异或

与 136. 只出现一次的数字题目类似，异或的运算法则是 “两个输入相同时为0，不同则为1”，例如输入是[0,1,3,4]

数组下标和其值进行异或操作后，就变成了数组中只有一个数字出现一次。

//2020.07.23
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for(int i = 0; i < nums.length; i++){
            res ^= i ^ nums[i];
        }
    return res;
    }
}

279. 完全平方数中等

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。
示例 :
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

思路：动态规划

时间复杂度：O(n*sqrt(n))，一个嵌套循环，其中外部循环是 n 次迭代，而内部循环最多需要 sqrt(n)次迭代

class Solution {//执行用时：47 ms, 在所有 Java 提交中击败了43.23%的用户，2020/07/23
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            dp[i] = i; //最坏结果
            for(int j = 1; i - j * j >= 0; j++){
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);//动态转移方程
            }
        }
    return dp[n];
    }
}

313. 超级丑数中等

编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。（丑数是只包含质因数 2, 3, 5 的正整数。）
示例:
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
说明:

• 1 是任何给定 primes 的超级丑数。
• 给定 primes 中的数字以升序排列。
• 0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000 。
• 第 n 个超级丑数确保在 32 位有符整数范围内。

思路：动态规划

与264. 丑数 II类似，对题解https://leetcode-cn.com/problems/super-ugly-number/solution/javazui-rong-yi-li-jie-de-dong-tai-gui-hua-fen-xi-/中index数组的理解不清。代码来自这个题解。

class Solution {//执行用时：18 ms, 在所有 Java 提交中击败了93.34%的用户，2020/07/23
    public int nthSuperUglyNumber(int n, int[] primes) {
        int len = primes.length;
        int dp[] = new int[n];
        dp[0] = 1;
        /*梳理一下思路，dp[i]保存的是第i个超级丑数*/
        /*index[i]表示的是primes里面的第i个数下一个将要相乘的数在dp中的位置，
        反过来想，对于每个primes来说，我们都需要和dp中已经算出来的结果相乘算，
        然后取最小的那个作为新的dp元素
        索引index实际上表示是这个素数已经和dp中的哪个位置结合了，下一个位置的坐标是多少 */
        int index[] = new int[len];
        /*可能存在重复的丑数，所以呢，不要在for循环里面加break，把所有的情况都+1*/
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            /*遍历对比一下值，找出最小的，*/
            for (int j = 0; j < len; j++) {
                if (min > primes[j] * dp[index[j]]) {
                    min = primes[j] * dp[index[j]];//这个地方就是当前质因数和他要结合的dp
                }
            }
            dp[i] = min;
            /*那个素数要乘以dp的坐标index要加1，向后推一个位
            * 如果存在重复的值，也就是说不同的质因数相乘，得出来相同的结果了，
            * 我们就把这几个位置都+1，这样就可以避免出现重复的值了。
            * 你想想，假如你找到了对应的素数的index，把它加1之后就break掉，那么后面的数也可以算出这个结果，
            * 下次循环的时候，势必会把这个重复的数当成下一个dp，因为这个数肯定要比下一个丑数小
            * 所以我们在for循环中不要加break；*/
            for (int j = 0; j < len; j++) {
                if (min == primes[j] * dp[index[j]]) {
                    index[j]++;
                }
            }

        }
        return dp[n - 1];

    }
}

326. 3的幂简单

给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1:
输入: 27，输出: true
示例 2:
输入: 0，输出: false
进阶：
你能不使用循环或者递归来完成本题吗？

思路：使用对数函数log

使用换底公式

若 n 是 3 的幂则 i 是整数。在 Java 中，我们通过取小数部分（利用 % 1）来检查数字是否是整数，并检查它是否是 0。

class Solution {//执行用时：16 ms, 在所有 Java 提交中击败了39.76%的用户，2020/07/23
    public boolean isPowerOfThree(int n) {
        if(n <= 0)
            return false;
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

343. 整数拆分中等

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
**说明: **你可以假设 *n *不小于 2 且不大于 58。

思路一：动态规划

class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了17.14%的用户,2020/07/23
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1);
        for(int i = 3; i <= n; i++){
            for(int j = 1; j < i; j++){
                //如果i - j比dp[i - j]要大，就不用再继续分解了
                //以 8 为例：1 与 7 是一个解，1 与 7 的分解的结果也是一个解
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));          
            }
        }
        return dp[n];
    }
}

思路二：归纳

当 n > 3时，即 n = 3a + b 时，并分为以下三种情况：
当 b = 0 时，直接返回 3^a；
当 b = 1 时，要将一个 1 + 3 转换为 2+2，因此返回 3^a-1×4；
当 b = 2时，返回 3^a×2。

class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户,2020/07/23
    public int integerBreak(int n) {
        if(n <= 3)
            return n - 1;
        int a = n / 3;  //a是商
        int b = n % 3;  //b是余数
        if(b == 0){
            return (int)(Math.pow(3, a));
        }   
        else if(b == 1){
            return (int)(Math.pow(3, a-1) * 4);
        }  
        else{
            return (int)(Math.pow(3, a) * 2);
        }
          
    }
}