【Java每日一题,容器+暴力优化】csp202109-2 非零段划分

简介: 【Java每日一题,容器+暴力优化】csp202109-2 非零段划分

Introduction


Input

Output

Sample

input

11
3 1 2 0 0 2 0 4 5 0 2

output

5

Solution

import java.util.Collection;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[] arr=new int[n+2];
        TreeMap<Integer, LinkedList<Integer>> treeMap=new TreeMap();
        for(int i=1;i<=n;i++){
            arr[i]=s.nextInt();
            if(arr[i]!=0){
                if(!treeMap.containsKey(arr[i])){
                    LinkedList<Integer> linkedList=new LinkedList();
                    linkedList.add(i);
                    treeMap.put(arr[i],linkedList);
                }else {
                    treeMap.get(arr[i]).add(i);
                }
            }
        }
        int count=0;
        for(int i=1;i<=n;i++){
            if(arr[i+1]==0&&arr[i]!=0){
                count++;
            }
        }
        int max=count;
        Collection<LinkedList<Integer>> lists = treeMap.values();
        for(LinkedList<Integer> list:lists){
            for(int index:list){
                arr[index]=0;
                if(arr[index-1]==0&&arr[index+1]==0){
                    count--;
                }else if(arr[index+1]!=0&&arr[index-1]!=0) {
                    count++;
                }
            }
            max= Math.max(max,count);
        }
        System.out.println(max);
    }
}

Experience

csp第二题肯定来说用暴力解决的话只能得70分。这里的优化方法参考了https://blog.csdn.net/weixin_41565005/article/details/120666496。提供的思路非常有用,用到了java里面的TreeMap。在第一次计算非零序列的时候,我简化了一下,数量只需要遍历的时候判断 arr[i+1]==0&&arr[i]!=0 即可。


相关文章
|
2月前
|
Java 流计算
利用java8 的 CompletableFuture 优化 Flink 程序
本文探讨了Flink使用avatorscript脚本语言时遇到的性能瓶颈,并通过CompletableFuture优化代码,显著提升了Flink的QPS。文中详细介绍了avatorscript的使用方法,包括自定义函数、从Map中取值、使用Java工具类及AviatorScript函数等,帮助读者更好地理解和应用avatorscript。
利用java8 的 CompletableFuture 优化 Flink 程序
|
2月前
|
缓存 算法 Java
Java中的内存管理:理解与优化
【10月更文挑战第6天】 在Java编程中,内存管理是一个至关重要的主题。本文将深入探讨Java内存模型及其垃圾回收机制,并分享一些优化内存使用的策略和最佳实践。通过掌握这些知识,您可以提高Java应用的性能和稳定性。
49 4
|
14天前
|
监控 算法 Java
Java虚拟机垃圾回收机制深度剖析与优化策略####
【10月更文挑战第21天】 本文旨在深入探讨Java虚拟机(JVM)中的垃圾回收机制,揭示其工作原理、常见算法及参数调优技巧。通过案例分析,展示如何根据应用特性调整GC策略,以提升Java应用的性能和稳定性,为开发者提供实战中的优化指南。 ####
32 5
|
27天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
45 6
|
1月前
|
Java 数据库连接 数据库
优化之路:Java连接池技术助力数据库性能飞跃
在Java应用开发中,数据库操作常成为性能瓶颈。频繁的数据库连接建立和断开增加了系统开销,导致性能下降。本文通过问题解答形式,深入探讨Java连接池技术如何通过复用数据库连接,显著减少连接开销,提升系统性能。文章详细介绍了连接池的优势、选择标准、使用方法及优化策略,帮助开发者实现数据库性能的飞跃。
30 4
|
1月前
|
存储 Java 开发者
成功优化!Java 基础 Docker 镜像从 674MB 缩减到 58MB 的经验分享
本文分享了如何通过 jlink 和 jdeps 工具将 Java 基础 Docker 镜像从 674MB 优化至 58MB 的经验。首先介绍了选择合适的基础镜像的重要性,然后详细讲解了使用 jlink 构建自定义 JRE 镜像的方法,并通过 jdeps 自动化模块依赖分析,最终实现了镜像的大幅缩减。此外,文章还提供了实用的 .dockerignore 文件技巧和选择安全、兼容的基础镜像的建议,帮助开发者提升镜像优化的效果。
|
2月前
|
缓存 前端开发 JavaScript
9大高性能优化经验总结,Java高级岗必备技能,强烈建议收藏
关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。本文介绍了9种性能优化方法,涵盖代码优化、数据库优化、连接池调优、架构层面优化、分布式缓存、异步化、Web前端优化、服务化、硬件升级、搜索引擎和产品逻辑优化。欢迎留言交流。
|
1月前
|
存储 缓存 Java
Java应用瘦身记:Docker镜像从674MB优化至58MB的实践指南
【10月更文挑战第22天】 在容器化时代,Docker镜像的大小直接影响到应用的部署速度和运行效率。一个轻量级的Docker镜像可以减少存储成本、加快启动时间,并提高资源利用率。本文将分享如何将一个Java基础Docker镜像从674MB缩减到58MB的实践经验。
68 1
|
2月前
|
消息中间件 监控 算法
Java性能优化:策略与实践
【10月更文挑战第21】Java性能优化:策略与实践
|
2月前
|
SQL 监控 Java
Java性能优化:提升应用效率与响应速度的全面指南
【10月更文挑战第21】Java性能优化:提升应用效率与响应速度的全面指南