当前位置: 首页 > news >正文

代码随想录刷题day07|(数组篇)58.区间和

目录

一、数组理论基础

二、前缀和

三、相关算法题目

四、总结

五、待解决问题


一、数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

代码随想录 (programmercarl.com)

特点:

1.下标从0开始,内存中地址空间是连续的

2.查询快,增删慢

3.二维数组中,行为第一索引,列为第二索引

4.一旦创建以后,长度不能发生变化

5.元素无法删除,只能被覆盖

二、前缀和

前缀和在涉及计算数组区间和问题上是常用技巧,其主要思想是:计算出从下标0到下标 i(0< i < 数组长度)的数值之和p[i],存放在另一数组p中,当需要计算某个区间和时,即可利用数组p得出结果,只需一个O(1)的操作,无需多次遍历元素数组,从而降低算法时间复杂度。

本题可以利用前缀和的思想,其中需要注意求解区间。例如,某一数组 array [1,2,3,4,5,6],对应p数组为 [1,3,6,10,15,21](p[0] = array[0],p[1] = array[0] + array[1]...以此类推),现在要计算数组array下标2到下标5的数值之和(即:3,4,5,6的和:18),那么由p数组可知,应为:p[5] - p[1] = 21-3=18,而不是:p[5] - p[2],因为p[2]是包含了下标2的(p[2]=p[0] + p[1] + p[2]),具体可参考下图:

图源代码随想录 

三、相关算法题目

58.区间和

58. 区间和(第九期模拟笔试) (kamacoder.com)

两种方法:直接求和法和前缀和法

直接求和时间复杂度比较高,不推荐,暂不赘述。

前缀法:

import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt();int[] Array = new int[n];int[] p = new int[n];int sum1 = 0;in.nextLine();int i = 0;while(in.hasNextInt() && i < n){Array[i] = in.nextInt();sum1 += Array[i];p[i] = sum1;in.nextLine();i++; //否则while成死循环 ⭐️}while(in.hasNextInt()){int a = in.nextInt();//in.nextLine();int b = in.nextInt();int sum2;if(a == 0){sum2 = p[b];}else{sum2 = p[b] - p[a-1];}System.out.println(sum2);}in.close();}
}

四、总结

1.最后记得关掉输入流:in.close();

2.第一个while循环中,循环体中记得加条件控制语句:i++,否则while成死循环;或者可以换成for循环;

3.可以通过按Ctrl+D来手动结束输入流,这样程序会停止读取输入并退出;

4.本题用了ACM输入输出模式,具体可见:面试 | Java 算法的 ACM 模式_java acm模式-CSDN博客

五、待解决问题

in.nextLine();这行语句有什么作用?为什么加不加都不影响程序的运行?和in.nextInt();?

相关文章:

代码随想录刷题day07|(数组篇)58.区间和

目录 一、数组理论基础 二、前缀和 三、相关算法题目 四、总结 五、待解决问题 一、数组理论基础 数组是存放在连续内存空间上的相同类型数据的集合。 代码随想录 (programmercarl.com) 特点&#xff1a; 1.下标从0开始&#xff0c;内存中地址空间是连续的 2.查询快&…...

【Linux】进程结束和进程等待

进程的结束 退出码的认识 在我们学习C/C的时候我们通常在进行写main函数时&#xff0c;main函数主体写完后通常会进行写一条语句 " return 0 " &#xff0c;这里的这条语句到底是什么意思呢&#xff1f;&#xff1f; 我们知道当在主函数中调用其他函数或者在其他函…...

可编辑精品PPT | 城投集团(行业)数字化解决方案

这个PPT详细介绍了城投集团的数字化转型解决方案。首先&#xff0c;它概述了数字化转型的背景&#xff0c;包括政策要求和行业趋势&#xff0c;并指出集团在信息化方面取得的阶段性成果及存在的不足。方案提出了数字化转型的总体规划&#xff0c;明确了总体目标、思路和推进策略…...

统计学习算法——决策树

内容来自B站Up主&#xff1a;风中摇曳的小萝卜https://www.bilibili.com/video/BV1ar4y137GD&#xff0c;仅为个人学习所用。 问题引入 有15位客户向某银行申请贷款&#xff0c;下面是他们的一些基本信息&#xff0c;类别列表示是否通过贷款申请&#xff0c;是表示通过贷款申…...

基于网络爬虫技术的网络新闻分析

文末附有完整项目代码 在信息爆炸的时代&#xff0c;如何从海量的网络新闻中挖掘出有价值的信息呢&#xff1f;今天就来给大家分享一下基于网络爬虫技术的网络新闻分析的实现过程。 首先&#xff0c;我们来了解一下系统的需求。我们的目标是能够实时抓取凤凰网新闻、网易新闻、…...

51_Lua面向对象编程

面向对象编程(Object Oriented Programming,OOP)是一种非常流行的计算机编程架构。像C++、Java、Objective-C、Smalltalk、C#、Ruby等编程语言都支持面向对象编程。 1.面向对象编程特性 面向对象编程是一种编程范式,它使用“对象”来设计软件。对象是数据和行为的封装单元…...

关于在 Kotlin DSL 中,ndk 的配置方式

在 Kotlin DSL 中&#xff0c;ndk 的配置方式有所不同&#xff0c;取决于 Android Gradle 插件版本。ndk { abiFilters(…) } 在 Kotlin DSL 中实际上是 externalNativeBuild 的一部分&#xff0c;需要通过正确的上下文调用。 错误代码&#xff1a; ndk {abiFilters("ar…...

【论文阅读+复现】High-fidelity Person-centric Subject-to-Image Synthesis

以人物为中心的主体到图像的高保真合成&#xff0c;CVPR2024 code&#xff1a;CodeGoat24/Face-diffuser: [CVPR2024] Official implementation of High-fidelity Person-centric Subject-to-Image Synthesis. paper&#xff1a;2311.10329 背景 研究问题&#xff1a;这篇文…...

Spring Boot 应用开发入门

一、Spring Boot简介 Spring Boot 是一个基于 Spring 框架的开源 Java 基础框架&#xff0c;它简化了基于 Spring 的应用开发。Spring Boot 提供了一种快速、便捷的方式来创建独立、生产级的基于 Spring 框架的应用程序。它通过提供一系列的“启动器”依赖&#xff0c;帮助开发…...

【C语言】字符串函数详解

文章目录 Ⅰ. strcpy -- 字符串拷贝1、函数介绍2、模拟实现 Ⅱ. strcat -- 字符串追加1、函数介绍2、模拟实现 Ⅲ. strcmp -- 字符串比较1、函数介绍2、模拟实现 Ⅳ. strncpy、strncat、strncmp -- 可限制操作长度Ⅴ. strlen -- 求字符串长度1、函数介绍2、模拟实现&#xff08…...

【Vim Masterclass 笔记14】S07L29 + L30:练习课08 —— Vim 文本对象同步练习(含点评课内容)

文章目录 L29 Exercise 08 - Text Objects1 训练目标2 操作指令2.1. 打开 textobjectspractice.txt 文件2.2. 单词对象练习 Word Objects2.3. 区块对象 ( ) 练习 Block Object ( )2.4. 引用字符串练习 Quoted Strings2.5. 区块对象 [ ] 练习 Block Object [ ]2.6. 区块对象 <…...

非PHP开源内容管理系统(CMS)一览

在现代网站开发中&#xff0c;内容管理系统&#xff08;CMS&#xff09;是不可或缺的工具。虽然许多广泛使用的CMS&#xff08;如WordPress和Joomla&#xff09;是基于PHP开发的&#xff0c;但其他编程语言同样诞生了许多优秀的开源CMS&#xff0c;适用于不同需求和技术栈的项目…...

WEB 攻防-通用漏-XSS 跨站脚本攻击-反射型/存储型/DOMBEEF-XSS

XSS跨站脚本攻击技术&#xff08;一&#xff09; XSS的定义 XSS攻击&#xff0c;全称为跨站脚本攻击&#xff0c;是指攻击者通过在网页中插入恶意脚本代码&#xff0c;当用户浏览该网页时&#xff0c;恶意脚本会被执行&#xff0c;从而达到攻击目的的一种安全漏洞。这些恶意脚…...

SQLAlchemy -批量插入时忽略重复

PostgreSQL 有一个很棒的INSERT() ON CONFLICT DO NOTHING子句,您可以将其与 SQLAlchemy 一起使用: from sqlalchemy.dialects.postgresql import insert session.execute(insert(MyTable).values(my_entries).on_conflict_do_nothing())MySQL 有类似的INSERT IGNORE子句,但…...

1月13日学习

[HITCON 2017]SSRFme 直接给了源代码&#xff0c;题目名称还是ssrf&#xff0c;那么该题大概率就是SSRF的漏洞&#xff0c;进行代码审计。 <?php// 检查是否存在 HTTP_X_FORWARDED_FOR 头&#xff0c;如果存在&#xff0c;则将其拆分为数组&#xff0c;并将第一个 IP 地址…...

Steam个人开发者注册备记

具体的注册过程有很多同志已经写过了&#xff0c;这里只写一点自己搞得有点费劲的地方。有点久了记得也不多了。 1.姓名用汉语拼音&#xff0c;参考护照上的&#xff0c;一般是Zhang Sanli这样的格式&#xff0c;姓一个单词&#xff0c;名字一个单词&#xff08;不管1个字还是…...

django在线考试系统

Django在线考试系统是一种基于Django框架开发的在线考试平台&#xff0c;它提供了完整的在线考试解决方案。 一、系统概述 Django在线考试系统旨在为用户提供便捷、高效的在线考试环境&#xff0c;满足教育机构、企业、个人等不同场景下的考试需求。通过该系统&#xff0c;用…...

Laravel 中 Cache::remember 的基本用途

在 Laravel 中&#xff0c;Cache::remember 方法用于缓存数据&#xff0c;以提高应用程序的性能。当需要从数据库或其他较慢的数据源中检索数据时&#xff0c;可以使用 Cache::remember 来检查请求的数据是否已经被缓存。如果数据已缓存&#xff0c;则直接从缓存中读取&#xf…...

前端进程和线程及介绍

前端开发中经常涉及到进程和线程的概念&#xff0c;特别是在浏览器中。理解这两个概念对于理解浏览器的工作机制和前端性能优化非常重要。以下是详细介绍&#xff1a; 1. 什么是进程和线程&#xff1f; 进程&#xff1a; 是操作系统分配资源的基本单位。一个程序启动后&#xf…...

OpenGL —— 基于Qt的视频播放器 - ffmpeg硬解码,QOpenGL渲染yuv420p或nv12视频(附源码)

运行效果 工程说明 源码 vertex.glsl...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...