1.背包问题
using namespace std; int w[501]; long long v[501]; long long dp[501][501]; //
int main() {
int N, c;
cin >> N >> c;
for (int i = 1; i <= N; i++) {
cin >> w[i];
}
for (int i = 1; i <= N; i++) {
cin >> v[i];
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= c; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= c; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
cout << dp[N][c] << endl;
return 0;
}
2.戳气球
using namespace std; int main(){
int points[102];
points[0] = 1;
int x = 1;
int dp[102][102] = {0};
int temp;
while(cin>>temp){
points[x++] = temp;
if (cin.peek() == '\n') break;
}
points[x] = 1;
int n = x-1;
for (int i = n; i >= 0; i--) {
for (int j = i + 2; j <= x; j++) {
for (int k = i + 1; k < j; k++) {
int sum = points[i] * points[k] * points[j];
sum += dp[i][k] + dp[k][j];
dp[i][j] = max(dp[i][j], sum);
}
}
}
cout<<dp[0][x];
} 3.打家劫舍
using namespace std; int main(){
int A[101];
int dp[101]={0};
int n,x=0;
while(cin>>n){
A[x++] = n;
if (cin.peek() == '\n') break;
}
dp[0] = A[0];
for(int i=1;i<x;i++){
dp[i] = max(dp[i-1],dp[i-2]+A[i]);
}
cout<<dp[x-1];
} 4.大礼包
using namespace std;
vector price; vector<vector> special; vector needs; int n, m; int min_cost;
int calc_single(const vector& cur_needs) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += cur_needs[i] * price[i];
}
return sum;
}
bool is_valid(const vector& sp, const vector& cur_needs) {
for (int i = 0; i < n; i++) {
if (sp[i] > cur_needs[i]) return false;
}
return true;
}
void backtrack(vector cur_needs, int cost) {
int current = cost + calc_single(cur_needs);
if (current < min_cost) {
min_cost = current;
}
for (const auto& sp : special) {
if (is_valid(sp, cur_needs)) {
vector<int> new_needs = cur_needs;
for (int i = 0; i < n; i++) {
new_needs[i] -= sp[i];
}
backtrack(new_needs, cost + sp[n]);
}
}
}
int main() {
int x;
string line;
getline(cin, line);
istringstream iss(line);
while (iss >> x) {
price.push_back(x);
}
m = price.back();
price.pop_back();
n = price.size();
for (int i = 0; i < m; i++) {
vector<int> sp;
for (int j = 0; j < n + 1; j++) {
cin >> x;
sp.push_back(x);
}
int single_sp = 0;
for (int j = 0; j < n; j++) {
single_sp += sp[j] * price[j];
}
if (sp[n] < single_sp) {
special.push_back(sp);
}
}
needs.clear();
for (int i = 0; i < n; i++) {
cin >> x;
needs.push_back(x);
}
min_cost = calc_single(needs);
backtrack(needs, 0);
cout << min_cost << endl;
return 0;
} 5.电话号码字母组合
using namespace std;
//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 //答案按字母顺序返回。 //给出数字到字母的映射如下（与电话按键相同）。 // 注意 1 不对应任何字母。 vectors; vectora; int main() {
// 数字到字母映射（关键修正）
a.push_back(""); // 0
a.push_back(""); // 1
a.push_back("abc"); // 2
a.push_back("def"); // 3
a.push_back("ghi"); // 4
a.push_back("jkl"); // 5
a.push_back("mno"); // 6
a.push_back("pqrs"); // 7
a.push_back("tuv"); // 8
a.push_back("wxyz"); // 9
int n; cin >> n;
int num = 0;
while (n) {
int x= n %10;
s.push_back(a[x]);
n /= 10;
num++;
}
//cout << num;
reverse(s.begin(), s.end());
if (num == 0)cout << "[]";
else if (num == 1) {
cout << "[";
cout << s[0];
cout << "]";
}
else if (num == 2) {
cout << "[";
for (int i = 0; i < s[0].size(); i++) {
for (int j = 0; j < s[1].size(); j++) {
if(i==s[0].size()-1&&j==s[1].size()-1)cout << s[0][i] << s[1][j];
else cout << s[0][i] << s[1][j] << ", ";
}
}
cout << "]";
}
else if (num == 3) {
cout << "[";
for (int i = 0; i < s[0].size(); i++) {
for (int j = 0; j < s[1].size(); j++) {
for (int k = 0; k < s[2].size(); k++) {
if (i == s[0].size() - 1 && k == s[2].size() - 1 && j == s[1].size() - 1)cout << s[0][i] <<s[1][j] << s[2][k] ;
else cout << s[0][i] << s[1][j] << s[2][k]<<", ";
}
}
}
cout << "]";
}
else if (num == 4) {
cout << "[";
for (int i = 0; i < s[0].size(); i++) {
for (int j = 0; j < s[1].size(); j++) {
for (int k = 0; k < s[2].size(); k++) {
for (int m = 0; m < s[3].size(); m++) {
if (i == s[0].size() - 1 && k == s[2].size() - 1 && j == s[1].size() - 1 && m== s[3].size() - 1)cout << s[0][i] << s[1][j] << s[2][k]<<s[3][m] ;
else cout << s[0][i] << s[1][j] << s[2][k]<<s[3][m]<<", ";
}
}
}
}
cout << "]";
}
}
6.二叉树
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* construct(vector& nums, int left, int right) {
if (left > right) return nullptr;
int max_idx = left;
for (int i = left; i <= right; ++i) {
if (nums[i] > nums[max_idx]) max_idx = i;
}
TreeNode* node = new TreeNode(nums[max_idx]);
node->left = construct(nums, left, max_idx - 1);
node->right = construct(nums, max_idx + 1, right);
return node;
}
void preorder(TreeNode* root, string& res) {
if (!root) {
return; // 仅在有父节点时才添加null，避免尾部多余null
}
res += to_string(root->val) + " ";
if (root->left || root->right) { // 若有子节点，才处理左右孩子（包括null）
if (root->left) {
preorder(root->left, res);
} else {
res += "null ";
}
if (root->right) {
preorder(root->right, res);
} else {
res += "null ";
}
}
}
int main() {
vector<int> nums;
int x;
while (cin >> x) {
nums.push_back(x);
}
if (nums.empty()) {
cout << endl;
return 0;
}
TreeNode* root = construct(nums, 0, nums.size() - 1);
string res;
preorder(root, res);
if (!res.empty()) res.pop_back(); // 移除最后的空格
cout << res << endl;
return 0;
} 7.反转括号
using namespace std;
vectorv; stacks;
int num1 = 0, num2 = 0;
int main() {
string str;
cin >> str;
num1 = 0; num2 = 0;
for (int i = 0; i < (int)str.size(); i++) {
char n = str[i];
// 不在括号中：直接进 v
if (num1 == num2 && n != '(') {
v.push_back(n);
continue;
}
// 遇到 '('：开始进入括号处理
if (n == '(') {
num1++;
s.push(n);
continue;
}
// 在括号内：字母进栈
if (n >= 'a' && n <= 'z') {
s.push(n);
continue;
}
// 遇到 ')'：完成一层反转（从内到外）
if (n == ')') {
num2++;
// 把最近 '(' 后面的内容弹出并“反转”回栈
vector<char> tmp;
while (!s.empty() && s.top() != '(') {
tmp.push_back(s.top());
s.pop();
}
if (!s.empty() && s.top() == '(') s.pop(); // 弹掉 '('
// tmp 的顺序就是反转后的顺序，直接压回栈
for (int j = 0; j < (int)tmp.size(); j++) s.push(tmp[j]);
// 如果这一段括号整体匹配结束，把栈内容输出到 v
if (num1 == num2) {
vector<char> out;
while (!s.empty()) {
out.push_back(s.top());
s.pop();
}
reverse(out.begin(), out.end());
for (int j = 0; j < (int)out.size(); j++) v.push_back(out[j]);
}
}
}
for (int i = 0; i < (int)v.size(); i++) cout << v[i];
return 0;
}
8.分割回文串
using namespace std; vector<vector> res; vector path; string s; bool isPalindrome(int l, int r) {
while(l < r) {
if(s[l] != s[r]) return false;
l++;
r--;
}
return true;
} void backtrack(int start) {
if(start == s.size()) {
res.push_back(path);
return;
}
for(int i = start; i < s.size(); i++) {
if(isPalindrome(start, i)) {
path.push_back(s.substr(start, i - start + 1));
backtrack(i + 1);
path.pop_back();
}
}
} int main() {
cin >> s;
backtrack(0);
cout << "[";
for(int i = 0; i < res.size(); i++) {
cout << "[";
for(int j = 0; j < res[i].size(); j++) {
cout << res[i][j];
if(j != res[i].size() - 1) cout << ", ";
}
cout << "]";
if(i != res.size() - 1) cout << ", ";
}
cout << "]";
return 0;
} 9.括号生成
using namespace std; vectorv; string s; vectorans; //数字 n 代表生成括号的对数，请你设计一个函数， //用于能够生成所有可能的并且有效的括号组合。 //有效括号组合需满足：左括号必须以正确的顺序闭合。 //请按照括号生成的层数有大到小排序，如输入3时，先生成((()))，最后再生成 ()()() //[((())), (()()), (())(), ()(()), ()()()]
void dfs(int l,int r,int n) {
if (s.size() == n * 2) {
ans.push_back(s);
return;
}
if (l < n) {
s.push_back('(');
dfs(l + 1, r, n);
s.pop_back();
}
if (r < l) {
s.push_back(')');
dfs(l, r + 1, n);
s.pop_back();
}
}
int main() {
int n; cin >> n;
dfs(0, 0, n);
cout << "[";
for (int i = 0; i < ans.size(); i++) {
if (i != ans.size() - 1)
cout << ans[i] << ", ";
else
cout << ans[i];
}
cout << "]";
}
10.连续数组最大和
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int max_sum = nums[0];
int current = nums[0];
for (int i = 1; i < n; i++) {
current = max(nums[i], current + nums[i]);
max_sum = max(max_sum, current);
}
cout << max_sum;
return 0;
} 11.目标和
using namespace std; vectorv; //给你一个整数数组 nums 和一个整数 target 。 //向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： //例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 // 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 //标准输入 //1 1 1 1 1 //3 //标准输出 //5 int num = 0; int target; void dfs(int cnt,int temp) {
if (cnt == v.size()) {
if (temp == target) {
num++;
}
return;
}
dfs(cnt+1, temp + v[cnt]);
dfs(cnt+1, temp - v[cnt]);
}
int main() {
int n;
while (cin >> n) {
v.push_back(n);
if (cin.peek() == '\n') break;
}
cin >> target;
dfs(0, 0);
cout << num;
return 0;
} 12.三数之和
using namespace std;
static vector<vector> ans; static vector path; static vector a; static int n;
void dfs(int start, int depth, long long sum) {
if (depth == 3) {
if (sum == 0) ans.push_back(path);
return;
}
// 剪枝：剩余元素不够选满3个
if (n - start < 3 - depth) return;
for (int i = start; i < n; i++) {
// 去重：同一层同一个值只用一次
if (i > start && a[i] == a[i - 1]) continue;
// 进一步剪枝（利用已排序）
// 估算最小可能和：当前选a[i] + 后面最小的(3-depth-1)个
long long minSum = sum + a[i];
int need = 3 - (depth + 1);
for (int t = 1; t <= need; t++) minSum += a[i + t]; // i+t一定存在，因为前面保证元素够
if (minSum > 0) break; // 后面只会更大，直接结束循环
// 估算最大可能和：当前选a[i] + 后面最大的need个
long long maxSum = sum + a[i];
for (int t = 0; t < need; t++) maxSum += a[n - 1 - t];
if (maxSum < 0) continue; // 即使取最大也不够到0，换更大的a[i]
path.push_back(a[i]);
dfs(i + 1, depth + 1, sum + a[i]);
path.pop_back();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
// 小剪枝：如果最小>0或最大<0，直接无解
if (n < 3 || a.front() > 0 || a.back() < 0) {
cout << "[]";
return 0;
}
dfs(0, 0, 0);
// 输出
cout << "[";
for (int i = 0; i < (int)ans.size(); i++) {
cout << "[";
for (int j = 0; j < 3; j++) {
cout << ans[i][j];
if (j != 2) cout << ",";
}
cout << "]";
if (i != (int)ans.size() - 1) cout << ",";
}
cout << "]";
return 0;
} 13.跳跃游戏
using namespace std;
int jump(vector& nums) {
int n = nums.size();
if (n == 1) return 0;
int jumps = 0;
int current_end = 0;
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
farthest = max(farthest, i + nums[i]);
if (i == current_end) {
jumps++;
current_end = farthest;
}
}
return jumps;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cout << jump(nums);
return 0;
} 14.完全平方数
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n + 1, 1e9);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[n];
return 0;
}
15.优美的数列
using namespace std;
int cnt = 0; int n;
void backtrack(int pos, vector& used) {
if (pos > n) {
cnt++;
return;
}
for (int i = 1; i <= n; i++) {
if (!used[i] && (i % pos == 0 || pos % i == 0)) {
used[i] = true;
backtrack(pos + 1, used);
used[i] = false;
}
}
}
int main() {
cin >> n;
vector<bool> used(n + 1, false);
backtrack(1, used);
cout << cnt;
return 0;
} 16.找出所有子集的异或
using namespace std; vectorv; string s; vector<vector>res;
//找到所有的子集 //[1,3] 共有 4 个子集 空 、1、3、1，3
vector nums; int ans = 0;
void dfs(int idx, int curXor) {
// 所有元素都考虑完了
if (idx == nums.size()) {
ans += curXor;
return;
}
// 不选 nums[idx]
dfs(idx + 1, curXor);
// 选 nums[idx]
dfs(idx + 1, curXor ^ nums[idx]);
}
int main() {
int n;
while (cin >> n) {
nums.push_back(n);
}
dfs(0, 0);
cout << ans << endl;
return 0;
}
17.找到k个最长重复字符串
using namespace std;
int longestSubstring(string s, int k) {
int n = s.size();
if (n == 0 || k > n) return 0;
if (k == 0) return n;
vector<int> cnt(26, 0);
for (char c : s) cnt[c - 'a']++;
int split = -1;
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0 && cnt[i] < k) {
split = 'a' + i;
break;
}
}
if (split == -1) return n;
int max_len = 0;
int start = 0;
for (int i = 0; i < n; i++) {
if (s[i] == split) {
max_len = max(max_len, longestSubstring(s.substr(start, i - start), k));
start = i + 1;
}
}
max_len = max(max_len, longestSubstring(s.substr(start), k));
return max_len;
}
int main() {
string s;
int k;
cin >> s >> k;
cout << longestSubstring(s, k);
return 0;
} 18.整数拆分
using namespace std; int main(){
int N;
int dp[59]={0};
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
cin>>N;
for(int i=3;i<=N;i++){
for(int j=1;j<i;j++){
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
cout<<dp[N];
} 19.走网格
using namespace std; vectorv; //m行n列的网格，从左上角(1,1)出发，每一步只能向下或者向右，问共有多少种方法可以走到右下角(m,n)
int main() {
int m, n;
cin >> m >> n;
int dp[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0)dp[i][j] = 1;
else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
cout << dp[m - 1][n - 1];
} 20.组合问题
using namespace std; vectorv; string s; vector<vector>res; vectorans; //给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 //input:4 2 //output:[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] void dfs(int n,int k,int num) {
if (v.size() == k) {
res.push_back(v);
return;
}
for (int i = num; i <= n; i++) {
v.push_back(i);
dfs(n, k, i + 1);
v.pop_back();
}
} int main() {
int n, k;
cin >> n >> k;
dfs(n, k, 1);
cout << "[";
for (int i = 0; i < res.size(); i++) {
cout << "[";
for (int j = 0; j < res[i].size(); j++) {
if (j != res[i].size() - 1) cout << res[i][j] << ", ";
else cout << res[i][j];
}
cout << "]";
if (i != res.size() - 1) cout << ", ";
}
cout << "]";
} 21.最长回文串
using namespace std;
// 声明expand函数 int expand(string s, int left, int right);
string longestPalindrome(string s) {
int n = s.size();
if (n <= 1) return s;
int start = 0, maxLen = 1;
for (int i = 0; i < n; i++) {
int l1 = expand(s, i, i); // 奇数长度回文
int l2 = expand(s, i, i + 1); // 偶数长度回文
int len = max(l1, l2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2; // 计算起始位置
}
}
return s.substr(start, maxLen);
}
// 实现expand函数 int expand(string s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1; // 返回回文长度
}
int main() {
string s;
cin >> s;
cout << longestPalindrome(s);
return 0;
} 25.组合
using namespace std; vectorv; //给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 //你需要按顺序返回答案。 vector<vector>nums; void dfs(int start,int n,int k) {
if (v.size()==k) {
nums.push_back(v);
return;
}
for (int i = start; i <= n; i++) {
v.push_back(i);
dfs(i + 1, n, k);
v.pop_back();
}
}
int main() {
int n, k;
cin >> n >> k;
dfs(1, n, k);
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums[i].size(); j++) {
if (j != nums[i].size() - 1)cout << nums[i][j] << " ";
else cout << nums[i][j];
}
if (i != nums.size() - 1) cout << endl;
}
}
27.Partition to K Equal Sum Subsets
using namespace std; vectorv; //分割为k个等和子集 //给定整数组 nums 和整数 k，如果可以将该数组拆分为 k 个非空子集，且其和均相等，则返回 true。 //输入 //4 3 2 5 1 //3 //输出 //true
vector<vector>nums;
int main() {
int num = 0;
int n;
while (cin >> n) {
num += n;
v.push_back(n);
if (cin.peek() == '\n')break;
}
int k; cin >> k;
if (num % k == 0)cout << "true";
else cout << "false";
} 28.分割等和子集
using namespace std; vectorv; //给定一个非空的正整数数组 nums(nums.length < 5) ，请判断能否将这些数字分成元素和相等的两部分。 //输入 //1 5 11 5 //输出 //true
vector<vector>nums;
int main() {
int n;
int cnt = 0;
while (cin >> n) {
cnt++;
v.push_back(n);
if (cin.peek() == '\n')break;
}
//cout << cnt<<endl;
if (cnt == 1)cout << "false";
else if (cnt == 2) {
if (v[0] == v[1])cout << "true";
else cout << "false";
}
else if (cnt == 3) {
sort(v.begin(), v.end());
if (v[0] + v[1] == v[2]) cout << "true";
else cout << "false";
}
else
{
sort(v.begin(), v.end());
if (v[0] + v[3] == v[1] + v[2])cout << "true";
else if (v[3] == v[0] + v[1] + v[2])cout << "true";
else cout << "false";
}
}