Day 55

第1155题:

这里有 d 个一样的骰子,每个骰子上都有 f 个面,分别标号为 1, 2, ..., f。

我们约定:掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 target,请你计算出有多少种不同的组合情况(所有的组合情况总共有 f^d 种),模 10^9 + 7 后返回。来源:力扣(LeetCode)

 1、题目由动态规划得出最终解,那么就利用一个二位数组dp[i][j]来存储 i 颗筛子和target为 j 的组合情况;

  那么可以得出dp[i][j]的组合是等于i - 1个筛子组成j - 1、j - 2、……一直到 j - f的组合之和;

  也就是dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+…dp[i-1][j-f],因为筛子有 f 个面,所以得加上这些种情况;

  最终得出结果。

  

 第941题:

给定一个整数数组 A,如果它是有效的山脉数组就返回 true,否则返回 false。来源:力扣(LeetCode)

让我们回顾一下,如果 A 满足下述条件,那么它是一个山脉数组:

A.length >= 3
在 0 < i < A.length - 1 条件下,存在 i 使得:
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]

1、定义一个left指针从0向右遍历,只要是一直递增就一直遍历,直到不是递增;

  定义一个right指针从length-1向左遍历,只要递减就一直向左走,直到不是递减;

  最后判断left和right是否指向一处。

  



 

原文地址:https://www.cnblogs.com/liang-yi-/p/13580456.html