当前位置: 首页 > 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.…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...