LeetCode 第十六天

n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

分析:

动态规划.

https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/

class Solution {
    
    public double[] dicesProbability(int n) {
    
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
    
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
    
                for (int k = 0; k < 6; k++) {
    
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

扑克牌中的顺子

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

分析:

首先建立一个集合, 把这五个数放入集合中, 如果数字为0则跳过, 如果出现重复数字则直接返回false.
插入集合完成后,判断其最大值-最小值<5是否成立?成立则返回true.

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        ma, mi = 0, 14
        coll = set()
        for num in nums:
            if num == 0: continue
            if num > ma: ma = num
            if num < mi: mi = num
            if num in coll: return False
            coll.add(num)
            
        return ma - mi < 5

最长的斐波那契子序列长度

如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

分析:

因为给的是一个严格递增的正整数数组形成序列,则用一个哈希表存储这些数字.然后遍历整个数组,先遍历出前两个数字的可能的所有情况,得到第三个数的值,然后去哈希表查找是否有这个数,如果有则继续查找,直到在哈希表中找不到对应值,并记录下长度与maxlen比较.

class Solution {
    
    public int lenLongestFibSubseq(int[] arr) {
    
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
    
            set.add(arr[i]);
        }
        int maxlen = 0;
        for (int i = 0; i < arr.length; i++) {
    
            for (int j = i+1; j < arr.length; j++) {
    
                int sum = arr[i] + arr[j];
                int a = arr[j];
                int len = 2;
                while (set.contains(sum)){
    
                    int b = sum;
                    len++;
                    sum = sum + a;
                    a = b;
                }
                if (len>=3 && len>maxlen) maxlen = len;
            }
        }
        return maxlen;
    }
}