C/C++每日一练(20230418) 搜索插入位置、最长有效括号、子集-阿里云开发者社区

C/C++每日一练(20230418) 搜索插入位置、最长有效括号、子集

2024-01-30 45

版权

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

简介： C/C++每日一练(20230418) 搜索插入位置、最长有效括号、子集

1. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5

输出: 2

示例 2:

输入: [1,3,5,6], 2

输出: 1

示例 3:

输入: [1,3,5,6], 7

输出: 4

示例 4:

输入: [1,3,5,6], 0

输出: 0

出处：

https://edu.csdn.net/practice/25855286

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int lo = -1;
        int hi = nums.size();
        while (lo + 1 < hi)
        {
            int mid = lo + (hi - lo) / 2;
            if (target > nums[mid])
            {
                lo = mid;
            }
            else
            {
                hi = mid;
            }
        }
        return hi;
    }
};
int main()
{
  Solution s;
  vector<int> nums = {1,3,5,6};
  cout << s.searchInsert(nums, 5) << endl;
  cout << s.searchInsert(nums, 2) << endl;
  cout << s.searchInsert(nums, 7) << endl;
  cout << s.searchInsert(nums, 0) << endl;
  return 0;
}

输出：

２

１

４

０

2. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"

输出：2

解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"

输出：4

解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""

输出：0

cdd提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

以下程序实现了这一功能，请你填补空白处的内容：

```c++
#include 
using namespace std;
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        stack stk;
        int invalid = -1;
        int len = 0, max_len = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(')
            {
                stk.push(i);
            }
            else
            {
                if (stk.empty())
                {
                    invalid = i;
                }
                else
                {
                    stk.pop();
                    ___________________;
                }
            }
        }
        return max_len;
    }
};
```

出处：

https://edu.csdn.net/practice/25855287

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        stack<int> stk;
        int invalid = -1;
        int max_len = 0;
        for (int i = 0; (size_t)i < s.length(); i++)
        {
            if (s[i] == '(')
            {
                stk.push(i);
            }
            else
            {
                if (stk.empty())
                {
                    invalid = i;
                }
                else
                {
                    stk.pop();
          if (stk.empty())
          {
              max_len = max(i - invalid, max_len);
          }
          else
          {
              max_len = max(i - stk.top(), max_len);
          }
                }
            }
        }
        return max_len;
    }
};
int main()
{
  Solution s;
  cout << s.longestValidParentheses("(()") << endl;
  cout << s.longestValidParentheses(")()())") << endl;
  cout << s.longestValidParentheses("") << endl;
  return 0;
}

输出：

3. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

以下程序实现了这一功能，请你填补空白处内容：

```c++
#include 
using namespace std;
class Solution
{
public:
    vector> subsets(vector &nums)
    {
        vector> res;
        dfs(nums, 0, res);
        return res;
    }
private:
    vector stack;
    void dfs(vector &nums, int start, vector> &res)
    {
        res.push_back(stack);
        for (int i = start; i < nums.size(); i++)
        {
            ______________;
        }
    }
};
```

出处：

https://edu.csdn.net/practice/25855288

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> subsets(vector<int> &nums)
    {
        vector<vector<int>> res;
        dfs(nums, 0, res);
        return res;
    }
private:
    vector<int> stack;
    void dfs(vector<int> &nums, int start, vector<vector<int>> &res)
    {
        res.push_back(stack);
        for (int i = start; (size_t)i < nums.size(); i++)
        {
      stack.push_back(nums[i]);
      dfs(nums, i + 1, res);
      stack.pop_back();
        }
    }
};
string vectorToString(vector<int> vect) {
    stringstream ss;
  ss << "[";
    for (size_t i = 0; i < vect.size(); i++)
  {
        ss << to_string(vect[i]);
        ss << (i < vect.size() - 1 ? "," : "");
    }
    ss << "]";
    return ss.str();
}
string vector2DToString(vector<vector<int>> vect) {
    string res = "[";
    size_t len = vect.size();
    for (size_t i = 0; i < len; i++)
  {
        res += vectorToString(vect[i]);
        if (i+1 != len)
          res += ",";
    }
    res += "]";
    return res;
}
int main()
{
  Solution s;
  vector<int> nums = {1,2,3};
  cout << vector2DToString(s.subsets(nums)) << endl;
  return 0;
}