《LeetCode》——LeetCode刷题日记2

简介: 《LeetCode》——LeetCode刷题日记2



1、旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字

题目如下:

接下来我会给出两种解题思路供大家去解决这个题:

解析如下:

根据题意我们知道这是一个数组问题,本质其实是一个求最小值问题

🔥方法一:

  1. 理论上,遍历一次即可,但是我们可以根据题面使用稍微高效且更简单一点的做法;
  2. 按照要求,要么是一个非递减排序的数组(最小值在最开始),要么是一个旋转(最小值在中间某个地方) ;
  3. 而且,旋转之后有个特征,就是在遍历的时候,原始数组是非递减的,旋转之后,就有可能出现递减,引起递减的数字,就是最小值

代码如下:

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];
    }
};

🔥方法二:

  1. 主要思路就是采用二分查找的方式,进行定位;
  2. 首先定义首尾下标,因为是非递减数组旋转,所以旋转最后可以看做成两部分,前半部分整体非递减,后半部分整体非递减,前半部分整体大于后半部分;
  3. 所以,我们假设如下定义,left指向最左侧,right指向最右侧,mid为二分之后的中间位置;
  4. 则,a[mid] >= a[left],说明mid位置在原数组前半部分,进一步说明,目标最小值,在mid的右侧,让left=mid;
  5. a[mid] < a[left], 说明mid位置在原数组后半部分,进一步说明,目标最小值,在mid的左侧,让right=mid;
  6. 这个过程,会让[left, right]区间缩小;
  7. 这个过程中,left永远在原数组前半部分,right永远在原数组的后半部分,而范围会一直缩小 ;
  8. 当left和right相邻时,right指向的位置,就是最小元素的位置;
  9. 但是,因为题目说的是非递减,也就意味着数据允许重复,因为有重复发,就可能会有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、矩形覆盖

题霸:矩形覆盖

题目如下:

🔥方法如下:

  1. 用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,每次放置的时候,无非两种放法,横着放或竖着放;
  2. 其中,横着放一个之后,下一个的放法也就确定了,故虽然放置了两个矩形,但属于同一种放法;
  3. 其中,竖着放一个之后,本轮放置也就完成了,也属于一种方法;
  4. 所以,当2*n的大矩形被放满的时候,它无非就是从上面两种放置方法放置来的;
  5. 我们继续使用dp来进行处理,当然后续会发现,斐波那契数列的方式也可以处理,因为之前已经讲过,就留给大家完成;
  6. 状态定义:f(n) : 用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形所用的总方法数;
  7. 状态递推:f(n) = f(n-1)【最后一个竖着放】 + f(n-2)【最后两个横着放】;
  8. 初始化: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、树的子结构

剑指 Offer 26. 树的子结构

题目如下:

 🔥方法如下:

解题思路:

  1. 二叉树都是递归定义的,所以递归操作是比较常见的做法 ;
  2. 首先明白:子结构怎么理解,可以理解成子结构是原树的子树(或者一部分);
  3. 也就是说,B要是A的子结构,B的根节点+左子树+右子树,都在A中存在且构成树形结构 ;
  4. 比较的过程要分为两步: 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;
    }
};

到此,便是以上题目的全部讲解。希望对大家有所帮助!!

 

相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
44 4
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
49 7
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
24 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
49 5
|
3月前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
46 3
|
3月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
21 3