九日集训第三天

目录

搜索旋转排序数组

搜索旋转排序数组||

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

爬楼梯

斐波那契数

第N个泰波那契数

差的绝对值为K的数对数目

猜数字

拿硬币

山峰数组的峰顶索引

---

搜索旋转排序数组

class Solution {
public:int search(vector<int>& nums, int target) {for(int i=0;i<nums.size();i++){if(nums[i]==target)return i;}return -1;}
};

搜索旋转排序数组||

class Solution {
public:bool search(vector<int>& nums, int target) {for(int i=0;i<nums.size();i++){if(nums[i]==target)return true;}return false;}
};

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

class Solution {
public:int findMin(vector<int>& nums) {int res=INT_MAX;for(int i=0;i<nums.size();i++){res=min(res,nums[i]);}return res;}
};

爬楼梯

class Solution {
public:int climbStairs(int n) {if(n<=3)return n;int a=1;int b=2;for(int i=3;i<=n;i++){int t=a+b;a=b;b=t;}return b;}
};

斐波那契数

class Solution {
public:int fib(int n) {if(n<=1)return n;int a=0;int b=1;for(int i=2;i<=n;i++){int t=a+b;a=b;b=t;}return b;}
};

第N个泰波那契数

class Solution {
public:int tribonacci(int n) {if(n==0)return 0;if(n==1)return 1;if(n==2)return 1;int a=0;int b=1;int c=1;for(int i=3;i<=n;i++){int C=a+b+c;int B=c;int A=b;a=A;b=B;c=C;}return c;}
};

差的绝对值为K的数对数目

class Solution {
public:int countKDifference(vector<int>& nums, int k) {int res=0;for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){if(abs(nums[i]-nums[j])==k)res++;}}return res;}
};

猜数字

class Solution {
public:int game(vector<int>& guess, vector<int>& answer) {int res=0;for(int i=0;i<3;i++){if(guess[i]==answer[i])res++;}return res;}
};

拿硬币

class Solution {
public:int minCount(vector<int>& coins) {int res=0;for(int i=0;i<coins.size();i++){if(coins[i]%2==1){res++;coins[i]--;}res+=coins[i]/2;}return res;}
};

山峰数组的峰顶索引

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left=1;int right=arr.size()-2;int res=0;while(left<=right){int mid=left+((right-left)>>1);if(arr[mid]<arr[mid+1]){left=mid+1;}else if(arr[mid]>arr[mid+1]){right=mid-1;res=mid;}}return res;}
};