LeetCode每日一题之 寻找数组中心下标

题目介绍:

题目链接:. - 力扣(LeetCode)

算法原理:

这道题仍然可以使用前缀和的思想来求解,不理解基础前缀和模板的可以看我前面的博客,上图中0-2号位元素的和可以很好地用前缀和数组求出,而后面4-5号位元素则需要利用前缀和的变种----后缀和,利用同样的原理构建出后缀和数组,也可以很好求出,4-5号位元素的和。

这里的前缀和数组要进行一些修改,从题干中可以注意到,它求和时是不需要加上中心下标对应的元素的,所以我们创建前缀和f数组,后缀和g数组:

f[i]表示nums数组[0~(i-1)]区间所有元素的和。f[i]=f[i-1]+nums[i-1] 

g[i]表示nums数组[(i+1)~(n-1)]区间所有元素的和。g[i]=g[i+1]+nums[i+1]

使用前缀和,后缀和数组:

有了前缀和数组 和 后缀和数组后这道题就容易多了,我们只需从左往右遍历一遍数组,当f[i]==g[i]时,我们就返回i,循环完后,没找到就返回-1.

代码实现:

C++:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        //构建前缀和数组和后缀和数组
        vector<int> f(n),g(n);
        int i = 1;
        for(i=1;i<n;i++)
        {
            f[i]=f[i-1]+nums[i-1];
        }
        for(i=n-2;i>=0;i--)
        {
            g[i]=g[i+1]+nums[i+1];
        }
        //使用前缀和数组和后缀和数组
        for(i=0;i<n;i++)
        {
            if(f[i]==g[i])
            {
                return i;
            }
        }
        return -1;
    }
};

 

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

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

相关文章

系统安全保证措施-word

【系统安全保证措施-各支撑材料直接套用】 一、 身份鉴别 二、 访问控制 三、 通信完整性、保密性 四、 抗抵赖 五、 数据完整性 六、 数据保密性 七、 应用安全支撑系统设计 软件全套资料下载进主页。

智慧公厕系统的运作过程

智慧公厕是一种新型的未来城市公共厕所&#xff0c;通过物联网、互联网、大数据、云计算、自动化控制等技术&#xff0c;实现公共厕所使用、运营、管理、养护的全过程全方位信息化。 那么&#xff0c;智慧公厕是如何运作的&#xff1f;智慧公厕的运作过程包括什么技术&#xf…

广度优先搜索和深度优先搜索

广度优先搜索 广度优先搜索&#xff08;Breadth-First-Search&#xff0c;BFS&#xff09;类似于二叉树的层序遍历算法&#xff08;借助队列&#xff09;&#xff0c;其基本思想是&#xff1a;首先访问起始顶点&#xff0c;接着由v出发&#xff0c;依次访问v的各个未访问过的邻…

【LeetCode: 212. 单词搜索 II - dfs】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

基于SSM框架的商场导视系统设计与实现

目 录 摘 要 1 Abstract 2 引 言 3 1 系统开发相关技术 5 1.1 框架技术 5 1.1.1Spring框架 5 1.1.2Mybatis框架 5 1.1.3SpringMVC框架 6 1.2 MySQL数据库 7 1.3前端技术 7 1.3.1ECharts图表技术 7 1.3.2bookstorp框架技术 8 1.4 本章小结 8 2 系统需求分析 9 2.1 系统需求实现…

ThreadLocal源码分析

简介 ThreadLocal是JDK提供的&#xff0c;支持线程本地变量。也就是说&#xff0c;如果我们创建了一个ThreadLocal变量&#xff0c;则访问这个变量的每个线程都会有这个变量的一个本地副本。如果多个线程同时对这个变量进行读写操作时&#xff0c;实际上操作的是线程自己本地内…

内存映射实现父子进程通信

创建内存映射区&#xff1a; void *mmap(void *addr ,size_t length,int prot,int flags,int fd,off_t offset); 参数&#xff1a; addr 指定映射区的首地址。通常NULL&#xff0c;表示让系统自动分配length 共享内存映射区的长度prot 共享内存的读写属性 PROT_READ PR…

电脑资料管理软件(5个高效批量管理电脑资料的方法)

企业电脑资料管理是企业一大难题&#xff0c;为什么这样说&#xff1f; 首先&#xff0c;企业电脑资料的数量庞大且种类繁多。 其次&#xff0c;电脑资料的安全性和保密性要求高。 再者&#xff0c;电脑资料的管理涉及到多个部门和员工的协作。 ...... 针对此类情况很多企业…

基于深度视觉实现机械臂对目标的识别与定位

机械臂手眼标定 根据相机和机械臂的安装方式不同&#xff0c;手眼标定分为眼在手上和眼在手外两种方式&#xff0c;双臂机器人的相机和机械臂基座的相对位置固定&#xff0c;所以应该采用眼在手外的手眼标定方式。 后续的视觉引导机械臂抓取测试实验基于本实验实现&#xf…

Chatgpt异常10秒恢复大法--亲测有效

Chatgpt异常10秒恢复大法--亲测有效! 这几天有没有朋友GPT界面正常&#xff0c;打字不回复?各种恼(我本人)今天偶然看到群友讨论&#xff0c;10秒钟恢复了! 极简步骤:Chorme界面按F12--应用--存储--清楚缓存搞定! 更多资料&#xff1a; 极简步骤:Chorme界面按F12--应用--存储-…

GSM8K数据集分享

来源: AINLPer公众号&#xff08;每日干货分享&#xff01;&#xff01;&#xff09; 编辑: ShuYini 校稿: ShuYini 时间: 2024-3-3 先进的语言模型可以在许多任务上与人类表现相媲美&#xff0c;但它们仍然难以执行多步骤数学推理任务。为此OpenAI团队创建了一个高质量、语言多…

Centos安装Jenkins

1、更新系统 &#xff08;1&#xff09;更新下系统 sudo yum -y update 安装用于下载java 17二进制文件的wget命令行工具 sudo yum -y install wget vim 2、卸载centos自带的jdk 由于我们安装的版本比较高&#xff0c;需要jdk17&#xff0c;卸载centos自带的jdk。用 下面的…

阿里云DSW做AI绘画时的显卡选择A10?V100?

V100是Volta架构&#xff0c;A10是Ampere架构&#xff0c;架构上讲A10先进点&#xff0c;其实只是制程区别&#xff0c;用起来没区别。 V100是HBM的内存读取&#xff0c;带宽大&#xff0c;但是DDR5的。 二块卡都是全精度为主的算力卡&#xff0c;半精度优势不明显。 需要用…

3/7—21. 合并两个有序链表

代码实现&#xff1a; 方法1&#xff1a;递归 ---->难点 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* mergeTwoLists(struct ListNode *list1, struct ListNode *list2) {/*1.如果l1为…

前端知识点、技巧、webpack、性能优化(持续更新~)

1、 请求太多 页面加载慢 &#xff08;webpack性能优化&#xff09; 可以把 图片转换成 base64 放在src里面 减少服务器请求 但是图片会稍微大一点点 以上的方法不需要一个一个自己转化 可以在webpack 进行 性能优化 &#xff08;官网有详细描述&#xff09;

Yolov8有效涨点,添加多种注意力机制,修改损失函数提高目标检测准确率

目录 简介 CBAM注意力机制原理及代码实现 原理 代码实现 GAM注意力机制 原理 代码实现 修改损失函数 YAML文件 完整代码 &#x1f680;&#x1f680;&#x1f680;订阅专栏&#xff0c;更新及时查看不迷路&#x1f680;&#x1f680;&#x1f680; http://t.csdnimg.c…

数据结构:Heap(二叉树)的基本操作

目录 1.有关二叉树必须知道的几个基本概念 2.有关二叉树的基本操作 2.0有关元素的定义以及要进行的操作 2.1初始化和销毁操作 2.2插入操作以及上调操作 2.2.1插入操作以及上调操作的图解 2.2.2插入操作以及上调操作的代码 2.3删除根元素及其下调操作 2.3.2删除根元素及…

Pandas 之 merge

merge的作用&#xff1a; merge函数在Python的pandas库中的作用是用来合并两个或多个DataFrame数据表&#xff0c;依据指定的一个或多个键&#xff08;通常是列名&#xff09;进行连接操作[1]。 merge函数可以有多种连接类型&#xff08;如内连接inner、左连接left、右连接ri…

【科研基础|课程】信息论

信息论课程 -上海交大 - 2020春季学期 F:\B\2.sources\CS258信息论 文章目录 1- 信息熵 | 联合熵 | 条件熵 | 链式法则1.1-Entropy1- 信息熵 | 联合熵 | 条件熵 | 链式法则 P3 信息熵 | 联合熵 | 条件熵 | 链式法则 1.1-Entropy Entropy: Brief History 熵的由来,由热力学…

【sw网络监控】通过snmp协议相关的snmp-exporter(收集交换机网络监控数据)+ promethus + grafana

本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》&#xff1a;python零基础入门学习 《python运维脚本》&#xff1a; python运维脚本实践 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8…