【教3妹学编程-算法题】2913. 子数组不同元素数目的平方和 I
-----------------第二天------------------------
面试官 : 好的, 我们再来做个算法题吧。平时工作中会尝试用算法吗, 用到了什么数据结构?
3妹 : 有用到, 用到了 bla bla…
面试官 : 好的, 题目是这样的:
题目:
给你一个下标从 0 开始的整数数组 nums 。
定义 nums 一个子数组的 不同计数 值如下:
令 nums[i…j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组(满足 0 <= i <= j < nums.length ),那么我们称子数组 nums[i…j] 中不同值的数目为 nums[i…j] 的不同计数。
请你返回 nums 中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大,请你将它对 109 + 7 取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
示例 1:
输入:nums = [1,2,1]
输出:15
解释:六个子数组分别为:
[1]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[1]: 1 个互不相同的元素。
[1,2]: 2 个互不相同的元素。
[2,1]: 2 个互不相同的元素。
[1,2,1]: 2 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 + 22 + 22 + 22 = 15 。
示例 2:
输入:nums = [2,2]
输出:3
解释:三个子数组分别为:
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 = 3 。
提示:
1 <= nums.length <= 100
1 <= nums[i] <= 100
思路:
1、使用哈希表统计各数字出现次数。
2、枚举每个元素,分别作为子数组的起始元素,每次步长递增1,使用列表记录步长的统计结果。
3、引用的方式,错位继承步长+1的结果。以{1,2,3}为例,起始元素为2且步长为1的结果,等于上一个起始元素1且步长为3的结果,并去掉元素1。
java代码:
class Solution {public int sumCounts(List<Integer> nums) {int sum = 0;int key = (int) (Math.pow(10, 9) + 7);int len = nums.size();// 按步长统计List<HashMap<Integer, Integer>> stepList = new ArrayList<>(len);// 枚举,各个元素分别作为子数组的起始元素for (int i = 0; i < len; i++) {// 步长递增for (int j = 0; i + j < len; j++) {int num = nums.get(i + j);HashMap<Integer, Integer> numCntMap = new HashMap<>();if (i == 0) {if (j == 0) {numCntMap.put(num, 1);} else {// 继承上一次步长-1的结果numCntMap.putAll(stepList.get(j - 1));if (numCntMap.containsKey(num)) {// 和上个元素重复numCntMap.put(num, numCntMap.get(num) + 1);} else {// 不重复numCntMap.put(num, 1);}}} else {if (j == 0) {sum = (sum + 1) % key;continue;} else {// 错位,继承步长+1的结果,并移除上一个元素// numCntMap.putAll(stepList.get(j + 1));// 优化:将putAll每次都要复制遍历全部,改为直接引用numCntMap = stepList.get(j + 1);int preNum = nums.get(i - 1);int preNumCnt = numCntMap.get(preNum);if (preNumCnt == 1) {numCntMap.remove(preNum);} else {numCntMap.put(preNum, preNumCnt - 1);}}}if (i == 0) {stepList.add(numCntMap);} else {// 更新stepList.set(j, numCntMap);}// 累加平方和sum = (sum + (int) (Math.pow(numCntMap.keySet().size(), 2))) % key;}}return sum;}
}
相关文章:

【教3妹学编程-算法题】2913. 子数组不同元素数目的平方和 I
-----------------第二天------------------------ 面试官 : 好的, 我们再来做个算法题吧。平时工作中会尝试用算法吗, 用到了什么数据结构? 3妹 : 有用到, 用到了 bla bla… 面试官 : 好的, 题目是这样的࿱…...
是否会有 GPT-5 的发布?
本心、输入输出、结果 文章目录 是否会有 GPT-5 的发布?前言围绕 GPT-5 的信息OpenAI 期待增长GPT-5 - 到底是真的在训练,还是一个虚构的故事Sam Altman字里行间包含的信息我们在什么时候可以期待 GPT-5 的发布GPT-5 预计将在哪些方向努力GPT-5 在听觉领域GPT-5 在视频处理领…...
使用 Selenium Python 检查元素是否存在
像 Selenium 这样的自动化工具使我们能够通过不同的语言和浏览器自动化 Web 流程并测试应用程序。 Python 是它支持的众多语言之一,并且是一种非常简单的语言。 它的Python客户端帮助我们通过Selenium工具与浏览器连接。 Web 测试对于开发 Web 应用程序至关重要&am…...

const迭代器与模板构造函数
在自己实现C中list的时候,当实现const迭代器的时候,发现报错了,一直思考到现在 才发现是一个,很简单的问题,但是也让我有了一点感受,我在这里给大家分享一下。文章目录 1.当时遇到的问题2.解决方法3. 自己的…...

在Qt中解决opencv的putText函数无法绘制中文的一种解决方法
文章目录 1.问题2.查阅资料3.解决办法 1.问题 在opencv中,假如直接使用putText绘制中文,会在图像上出现问号,如下图所示: 2.查阅资料 查了一些资料,说想要解决这个问题,需要用到freetype库或者用opencv…...

【Linux】第六站:Centos系统如何安装软件?
文章目录 1.Linux安装软件的方式2.Linux的软件生态3. yum4. rzsz软件的安装与卸载5.yum如何知道去哪里下载软件? 1.Linux安装软件的方式 在linux中安装软件常用的有三种方式 源代码安装(我们还需要进行编译运行后才可以,很麻烦) …...

Istio 实战
文章目录 Istio流量管理分享会【1】什么是istio?【2】istio 可以干什么?【3】业务中的痛点?【4】istio 高级流量管理5.1 istio 组件介绍与原理5.2 sidercar何时注入?如何控制是否注入?5.3 查看sidecar 容器插入的容器中的iptablesDestination RuleVirtual ServiceGateways…...

【Midjourney入门教程4】与AI对话,写好prompt的必会方法
文章目录 1、语法2、单词3、要学习prompt 框架4、善用参数(注意版本)5、善用模版6、临摹7、垫图 木匠不会因为电动工具的出现而被淘汰,反而善用工具的木匠,收入更高了。 想要驾驭好Midjourney,可以从以下方面出发调整&…...

基于单片机的智能灭火小车设计
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 技术交流认准下方 CSDN 官方提供的联系方式 文章目录 概要 一、整体设计方案1.1 整体设计任务1.2 整体设计要求1.3 系统整体方案设计1.3.1 整体模块设计1.3.2 整体设计方案选择…...

[Machine Learning][Part 7]神经网络的基本组成结构
这里我们将探索神经元/单元和层的内部工作原理。特别是,与之前学习的回归/线性模型和逻辑模型进行比较。最后接介绍tensorflow以及如何利用tensorflow来实现这些模型。 神经网络和大脑的神经元工作原理类似,但是比大脑的工作原理要简单的多。大脑中神经元的工作原理…...

精准测试:提高软件质量和用户满意度的利器
📢专注于分享软件测试干货内容,欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正!📢交流讨论:欢迎加入我们一起学习!📢资源分享:耗时200小时精选的「软件测试」资…...
代碼隨想錄算法訓練營|第五十八天|583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结篇。刷题心得(c++)
目录 讀題 583. 两个字符串的删除操作 自己看到题目的第一想法 看完代码随想录之后的想法 72. 编辑距离 看完代码随想录之后的想法 583. 两个字符串的删除操作 - 實作 思路 代碼隨想錄思路 Code 72. 编辑距离 - 實作 思路 Code 编辑距离总结篇 判斷子序列 不同…...

JavaScript基础之BOM与DOM
文章目录 BOM操作window对象window的子对象之navigator对象(了解即可)window的子对象之screen对象(了解即可)window的子对象之history对象(了解即可)window的子对象之location对象 弹出框警告框确认框提示框…...

【Linux学习笔记】进程概念(中)
1. 操作系统的进程状态2. Linux操作系统的进程状态3. 僵尸进程4. 孤儿进程5. 进程优先级5.1. 优先级是什么和为什么要有优先级5.2. Linux中的进程优先级 6. 进程切换7. 环境变量7.1. 环境变量的认识7.2. 环境变量相关的命令7.3. 环境变量和本地变量7.4. 命令行参数7.5. 获取环境…...

scanpy赋值问题
今天发现一个很奇怪的bug import numpy as np import pandas as pd import anndata as ad from scipy.sparse import csr_matrix print(ad.__version__)counts csr_matrix(np.random.poisson(1, size(100, 2000)), dtypenp.float32) adata1 ad.AnnData(counts) print(adata1)…...

腾讯云域名备案后,如何解析到华为云服务器Linux宝塔面板
一、购买域名并且进行备案和解析,正常情况下,购买完域名,如果找不到去哪备案,可以在腾讯云上搜索“备案”关键词就会出现了,所以这里不做详细介绍,直接进行步骤提示: 二、申请ssl证书࿰…...
odoo 按钮打印pdf报表
odoo打印一般是在动作里面进行的 所以此方法可用自定义按钮进行打印 <template id"report_sale_line_packing_template"> xxx </template><template id"report_sale_line_packing"><t t-call"web.basic_layout"><t …...

用逻辑分析仪观察串口Uart数据波形
一、概述 只讨论嵌入式编程中较为常用的异步串行接口(Universal Asynchronous Receiver/Transmitter, UART),TTL电平。 串口的参数一般有: 1.波特率,数据传输速率,单位bps(bits per…...
数据结构-栈应用括号匹配
1、顺序栈的定义 2、顺序栈的入栈,出栈,取出栈顶元素,匹配判断函数 3、顺序栈的运行测试 4、实现代码 #include<iostream> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; #define M…...
leetcode做题笔记209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输入&#…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...

什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...

倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...