笔试算法题分享

草船借箭

题目:

题目描述:
程序员小周同学这几天在看《三国演义》。今天他看到了“草船借箭”这一回,在钦佩诸葛亮巧借东风向曹操“借"箭的同
时,小周想到这么一个问题: 如果诸葛亮一共派出了N条放置草人的船来“借"箭。“悚慨”的曹操向第1条草船上射了A支
箭、第2条草船上射了B支箭,第3条草船上射的箭的数量等于前面两条船上箭的数量之和多一支,第4条草船上射的箭的
数量等于前面三条船上的箭的数量之和多一支,...,以此类推,第N条草船上箭的数量等于前面N-1条船上箭的数量之和
多一支。 下面问题来了,请问这一次诸葛亮一共从曹操那里“借”了多少支箭呢?
输入描述
输入三个正整数N、A和B,三个正整数都不超过1000,并且保证N>1,且两两之间用空格隔开。
输出描述
输出诸葛亮“借”箭的总数量。结果对1e9+7取模。
样例输入
4 1 2
样例输出
15

思路:

  1. 求出每条船上的箭头数量。由nums保存

​ a.当天箭头的数量是前面箭头数量和+1,由 preSum保存

  1. 求出所有总和,即nums数组求和即可

如果写过斐波拉切数列那么本题思路就会比较明确。


#include <cmath>
#include <vector>
#include <stdint.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <climits>
#include <deque>
#include <bitset>
#include <functional>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <stack>
#include <queue>
using namespace std; 

int main() {
    long long mod = 1e9 + 7;
    int n = -1; cin >> n;
    vector<int> nums(n,0);
    cin >> nums[0] >> nums[1];
    long long preSum = nums[0] + nums[1];
    for (int i = 2; i < n; ++i) {
        nums[i] = (preSum + 1)%mod;
        preSum += nums[i];
        preSum %= mod;
    }
    long long res = 0;
    for (int i = 0; i < nums.size(); ++i) {
        res += nums[i];
        res %= mod;
    }
    cout << res << endl;
    return 0;
}

随机数选最少数字求和

本题也可见https://blog.csdn.net/qq_43522889/article/details/132460220,但是个人觉得有些链接中写的思路有问题。

题目:

小明用计算机随机生成了N个正整数,他希望从这N个数中选取若干个数,使得它们的和等于M。这些随机生成的数字可能会相同,但是每个数字最多只允许使用一次。
当然这样的选取方案可能不存在,也可能有多个。
现在希望编写一个程序,能够找出数字个数最少的选取方案,输出对应的最少数字的个数,如果无解输出“No solution”。
输入描述:

单组输入,每组入2行。
第1行包含两个正整数N和M,分别表示初始输入的正整数个数和目标数字和(N<=1e3,M<=1e5)。
第2行为N个正整数,两两之间用空格隔开(每一个正整数均小于等于1e5)。
输出描述:

输出数字个数最少的选取方案中所包含的最少数字个数,如果无解输出“No solution”。
样例:

输入
5 5
1 3 2 1 1
输出
2

思路:

只需要输出最后的个数,因此大概率是dp。

dp三要素:

​ dp含义:dp[i][j]表示考虑前i个数字的情况下,组合成j的最少数字个数。

​ 属性:最小值,最少数字个数。

​ 状态转移方程:

dp[i][j] = min({ dp[i][j], dp[i - 1][j] });
if (j >= thisNum) {
dp[i][j] = min({dp[i][j],dp[i - 1][j - thisNum] + 1 });
}

代码:



#include <cmath>
#include <vector>
#include <stdint.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <climits>
#include <deque>
#include <bitset>
#include <functional>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <stack>
#include <queue>
using namespace std; 

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> dp(n + 1, vector<int>(m+10, INT_MAX/2));//dp[i][j]表示考虑前i个数字,组合为j的最小的数字个数
    for (int i = 0; i < n + 1; ++i) {
        dp[i][0] = 0;//任何组合组成0 需要的个数是0个
    }
    vector<int> numsVt;
    for (int i = 0; i < n; ++i) {
        int t = -1; cin >> t;
        numsVt.push_back(t);
    }
    for (int i = 1; i <= n; ++i) {
        int thisNum = numsVt[i - 1];
        if (thisNum > m) { continue; }
        dp[i][thisNum] = 1;  //特殊赋值
        
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = min({ dp[i][j], dp[i - 1][j] });
            if (j >= thisNum) {
                dp[i][j] = min({dp[i][j],dp[i - 1][j - thisNum] + 1 });
            }

        }
    }
    if (dp[n][m] == INT_MAX / 2) {
        cout << "No solution" << endl;
    }
    else
    {
        cout << dp[n][m] << endl;
    }
    return 0;
}

我的博客园:https://www.cnblogs.com/swx123
我的github(代码一般都放在这里):https://github.com/578223592

热门相关:慕少,你老婆又重生了   名门盛婚:首席,别来无恙!   我成了暴戾帝君的小娇包   网游三国之城市攻略   嫡嫁千金