第一种用循环做,很简单
// 循环 class Solution { public: int search(vector& nums, int target) { for(int i = 0;i 第二种用二分来做
- 因为他说在某个地方翻转了,所以就变成了两条升序的序列。
- 第一步:二分,分开两条序列。
- 第二步:通过判断target与nums[0]的大小比较,判断target应该在哪一段
- 第三步:再次二分
class Solution { public: int search(vector81. 搜索旋转排序数组 II& nums, int target) { int l = 0,r = nums.size() - 1; while(l < r){ // 首先二分找两段 int mid = l + r + 1 >> 1; if(nums[mid] >= nums[0]) l = mid; // 如果mid >= 0 说明mid在第一段区间里,更新l else r = mid - 1; } // 第二步 if(target >= nums[0]) l = 0; else l = r + 1, r = nums.size() - 1; //再二分,找target while(l < r){ int mid = l + r >> 1; if(nums[mid] >= target) r = mid; else l = mid + 1; } return nums[r] == target ? r : -1; } }; 跟上一题一样,可以用二分也可以循环
比上一道题多了一点 *** 作,就是删掉前一段或者后一段重复的部分,反正题目只是要判断有没有,因为是重复,删掉一段另一段也会有,不会影响最后结果。
class Solution { public: bool search(vector153. 寻找旋转排序数组中的最小值1& nums, int target) { if(nums.empty()) return false; int R = nums.size() - 1; while(R >= 0 && nums[R] == nums[0]) R--; if(R < 0)return nums[0] == target; int l = 0,r = R; while(l < r){ int mid = l + r + 1 >> 1; if(nums[mid] >= nums[0]) l = mid; else r = mid - 1; } if(target >= nums[0]) l = 0; else l++,r = R; while(l < r){ int mid = l + r >> 1; if(nums[mid] >= target) r = mid; else l = mid + 1; } return nums[r] == target; } }; 二分没的说
class Solution { public: int findMin(vector70. 爬楼梯& nums) { int l = 0,r = nums.size() - 1; if(nums[r] >= nums[l]) return nums[0]; while(l < r){ int mid = l + r >> 1; if(nums[mid] < nums[0]) r = mid; else l = mid + 1; } return nums[r]; } }; 0 1 2 3 4 5 6 7 8(前面的数是指从前一个台阶爬一个台阶上来,后面的数是从前两个台阶爬两个台阶上来)
1 1 1+1 2+1 3+2 5+3 8+5 。。。。。
所以我们能看出来每一个是前两个的和,也就是斐波那契额数列
class Solution { public: int climbStairs(int n) { int a = 1,b = 1; while(--n){ int c = a + b; a = b,b = c; } return b; } };509. 斐波那契数斐波那契递归
class Solution { public: int fib(int n) { if(n == 0) return 0; if(n <= 2) return 1; return fib(n - 1) + fib(n - 2); } };1137. 第 N 个泰波那契数就照葫芦画瓢
class Solution { public: int tribonacci(int n) { if(n == 0) return 0; if(n < 3) return 1; int a = 0,b = 1,c = 1; n = n-2; while(n--){ int d = a + b + c; a = b,b = c,c = d; } return c; } };欢迎分享,转载请注明来源:内存溢出
评论列表(0条)