1、最大组合数
给你 m个整数，你可以按照一定的顺序将他们首尾相连构成一个新的组合数字。请输出值最大的组合数字。
如整数1，23，组合起来有两种情况，123和231，因为231>123，所以231答案。
再比如， 输入:123，456，78，输出:78456123。
请你使用C++实现。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>// 自定义排序函数
bool compare(const std::string &a, const std::string &b) {return a + b > b + a;
}std::string largestNumber(std::vector<int> &nums) {// 将整数转为字符串std::vector<std::string> numStrs;for (int num : nums) {numStrs.push_back(std::to_string(num));}// 使用自定义的比较函数进行排序std::sort(numStrs.begin(), numStrs.end(), compare);// 如果排序后第一个字符串是 "0"，说明所有数字都是 0if (numStrs[0] == "0") {return "0";}// 拼接排序后的字符串std::string result;for (const std::string &str : numStrs) {result += str;}return result;
}int main() {// 输入测试数据std::vector<int> nums = {123, 456, 78};// 输出最大组合数字std::string result = largestNumber(nums);std::cout << "最大组合数字: " << result << std::endl;return 0;
}这个题主要用到了字典序，字典序遵循以下规则：
- 首先比较两个字符串的第一个字符。字母或数字越小的排在前面，越大的排在后面。
- 如果第一个字符相同，则继续比较第二个字符，以此类推，直到找到不同的字符为止。
- 如果一个字符串的前缀与另一个字符串相同，较短的字符串排在前面。
在程序中，字典序常用来对字符串进行排序，比如在C++的 std::sort 中，默认的比较方式就是字典序。
2、公平送礼
现在进行礼品派发活动，不同礼品价格不同，为公平起见，需要将金部的礼品公平的分配到粉丝手中，里每位粉丝全到的礼品总价格相同。请帮忙确认以下的礼品教量和价格是否可以满是公平的分配原则，可以则返回true，否则返回false。
输入：5，4，1，3，2，3，2
输出：true
因为可以按照(5)、(2，3)、(2，3)、(1，4)组合。
C语言实现。
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param prices int整型一维数组 礼物的价格* @param pricesLen int prices数组长度* @param k int整型 粉丝人数* @return bool布尔型*/
#include <stdlib.h>
#include <stdbool.h>
int mycompare(const void* p1, const void* p2) {return *(int*)p2 - *(int*)p1;
}
// 回溯法
bool huisu(int* prices, int* fans, int targetPrice, int idx, int pricesLen, int k) {if (idx == pricesLen) return true;int cur = prices[idx];for (int i = 0; i < k; i++) {if(fans[i] + cur <= targetPrice) {fans[i] += cur;int a = fans[i];// 如果满足就再多分一份礼物if (huisu(prices, fans, targetPrice, idx+1, pricesLen, k)) {return true;}fans[i] -= cur;}if(fans[i] == 0) break;}return false;
}
bool canEqualDistribution(int* prices, int pricesLen, int k) {// write code hereint sum = 0;for (int i = 0; i < pricesLen; i++) {sum += prices[i];}if (sum % k != 0) {return false;}int targetPrice = sum / k;qsort(prices, pricesLen, sizeof(int), mycompare);if (prices[0] > targetPrice) return false;int *fans = (int*)calloc(k, sizeof(int));bool res = huisu(prices, fans, targetPrice, 0, pricesLen, k);free(fans);return res;
}int main() {int prices[] = {5, 4, 1, 3, 2, 3, 2};int n = sizeof(prices) / sizeof(prices[0]);int k = 4;canEqualDistribution(prices, n, k);return 0;
}
这道题主要用回溯法解决，注意C语言的语法问题。
3、最长递增子序列
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int longestIncreasingSubsequence(const vector<int> &nums)
{if (nums.empty())return 0;// dp[i] 代表以 nums[i] 结尾的最长递增子序列的长度vector<int> dp(nums.size(), 1);int maxLength = 1;for (int i = 1; i < nums.size(); ++i){for (int j = 0; j < i; j++){if (nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}maxLength = max(maxLength, dp[i]);}cout << maxLength << endl;cout << dp[nums.size() - 1] << endl;return dp[nums.size() - 1];
}int main()
{int n;cin >> n;vector<int> nums(n);for (int i = 0; i < n; ++i){cin >> nums[i];}cout << longestIncreasingSubsequence(nums) << endl;return 0;
}动态规划求解，这里注意要用两个for循环，一个是不行的，会忽略掉很多种情况。一个for循环遍历求dp[i]，另一个for循环查看有没有比nums[i]小的，只要有都加入子序列。