1. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
出处：
https://edu.csdn.net/practice/26235228
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: bool containsDuplicate(vector<int> &nums) { if (nums.empty()) { return false; } sort(nums.begin(), nums.begin() + nums.size()); for (int i = 0; i < nums.size() - 1; i++) { if (nums[i] == nums[i + 1]) { return true; } } return false; } }; int main() { Solution s; vector<int> nums = {1,2,3,1}; cout << (s.containsDuplicate(nums) ? "true" : "false") << endl; nums = {1,2,3,4}; cout << (s.containsDuplicate(nums) ? "true" : "false") << endl; nums = {1,1,1,3,3,4,3,2,4,2}; cout << (s.containsDuplicate(nums) ? "true" : "false") << endl; return 0; }
输出：
true
false
true
2. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
输出：[[7],[2,2,3]]
示例 2：
输入：candidates = [2,3,5], target = 8,
输出：[[2,2,2,2],[2,3,3],[3,5]]
提示：
1 <= candidates.length <= 301 <= candidates[i] <= 200candidate中的每个元素都是独一无二的。1 <= target <= 500
以下程序实现了这一功能，请你填补空白处内容：
···c++ #include using namespace std; class Solution { public: vector> combinationSum(vector &candidates, int target) { vector> res; dfs(candidates, 0, target, res); return res; } private: vector stack; void dfs(vector &candidates, int start, int target, vector> &res) { if (target < 0) { return; } else if (target == 0) { res.push_back(stack); } else { for (int i = start; i < candidates.size(); i++) { stack.push_back(candidates[i]); _____________________________; stack.pop_back(); } } } }; ```
出处：
https://edu.csdn.net/practice/26235229
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<vector<int>> combinationSum(vector<int> &candidates, int target) { vector<vector<int>> res; dfs(candidates, 0, target, res); return res; } private: vector<int> stack; void dfs(vector<int> &candidates, int start, int target, vector<vector<int>> &res) { if (target < 0) { return; } else if (target == 0) { res.push_back(stack); } else { for (int i = start; i < candidates.size(); i++) { stack.push_back(candidates[i]); dfs(candidates, i, target - candidates[i], res); stack.pop_back(); } } } }; string ArrayToString(vector<int> arr){ string res = "["; int size = arr.size(); for (int i = 0; i < size; i++) { res += to_string(arr[i]); if (i != size-1) { res += ","; } } return res + "]"; } void PrintArrays(vector<vector<int>> vect){ cout << "["; int size = vect.size(); for (int i = 0; i < size; i++) { cout << ArrayToString(vect[i]); if (i != size-1) { cout << ","; } } cout << "]" << endl; } int main() { Solution s; vector<int> candidates = {2,3,6,7}; PrintArrays(s.combinationSum(candidates, 7)); candidates = {2,3,5}; PrintArrays(s.combinationSum(candidates, 8)); return 0; }
输出：
[[2,2,3],[7]]
[[2,2,2,2],[2,3,3],[3,5]]
3. 给表达式添加运算符
给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。
示例 1:
输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]
示例 2:
输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
示例 3:
输入: num = "105", target = 5
输出: ["1*0+5","10-5"]
示例 4:
输入: num = "00", target = 0
输出: ["0+0", "0-0", "0*0"]
示例 5:
输入: num = "3456237490", target = 9191
输出: []
提示：
1 <= num.length <= 10num仅含数字-2^31 <= target <= 2^31 - 1
出处：
https://edu.csdn.net/practice/26235230
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<string> addOperators(string num, int target) { vector<string> res; addOperatorsDFS(num, target, 0, 0, "", res); return res; } void addOperatorsDFS(string num, int target, long long diff, long long curNum, string out, vector<string> &res) { if (num.size() == 0 && curNum == target) res.push_back(out); for (int i = 1; i <= num.size(); ++i) { string cur = num.substr(0, i); if (cur.size() > 1 && cur[0] == '0') return; string next = num.substr(i); if (out.size() > 0) { addOperatorsDFS(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res); addOperatorsDFS(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res); addOperatorsDFS(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res); } else addOperatorsDFS(next, target, stoll(cur), stoll(cur), cur, res); } } }; string ArrayToString(vector<string> arr){ string res = "["; int size = arr.size(); for (int i = 0; i < size; i++) { res += arr[i]; if (i != size-1) { res += ","; } } return res + "]"; } int main() { Solution s; string num = "123"; cout << ArrayToString(s.addOperators(num, 6)) << endl; num = "232"; cout << ArrayToString(s.addOperators(num, 8)) << endl; num = "105"; cout << ArrayToString(s.addOperators(num, 5)) << endl; num = "00"; cout << ArrayToString(s.addOperators(num, 0)) << endl; num = "3456237490"; cout << ArrayToString(s.addOperators(num, 9191)) << endl; num = "3236"; cout << ArrayToString(s.addOperators(num, 24)) << endl; return 0; }
输出：
[1+2+3,1*2*3]
[2+3*2,2*3+2]
[1*0+5,10-5]
[0+0,0-0,0*0]
[]
[3*2+3*6,3*2*3+6]
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
