《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实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
46 4
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2
|
5天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
8 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
54 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的实现代码。
47 3