草庐IT

【LeetCode】剑指 Offer（27）

戊子仲秋 2023-04-24 原文

目录

题目：剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    int search(vector<int>& nums, int target) {

    }
};

解题思路：

那么这道题呢，

如果只是作为一道题，或者说笔试题，

我们当然是二话不说直接暴力拿下，

来看代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int cnt = 0;
        for(auto e : nums) if(e == target) cnt++;
        return cnt;        
    }
};

是的，就是这么简单，三行代码暴力拿下，

但是，很显然，这道题肯定不只是让你随便暴力拿下，

如果是在面试的时候，面试官让你讲讲这道题，你确实可以先给面试官

讲讲暴力的解法，但要是你只会暴力，那估计就要直接回家等通知了，

很显然，作为一个有序数组，这道题可以用二分进行优化：

我们可以通过二分法确定左右边界，然后让右边界 - 左边界 + 1求出答案。

具体思路如下：

先确定右边界：（让左下标一直往右边靠）

如果 nums[mid] <= target，就让 left = mid + 1;

 让左下标一直往右边走：

 直到走出taget位置，让右下标往右靠：

这样 left > right ，循环结束，找到右边界left，

特殊情况：

1. 如果数组内不存在target，right所在位置就不是target；

2. 如果数组不存在target且数组内所以元素都 > target 或者 数组根本没有元素，right就 < 0

也就是right会跑出数组，甚至本来就不在数组里面，

这两种情况就直接返回 0 表示不存在 target 值。

接下来是确定左边界，我们现将求出的右边界存下来：

（让右下标一直往左走）

如果 nums[mid] < target，就让 left = mid + 1;

 如果 nums[mid] >= target，就让 right = mid - 1;

 让右下标一直往左走：

 这样 left > right ，循环结束，找到左边界right，

 最后再让 右边界 - 左边界 + 1 即可，

下面是具体代码：

代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //先确定右边界
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = (left + right) >> 1;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }

        //右边界如果跑出数组或者所在位置不等于target，证明数组内没有target，就直接返回0
        if(right < 0 || nums[right] != target) return 0;

        //将右边界存下来
        int r = right;

        //再确定左边界
        left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = (left + right) >>  1;
            if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }

        //返回：右边界 - 左边界 + 1
        return r - left + 1;
    }
};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看

LeetCodeOfferxffxff0cxff0算法c++

有关【LeetCode】剑指 Offer（27）的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  3. day1-数组part01| 704. 二分查找、27. 移除元素 - 2

    数组理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标从0开始数组内存空间的地址是连续的c++中vector和array的区别1、vector是顺序容器，其利用连续的内存空间来存储元素，但是其内存空间大小是能够改变的。2、array是顺序容器，其也是利用连续的内存空间来存储元素，但它的内存空间是固定大小的，申请之后就无法改变。3、vector的底层是array实现的二维数组二维数组在内存的空间地址是连续的704|二分查找思路1、把整个数组一分为二；2、判断目标值在左区间还是右区间，若在左区间，则修改右区间指针的位置；若在右区间，则修改新区间的左区间位置3、重复上述过程，直到lef

  4. 【测试面经】软件测试面试题大全，软件测试必问必背面试题，敢说会70%就可以轻松拿offer...... - 2

    目录：导读前言一、测试面试基础题二、测试实战面试题三、测试基础知识点四、总结前言大部分人学软件测试的从业者，在找工作的同时，会因为软件测试面试题挡在门前。……跳槽最重要的一步自然是面试，正值跳槽季，网上出现了各种面试题，一时会让人眼花缭乱，分不清最该看哪个，所以为大家做了一些软件测试面试的真题，想跳槽的小伙伴们，请准备好你的小本本！一、测试面试基础题1、简述测试流程？2、什么是软件测试？软件测试的目的与原则？3、软件生存周期及其模型是什么？4、什么是软件质量？5、自动化测试脚本开发的主要步骤？6、目前主要的测试用例设计方法是什么？7、常见的测试用例设计方法都有哪些?请分别以具体的例子来说明这些

  5. LeetCode——2347. 最好的扑克手牌 - 2

    一、题目给你一个整数数组ranks和一个字符数组suit。你有5张扑克牌，第i张牌大小为ranks[i]，花色为suits[i]。下述是从好到坏你可能持有的手牌类型：“Flush”：同花，五张相同花色的扑克牌。“ThreeofaKind”：三条，有3张大小相同的扑克牌。“Pair”：对子，两张大小一样的扑克牌。“HighCard”：高牌，五张大小互不相同的扑克牌。请你返回一个字符串，表示给定的5张牌中，你能组成的最好手牌类型。注意：返回的字符串大小写需与题目描述相同。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/best-poker-hand/d

  6. LeetCode：344. 反转字符串 - 2

    🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123一、🌱344.反转字符串题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。来源：力扣（LeetCode）难度：简单提示：1s[i]都是ASCII码表中的可打印字符示例1：输入：s=[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]示例2：输入：s=[“H”,“a”,“n”,“n”,“a”,“h”]输出：[“h”,“a”,“n”,“n”,“a”,“H”

  7. 【日常系列】LeetCode《28·动态规划3》 - 2

    数据规模->时间复杂度10^8内容二维数组中的路径问题买卖股票的最佳时机lc62【剑指098】【top100】：不同路径https://leetcode.cn/problems/unique-paths/提示：1题目数据保证答案小于等于2*10^9#方案一：dfs+记忆化classSolution:defuniquePaths(self,m:int,n:int)->int:memo=[[-1]*nfor_inrange(m)]defdfs(i,j):ifi==m-1andj==n-1:return1ifi>=morj>=n:return0ifmemo[i][j]!=-1:returnmemo[

  8. LeetCode：454. 四数相加 II —— 哈希表为什么叫哈希表~ - 2

    🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123hash是什么，哈希表为什么叫哈希表？一、🌱454.四数相加II题目描述：给你四个整数数组nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i,j,k,l)能满足：0nums1[i]+nums2[j]+nums3[k]+nums4[l]==0来源：力扣（LeetCode）难度：中等提示：n==nums1.lengthn==nums2.lengthn==nums3.lengthn==nums4.length1-2^28示例1：输入：nums1=[1,2],nums2=[-2,-1],n

  9. 【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅳ - 2

     Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。🌈个人主页：主页链接🌈算法专栏：专栏链接     我会一直往里填充内容哒！🌈LeetCode专栏：专栏链接     目前在刷初级算法的LeetBook。若每日一题当中有力所能及的题目，也会当天做完发出🌈代码仓库：Gitee链接🌈点击关注=收获更多优质内容🌈目录题目:111. 二叉树的最小深度题解:代码实现:题目:700. 二叉搜索树中的搜索题解:代码实现:题目:701. 二叉搜索树中的插入操作题解:代码实现:题目:450. 删除二叉搜索树中的节点题解:代码实现:完结撒花：人生苦短，

  10. 【LeetCode】轮转数组 - 2

    👻内容专栏：《LeetCode刷题专栏》🐨本文概括：189.轮转数组🐼本文作者：花碟🐸发布时间：2023.4.12目录思想1暴力求解代码实现：思想2三次倒置代码实现： 思想3memcpy零时拷贝代码实现：189.轮转数组 点击跳转到LeetCode平台OJ页面题目：​​​​​​​给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例1：输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,5]向右轮转3步:[5,6,7,1,2,3,4]

随机推荐