C/C++每日一练(20230422)

简介: 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 <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]);
                _____________________________;
                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;
}


输出:

[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]




目录
相关文章
|
6月前
|
Linux 监控 Ubuntu
Linux 终端操作命令(1)
Linux 终端操作命令(1)
98 1
Linux 终端操作命令(1)
|
6月前
|
算法 Java Go
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
47 1
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
|
6月前
|
Linux 监控 Shell
Linux 终端命令之文件浏览(4) head, tail
Linux 终端命令之文件浏览(4) head, tail
61 0
Linux 终端命令之文件浏览(4) head, tail
|
6月前
|
Shell Linux 机器学习/深度学习
Linux 终端操作命令(3)内部命令用法
Linux 终端操作命令(3)内部命令用法
90 0
Linux 终端操作命令(3)内部命令用法
|
6月前
|
Python Linux Ubuntu
Linux系统部署Python语言开发运行环境
Linux系统部署Python语言开发运行环境
220 0
Linux系统部署Python语言开发运行环境
|
6月前
|
Go Unix 开发者
Go语言time库,时间和日期相关的操作方法
Go语言time库,时间和日期相关的操作方法
102 0
Go语言time库,时间和日期相关的操作方法
|
6月前
|
C++ 存储 Serverless
力扣C++|一题多解之数学题专场(2)
力扣C++|一题多解之数学题专场(2)
50 0
力扣C++|一题多解之数学题专场(2)
|
6月前
|
Go 机器学习/深度学习 Rust
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
87 0
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
|
6月前
|
Java Go C++
Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列
Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列
64 0
Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列
|
6月前
|
Java Go C++
Golang每日一练(leetDay0111) 摆动排序II\I Wiggle Sort
Golang每日一练(leetDay0111) 摆动排序II\I Wiggle Sort
57 0
Golang每日一练(leetDay0111) 摆动排序II\I Wiggle Sort