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

【教3妹学编程-算法题】2913. 子数组不同元素数目的平方和 I

image.png

-----------------第二天------------------------
image.png

面试官 : 好的, 我们再来做个算法题吧。平时工作中会尝试用算法吗, 用到了什么数据结构?
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

-----------------第二天------------------------ 面试官 : 好的&#xff0c; 我们再来做个算法题吧。平时工作中会尝试用算法吗&#xff0c; 用到了什么数据结构&#xff1f; 3妹 : 有用到&#xff0c; 用到了 bla bla… 面试官 : 好的&#xff0c; 题目是这样的&#xff1…...

是否会有 GPT-5 的发布?

本心、输入输出、结果 文章目录 是否会有 GPT-5 的发布?前言围绕 GPT-5 的信息OpenAI 期待增长GPT-5 - 到底是真的在训练,还是一个虚构的故事Sam Altman字里行间包含的信息我们在什么时候可以期待 GPT-5 的发布GPT-5 预计将在哪些方向努力GPT-5 在听觉领域GPT-5 在视频处理领…...

使用 Selenium Python 检查元素是否存在

像 Selenium 这样的自动化工具使我们能够通过不同的语言和浏览器自动化 Web 流程并测试应用程序。 Python 是它支持的众多语言之一&#xff0c;并且是一种非常简单的语言。 它的Python客户端帮助我们通过Selenium工具与浏览器连接。 Web 测试对于开发 Web 应用程序至关重要&am…...

const迭代器与模板构造函数

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

在Qt中解决opencv的putText函数无法绘制中文的一种解决方法

文章目录 1.问题2.查阅资料3.解决办法 1.问题 在opencv中&#xff0c;假如直接使用putText绘制中文&#xff0c;会在图像上出现问号&#xff0c;如下图所示&#xff1a; 2.查阅资料 查了一些资料&#xff0c;说想要解决这个问题&#xff0c;需要用到freetype库或者用opencv…...

【Linux】第六站:Centos系统如何安装软件?

文章目录 1.Linux安装软件的方式2.Linux的软件生态3. yum4. rzsz软件的安装与卸载5.yum如何知道去哪里下载软件&#xff1f; 1.Linux安装软件的方式 在linux中安装软件常用的有三种方式 源代码安装&#xff08;我们还需要进行编译运行后才可以&#xff0c;很麻烦&#xff09; …...

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、善用参数&#xff08;注意版本&#xff09;5、善用模版6、临摹7、垫图 木匠不会因为电动工具的出现而被淘汰&#xff0c;反而善用工具的木匠&#xff0c;收入更高了。 想要驾驭好Midjourney&#xff0c;可以从以下方面出发调整&…...

基于单片机的智能灭火小车设计

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

[Machine Learning][Part 7]神经网络的基本组成结构

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

精准测试:提高软件质量和用户满意度的利器

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…...

代碼隨想錄算法訓練營|第五十八天|583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结篇。刷题心得(c++)

目录 讀題 583. 两个字符串的删除操作 自己看到题目的第一想法 看完代码随想录之后的想法 72. 编辑距离 看完代码随想录之后的想法 583. 两个字符串的删除操作 - 實作 思路 代碼隨想錄思路 Code 72. 编辑距离 - 實作 思路 Code 编辑距离总结篇 判斷子序列 不同…...

JavaScript基础之BOM与DOM

文章目录 BOM操作window对象window的子对象之navigator对象&#xff08;了解即可&#xff09;window的子对象之screen对象&#xff08;了解即可&#xff09;window的子对象之history对象&#xff08;了解即可&#xff09;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宝塔面板

一、购买域名并且进行备案和解析&#xff0c;正常情况下&#xff0c;购买完域名&#xff0c;如果找不到去哪备案&#xff0c;可以在腾讯云上搜索“备案”关键词就会出现了&#xff0c;所以这里不做详细介绍&#xff0c;直接进行步骤提示&#xff1a; 二、申请ssl证书&#xff0…...

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数据波形

一、概述 只讨论嵌入式编程中较为常用的异步串行接口&#xff08;Universal Asynchronous Receiver/Transmitter&#xff0c; UART&#xff09;&#xff0c;TTL电平。 串口的参数一般有&#xff1a; 1.波特率&#xff0c;数据传输速率&#xff0c;单位bps&#xff08;bits per…...

数据结构-栈应用括号匹配

1、顺序栈的定义 2、顺序栈的入栈&#xff0c;出栈&#xff0c;取出栈顶元素&#xff0c;匹配判断函数 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] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0 。 示例 1&#xff1a; 输入&#…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...