线性DP-前缀和

哪种连续子字符串更长

思路

我们遍历输入字符串s中的每个字符。对于每个字符,我们检查它是1还是0,并相应地更新currentLength1currentLength0。当我们遇到一个1时,我们增加currentLength1的值,并将currentLength0重置为0,因为我们正在构建一个连续的1的子字符串。类似地,当我们遇到一个0时,我们增加currentLength0的值,并将currentLength1重置为0

在每次更新currentLength1currentLength0之后,我们还使用Math.max函数来更新maxLength1maxLength0,以确保我们总是记录最长的连续子字符串长度。

最后,我们比较maxLength1maxLength0的值,如果maxLength1大于maxLength0,则返回true,否则返回false

代码

public class 子字符串 {
	public static boolean checkBinaryString(String s) {
		int maxLength1 = 0;
		int maxLength0 = 0 ;
		int currentLength1 = 0;
		int currentLength0 = 0;
		
		for(char c:s.toCharArray()) {
			if(c=='1') {
				currentLength1++;
				currentLength0=0;//遇到1时 重置0的连续的长度
			}else {
				currentLength0++;
				currentLength1=0;//遇到0时重置1的连续的长度
			}
		    //更新最长连续的子字符串的长度
			maxLength1=Math.max(maxLength1, currentLength1);
			maxLength0=Math.max(maxLength0, currentLength0);	
		}

		return maxLength1 > maxLength0;
		
	}
	public static void main(String[] args) {
		String s="110100010";
		System.out.println(checkBinaryString(s));
		
		String v="1101";
		System.out.println(checkBinaryString(v));
		
	}
	

}

知识

for(char c : s.toCharArray())

在Java中,for(char c : s.toCharArray()) 是一个增强型for循环(也称为"foreach"循环),它允许你遍历数组或集合的每个元素而不需要显式地使用索引或迭代器。在这个特定的例子中,s.toCharArray()方法将字符串s转换成一个字符数组,然后增强型for循环遍历这个数组,每次迭代都将数组中的一个字符赋值给变量c

这里是for(char c : s.toCharArray())循环的详细步骤:

  1. s.toCharArray():这个方法调用将字符串s转换成一个新的字符数组。例如,如果s"1101",那么s.toCharArray()将返回一个包含字符'1''1''0', 和'1'的字符数组。

  2. for(char c : ...):这是增强型for循环的语法。对于字符数组中的每个元素(在这个例子中是每个字符),循环体将执行一次。

    • 在每次迭代中,数组中的一个字符会被赋值给变量c
    • 循环体会执行,通常是执行一些操作,比如更新计数器、检查条件等。
    • 当数组中的所有元素都被访问过后,循环结束。

在你的checkBinaryString方法中,增强型for循环用于遍历字符串s中的每个字符。在循环体内,你检查当前字符是'1'还是'0',并相应地更新currentLength1currentLength0变量来跟踪当前正在构建的连续1或连续0的子字符串的长度。

寻找数组的中心下标

思路

拿到题目后思考:数组的下标是从0开始的,且是中心下标的那个对应元素值不会被 + 到左右任何一侧,这个元素相当于一个分界线。

这个CenterIndexFinder类包含了一个findCenterIndex方法,该方法用于查找一个整数数组的中心下标。中心下标是数组的一个下标,其左侧所有元素之和等于右侧所有元素之和。如果没有中心下标,则返回-1。

下面是对findCenterIndex方法的详细解释:

  1. 参数
    • nums:输入的整数数组。
  2. 变量初始化
    • n:数组nums的长度。
    • prefixSum:一个长度为n + 1的数组,用于存储前缀和。前缀和是一种快速计算数组某个区间和的技术。prefixSum[i]表示nums数组中前i个元素的和。
    • leftSum:一个变量,用于存储当前下标左侧的元素之和。
  3. 计算前缀和
    • 通过一个循环,计算nums数组的前缀和,并存储在prefixSum数组中。循环结束时,prefixSum[i]将包含nums数组中前i个元素的和。
  4. 寻找中心下标
    • 再次遍历nums数组,对于每个下标i
      • 计算右侧元素之和rightSum。由于prefixSum[n]表示整个数组的和,prefixSum[i + 1]表示下标i右侧(不包括i)的元素之和,因此rightSum可以通过prefixSum[n] - prefixSum[i + 1]得到。
      • 比较leftSumrightSum。如果它们相等,说明找到了中心下标,返回当前下标i
      • 更新leftSum,将其加上当前元素nums[i],为下一个下标的检查做准备。
  5. 返回结果
    • 如果遍历完整个数组都没有找到中心下标,则返回-1。
  6. 主函数main
    • 定义一个示例数组nums
    • 调用findCenterIndex方法,并将结果存储在centerIndex变量中。
    • 打印结果。

对于给定的示例数组{1, 7, 3, 6, 5, 6},输出将是Center index: 3,因为下标3(对应元素6)左侧的元素和(1 + 7 + 3 = 11)等于右侧的元素和(5 + 6 = 11)。

代码

public class 中心下标 {

	public static  int findCenterIndex(int[] nums) {
		int n=nums.length;
		int [] prefixSum = new int[n+1];
		for(int i=0;i<n;i++) {
			prefixSum[i+1]=prefixSum[i]+nums[i];
		}
		
		int leftSum = 0; //左侧元素之和
		
		//遍历数组,计算每个下标处的左侧元素之和		
		for(int i=0;i<n;i++) {
			int rightSum = prefixSum[n]-prefixSum[i+1];

			//检查左右元素之和是否相等
			if(leftSum == rightSum) {
				return i;
			}
			//更新左侧元素之和,为下一个下标的检查做准备
			leftSum +=nums[i];
		}
		//如果没找到,返回-1
		return -1;
		
	}
	public static void main(String[] args) {
		int [] nums= {1,7,3,6,5,6};
		int centerIndex =findCenterIndex(nums);
		System.out.println(centerIndex);
	}
	
}

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

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

相关文章

2023秋季飞书未来无限大会--随笔

这个时代的飞书 数字时代 工作协同平台 AI时代 帮助企业和个人用好AI 企业如何引用大模型能力&#xff1f; 智慧体— 接近人&#xff0c;有进步空间智能伙伴 用时代的科技打造爱不释手的好产品 移动互联网 – 改变信息分发方式 大模型 –自然的人机交互方式 业务协同 …

Swagger接口文档管理工具

Swagger 1、Swagger1.1 swagger介绍1.2 项目集成swagger流程1.3 项目集成swagger 2、knife4j2.1 knife4j介绍2.2 项目集成knife4j 1、Swagger 1.1 swagger介绍 官网&#xff1a;https://swagger.io/ Swagger 是一个规范和完整的Web API框架&#xff0c;用于生成、描述、调用和…

kali linux通过aircrack-ng命令破解wifi密码

相关阅读&#xff1a;如何破解攻击WiFi 百度安全验证https://baijiahao.baidu.com/s?id1764248756021219497&wfrspider&forpc上面2篇文章写得都很不错 一、前期准备工作 1、将无线网卡挂载到Kali上 ​ 将无线网卡插到电脑上&#xff0c;如果弹出检测到新的USB设备&…

break,continue

break&#xff1a;跳出并结束循环 continue:跳过本次循环&#xff0c;执行下一次循环 代码演示&#xff1a; package com.zhang.loop;public class BreakAndContinueDemo8 {public static void main(String[] args) {//掌握break和continue的作用//1. break&#xff1a;跳出循…

​LeetCode解法汇总2673. 使二叉树所有路径值相等的最小代价

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个整数 n 表示一棵 满二叉树 里面节…

Java设计模式 | 七大原则之迪米特法则

基本介绍 一个对象应该对其他对象保持最少的了解类与类关系越密切&#xff0c;耦合度越大迪米特法则&#xff08;Demeter Principle&#xff09;又叫最少知道法则&#xff0c;即一个类对自己依赖的类知道的越少越好。也就是说&#xff0c;对于被依赖的类不管多么复杂&#xff…

虚拟机 VMware 安装 Windows2000 (iso 光盘镜像)

上篇博客关于 kali 的安装&#xff0c;我们下载的直接是 vmx 文件 这次我们以 iso 文件为例&#xff0c;因此配置过程会有些许不同 先在本地新建一个文件夹用于存放我们一会儿下载的 iso 镜像文件 下载好后是一个后缀为 .iso 的文件 同样我们先打开 VMware 依次点击文件 -&g…

亚信安慧AntDB开启超融合数据库新纪元

&#xff08;一&#xff09; 前言 据统计&#xff0c;在信息化时代的今天&#xff0c;人们一天所接触到的信息量&#xff0c;是古人一辈子所能接收到的信息量的总和。当今社会中除了信息量“多”以外&#xff0c;人们对信息处理的“效率”和“速度”的要求也越来越高。譬如&…

lv21 QT对话框3

1 内置对话框 标准对话框样式 内置对话框基类 QColorDialog, QErrorMessage QFileDialog QFontDialog QInputDialog QMessageBox QProgressDialogQDialog Class帮助文档 示例&#xff1a;各按钮激发对话框实现基类提供的各效果 第一步&#xff1a;实现组件布局&…

C语言标准库函数qsort( )——数据排序

大家好&#xff01;我是保护小周ღ&#xff0c;本期为大家带来的是深度解剖C语言标准库函数 qsort()&#xff0c;qsort()函数他可以对任意类型的数据排序&#xff0c;博主会详细解释函数使用方法&#xff0c;以及使用快速排序的左右指针法模拟实现函数功能&#xff0c;这样的排…

本科毕业设计:计及并网依赖性的分布式能源系统优化研究。(C语言实现)(内包含NSGA II优化算法)(一)

目录 前言 1、分布式能源系统模型介绍 2、运行策略 前言 本篇文章介绍的是我的毕业设计&#xff0c;我将C语言将其实现。 1、分布式能源系统模型介绍 这是我将研究的分布式能源系统的框架&#xff0c;内部供能装置包括&#xff1a;太阳能光伏板&#xff1b;sofc燃料电池、太阳…

【数据结构】周末作业

1.new(struct list_head*)malloc(sizeof(struct list_head*)); if(newNULL) { printf("失败\n"); return; } new->nextprev->next; prev->nextnew; return; 2.struct list_head* pprev->next; prev->nextp->next; p->next->prevpr…

设计模式----装饰器模式

在软件开发过程中&#xff0c;有时想用一些现存的组件。这些组件可能只是完成了一些核心功能。但在不改变其结构的情况下&#xff0c;可以动态地扩展其功能。所有这些都可以釆用装饰器模式来实现。 装饰器模式 允许向一个现有的对象添加新的功能&#xff0c;同时又不改变他的…

python_可视化_交互_多条线段点击高亮显示

需求 使用matplotlib 绘制折线图 响应鼠标事件 单击折线 线条高亮显示 解决方法: 使用 mplcursors 库, 一句代码可实现. 代码 import matplotlib.pyplot as plt import mplcursors import numpy as np# 生成一些示例数据 x np.linspace(0, 10, 100) y np.sin(x)# 创建绘图…

Linux的gdb调试

文章目录 一、编译有调试信息的目标文件二、启动gdb调试文件1、查看内容list/l&#xff1a;l 文件名:行号/函数名&#xff0c;l 行号/函数名2、打断点b&#xff1a;b文件名:行号/函数名&#xff0c;b 行号/函数名 与 查看断点info/i&#xff1a;info b3、删除断点d&#xff1a;…

基于InternLM和LangChain搭建自己的知识库

背景 LLM存在一定的局限性&#xff0c;如&#xff1a; 知识时效性受限&#xff1a;如何让LLM能够获取最新的知识专业能力有限&#xff1a;如何打造垂直领域的大模型定制化成本高&#xff1a;如何打造个人专属的LLM应用 正文 为了突破LLM的局限性&#xff0c;目前有两种范式…

Python入门学习:if语句与条件控制--and、or、in、not in详解与实践

Python入门学习&#xff1a;if语句与条件控制–and、or、in、not in详解与实践 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1…

Zookeeper启动报错排查

前言&#xff1a;生产linux部署的zookeeper&#xff0c;执行启动脚本后&#xff0c;还是无法使用&#xff0c;故进行重启排查 在zookeeper的bin目录下执行 ./zkServer.sh start-foreground 可实时查看启动日志排查问题 根据上面的日志可以看出&#xff0c;是zoo.cfg配置文件里…

本地快速部署谷歌开放模型Gemma教程(基于LMStudio)

本地快速部署谷歌开放模型Gemma教程&#xff08;基于LMStudio&#xff09; 一、介绍 Gemma二、部署 Gemma2.1 部署工具2.1 部署步骤 三、总结 一、介绍 Gemma Gemma是一系列轻量级、最先进的开放式模型&#xff0c;采用与创建Gemini模型相同的研究和技术而构建。可以直接运行在…

Kafka安全模式之身份认证

一、简介 Kafka作为一个分布式的发布-订阅消息系统&#xff0c;在日常项目中被频繁使用&#xff0c;通常情况下无论是生产者还是消费者只要订阅Topic后&#xff0c;即可进行消息的发送和接收。而kafka在0.9.0.0版本后添加了身份认证和权限控制两种安全服务&#xff0c;本文主要…