菜鸟刷题Day5

⭐作者:别动我的饭
⭐专栏:菜鸟刷题
⭐标语:悟已往之不谏,知来者之可追
在这里插入图片描述

一.一维数组的动态和:1480. 一维数组的动态和 - 力扣(LeetCode)

描述

给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例:

输入:nums = [1,2,3,4]
输出:[1,3,6,10]
解释:动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

解题思路

1.通过观察示例可以发现,其实runningSum[0]和nums[0]相等,runningSum[1]=runningSum[0]+nums[1];所以我们可以得到这样一个结论:当 i > 0时:runningSum[i]=runningSum[i-1]+nums[i];

我可以新开辟一个数组(大小和nums一样大),将累加的结果存放到这个新开的数组中,再返回这个新开辟的数组。

int* runningSum(int* nums, int numsSize, int* returnSize)
{	
    int*tmp=(int*)malloc(sizeof(int)*numsSize);
    tmp[0]=nums[0];
    
    for(int i=1;i<numsSize;i++)
    {
        tmp[i]=tmp[i-1]+nums[i];
    }
    *returnSize=numsSize;
    
    return tmp;
}

2.直接在原地改变,除了第一项不用改变以外,后面的每一项元素都是前面元素累加的结果。

int* runningSum(int* nums, int numsSize, int* returnSize)
{
    for(int i=1;i<numSize;i++)
    {
         nums[i]+=nums[i-1];
    }
    
    *returnSize=numsSize;
    
    return nums;
}

二.搜索插入位置:35. 搜索插入位置 - 力扣(LeetCode)

描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。


解题思路

看到说时间复杂度位O(log n)就让人想起二分查找算法,二分查找虽然强大,但是有一个很大的缺陷就是要求被查找的数据必须要有序。正好题目说了是一个排序数组,那还不二分走起

int searchInsert(int* nums, int numsSize, int target)
{
    int begin=0;
    int end=numsSize-1;
    int mid=0;
    
    while(begin<=end)
    {
        mid=(begin+end)/2;
        
        if(nums[mid]<target)
        {
            begin=mid+1;
        }
        else if(nums[mid]>target)
        {
            end=mid-1;
        }
        else//相等
        {
            return mid;
        }
        

    }
   return begin;
}

关于最后的返回值:位于begin左边的数一定小于目标值,而在end右边的数一定是大于end的,也就是说目标值要么在begin和end的中间,要么就在begin和end之间的某个位置插入,而最后的结束条件是begin>end,也就是说这中间只有begin是一直在改变的,因此如果最后在数组中找不到这个元素,那么它的插位置一定是begin位置


三.搜索旋转排序数组:33. 搜索旋转排序数组 - 力扣(LeetCode)

描述

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。


解题思路

首先映入眼帘的还是O(log n),那么用二分查找吗?一看是升序排序数组,但是这里又说了,会在某个位置旋转一下。好像不能用二分

但是(我知道你在等但是),在k位置旋转以后,仍然是局部有序的。如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的,我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪一半了

这里只要通过控制下标就可以实现在一个数组内分割出两个数组的目的

int search(int* nums, int numsSize, int target)
{
    //核心在于只是局部有序

    int begin=0,end=numsSize-1;
    while(begin<=end)
    {
        int mid=(begin+end)/2;

        if(nums[mid]==target)
            return mid;

        //二分查找只能在有序数列中进行,所以要判断有序范围,一定是局部有序
        if(nums[mid]<nums[end])//说明右边数组有序
        {
            //判断一下目标值是否在右边数组中,既然在右边数组,那么就要重新调整一下mid的值
            if(nums[mid]<target&&nums[end]>=target)
                 begin=mid+1;
            else
                end=mid-1;      
        }
        else
        {
            //左边数组有序,还要判断一下是否在左边数组中
            if(nums[mid]>target&&nums[begin]<=target)
                end=mid-1;
            else
                begin=mid+1;
        }

    }
    //到这里就是找不到
    return -1;
}

四.二进制链表转整数:1290. 二进制链表转整数 - 力扣(LeetCode)

描述

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值
链表不为空; 链表的结点总数不超过 30; 每个结点的值不是0就是 1

示例:

输入:head = [1,0,1]
输出:5
解释:二进制数 (101) 转化为十进制数 (5)

解题思路

1.建立一个数组,然后遍历链表,将链表中的值存取到数组中,将数组的内容转换成十进制,在size-1位置的反而是于二的零次方相乘,所以可以得到如下代码

	int getDecimalValue(struct ListNode* head)
 {

    int arr[31];
    int i=0;
    int flag=0;//做标记,如果数组中没有1,无论链表多长结果都是0
    while(head!=NULL)
    {
        arr[i]=head->val;
        i++;
        if(head->val==1)
        {
            flag=1;
        }
        head=head->next;
    }
    //将链表中的数值全部提取到数组中,必须要拿到数组的有效长度
    int sum=0;
    int sz=i;

    if(flag==0)
        return 0;
    else
    {
        for(i=0;i<sz;i++)
        {
           if(arr[i]!=0)
           {
                sum+=pow(2,sz-1-i);
           }
        }
    }

    return sum;
}

2.此外还可以利用位运算,第一次就从链表中拿到的那个数其实是二的size-1次方,而左移一位就有乘二的效果

int getDecimalValue(struct ListNode* head)
{
    int sum=0;
    
    while(head!=NULL)
    {
        sum=(sum<<1)+head->val;
        
        head=head->next;
    }
    
    return sum;
}

人们总是高估短期努力能带来的提升,而忽略长期坚持带来的改变。今天是第五天,也是第二十题了,你还在坚持吗?

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/2910.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏&#x1f33b;《刷题笔记》文章目录前言&#x1f496; 1、二维数组中的查找题目描述思路&#x1f496; 2、替换空格题目描述思路&#x1f496; 3、从尾到头打印链表题目描述思路一&#xff08;反转函数&#xff09;思路二&#xff08;递归&#xff09;思路二&a…

Celery使用:优秀的python异步任务框架

目录Celery 简介介绍安装基本使用Flask使用Celery异步任务定时任务Celery使用Flask上下文进阶使用参考停止Worker后台运行Celery 简介 介绍 Celery 是一个简单、灵活且可靠的&#xff0c;处理大量消息的分布式系统&#xff0c;并且提供维护这样一个系统的必需工具。 它是一个…

文心一言 vs GPT-4 —— 全面横向比较

文心一言 vs GPT-4 —— 全面横向比较 3月15日凌晨&#xff0c;OpenAI发布“迄今为止功能最强大的模型”——GPT-4。我第一时间为大家奉上了体验报告《OpenAI 发布GPT-4——全网抢先体验》。 时隔一日&#xff0c;3月16日下午百度发布大语言模型——文心一言。发布会上&#…

4万字企业数字化转型大数据湖项目建设和运营综合解决方案WORD

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用&#xff0c;如有侵权请联系删除。部分资料内容&#xff1a; 3.1.4沙盒管理 利用Docker, 基于kubernetes主打的容器技术与微服务应用基础平台&#xff0c;HDFS和YARN均可依此建模&#xff0c;为上层应用提供微服…

不愧是2023年就业最难的一年,还好有车企顶着~

就业龙卷风已经来临&#xff0c;以前都说找不到好的工作就去送外卖&#xff0c;但如今外卖骑手行业都已经接近饱和状态了&#xff0c;而且骑手们的学历也不低&#xff0c;本科学历都快达到了30%了&#xff0c;今年可以说是最难找到工作的一年。 像Android 开发行业原本就属于在…

学习 Python 之 Pygame 开发魂斗罗(十)

学习 Python 之 Pygame 开发魂斗罗&#xff08;十&#xff09;继续编写魂斗罗1. 解决敌人不开火的问题2. 创建爆炸效果类3. 为敌人跳入河中增加爆炸效果4. 玩家击中敌人继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗&#xff08;九&#xff09;中&#xff0c;…

深度长文 | 数据安全共享技术发展综述及在能源电力领域应用研究

开放隐私计算 编者按数据要素的流通共享与协同应用是数字时代中数据要素市场培育的核心内容&#xff0c;数据安全共享技术能够有效实现数据的安全共享&#xff0c;避免“数据孤岛”现象、隐私泄露事件等.本文对国内外数据安全共享技术研究成果及进展进行了全面综述.首先&#x…

[前端笔记037]vue2之vuex

前言 本笔记参考视频&#xff0c;尚硅谷:BV1Zy4y1K7SH p105 - p116 vuex简介和基本使用 概念&#xff1a;专门在 Vue 中实现集中式状态&#xff08;数据&#xff09;管理的一个 Vue 插件&#xff0c;对 vue 应用中多个组件的共享状态进行集中式的管理&#xff08;读/写&…

CVPR 2023 | 旷视研究院入选论文亮点解读

近日&#xff0c;CVPR 2023 论文接收结果出炉。近年来&#xff0c;CVPR 的投稿数量持续增加&#xff0c;今年收到有效投稿 9155 篇&#xff0c;和 CVPR 2022 相比增加 12%&#xff0c;创历史新高。最终&#xff0c;大会收录论文 2360 篇&#xff0c;接收率为 25.78 %。本次&…

烤鱼界头牌半天妖发文致歉,背后暴露了哪些问题?

3月24日&#xff0c;半天妖烤鱼官方针对“两家门店食品安全问题”&#xff0c;发表致歉声明&#xff0c;并宣布将两家涉事门店永久关停。半天妖烤鱼爆出的食品安全问题再次提醒我们&#xff0c;加强门店监管和管理工作&#xff0c;保障消费者的健康和安全&#xff0c;成为了行业…

7.避免不必要的渲染

目录 1 组件更新机制 2 虚拟DOM配合Diff算法 3 减轻state 4 shouldComponentUpdate() 4.1 基本使用 4.2 使用参数 5 纯组件 5.1 基本使用 5.2 纯组件的比较方法 shallow compere 1 组件更新机制 当父组件重新渲染时&#xff0c;父组件的所有子组件也会重新…

如何理解AQS

AQS核心数据结构 AQS内部主要维护了一个FIFO&#xff08;先进先出&#xff09;的双向链表。 AQS数据结构原理 AQS内部维护的双向链表中的各个节点分别指向直接的前驱节点和直接的后续节点。所以&#xff0c;在AQS内部维护的双向链表可以从其中的任意一个节点遍历前驱结点和后…

【尝鲜版】ChatGPT插件开发指南

3月23日&#xff0c;OpenAI官方发布了一则公告&#xff0c;宣告ChatGPT已经支持了插件功能&#xff0c;现在处于内测阶段。插件的意义不仅仅在于功能的扩展&#xff0c;它直接让ChatGTP拥有了联网的能力&#xff01;简直是猛兽出笼、蛟龙出海&#xff0c;要让ChatGPT大杀特杀啊…

phpstorm断点调试

环境&#xff1a;win10phpstorm2022phpstudy8lnmp 1、phpinfo(); 查看是否安装xdebug&#xff0c;没有走以下流程 2、phpstudy中切换不同版本php版本&#xff0c;有些版本不支持xdebug&#xff08;如php8.0.2&#xff09;&#xff0c;有些已经自带了&#xff08;如php7.3.9&a…

Java奠基】Java经典案例讲解

目录 卖飞机票 找质数 开发验证码 数组元素的复制 评委打分 数字加密 数字解密 抢红包 模拟双色球 二维数组 卖飞机票 需求&#xff1a;机票价格按照淡季旺季、头等舱和经济舱收费、输入机票原价、月份和头等舱或经济舱。按照如下规则计算机票价格&#xff1a; 旺季&…

技术分享——Java8新特性

技术分享——Java8新特性1.背景2. 新特性主要内容3. Lambda表达式4. 四大内置核心函数式接口4.1 Consumer<T>消费型接口4.2 Supplier<T>供给型接口4.3 Function<T,R>函数型接口4.4 Predicate<T> 断定型接口5. Stream流操作5.1 什么是流以及流的类型5.2…

[攻城狮计划]如何优雅的在RA2E1上运行RT_Thread

文章目录[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread准备阶段&#x1f697;开发板&#x1f697;开发环境&#x1f697;下载BSP&#x1f697;编译烧录连接串口总结[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread &#x1f680;&#x1f680;开启攻城狮的成长之旅&#xff0…

【ChatGPT】教你搭建多任务模型

ChatGPT教你搭建多任务模型 You: tell me what’s your version of gpt ? ChatGPT: As an AI language model developed by OpenAI, I am based on the GPT (Generative Pretrained Transformer) architecture. However, my version is known as GPT-3.5, which is an updat…

数据泄漏防护 (DLP) 工具保护敏感数据

通过实时安全监控&#xff0c;通过端点&#xff08;即 USB、电子邮件、打印等&#xff09;检测、中断和防止敏感数据泄露。使用 DataSecurity Plus 的数据泄漏防护 &#xff08;DLP&#xff09; 工具保护敏感数据不被泄露或被盗。DataSecurity Plus 主要功能包括&#xff1a; …

Android APP检查设备是否为平板

正文 Android APP判断设备是否为平板的三种方法&#xff1a; 通过屏幕尺寸判断。一般来说&#xff0c;平板电脑的屏幕尺寸比手机大很多&#xff0c;可以根据屏幕的长宽比和尺寸等信息来区分设备类型。通过屏幕像素密度判断。一般来说&#xff0c;平板电脑的屏幕像素密度比手机…