|
1.杨辉三角
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
ll C(int a, int b)
{
ll res = 1;
for(ll up = a, down = 1; down <= b; up --, down ++)
{
res = res * up / down;
if(res > n) return res;
}
return res;
}
bool check(int j)
{
ll l = 2 * j, r = max((ll)n, l);
while(l < r)
{
ll k = l + r >> 1;
if(C(k, j) >= n) r = k;
else l = k + 1;
}
if(C(r, j) != n) return false;
cout<<(r + 1) * r / 2 + j + 1<<endl;
return true;
}
int main()
{
cin>>n;
for(int j=16; ;j--)
if(check(j))
break;
return 0;
}
2.节点选择
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > v;//存放树形结构
int dp[100005][2] = {0};
void dfs(int a, int pre){
for(int i = 0; i < v[a].size(); i++){
int t = v[a][i];
if(t != pre){//只要不是相邻节点就符合题意
dfs(t, a);
dp[a][0] += max(dp[t][0], dp[t][1]);//不选择该节点，保存下一节点的最大值
dp[a][1] += dp[t][0];//选择该节点，下一节点只能不选择
}
}
}
int main(){
int n, a, b;
cin >> n;
v.resize(n + 1);//给定数据大小
for(int i = 1; i <= n; i ++)
cin >> dp[i][1];//输入节点的权重
for(int i = 0; i < n-1; i ++){
cin >> a >> b;//输入节点之间的关系
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, 0);
cout << max(dp[1][0], dp[1][1]) << endl;
return 0;
}
3.耐摔指数
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<cmath>
const int maxn=1e5+5;
typedef long long ll;
using namespace std;
int f2[105],f3[105];
int main(){
int n;
while(~scanf("%d",&n)){
int i=0;
while(f3[i]<n){
i++;
f2[i]=f2[i-1]+i;//这里i本身就++了，所以不用加一了
f3[i]=f3[i-1]+f2[i-1]+1;
}
cout<<i<<endl;
}
return 0;
}
4.K好数
#include<iostream>
using namespace std;
int K, L;
long long int m1[1000],m2[1000];
int i0;//fun
//根据进制数进行初始化
void fun_extra() {
i0 = L;
for (int i = 0; i < K; i++) {
if (i == 0) {
m1[i] = 0;
}
else {
m1[i] = 1;
}
m2[i] = 0;
}
}
void fun(long long int * m0_1, long long int *m0_2) {
for (int i = 0; i < K; i++) {
m0_2[i] = 0;
for (int j = 0; j < K; j++) {
if (j != i + 1 && j != i - 1) {
m0_2[i] += m0_1[j];
}
}
m0_2[i] %= 1000000007;
}
i0--;
if (i0 > 1) {
fun(m0_2, m0_1);
}
else {
long long int sum = 0;
for (int i = 0; i < K; i++) {
sum += m0_2[i];
}
cout<< sum % 1000000007;
}
}
//K进制数；L位数；
int main() {
cin >> K >> L;
fun_extra();
fun(m1, m2);
return 0;
}
Leetcode
509.斐波那契数
class Solution {
public:
int fib(int N) {
if (N <= 1) {
return N;
}
return memoize(N);
}
public:
int memoize(int N) {
vector<int> temp(N+1);
temp[0] = 0;
temp[1] = 1;
for (int i = 2; i <= N; i++) {
temp[i] = temp[i - 1] + temp[i - 2];
}
return temp[N];
}
};
1137.
class Solution {
public:
int tribonacci(int n) {
if (n <= 1) {
return n;
}
if (n == 2) return 1;
return memoize(n);
}
public:
int memoize(int n) {
int sum = 0;
int first = 0;
int second = 1;
int third = 1;
for (int i = 3; i <= n; i++) {
sum = first + second+third;
first = second;
second = third;
third = sum;
}
return sum;
}
};
70.
public class 爬楼梯_for循环 {
public static void main(String[] args) {
int result = climbStairs(4);
System.out.println(result);
}
public static int climbStairs(int n) {
//小于等于2的时候，直接返回n
if (n <= 2) {
return n;
}
int a = 1;
int b = 2;
int temp=0;
for (int i = 3; i < n+1; i++) {
temp=b;
b=a+b;
a=temp;
}
return b;
}
}
746.
public class minCostClimbingStairs746 {
public static void main(String[] args) {
int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
System.out.println(minCostClimbingStairs(cost));
}
public static int minCostClimbingStairs(int[] cost) {
int length = cost.length;
int[] f = new int[length+1]; //设定每次的0最优代价
f[0] = 0; //初始化来到第一个台阶的最小代价
f[1] = 0; //初始化来到第二个台阶的最小代价
for (int i = 2; i < length+1; i++) {
f[i] = Math.min(f[i-2]+cost[i-2],f[i-1]+cost[i-1]);
}
return f[length];
}
}
121.
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0) return 0;
int minprices=prices[0];
int profit=0;
for(int i=1;i<prices.size();++i){
profit=max(prices[i]-minprices,profit);
minprices=minprices>prices[i]?prices[i]:minprices;
}
return profit;
}
};
1143.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
l = [[0]*(n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
l[i][j] = l[i-1][j-1] + 1
else:
l[i][j] = max(l[i-1][j], l[i][j-1])
return l[-1][-1]
|