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; }
输出：
1
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; }
输出：
[[-1,-1,2],[-1,0,1]]
