【优选算法题练习】day10

这篇具有很好参考价值的文章主要介绍了【优选算法题练习】day10。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


一、137. 只出现一次的数字 II

1.题目简介

137. 只出现一次的数字 II
给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。
【优选算法题练习】day10,优选算法题练习,算法,leetcode

2.解题思路

分别记录数组中所有元素每一个比特位的值出现的次数,其中将不能被3整除的比特位结合起来就是要找的值出现一次的数字

3.代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i = 0;i < 32; ++i)
        {
            int sum = 0;
            for(auto& e : nums)
            {
                if(((e >> i) & 1) == 1) sum++;
            }
            if(sum % 3)
            {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

4.运行结果

【优选算法题练习】day10,优选算法题练习,算法,leetcode

二、剑指 Offer 53 - II. 0~n-1中缺失的数字

1.题目简介

剑指 Offer 53 - II. 0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
【优选算法题练习】day10,优选算法题练习,算法,leetcode

2.解题思路

二分法
寻找缺失的那个数,可能出现的情况有两种:
1.mid对应的数组元素nums[mid]等于mid此时我们应该在mid + 1~right之间寻找;
2.mid对应的数组元素不等于mid(只可能是比mid大,如果元素mid缺失nums[mid]就一定大于mid)此时我们应该在left~mid之间寻找。

当left == right时,会有两种情况:
1.left对应的元素nums[left]不等于left(大于left),则缺失的数字就是left(缺失的数字在0~n-2之间)
2.left对应的元素nums[left]等于left,则缺失的数字就是left+1(缺失的数字是n-1)

3.代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] == mid) left = mid + 1;
            else right = mid;
        }
        return left == nums[left] ? left + 1 : left;
    }
};

4.运行结果

【优选算法题练习】day10,优选算法题练习,算法,leetcode

三、153. 寻找旋转排序数组中的最小值

1.题目简介

153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
【优选算法题练习】day10,优选算法题练习,算法,leetcode
【优选算法题练习】day10,优选算法题练习,算法,leetcode

2.解题思路

二分法
将数组分为两部分升序的子数组:AB和CD两部分(A是第一部分的第一个元素,B是第一部分的最后一个元素;C和D类似)

3.代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[right]) //说明mid位于第一部分。则要在mid + 1~right之间寻找数组的最小值
            left = mid + 1;
            else//说明mid位于第二部分,则要在left~mid之间进行寻找
            right = mid;
        }
        return nums[left];
    }
};

4.运行结果

【优选算法题练习】day10,优选算法题练习,算法,leetcode


总结

今天是算法练习的第10天。
天道酬勤 ,继续加油。
本文题目均来源于Leetcode,小伙伴们可以通过点击题目简介中的链接,跳转到原页面进行练习。
如果本篇文章对你有所启发的话,希望可以多多支持作者,谢谢大家!文章来源地址https://www.toymoban.com/news/detail-618098.html

到了这里,关于【优选算法题练习】day10的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(43)
  • 【SQL刷题】Day10----SQL高级过滤函数专项练习

    博主昵称:跳楼梯企鹅 博主主页面链接: 博主主页传送门 博主专栏页面连接: 专栏传送门--网路安全技术 创作初心:本博客的初心为与技术朋友们相互交流,每个人的技术都存在短板,博主也是一样,虚心求教,希望各位技术友给予指导。 博主座右铭:发现光,追随光,

    2023年04月09日
    浏览(50)
  • Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)

    题目: 例子: 分析题目: 主要目的:求出各个字符串的公共前缀 思路(本人解法): 用所给实例来看,不难看出我们可以直接以竖着对应来查看是否是公共前缀 ,  这样就有了一定的思路 , 然后接着想如何让他找到最长的公共前缀后就 停止下来呢  这样就能想到,从最

    2024年02月11日
    浏览(39)
  • 贪心算法练习day.1

    贪心算法是一种常见的解决优化问题的方法,其基本思想就是在问题的每个决策阶段,都选择当前看起来最优的选择,即 贪心地做出局部的最优决策,以此得到全局的最优解, 例如在十张面额不同的钞票,让我们去取5张,那如何拿到最多的钱呢?那我们每次取钞票时只需要

    2024年04月27日
    浏览(36)
  • 贪心算法练习day2

    1)初始化最小字母为‘Z’,确保任何字母都能与之比较 2)遍历单词,找到当前未删除字母中的最小字母 3)获取当前位置的字母  current = word.charAt(i); 4)删除最小字母之前的所有字母  word=word.substring(index+1); 5)  将最小字母添加到结果字符,更新剩余可删除字母数量 t -=

    2024年02月20日
    浏览(40)
  • 算法练习--leetcode 数组

    输入n阶楼梯,每次爬1或者2个台阶,有多少种方法可以爬到楼顶? 示例1:输入2, 输出2 一次爬2阶; 一次爬1阶; 故两种方法。 示例2: 输入3, 输出3 三个1; 一个1 + 一个 2; 一个2 + 一个1; 思路分析: 采用递归求解 python实现: java实现 : 类似爬楼梯问题。   给定一个 整

    2024年02月14日
    浏览(41)
  • 【算法练习Day51】柱状图中最大的矩形

    ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:练题 🎯 长路漫漫浩浩,万事皆有期待 力扣题目链接 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩

    2024年01月22日
    浏览(44)
  • Day10|LeetCode232.用栈实现队列、LeetCode 225. 用队列实现栈

    栈和队列理论基础: 队列是先进先出,栈是先进后出。如图所示: 栈和队列是STL(C++标准库)里面的两个数据结构。 栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说我们可以控制使用哪种容器来实现栈的功能)。  栈的内部结构,

    2024年02月14日
    浏览(40)
  • 每天一道算法练习题--Day18 && 第一章 --算法专题 --- ----------前缀树

    字典树也叫前缀树、Trie。它本身就是一个树型结构,也就是一颗多叉树,学过树的朋友应该非常容易理解,它的核心操作是插入,查找。删除很少使用,因此这个讲义不包含删除操作。 截止目前(2020-02-04) 前缀树(字典树) 在 LeetCode 一共有 17 道题目。其中 2 道简单,8 个

    2024年02月02日
    浏览(52)
  • 代码随想录算法练习Day1:二分查找

    题目链接:704. 二分查找 卡哥视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找 二分法概述: 二分法(Binary Search)是一种在有序数组或列表中查找目标元素的算法。 二分法使用前提 : 有序数组或列表 :二分法要求在查找的数据结

    2024年04月23日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包