【思特奇杯·云上蓝桥-算法集训营】第3周

【思特奇杯·云上蓝桥-算法集训营】第3周

目录

509. 斐波那契数1137. 第 N 个泰波那契数70. 爬楼梯746. 使用最小花费爬楼梯121. 买卖股票的最佳时机剑指 Offer II 095. 最长公共子序列杨辉三角节点选择耐摔指数K 好数

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

class Solution
{
public:
	int fib(int n)
	{
		if (n <= 0)
			return n;
		int a = 0, b = 1, c = 1;
		for (int i = 3; i <= n; i++)
		{
			a = b;
			b = c;
			c = a + b;
		}
		return c;
	}
};

1137. 第 N 个泰波那契数

class Solution {
public:
    int tribonacci(int n) {
        if(n<=2)return n==0?0:1;
        long long a=0,b=1,c=1,d=2;
        for(int i=3;i<=n;i++)
        {
            a=b;
            b=c;
            c=d;
            d=c+a+b;
        }
        return c;
    }
};

70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        if(n<=3)return n;
        int a=1,b=2,c=3;
        for(int i=4;i<=n;i++){
            a=b;
            b=c;
            c=a+b;
        }
        return c;
    }
};

746. 使用最小花费爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int n = cost.size();
        vector dp(n + 1);
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};

121. 买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

剑指 Offer II 095. 最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector dp(text2.size()+1);
        for(int i = 1;i<=text1.size();i++){
            int pre=0;
            for(int j =1;j<=text2.size();j++){
                // cur表示（i，j）下一次循环就变成（i-1，j-1）了
                int cur = dp[j];
                // i-1,j-1 表示字符串从0开始，但是dp从1开始
                if(text1[i-1]==text2[j-1]){
                    dp[j]=pre+1;
                }else{
                    dp[j]=max(dp[j],dp[j-1]);
                }
                //pre 表示（i-1，j-1）
                pre =cur;
            }
        }
        return dp[text2.size()];
    }

};

杨辉三角

#include 
#include 
#include 
using namespace std;
typedef long long LL;
int n;
LL C(int a, int b)   //计算C（a，b）
{
    LL res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++)
    {
        res = res * i / j;
        if(res > n)
            return res;     // 大于n已无意义，且防止爆LL
    }
    return res;
}
bool check(int k)
{
    // 二分该斜行,找到大于等于该值的第一个数
    // 左边界2k，右边界为max(l, n)取二者最大，避免右边界小于左边界
    int l = 2 * k, r = max(n,l);
    while(l < r)
    {
        int mid = l + r >> 1;
        if(C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if(C(r, k) != n)
        return false;
    cout << 1ll*(r + 1) * r / 2 + k + 1 << endl;
    return true;
}
int main()
{
    cin >> n;
    // 从第16斜行枚举
    for(int i = 16; ; i--)
        if(check(i))
            break;
    return 0;
}

节点选择

#include 
#include 
using namespace std;

int dp[100010][2];
vector> v;

void dfs(int node, int pre)
{
	for (int i = 0; i < v[node].size(); i++)
	{
		int temp = v[node][i];
		if (temp != pre)
		{
			dfs(temp, node);
			dp[node][0] += max(dp[temp][0], dp[temp][1]);
			dp[node][1] += dp[temp][0];
		}
	}
}

int main()
{
	int n, a, b;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> dp[i][1];
	}
	v.resize(n + 1);
	for (int i = 1; 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]);
	return 0;
}

耐摔指数

#include 
using namespace std;

int f2[105], f3[105];

int main()
{
	int n;
	cin >> 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;
}

K 好数

#include 
#include 
using namespace std;
long long d[105][105];
const int INF = 1000000007;
long long sum;
int main()
{
	int k, l, i, j, t;
	cin >> k >> l;
	for (j = 0; j < k; j++)
		d[1][j] = 1;
	for (i = 2; i <= l; i++)
		for (j = 0; j < k; j++)
			for (t = 0; t < k; t++)
				if (t != j - 1 && t != j + 1)
				{
					d[i][j] += d[i - 1][t];
					d[i][j] %= INF;
				}
	sum = 0;
	for (j = 1; j < k; j++)
	{
		sum += d[l][j];
		sum %= INF;
	}
	cout << sum << endl;
	return 0;
}