C/C++每日一练(20230404) 旋转排序数组最小值、石头剪刀布、三数之和-阿里云开发者社区

C/C++每日一练(20230404) 旋转排序数组最小值、石头剪刀布、三数之和

2024-01-30 20

版权

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

简介： C/C++每日一练(20230404) 旋转排序数组最小值、石头剪刀布、三数之和

1. 寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

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

输出：1

示例 2：

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

输出：0

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：

这道题是寻找旋转排序数组中的最小值的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

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

输出：

2. “石头剪刀布”游戏程序

设计一个“石头剪刀布”游戏程序。用户和程序分别扮演猜拳双方，用户选择石头、剪刀和布中的一项，程序随机选择另一项，与用户选择作比较，在界面中显示最终的胜负判定。

出处：

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

代码：

#include <stdlib.h>
#include <stdio.h>
int main()
{
    int id;
    int a[3]={1,2,3};
    int au = 0;
    while(1)
    {
        printf("1.剪刀,2.石头,3.布,0.退出\n");
        scanf("%d",&id);
        if(id == 0)
            break;
        au = a[rand()%3]; 
        if (au == 1)
        {
            printf("机器：剪刀\t");
            if(id == 1)
                printf("玩家:剪刀\t平局\n");
            else if(id == 2)
                printf("玩家:石头\t玩家赢\n");
            else
                printf("玩家:布\t机器赢\n");
        }
        else if(au == 2)
        {
            printf("机器：石头\t");
            if(id == 1)
                printf("玩家:剪刀\t机器赢\n");
            else if(id == 2)
                printf("玩家:石头\t平局\n");
            else
                printf("玩家:布\t玩家赢\n");
        }
        else
        {
            printf("机器：布\t");
            if(id == 1)
                printf("玩家:剪刀\t玩家赢\n");
            else if(id == 2)
                printf("玩家:石头\t机器赢\n");
            else
                printf("玩家:布\t平局\n");
        }
    }
    return 0;
}

输出：

略

3. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []

输出：[]

示例 3：

输入：nums = [0]

输出：[]

提示：

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

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

```c++
#include <algorithm>
#include <set>
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> r;
        if (nums.size() == 0)
            return r;
        sort(nums.begin(), nums.end());
        int cur, left, right;
        cur = 0;
        while (cur < nums.size())
        {
            if (nums[cur] > 0)
                break;
            left = cur + 1;
            right = nums.size() - 1;
            while (left < right)
            {
                int n = nums[cur] + nums[left] + nums[right];
                if (n == 0)
                {
                    r.emplace_back(vector<int>({nums[cur], nums[left], nums[right]}));
                    int t = left + 1;
                    __________________________;
                }
                else if (n > 0)
                {
                    int t = right - 1;
                    while (t > left && nums[t] == nums[right])
                        t--;
                    right = t;
                }
                else
                {
                    int t = left + 1;
                    while (t < right && nums[t] == nums[left])
                        t++;
                    left = t;
                }
            }
            int t = cur + 1;
            while (t < nums.size() && nums[t] == nums[cur])
                t++;
            cur = t;
        }
        return r;
    }
};
```

出处：

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

代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> r;
        if (nums.size() == 0)
            return r;
        sort(nums.begin(), nums.end());
        int cur, left, right;
        cur = 0;
        while (cur < nums.size())
        {
            if (nums[cur] > 0)
                break;
            left = cur + 1;
            right = nums.size() - 1;
            while (left < right)
            {
                int n = nums[cur] + nums[left] + nums[right];
                if (n == 0)
                {
                    r.emplace_back(vector<int>({nums[cur], nums[left], nums[right]}));
                    int t = left + 1;
          while (t < right && nums[t] == nums[left])
              t++;
          left = t;
          t = right - 1;
          while (t > left && nums[t] == nums[right])
              t--;
          right = t;
                }
                else if (n > 0)
                {
                    int t = right - 1;
                    while (t > left && nums[t] == nums[right])
                        t--;
                    right = t;
                }
                else
                {
                    int t = left + 1;
                    while (t < right && nums[t] == nums[left])
                        t++;
                    left = t;
                }
            }
            int t = cur + 1;
            while (t < nums.size() && nums[t] == nums[cur])
                t++;
            cur = t;
        }
        return r;
    }
};
void PrintArrays(vector<vector<int>> arr)
{
    cout << "[";
    for (int i = 0; i < arr.size(); i++) {
        cout << "[";
        for (int j = 0; j < arr[i].size(); j++) {
            cout << arr[i][j];
            if (j < arr[i].size() - 1) {
                cout << ",";
            }
        }
       cout << "]";
        if (i < arr.size() - 1) {
            cout << ",";
        }
    }
    cout << "]" << endl;
}
int main()
{
  Solution s;
  vector<int> nums = {-1,0,1,2,-1,-4};
  PrintArrays(s.threeSum(nums));
  return 0;
}