#10042. 「一本通 2.1 练习 8」收集雪花

news/2024/4/17 11:50:11

题目描述

不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来,作为礼物送给在南方的同学们。一共有 n 个时刻,给出每个时刻下落雪花的形状,用不同的整数表示不同的形状。在收集的过程中,同学们不希望有重复的雪花。你可以从任意 a 时刻开始,在 b 时刻停止。a 到 b 时刻中间的雪花也都将被收集。他们希望收集的雪花最多。

输入格式

第一行一个正整数 n;

第 2 行 n 个非负整数表示 n 个时刻雪花的形状。

输出格式

最多能收集雪花的数量。

样例

输入

5
1 2 3 2 1

输出

3

数据范围与提示

对于 97 分的数据, 1 ≤ n ≤ 1 0 6 , 0 ≤ x i ≤ 1 0 8 1\le n \le 10^6, 0\le x_i \le 10^8 1n106,0xi108。(为原始数据)

应用户要求,加入 3 分的数据, 1 ≤ n ≤ 1 0 6 , 0 ≤ x i ≤ 1 0 9 1\le n\le 10^6,0\le x_i\le 10^9 1n106,0xi109

又是一个不用哈希表的哈希题

大致思路

根据题意,我们需要找到最长不重复子序列,那么就可以借助强大的STL库中的map了

map<int,int> mapp;
unordered_map<int,int> mapp;

其中map基于红黑树实现,而unordered_map基于哈希实现,unordered_map的效率要快于普通的map,但必须在c++11及以上使用

for(int i=1;i<=n;i++){if(mapp[k[i]]==0){sum++;mapp[k[i]]=1;}

查询当前数有没有出现过,若无,则标记出现过。

else {while(mapp[k[i]]!=0){mapp[k[lcnt]]--;sum--;lcnt++;}mapp[k[i]]++;sum++;}

若当前数出现过,则从前面开始找到第一个重复的,过程内的所有数退回标记,即不选
最后max即可

ans=max(ans,sum);

AC CODE

#include<bits/stdc++.h>
using namespace std;
int ans=0,sum=0,n,lcnt=1,k[10000099];
/*unordered_*/map<int,int>mapp;
int main(){cin>>n;for(int i=1;i<=n;i++){![请添加图片描述](https://img-blog.csdnimg.cn/6fdf7246100748e79d1610bc49436ea0.jpeg)cin>>k[i];}for(int i=1;i<=n;i++){if(mapp[k[i]]==0){sum++;mapp[k[i]]=1;}else {while(mapp[k[i]]!=0){mapp[k[lcnt]]--;sum--;lcnt++;}mapp[k[i]]++;sum++;}ans=max(ans,sum);}cout<<ans;return 0;
}

附封面

请添加图片描述


http://www.ppmy.cn/news/603939.html

相关文章

linux环境下快速配置hadoop集群免密登录

背景 在hadoop的日常使用过程中经常需要登录某些机器&#xff0c;如何更好的免密登录呢&#xff1f;这将为我们节省大量的时间 操作 假设你需要在A机器上免密登录B机器&#xff0c;那么你首先要确定B机器下是有秘钥文件的。如何确定是否有&#xff1f;如果你的根目录下有.ss…

docker安装,以及docker源修改,docker-compose安装一条龙

一、docker 安装 1、使用官方安装脚本自动安装 curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun查看是否安装成功 docker --version成功&#xff1a; rootVM-12-5-ubuntu:~# docker --version Docker version 20.10.11, build dea9396二、docker 更换…

docker安装Mysql5.7以及远程登陆链接配置

1.安装mysql5.7 docker镜像 docker安装&#xff1a;docker安装一条龙 1、拉取官方mysql5.7镜像 docker pull mysql:5.7rootVM-12-5-ubuntu:/# docker pull mysql:5.7 5.7: Pulling from library/mysql ffbb094f4f9e: Pull complete df186527fc46: Pull complete fa362a6aa7b…

c语言中字符串数组的地址存放以及%s输出单个字符导致程序崩溃的问题

代码 总结下c语言中字符串数组的地址存放问题 #include <iostream> using namespace std; #include<bits/stdc.h>int main() {char *s;printf("s的地址是&#xff1a;%d\n", &s);s "hello";char *p s;printf("s存放的是hello的地…

语音识别过程

语音识别的过程

深度学习模型在图像识别中的应用:CIFAR-10数据集实践与准确率分析

文章目录 前言导入所需的库忽略证书验证下载并加载 CIFAR-10 数据集数据预处理构建深度学习模型编译模型模型训练模型评估进行图片识别测试图片运行效果完整代码完结 前言 深度学习模型在图像识别领域的应用越来越广泛。通过对图像数据进行学习和训练&#xff0c;这些模型可以自…

LeetCode 10. Regular Expression Matching python特性、动态规划、递归

前言 本文主要提供三种不同的解法&#xff0c;分别是利用python的特性、动态规划、递归方法解决这个问题 使用python正则属性 import reclass Solution2:# return a booleandef isMatch(self, s, p):return re.match(^ p $, s) ! None 使用递归方法 class Solution(obje…

python 浮点数未解之谜

疑问&#xff1a; print(8.10.03)ouput: 8.129999999999999 print(0.10.10.1-0.3)output: 5.551115123125783e-17 结论 多次遇到这个问题&#xff0c;第二遍看&#xff0c;依然没有理清楚怎么回事&#xff01;&#xff01;&#xff01;下次继续看&#xff01;&#xff01;&…

通过前序遍历和中序遍历构建二叉树 python实现

前言 通过前序遍历和中序遍历构建二叉树的原理&#xff0c;主要是找前序遍历根节点在中序遍历中的位置&#xff0c;然后将二叉树而成左子树和右子树&#xff0c;然后依次进行这样的操作,思路还是比较简单的 代码 class Node:def __init__(self, data, left, right):self.dat…

python 通过双栈实现队列

开始做法 # coding:utf-8# !/usr/bin/env python# Time: 2018/6/6 9:32# Author: sty# File: stack_queue.pyclass Solution():def __init__(self):self.stack1 []self.stack2 []def push(self, data):self.stack1.append(data)def pop(self):if len(self.stack1) 0 and le…

192. Word Frequency 使用shell统计词频

答案 cat words.txt | sed s/ /\n/g | sed /^$/d | sort | uniq -c | awk {print $2, $1} | sort -nrk2 解释 使用sed将空格替换成换行&#xff0c;并且删除空白行 然后使用sort进行排序然后统计出词频 最后将结果以答案要求的方式输出

寻找一个字符串的重复子串 后缀数组

什么是后缀数组 令字符串 SS[1]S[2]...S[n]SS[1]S[2]...S[n]&#xff0c; S[i,j]S[i,j]表示SS的子字符串&#xff0c;下标从ii到 jj。 SS的后缀数组AA被定义为一个数组&#xff0c;内容是 SS的所有后缀经过字典排序后的起始下标。 对于所有的有&#xff1a;1<i≤n:S[A[i−…

centos 非root用户(普通用户)替换yum安装软件方法

1 查看yum中是否有你需要的包 比如想安装graphviz&#xff0c;可以这样查看 yum list graphviz* 2 下载rpm包 然后我们从仓库中下载rpm包&#xff0c;比如我们要下载graphviz.x86_64&#xff0c;我们可以这样下载&#xff1a; yumdownloader graphviz.x86_64 3 解压RPM包…

Linux下 C语言统计时间差

前言 主要是为了统计下某段程序的运行时间 代码实现 主要调用了linux c下的<sys/time.h> #include<stdio.h> #include<sys/time.h>double tick(void) {struct timeval t;gettimeofday(&t, 0);return t.tv_sec 1E-6 * t.tv_usec; }int main(int argv…

LeetCode19. Remove Nth Node From End of List 删除链表中的倒数第n个位置的元素

前言 本文是LeetCode19. Remove Nth Node From End of List解法&#xff0c;这个题目需要删除链表中的倒数第n个位置的元素 代码 # -*- coding: utf-8 -*-# !/usr/bin/env python# Time: 2018/6/27 23:44# Author: sty# File: 19. Remove Nth Node From End of List.py impo…

使用python建立简单的单链表

代码 import sysclass ListNode:def __init__(self, x):self.val xself.next None# 将列表转换成链表 def list_to_listnode(numbers):dummy_root ListNode(0)ptr dummy_rootfor number in numbers:ptr.next ListNode(number)ptr ptr.nextptr dummy_root.nextreturn pt…

建议使用更加安全的ast.literal_eval去替代eval

前言 如果大家想要在python中将字符串转换成列表&#xff0c;数字&#xff0c;字典等操作&#xff0c;都会想到使用eval()&#xff0c;确实这个函数很好用&#xff0c;但是它却存在一定的安全性 eval的漏洞 如果用户使用如下的代码 open(rD://filename.txt, r).read()__imp…

XNOR-Net解读

XNOR-Net算法详解 XNOR-Net是YOLO的作者作为三作提出的面向计算资源不足的设备如MR眼镜、手机等提出的二进制网络。整篇论文分为两个部分&#xff1a; 1.将卷积核二值化&#xff08;1&#xff0c;-1&#xff09;的Binary-Weight-Networks&#xff1b; 2.将输入与卷积核都二值化…

hadoop 添加删除机器以及设置免密登录

添加hadoop机器 先在slaves中添加机器然后启动datanode $: ./usr/hadoop-0.20.2-cdh3u4/bin/hadoop-daemon.sh start datanode查看是否启动 $: jps4696 DataNode 4765 Jps启动tasktrack $: ./usr/hadoop-0.20.2-cdh3u4/bin/hadoop-daemon.sh start tasktracker 查看是否启…
最新文章