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; } };
到此,便是以上题目的全部讲解。希望对大家有所帮助!!