6.4号刷题

发表于 | 分类于 | 0 comments

第一题 357. Count Numbers with Unique Digits

题目描述

给定一个非负整数n，计算所有各位数字均不同的数字x的个数，其中0 ≤ x < 10^n。

算法

对于n = 1，f(1) = 10

对于n = 2, f(2) = 9 9 (对于10位我们可以选择1 - 9九个数字，对于个位，我们可以选择0-9十个数字，但是需要与之前的个位数字不相同，所以为9)

同理，n = 3，f(3) = 9 9 * 8
最终的结果为 f(1) + f(2) + f(3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class countNumbersWithUniqueDigits357 {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int begin = 10, first = 9;
        int sum = begin;
        for (int i = 1; i < n; i++) {
            begin--;
            if (begin > 0) {
                sum += first * begin;
                first *= begin;
            }
        }
        return sum;
    }
}

第二题 343. Integer Break

题目描述

给定给一个正整数n，将其分解成至少两个正整数的和，使这些整数的积最大化。返回可以得到的最大乘积。

算法

方法一 数学解

经过拆分的检验，可以发现，有3要3，没3要2，这时候这种拆分方式得到的乘机最大。证明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int integerBreak(int n) {
        if (n <= 3) return n == 2? 1:2;
        int three = n / 3, two = 0;
        if (n % 3 == 1) {
            three --;
            two = 2;
        } else if (n % 3 == 2) {
            two = 1;
        }
        int max =  (int) (Math.pow(3, three) * Math.pow(2, two));
        return max;      
    }
}

方法二 DP解法

从2-n之前的所有的可能性都记录在一个Array里面，之后利用之前的记录值求最终的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= 3 && j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i-j, dp[i-j]));
            }
        }
        return dp[n];        
    }
}

第三题 486. Predict the Winner

题目描述

给定一个非负整数数组表示一组分数。玩家1从数组两端任取一个数字，之后由玩家2选取，以此类推。每当一名玩家选择一个数字之后，另一位玩家就不能再选这个数字。重复此过程直到所有的数字都被选完。分数高的玩家获胜。

给定分数数组，预测玩家1是否可以获胜。可以假设每一个玩家都采用最优策略游戏。

算法

简单的

利用回溯的方法，从(0, length - 1)开始遍历所有的可能性，然后求出后选的可能得到的最大值最后判断是否为一个正数，如果是一个正数则进行输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return helper(nums, 0, nums.length - 1) >= 0;    
    }
    public int helper(int[] nums, int low, int high) {
        if (low == high) {
    
            return nums[low];
        }
        else {
            int result = Math.max(nums[low] - helper(nums, low + 1, high), nums[high] - helper(nums, low, high - 1));
            return result;
        }
    }
}

其中，对于player1，可以有两种选择，分别是low的和high的任选其一，选择完成之后。对于player2，其可以获得的最大收益可以遍历每一种可能性，并调用函数helper获得最后值。

DP方法

利用一个二维矩阵dp[i][j]存储当前选择的人从i到j可以获得的最大值(本题中，由于只需要胜负关系用差值计算)，之后不断更新，直到获得最终答案。

例子，例如[1, 5, 233, 7], 首先在第一次循环中，计算1-5,5-233,233-7可以获得的受益。之后不断扩大范围1-233,5-7,并利用之前的结果更新现在的收益，并最终更新到1-7可以获得的最大收益

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        if (n <= 0) return false;
        
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = nums[i];
        
        for (int len = 1; len < n; len++){
            for (int i = 0; i < n - len; i++) {
                int j = i + len;
                dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
            }
        }
        
        return dp[0][n-1] >= 0;        
    }
}