1、旋转数组的最小数字
题目如下：
接下来我会给出两种解题思路供大家去解决这个题：
解析如下：
根据题意我们知道这是一个数组问题，本质其实是一个求最小值问题
🔥方法一：
- 理论上，遍历一次即可，但是我们可以根据题面使用稍微高效且更简单一点的做法；
- 按照要求，要么是一个非递减排序的数组（最小值在最开始），要么是一个旋转(最小值在中间某个地方) ；
- 而且，旋转之后有个特征，就是在遍历的时候，原始数组是非递减的，旋转之后，就有可能出现递减，引起递减的数字，就是最小值
代码如下：
class Solution { public: int minArray(vector<int>& numbers) { if(numbers.empty()) return 0; for(int i=0; i<numbers.size()-1; ++i) { if(numbers[i] > numbers[i+1]) return numbers[i+1]; } return numbers[0]; } };
🔥方法二：
- 主要思路就是采用二分查找的方式，进行定位；
- 首先定义首尾下标，因为是非递减数组旋转，所以旋转最后可以看做成两部分，前半部分整体非递减，后半部分整体非递减，前半部分整体大于后半部分；
- 所以，我们假设如下定义，left指向最左侧，right指向最右侧，mid为二分之后的中间位置；
- 则，a[mid] >= a[left],说明mid位置在原数组前半部分，进一步说明，目标最小值，在mid的右侧，让left=mid；
- a[mid] < a[left], 说明mid位置在原数组后半部分，进一步说明，目标最小值，在mid的左侧，让right=mid；
- 这个过程，会让[left, right]区间缩小；
- 这个过程中，left永远在原数组前半部分，right永远在原数组的后半部分，而范围会一直缩小 ；
- 当left和right相邻时，right指向的位置，就是最小元素的位置；
- 但是，因为题目说的是非递减，也就意味着数据允许重复，因为有重复发，就可能会有a[left] == a[mid] == a[right]的情况，我们就无法判定数据在mid左侧还是右侧。（注意，只要有两者不相等，我们就能判定应该如何缩小范围）
代码如下：
class Solution { public: int minArray(vector<int>& numbers) { if(numbers.empty()) return 0; int left = 0; int right = numbers.size() - 1; int mid = 0; //要一直满足该条件，以证明旋转特性 while(numbers[left] >= numbers[right]){ if(right - left == 1){ //两个下标已经相邻了 mid = right; break; } mid = left + ((right - left) >> 1); //注意操作符优先级 if(numbers[mid] == numbers[left] && numbers[left] == numbers[right]){ //无法判定目标数据在mid左侧，还是右侧我们采用线性遍历方式 int result = numbers[left]; for(int i = left+1; i < right; i++){ if(result > numbers[i]){ result = numbers[i]; } } return result; } if(numbers[mid] >= numbers[left]){ //试想两者相等， 隐含条件numbers[left] >= numbers[right] //说明mid在前半部分 left = mid; } else{ //说明mid在后半部分 right = mid; } } return numbers[mid]; } };
2、矩形覆盖
题目如下：
🔥方法如下：
- 用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，每次放置的时候，无非两种放法，横着放或竖着放；
- 其中，横着放一个之后，下一个的放法也就确定了，故虽然放置了两个矩形，但属于同一种放法；
- 其中，竖着放一个之后，本轮放置也就完成了，也属于一种方法；
- 所以，当2*n的大矩形被放满的时候，它无非就是从上面两种放置方法放置来的；
- 我们继续使用dp来进行处理，当然后续会发现，斐波那契数列的方式也可以处理，因为之前已经讲过，就留给大家完成；
- 状态定义：f(n) : 用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形所用的总方法数；
- 状态递推：f(n) = f(n-1)【最后一个竖着放】 + f(n-2)【最后两个横着放】；
- 初始化：f(1) = 1,f(2) = 2,f(0)=1,注意f(0)我们这个可以不考虑。
代码如下：
class Solution { public: int rectCover(int number) { if (number <2) { //这里要充分考虑number是[0,1]时的情况，OJ一般测试用例设计的比较全面，会有0，1传进来，这个时候，后续的dp[1] = 1;就可能报错 return number; } //f(n) = f(n-1)+f(n-2) int* dp = new int[number + 1]; dp[1] = 1; dp[2] = 2; for ( int i = 3; i <= number; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } int num = dp[number]; delete dp; return num; } };
3、树的子结构
题目如下：
🔥方法如下：
解题思路：
- 二叉树都是递归定义的，所以递归操作是比较常见的做法 ；
- 首先明白：子结构怎么理解，可以理解成子结构是原树的子树(或者一部分)；
- 也就是说，B要是A的子结构，B的根节点+左子树+右子树，都在A中存在且构成树形结构 ；
- 比较的过程要分为两步： 1. 先确定起始位置 2. 在确定从该位置开始，后续的左右子树的内容是否一致
代码如下：
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: bool IsSameFromBegin(TreeNode* begin, TreeNode* beginSub) { //和下面的寻找代码不同的是，现在要执行的是第二步 if (nullptr == beginSub) { //beginSub为nullptr，说明已经比较完了 return true; } if (nullptr == begin) { //begin为空，说明beginSub不是你的子树 return false; } if (begin->val != beginSub->val) { return false; //说明，整树中，有不相等的节点 } //在比较左右子树是否相等 //这里大家深度想想递归是怎么返回的【整个递归的结果，由最深层调用的结果决定】 return IsSameFromBegin(begin->left, beginSub->left) && IsSameFromBegin(begin -> right, beginSub->right); } //比较的过程要分为两步 //1. 先确定起始位置 //2. 在确定从该位置开始，后续的左右子树的内容是否一致 bool isSubStructure(TreeNode* A, TreeNode* B) { //下面逻辑整体执行的是第一步 //先判定两棵树有没有为空的情况 if (A == nullptr || B == nullptr) { return false; } bool result = false; //找到了起始位置 if (A->val == B->val) { //从该起始位置开始，查找是否一致 result = IsSameFromBegin(A, B); } //如果A->val ！= B->val or 从起始位置开始，不一致 if (!result) { //在A树的左子树使用相同的方式找找 result = isSubStructure(A->left, B); } //左子树没有，再在右子树找找 if (!result) { result = isSubStructure(A->right, B); } return result; } };
到此，便是以上题目的全部讲解。希望对大家有所帮助！！
