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

【算法题】小红书2023秋招提前批算法真题解析

文章目录

  • 题目来源
  • T1:5900: 【DP】小红书2023秋招提前批-连续子数组最大和
  • 5801: 【二分查找】小红书2023秋招提前批-精华帖子
    • 解法1——排序+滑动窗口
    • 解法2——前缀和 + 二分查找
  • 5000: 【模拟】小红书2023秋招提前批-小红的数组构造
    • 解法——数学
  • 5300: 【哈希表】小红书2023秋招-推荐系统

题目来源

红书2023秋招提前批算法真题解析

T1:5900: 【DP】小红书2023秋招提前批-连续子数组最大和

https://oj.algomooc.com/problem.php?id=5900

在这里插入图片描述

做这题之前可以先做一下力扣中的:53. 最大子数组和 作为前置知识。

每次询问就是一批输入数据。
定义 dp 数组 [n][2] 表示 以 a[i] 为结尾且选 a[i] 的子数组的最大和是多少,第二维的 0 和 1 分别表示当前有没有将元素换成 x 的操作。

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();while (t-- != 0) {int n = sc.nextInt(), x = sc.nextInt();int[] a = new int[n];int[][] dp = new int[n][2];     // 没变和变了for (int i = 0; i < n; ++i) a[i] = sc.nextInt();dp[0][0] = a[0];dp[0][1] = x;int ans = Math.max(dp[0][0], dp[0][1]);for (int i = 1; i < n; ++i) {dp[i][0] = Math.max(dp[i - 1][0] + a[i], a[i]);dp[i][1] = Math.max(dp[i - 1][1] + a[i], dp[i - 1][0] + x);ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));}System.out.println(ans);}}
}

5801: 【二分查找】小红书2023秋招提前批-精华帖子

https://oj.algomooc.com/problem.php?id=5801
在这里插入图片描述

这道题目很像:2271. 毯子覆盖的最多白色砖块数

解法1——排序+滑动窗口

该解法的解析见:【LeetCode周赛】2022上半年题目精选集——双指针

在这里插入图片描述

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();int[][] e = new int[m][2];for (int i = 0; i < m; ++i) {e[i][0] = sc.nextInt();e[i][1] = sc.nextInt();}// 排序Arrays.sort(e, (x, y) -> x[0] - y[0]);int ans = 0, sum = 0;// 开滑(枚举右端点,尝试移动左端点)for (int l = 0, r = 0; r < m; ++r) {sum += e[r][1] - e[r][0];// 把超过的移出去while (e[r][1] - e[l][1] > k) {sum -= e[l][1] - e[l][0];l++;}// 检查第一个区间是否占完了if (e[r][1] - k > e[l][0]) {ans = Math.max(ans, sum - (e[r][1] - k - e[l][0]));} else ans = Math.max(ans, sum);}System.out.println(ans);}
}

解法2——前缀和 + 二分查找

前缀和是为了快速求出一个区间中的精华区一共有多少个精华帖子。
二分查找是为了快速找出以某一个精华区为起点时,最后一个被覆盖到的精华区的索引。

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();int[][] e = new int[m][2];int[] s = new int[m + 1];for (int i = 0; i < m; ++i) {e[i][0] = sc.nextInt();e[i][1] = sc.nextInt();s[i + 1] = s[i] + e[i][1] - e[i][0];}int ans = 0;for (int i = 0; i < m; ++i) {   // 枚举每个瓷砖作为起始瓷砖// 使用二分查找最后一个被覆盖到的瓷砖int l = i, r = m - 1;while (l < r) {int mid = l + r + 1 >> 1;if (e[i][0] + k < e[mid][0]) r = mid - 1;else l = mid;}ans = Math.max(ans, s[l] - s[i] + Math.min(e[i][0] + k, e[l][1]) - e[l][0]);}System.out.println(ans);}
}

5000: 【模拟】小红书2023秋招提前批-小红的数组构造

在这里插入图片描述

解法——数学

冷静思考!—— 最后的数组是这样的 k , 2 ∗ k , 3 ∗ k , . . . n ∗ k {k,2*k,3*k,...n*k} k,2k,3k,...nk

使用等差数列求和公式得答案为 k ∗ n ∗ ( n + 1 ) / 2 k * n * (n + 1) / 2 kn(n+1)/2

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), k = sc.nextInt();System.out.println((long)k * n * (n + 1) / 2);}
}

记得要转 long 否则答案会溢出 int。

5300: 【哈希表】小红书2023秋招-推荐系统

https://oj.algomooc.com/problem.php?id=5300#
在这里插入图片描述

按照题目要求读取数据,存入哈希表做计数统计。
将结果放入列表,自定义筛选和排序即可。

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Map<String, Integer> cnt = new HashMap<>();while (sc.hasNext()) {String word = sc.next();cnt.merge(word, 1, Integer::sum);}List<Pair> ls = new ArrayList<>();for (Map.Entry<String, Integer> entry: cnt.entrySet()) {if (entry.getValue() >= 3) {ls.add(new Pair(entry.getKey(), entry.getValue()));}}Collections.sort(ls, (x, y) -> {int c1 = x.value, c2 = y.value;return c1 != c2? c2 - c1: x.key.compareTo(y.key);});for (Pair p: ls) {System.out.println(p.key);}}
}class Pair {String key;Integer value;Pair(String key, Integer value) {this.key = key;this.value = value;}
}

相关文章:

【算法题】小红书2023秋招提前批算法真题解析

文章目录 题目来源T1&#xff1a;5900: 【DP】小红书2023秋招提前批-连续子数组最大和5801: 【二分查找】小红书2023秋招提前批-精华帖子解法1——排序滑动窗口解法2——前缀和 二分查找 5000: 【模拟】小红书2023秋招提前批-小红的数组构造解法——数学 5300: 【哈希表】小红…...

序列到序列学习(seq2seq)

permute(1,0,2)&#xff0c;将batch_size 放在中间state 最后一个时刻&#xff0c;每个层的输出...

基于Java+SpringBoot+Vue摄影分享网站的设计与实现 前后端分离【Java毕业设计·文档报告·代码讲解·安装调试】

&#x1f34a;作者&#xff1a;计算机编程-吉哥 &#x1f34a;简介&#xff1a;专业从事JavaWeb程序开发&#xff0c;微信小程序开发&#xff0c;定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事&#xff0c;生活就是快乐的。 &#x1f34a;心愿&#xff1a;点…...

接口测试系列 —— POSTMAN的简单使用

postman的基本使用 概述 我相信对于postman的介绍&#xff0c;网上一搜肯定很多很多。下面我就不打算跟大家普及postman了。只看应该怎么用postman进行接口测试。好了&#xff0c;下面咱们直接进入正文吧。 环境 postman之前是作为chrome插件形式存在的。后面变成了独立的应…...

一个帮各位填秋招表格省一点事的浏览器插件

最近应该很多和我一样的双非鼠鼠在秋招等面试&#xff0c;而且处于海投阶段&#xff0c;为了不忘记投了哪些公司&#xff0c;可以用这样一个表格来记录&#xff1a; 其中有些字段&#xff0c;比如状态、投递时间、查看进度的网址其实可以不手动输入&#xff0c;所以搞个插件来…...

react16之前diff算法的理解和总结

此篇文章所讨论的是 React 16 以前的 Diff 算法。而 React 16 启用了全新的架构 Fiber&#xff0c;相应的 Diff 算法也有所改变&#xff0c;本片不详细讨论Fiber。 fiber架构是为了支持react进行可中断渲染&#xff0c;降低卡顿&#xff0c;提升流畅度。 react16之前的版本&…...

JavaEE初阶(1)(冯诺依曼体系、CPU、CPU基本原理、如何衡量CPU的好坏?指令、操作系统、操作系统“内核”)

目录 冯诺依曼体系&#xff08;Von Neumann Architecture&#xff09; CPU CPU基本原理&#xff1a; 如何衡量CPU的好坏&#xff1f; 1、主频&#xff08;时钟速度&#xff09;&#xff1a; 2、核心数&#xff1a; 指令 操作系统 操作系统“内核” 冯诺依曼体系&#x…...

记录在yapi上传接口的问题

sorry ,upload api error cause:请求参数 data.path 不应少于 1 个字符 自己在写的代码中使用到了DeleteMapping DeleteMapping("/deleteCart/{skuId}")public Result deleteCart(PathVariable Long skuId,HttpServletRequest request){报上面的错误&#xff0c;原因…...

DevOps管理软件生命周期

整体的软件开发流程 PLAN&#xff1a;开发团队根据客户的目标制定开发计划 CODE&#xff1a;根据PLAN开始编码过程&#xff0c;需要将不同版本的代码存储在一个库中。GIT,SVN BUILD&#xff1a;编码完成后&#xff0c;需要将代码构建并且运行。MAVEN TEST&#xff1a;成功构建…...

快速解决 adb server version doesn‘t match this client

这个问题是由于电脑上安装了多个版本的adb工具&#xff0c;客户端和服务端的版本不一致&#xff0c;无法正常通信导致。最快的解决方法就是将Android SDK中adb复制到系统目录下。 操作步骤如下&#xff1a; 1. 查看adb版本和路径 执行adb version&#xff0c;如下&#xff0…...

【更新至2022年】2000-2022年全国31省市以2000年为基期的实际GDP、名义GDP、GDP平减指数数据(含原始数据+计算过程+计算结果)

2000-2022年31省市名义GDP 实际GDP GDP平减指数 1、时间&#xff1a;2000-2022 2、范围&#xff1a;31省市 3、来源&#xff1a;GJ统计J和统计NJ 4、指标&#xff1a;名义GDP、地区生产总值指数&#xff08;上年100&#xff09;、实际GDP&#xff08;以2000年为基期&#x…...

【LeetCode】剑指 Offer <二刷>(5)

目录 题目&#xff1a;剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣&#xff08;LeetCode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;剑指 Offer 11. 旋转数组的最小数字 - 力…...

rtsp 拉流 gb28181 收流 经AI 算法 再生成 rtsp server (一)

1、 rtsp 工具 1 vlc 必备工具 2 wireshark 必备工具 3 自己制作的工具 player 使用tcp 拉流&#xff0c;不自己写的话&#xff0c;使用ffmpeg 去写一个播放器就行 4 live555 编译好live555&#xff0c; 将live555的参数修改以下&#xff0c;主要是缓存大小 文章使用c 来写一…...

Jmeter系列-环境部署、详细介绍、安装目录介绍(1)

环境部署 官网下载Jmeter http://jmeter.apache.org/下载最新版本的 JMeter&#xff0c;解压文件到任意目录 安装JDK&#xff0c;配置Java环境 1、下载&#xff08;注意选择操作系统对应的位数32/64&#xff09; 官网 &#xff1a;http://www.oracle.com 2、安装&#xff0…...

更换 yum 阿里源 - 手把手教你怎么配置,在也不需要求别人了 - 看懂一个就相当于看懂了其他的linux系统

更换阿里源 我的是centos8 当然 centos7 也可以换 后面有更详细的怎么配 &#xff0c;再也不用求别人怎么弄了 最直接的方式 直接复制 执行 centos7 curl -o /etc/yum.repos.d/CentOS-Base.repo https://mirrors.aliyun.com/repo/Centos-7.repo或者 wget -O /etc/yum.repos.…...

966SEO扫地僧站群·万能HTML模板[V1.9.1]

扫地僧站群万能HTML模板是一款站点管理软件,其主要特点是可以将原始的html模板放入程序中,无需编写任何标签,程序会全自动替换处理,从而快速构建出一个完整的网站,这种模式相对于传统的网站建设方式更加快速、简单,同时可以大幅度降低网站建设的成本和难度.服务器及域名量的配置…...

angular:html2canvas对ion-avatar节点渲染不正确

问题&#xff1a; 如题 解决办法&#xff1a; 简单实现头像遮罩 <div class"ion-avatar" style"width: 40px; height: 40px; border-radius: 50%; overflow: hidden"><img src"" alt""/> </div><style>.ion-…...

使用dockerfile文件部署Python+PyWebIO项目

1、安装docker 教程详见之前的内容。https://blog.csdn.net/weixin_44691253/category_12101661.html 2、打包好Python项目 之前的文章中有提到我编写测试工具使用的框架&#xff1a;PythonRequestsPyWebIO框架详解&#xff0c;编写测试工具提高团队测试效率 打包项目时&am…...

【web开发】5.Mysql及python代码执行数据库操作

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、MYSQL二、MySQL管理查看已有数据库创建数据库删除数据库进入数据库创建表删除表展示表的行列插入数据查看表中的数据删除数据修改数据 三、python代码执行数据库…...

Android学习之路(13) Handler详解

1. 简介 Handler是一套 Android 消息传递机制,主要用于线程间通信。 用最简单的话描述&#xff1a; handler其实就是主线程在起了一个子线程&#xff0c;子线程运行并生成Message&#xff0c;Looper获取message并传递给Handler&#xff0c;Handler逐个获取子线程中的Message.…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...