【刷题记录】AcWing 435. 传球游戏

本文最后更新于:2021年5月8日 晚上

AcWing 435. 传球游戏

思路

一道简单的DP推导题目,推导过程中注意编号是循环的就好,每个人有两种状态,一种是从左边接到一种是从右边接到

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>

using namespace std;

const int N=35;

int n,m;
int f[N][N];

int main()
{
cin>>n>>m;
f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<n;j++)
f[i][j]=f[i-1][(j-1+n)%n]+f[i-1][(j+1)%n];
cout<<f[m][0]<<endl;
return 0;
}

LeetCode 7. 整数反转

思路

依次从右往左计算出每位数字,然后逆序累加在一个整数中。
另外,这题有两点需要注意:

因为int型整数逆序后可能会溢出,所以我们要用long long记录中间结果;在C++中,负数的取模运算和数学意义上的取模运算不同,结果还是负数,比如 −12%10=−2,所以我们不需要对负数进行额外处理。

时间复杂度分析:一共有 O(logn)
位,对于每一位的计算量是常数级的,所以总时间复杂度是 O(logn).

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int reverse(int x) {
int res=0;
while(x)
{
if(x>0 && res>(INT_MAX - x % 10)/10) return 0;
if(x<0 && res<(INT_MIN -x %10)/10) return 0;
res=res*10+x%10;
x/=10;
}
return res;
}
};

AcWing 78.左旋转字符串

思路

见代码

C++代码

1
2
3
4
5
6
class Solution {
public:
string leftRotateString(string str, int n) {
return str.substr(n)+str.substr(0,n);
}
};