C/C++每日一练(20230422) 存在重复元素、组合总和、给表达式添加运算符-阿里云开发者社区

C/C++每日一练(20230422) 存在重复元素、组合总和、给表达式添加运算符

2024-01-30 38

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C/C++每日一练(20230422) 存在重复元素、组合总和、给表达式添加运算符

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 <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
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 <= 10
num 仅含数字
-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;
}