Leetcode.2400 恰好移动 k 步到达某一位置的方法数目
题目链接
Leetcode.2400 恰好移动 k 步到达某一位置的方法数目 Rating : 1751
题目描述
给你两个 正 整数 startPos
和 endPos
。最初,你站在 无限 数轴上位置 startPos
处。在一步移动中,你可以向左或者向右移动一个位置。
给你一个正整数 k
,返回从 startPos
出发、恰好 移动 k
步并到达 endPos
的 不同 方法数目。由于答案可能会很大,返回对
1
0
9
+
7
10^9 + 7
109+7 取余 的结果。
如果所执行移动的顺序不完全相同,则认为两种方法不同。
注意:数轴包含负整数。
示例 1:
输入:startPos = 1, endPos = 2, k = 3
输出:3
解释:存在 3 种从 1 到 2 且恰好移动 3 步的方法:
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2. 可以证明不存在其他方法,所以返回 3 。
示例 2:
输入:startPos = 2, endPos = 5, k = 10
输出:0
解释:不存在从 2 到 5 且恰好移动 10 步的方法。
提示:
- 1 < = s t a r t P o s , e n d P o s , k < = 1000 1 <= startPos, endPos, k <= 1000 1<=startPos,endPos,k<=1000
解法:组合数学
我们定义 startPos ----> endPos
为正方向,endPos----> startPos
为负方向。
我们假设往 正方向 走了 a
步,那么往 负方向 就走了剩下的步数,即 k - a
步。
如果成立,必须满足 a − ( k − a ) = d a - (k - a) = d a−(k−a)=d , d = a b s ( s t a r t P o s − e n d P o s ) d = abs(startPos - endPos) d=abs(startPos−endPos)。
所以我们最后的答案为 C k a C_{k}^{a} Cka,即 C k k + d 2 C_{k}^{\frac{k+d}{2}} Ck2k+d。所以 k + d k + d k+d 必须是偶数才行,否则不符合要求。
对于组合数,我们利用递推式 C m n = C m − 1 n + C m − 1 n − 1 C_m^n = C_{m-1}^n + C_{m-1}^{n-1} Cmn=Cm−1n+Cm−1n−1,求出 C k k C_k^k Ckk。
最终返回 C k a C_k^a Cka即可。
时间复杂度: O ( k 2 ) O(k ^ 2) O(k2)
C++代码:
const int MOD = 1e9 + 7;
using LL = long long;
class Solution {
public:
int numberOfWays(int startPos, int endPos, int k) {
int d = abs(startPos - endPos);
if(d > k || (k + d) % 2 == 1) return 0;
LL c[k+1][k+1];
memset(c,0,sizeof c);
for(int i = 0;i <= k;i++){
c[i][0] = 1;
for(int j = 1;j <= i;j++) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
}
return c[k][(k + d) / 2];
}
};
相关文章
- flex vue 垂直居中居上_推荐几种在移动端实现垂直居中的方法[通俗易懂]
- 移动端实现拖拽的两种方法
- 为PHP加装eAccelerator方法
- Java 移动 ArrayList 中的元素的方法
- 博客搬家换空间方法教程
- js 判断函数或变量是否已定义的方法
- 网络工程师学Python-18-数学运算方法
- Oracle删除archivelog文件的正确方法
- Oracle表空间数据文件移动的方法
- 利用率Linux操作系统下计算CPU利用率的方法(linux计算cpu)
- 掌握Oracle数据库备份的有效方法(oracle备份方法)
- Hibernate between方法:设置在两者之间的条件
- Linux 下移动文件夹的实现方法(mv文件夹linux)
- Linux下快速移动文件夹的方法(mv文件夹linux)
- Linux快速移动文件的方法(linux怎么移动文件)
- Linux下移动文件夹的方法(linux文件夹移动)
- 与 Oracle 数据库运用 关联方法(oracle 关联方法)
- 几例在ASP存储过程的使用方法
- js中将多个语句写成一个语句的两种方法小结
- Apache支持CGI程序和SSI程序的设置方法
- svm各种工具箱方法以后查找
- jQuery让控件左右移动的三种实现方法
- php判断文件上传类型及过滤不安全数据的方法
- js实现键盘控制DIV移动的方法