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

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

 

相关文章
|
3天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
12 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
3天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
10 0
|
3天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
9 0
|
3天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
14 1
|
3天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
9 0
|
3天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
9 0
|
3天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
10 0
|
6天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
12 1
|
6天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
13 0
|
15天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
14 0