1. 求尾数与常数之和
数列的前3项都为1，从第4项开始，每项都是其前3项的和：1, 1, 1, 3, 5, 9, 17, … 请你编程求出数列第N项的4位尾数与90000之和。输入一个正整数N，输出所求的和。
出处：
https://edu.csdn.net/practice/27049317
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <iomanip> #include <algorithm> #include <set> using namespace std; #define NUM 10000 long long dp[1000000]; int main(){ int n; cin>>n; dp[1]=1; dp[2]=1; dp[3]=1; for(int i=4;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } cout<<dp[n]<<endl; long long x=dp[n]%NUM+90000; cout<<x; system("pause"); return 0; }
输出：
略，本质就是扩展的斐波那契数列。
2. 删除有序数组中的重复项
给你一个有序数组 nums ， 请你 原地 删除 重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列
出处：
https://edu.csdn.net/practice/27049318
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int removeDuplicates(vector<int> &nums) { if (nums.size() == 0) { return 0; } int count = 1; for (int i = 1; i < nums.size(); i++) { if (nums[i - 1] != nums[i]) { nums[count++] = nums[i]; } } return count; } }; int main(){ Solution s; vector<int> nums = {1,1,2}; cout << s.removeDuplicates(nums) << endl; nums = {0,0,1,1,1,2,2,3,3,4}; cout << s.removeDuplicates(nums) << endl; return 0; }
输出：
2
5
3. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,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 = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
出处：
https://edu.csdn.net/practice/27049319
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int findMin(vector<int> &nums) { int left = 0, right = nums.size() - 1; int mid = (left + right) / 2; while (left < right) { mid = (left + right) / 2; if (nums[mid] > nums[right]) left = mid + 1; else right = mid; } return nums[left]; } }; int main(){ Solution s; vector<int> nums = {3,4,5,1,2}; cout << s.findMin(nums) << endl; nums = {4,5,6,7,0,1,2}; cout << s.findMin(nums) << endl; nums = {11,13,15,17}; cout << s.findMin(nums) << endl; return 0; }
输出：
1
0
11
