154 篇
1. 成本计划的主线 规模估算 → 工作量估算 → 成本估算 → 成本预算/成本基线 2. 估算的基本认识 估算不是精确计算,一定有误差。 项目经验数据非常重要 不要太迷信某些数学模型 3. 软件单位 软件规模单位 LOC (Line of Code) 源代码长度的测量 FP (Function Point) 用系
进度计划的重要性 按时完成项目是项目经理最大的挑战之一 时间是项目规划中灵活性最小的因素 进度问题是项目冲突的主要原因 进度的定义 进度是对执行的活动和里程碑制定的工作计划日期表 项目进度计划 分为传统项目进度计划和敏捷项目进度计划 任务定义 确定为完成项目的各个交付成果所必须进行的诸项具体活动 项目任务的关联关系 项
软件质量基本概念 软件质量 质量模型 质量的形成 质量定义 质量是满足要求的程度,包括符合规定的要求和满足顾客隐含需求。 软件质量是软件满足明确说明或者隐含的需求的程度 质量的形成 质量形成于产品或者服务的开发过程中,而不是事后的检查(测试)把关等。 质量成本(CoQ) 预防成本:前期质量成本 缺陷成本:后期质量
软件配置管理过程 资产标识 资产关系 资产库管理 (基线)资产变更管理 资产状态统计 配置管理定义 记录软件产品的演化过程 得到精确的产品配置 最终保证软件产品的完整性、一致性、追朔性、可控性 配置管理的主要功能 版本管理 变更管理 过程支持 软件配置项 SCI: Software Configuration
1. 基本 COCOMO-81 公式 $$ E = a \times (KLOC)^b $$ 参数含义 | 参数 | 含义 | |---|---| | $E$ | 工作量,单位为人月 | | $KLOC$ | 交付的代码行数,单位为千行代码 | | $a, b$ | 依赖于项目自然属性的系数 | 项目类型与参数 | 项
功能亮点 智能问答:从人工回复到AI自动回答,基于先进的自然语言处理技术,助教AI能够理解学生的问题并提供准确、详细的解答,涵盖课程内容、作业指导、考试准备等多个方面。 对话Agent:人工助教不需要再手动翻阅文档来回答学生问题,助教AI能够直接从课程文档中提取相关信息,快速生成答案,提高响应效率。只要文档上传到了知
软件的特征 Software Characteristics Complexity 复杂性 Evolution 演化性 Artifact, reflecting human intelligence. 软件是一种人工制品,体现了人类智能。 一些事实 The Facts 只有 32% 的软件项目被认为是成功的,也就是功能
SA 概念 构件 + 连接件 SA有5个核心的组成要素 Component Connector Configuration Port Role SA有4+1视图 逻辑视图 进程视图 开发视图 物理视图 + 场景视图
1. 为什么要软件项目管理? 软件项目失败,往往不是因为不会写代码,而是因为不会管理。 典型误区有两个: “三边行动”: 边计划、边实施、边修改。看起来灵活,实际上容易导致目标不清、进度混乱、返工严重。 “六拍运动”: 拍脑门决策 → 拍肩膀鼓励 → 拍胸脯保证 → 拍桌子发火 → 拍屁股走人 → 拍大腿后悔。 这个很
配置读取 使用https://github.com/BurntSushi/toml.git作为toml配置文件的解析库 我们只需要Config.LoadConfig()函数来读取配置文件,其他部分不需要关心。 func LoadConfig() error { // 这里的路径需要根据实际情况修改,指向你的配置
HTTP 解析URL,获取协议、主机、端口、路径等信息。 生成HTTP请求信息 DNS解析 客户端本地缓存:浏览器和操作系统都会缓存 DNS 结果,同一个域名第二次访问直接命中,延迟几乎为零 本地 DNS 服务器缓存:你的 ISP 或公司 DNS 服务器缓存了大量热门域名,大多数请求在第2步就结束了 TTL 控制缓存时
前向安全 前向安全(Forward Secrecy,FS),更严格的版本叫 完美前向安全(Perfect Forward Secrecy,PFS),指的是:即使长期密钥(例如服务器的私钥)将来被泄露,攻击者也无法解密历史上已经截获的会话流量。 为什么需要前向安全 考虑一个不具备前向安全的场景:客户端用服务器的 RSA
RPC 全称为:Remote Procedure Call,远程过程调用。它是一种调用方式,而不是一个具体的协议。RPC 的核心思想是让程序员能够像调用本地方法一样去调用远端的服务方法。 总结 纯裸 TCP 是能收发数据,但它是个无边界的数据流,上层需要定义消息格式用于定义消息边界。于是就有了各种协议,HTTP 和
HTTP/1.1 的局限:半双工 TCP 协议本身是全双工的,客户端和服务端可以同时互相发送数据。但我们最常用的 HTTP/1.1 虽然基于 TCP,却是半双工的——在同一时刻,只有一个方向的数据传输在进行。 它的模型非常简单:客户端问,服务端答。只要客户端不发起请求,服务端就永远沉默。 这对于需要服务器主动推送数据的
主要对比HTTP1,HTTP2的协议特性和性能优化点。 HTTP/2 的优化主要体现在三个方面。 头部压缩 HPACK 第一,头部压缩(HPACK)。对常见 HTTP 头部通过静态表和 Huffman 编码压缩近一半体积,后续请求还可建立动态表,压缩率可达 90%。但动态表会占用内存,越大越影响并发能力,因此服务器需限
硬件优化 HTTPS 是计算密集型协议,选择计算能力更强的CPU,最好有AES-NI指令集的CPU,可以大幅提升加密解密性能。 软件优化 升级软件的版本,例如升级OpenSSL版本,利用最新的性能优化和安全特性。升级Linux内核版本,利用最新的网络协议栈优化和安全特性。 协议优化 密钥交换算法可以使用ECDHE算法,
TCP的特点 TCP的三个特点:面向连接,可靠传输,基于字节流的传输层通信协议。 TCP连接 怎么理解什么是连接 用于保证可靠性和流量控制维护的某些状态信息,这些信息的组合,包括 Socket、序列号和窗口大小称为连接。 所以,建立一个TCP连接需要客户端与服务器达成三个信息的共识。 Socket:IP地址和端口号
测试的粒度 单元测试:测试每一个单独的模块。 集成测试:测试模块之间的交互。 系统测试:由开发人员对整个系统进行测试。 验收测试:由客户根据用户需求对系统进行验证,通常没有正式的测试用例。 单元测试 对软件中的基本模块进行测试。 例如: 一个函数 一个类 一个组件 单元测试通常能发现的问题: 局部数据结构问题 算
1. 本章主线 项目初始 → 项目计划 → 项目执行控制 → 项目结束 而本章讲的就是第一个阶段:项目初始 / 项目确立。 本章四个重点: 项目立项 项目招投标 项目章程 案例总结 2. 项目为什么要启动? 项目不是凭空来的,而是为了满足某种业务、法律、用户或战略需要。 项目启动通常来自几个背景: 满足法规、法律
日志库 校园即时聊天系统需要一个日志库来记录系统运行时的各种信息,包括错误日志,访问日志,调试日志等。一个好的日志库能够帮助我们快速定位问题,分析系统行为,以及监控系统状态。 日志库的核心能力主要包括: 支持多输出目标,可根据不同环境将日志写入控制台、文件等多个位置。 提供分级日志能力,例如 INFO、WARN、ER
控制流图 图的形式化定义 一个图 $G$ 定义如下: $$G = (V, E)$$ $V$:有限且非空的顶点集合。 $E$:边的集合,边是顶点对。 $V = {v_1, v_2, v_3, v_4}$ $E = {(v_1, v_2), (v_1, v_3), (v_2, v_4), (v_3, v_4)}$ $V
1. 本章总框架 生存期模型选择 → 预测模型 → 迭代模型 → 增量模型 → 敏捷模型 → 混合模型 项目初始 -> 项目计划 -> 项目执行控制 -> 项目结束 项目确立和生存期 预测型:提前做大量计划,然后一次性执行。 迭代型:允许对未完成工作进行反馈、改进和修改。 增量型:向客户提供各个已完成、可立即使用的可交
Redis在校园即时聊天系统中的应用 Redis 是一种以内存为核心的数据库系统,因此具备很强的读写能力。由于数据直接保存在内存中,它可以在单位时间内完成大量读写请求,这使其非常适合高并发、低时延的业务场景。把 Redis 作为后端数据的存储与缓存媒介,能够有效提高系统处理请求的效率,并改善整体性能表现。 在本项目里,
主路径覆盖 Prime Path Coverage 如果一个图中包含循环,那么它就有无限多条路径。 因此,CPC 不可行。 CPC:Complete Path Coverage,完全路径覆盖。 简单路径 Simple Path 从节点 ni 到节点 nj 的一条路径,如果除了第一个节点和最后一个节点可以相同之外,没有任
需求管理的步骤:需求获取,需求分析,编写需求规格,需求验证,需求变更 5个过程。 需求变更管理 ① 建立需求基线 ② 确定需求变更控制过程 ③ 建立变更控制委员会(SCCB) ④ 进行需求变更影响分析 ⑤ 跟踪所有受需求变更影响的工作产品 ⑥ 建立需求基准版本和需求控制版本文档,维护需求变更的历史记录 ⑦ 跟踪每项需求
我的理解是为了保证消息的顺序性和防止老消息饿死 这段代码的设计意图,本质上是两个字: 补发 它把消息队列分成两层: ChatServer.Transmit:全局主队列,服务端真正消费这个队列 c.SendTo:当前客户端自己的“积压队列” 为什么要先用 for 把 SendTo 里的旧消息往 Transmit 搬,
数据流覆盖 Data Flow Coverage 数据流 Data Flow 超越结构覆盖 目标: 尽量确保变量的值被正确计算,并且被正确使用。 结构覆盖只关心“程序走没走到某些点或路径”,而数据流覆盖进一步关心“变量的定义和使用之间是否合理”。 Definition / def 变量的值被存入内存的位置。 也就是变量
1. 为什么要任务分解? 大事化小,把项目拆到可预测、可管理、可执行的工作单元。 强调:任务分解是项目管理的基础 任务分解过程 将一个项目分解为更多的工作细目或者子项目,使项目变得更小、更易管理、更易操作 任务分解结果 WBS( Work Breakdown Structure:任务分解结构) 练习 小题 任务分解是将
这里的 server 逻辑,核心就是一句话: 维护在线连接,消费待转发消息,再把消息分发给目标客户端。 核心文件是 internal/service/chat/server.go:25。 1. Server 里有什么 Server 结构体有 4 个关键成员: Clients map[string]*Client 按用
逻辑覆盖 Logic Coverage 程序中的逻辑 Logic in Program ((x > 5) && (y > 0)) 判定 / 决策 Decision 整个布尔表达式是一个decision 条件 Condition 表达式中的每个基本布尔子表达式是 condition。 判定覆盖 / 决策覆盖 Decisi
上来先盯着自己的 handler 盯了一会,越看越不对劲。 写到这一步,前面的 handler 基本能跑了,但越看越觉得别扭:日志全是 log.Fatal 跟 fmt.Println 混着来,错误常量到处散,handler 里又写参数校验又发邮件又操作 Redis。这一篇记录一次小重构,主题是三件事:日志
变异测试 Mutation Testing 什么是变异测试 通过创建程序的许多不同版本,将缺陷引入程序中,这些版本被称为变异体。 每个变异体都包含一个单独的缺陷。 测试用例会被同时应用到原始程序和变异程序上。 目标是让变异程序失败,从而证明测试用例的有效性。 变异测试是一种向程序中插入缺陷的方法,用来测试已有测试是否
黑盒测试 Blackbox Testing 随机测试 Random Testing 简单 = 强大 Simple = Powerful 随机不等于免费 Random != Free 随机不等于简单 Random != Simple 随机测试看起来简单,但真正做好并不容易。随机生成测试用例并不是“随便生成”,它仍然需要明
等价类划分 Equivalence Partitioning 等价类划分可以应用于多个测试层级: 单元测试 集成测试 系统测试 无须自动化工具,相对容易应用 可以灵活调整流程,以获得更多或者更少的测试用例。 输入域 程序的输入域包含该程序所有可能的输入 即使是很小的程序,输入域也大到近乎无穷 测试的本质是从输入域中
人力资源计划 组织结构的主要类型 职能型 项目型 矩阵型 干系人管理计划 干系人(Stakholder) 干系人(stakeholder)是能影响项目决策、活动或者结果的个人、群体或者组织,以及会受到或者自认为会受到项目决策、活动或者结果影响的个人、群体或者组织。 沟通计划 项目沟通的分类 内部沟通和外部沟通 正
测试中的默认选项 Default Options in Testing 基础选择 Base Choice 等价划分 Equivalence Partitioning 各输入变量的划分如下: | 输入A | 输入B | 输入C | 输入D | | ----- | ----- | ----- | ----- | | A1
风险管理 = 先识别风险,再评估优先级,再制定应对策略,最后持续控制。  风险是什么 风险是:未来可能发生、会造成损害的事情。 软件风险就是可能对开发过程或软件产品本身造成伤害或损失的因素。 常见考法: “需求变更属于什么风险?” 一般选:可预测风险 Known unknown。因为需求变更很常见,虽然不知道具体什
第 12 章:软件项目合同计划 本章要点有 4 个:合同类型、合同计划、敏捷项目合同计划、案例分析。PPT 一开始用 Email 模块外包举例:要考虑“委托哪个公司完成、多少钱合适”。 1. 先记两个基本概念 项目采购:为了执行项目而从项目团队外部获取产品、服务或者结果的过程,称为采购。 合同:合同是具有法律效力的协
第1页 Test Oracle(测试预言) 第2页 自动驾驶汽车——如何测试? 测试问题: 相同输入,结果可能不同,很难构造测试预言。 汽车因雨中行驶以及太阳方位问题,无法识别路标甚至行人; 摄像头在灰暗天空下无法识别白色汽车; 当公交车汇入车流时,系统误判其会停车。 → 致命碰撞事故 深度神经网络被用于自动驾驶
1. 本章主线 这一章属于 项目执行控制篇,主题是:项目不是只靠计划,关键还要在执行中不断采集数据、比较偏差、控制变更、必要时修正计划。 本章要点有四个: 项目集成计划 集成计划的执行控制 敏捷项目集成管理 案例分析 2. 项目集成管理:核心是“协调多个目标” PDF 里强调:项目集成管理由 项目经理负责。 项目
第1页 — Test Case Prioritization(测试用例排序) 标题: 测试用例排序(Test Case Prioritization) 第2页 — 测试用例排序(定义) 测试用例排序 给定一个初始测试集 $T_{init}$,找到满足以下条件的排列 $T \in PT$: $$\forall T',\
成本、时间管理 图解控制法 挣值分析法 网络图分析 图解控制法 资源图 进度图 成本图 资源图 项目进度图 费用曲线图 偏差分析与控制(以进度为例) 挣值分析原理 BCWS: 计划到今天应该完成的预算成本,也叫计划值PV Budgeted cost of work sdcheduled BCWP: 实际已经完成
可达性(Reach):语法可达 vs 语义可达 基础概念:什么是"可达"? 在控制流图(CFG)中,可达性描述的是:从某个节点出发,能不能"走到"另一个节点。 基本定义: 如果存在一条路径从 $v_1$ 开始、到 $v_2$ 结束,则称 $v_1$ 可以到达 $v_2$。 语法可达(Syntactic Reach)
第1章 测试概述 1.1 Fault Error Failure | 概念 | 中文 | 含义 | | ----------- | --------------- | ------------------
什么是区块链 区块链是一种共享的、不可变的数字分类账,能够在商业网络中记录交易和追踪资产,并提供单一可信信息源。 区块链作为一个去中心化的分布式数据库,数据存储在多台计算机上,具有抗篡改功能。交易通过共识机制进行验证,确保整个网络的一致性。 在区块链科技中,每笔交易都被分组为区块,然后这些区块链接在一起,形成一个安全透
微服务的核心组件 1. 服务注册与发现(Service Registry & Discovery) 服务实例动态启停、扩缩容,调用方不可能硬编码 IP。注册中心负责让服务"上线时登记、下线时注销",调用方按服务名查询可用实例。常见实现有 Consul、Nacos、etcd,以及 Go 生态里 go-micro、krat
问题描述 哎呀,Codex 的配置有时候真的像出门前换装备:自己订阅能用,别人中转提供的密钥也能用,但两边配置一切换起来,就很容易手忙脚乱。 咱遇到的场景是:平时可能会用别人提供的密钥跑一些任务,但如果那边突然报错、额度不稳定,或者认证状态不对,就需要马上切回自己的订阅。手动改 ~/.codex/config.toml
1. 安装鼠须管输入法 macOS从官网下载安装包 下载 Rime macOS 安装包 在设置中开启鼠须管输入法 2. 使用git安装雾凇拼音 雾凇拼音官网 雾凇拼音GitHub链接 打开mac的终端,输入以下bash脚本 cd ~/Library # 进入Rime安装的文件夹 mv Rime Rime_backup
问题描述 当打字过快的时候,我发现Mac的键盘有时候会出现大写键(Caps Lock)响应延迟的问题,导致切换拼音和ABC时出现卡顿现象,影响打字效率。特别是在配置鼠须管和ABC输入法的情况下,这个问题尤为明显. 例如按下Caps Lock键后,系统未变更为鼠须管拼音输入法,而是仍然停留在ABC输入法,导致输入的内容不
问题描述 欸,最近在做小三月的即时聊天系统前端时,账号密码提交这一步忽然提醒了咱:就算是本地开发,也不能总把安全这件事当成"上线之后再说"嘛。 前端平时用 npm run dev 跑在 127.0.0.1:5173,访问起来确实很方便。但如果要模拟更接近线上环境的 HTTPS,或者让浏览器在本地也走一套正式一点的 TL
如何在 Win 上配置 Agent 开发常见环境 本文记录在 Windows 上配置 GopherPaper 本地开发环境的过程。需要准备四类内容: 语言运行:Go(编译跑后端) 容器:Docker Desktop(一键起 MySQL / Redis / RabbitMQ / Milvus) 四个密钥:火山方舟大模型
RPC 使用RPC能够让我们像调用本地函数一样调用远程服务。
🚀 什么是Kafka Apache Kafka 是一个分布式消息队列系统,核心思想是 Producer(生产者)→ Topic(主题) → Consumer(消费者) 比如:用户下单 → 发一条消息到 order-topic → 库存服务、邮件服务各自消费这条消息。 🐹 什么是 kafka-go? kafka-g
题目描述 在一条环形道路上共有 n 个加油站,第 i 个加油站拥有 gas[i] 升汽油。 从第 i 个加油站开往第 i+1 个加油站需要消耗 cost[i] 升汽油(n-1 的下一个为 0)。 你从某个加油站出发,初始油箱为空,油箱容量无限。如果能够绕环路一周返回出发点,则返回该加油站的下标,否则返回 -1。 若存在
题目描述 咱来翻译下题面:给定一个整数数组 nums,再给一个窗口大小 k。这个窗口一开始覆盖数组最左边的 k 个元素,之后每次向右移动一位。 每次移动时,只能看到当前窗口里的 k 个数字,需要记录这个窗口中的最大值。最后返回所有窗口最大值组成的数组。 思路 如果每个窗口都重新扫一遍最大值,时间复杂度会变成 O(nk)
题目描述 给定一个 m x n 的二维面板,1 表示活细胞,0 表示死细胞。每个细胞都要根据周围八个方向的活细胞数量,按照题目的四条规则决定下一轮状态。 关键点在于:所有细胞的出生和死亡是同时发生的。所以在更新某个位置时,不能让它提前影响其他位置的判断。 题目要求直接在原数组 board 上完成更新,不需要返回值。 思
题目描述 给定一个 9 x 9 的数独棋盘,请判断当前已经填入的数字是否合法。 这里只需要验证已经出现的数字是否满足数独规则: 每一行中,数字 1-9 不能重复出现 每一列中,数字 1-9 不能重复出现 每一个 3 x 3 宫内,数字 1-9 不能重复出现 空白位置用 '.' 表示。需要注意的是,一个当前合法的棋盘
题目描述 给定一个 n x n 的二维矩阵 matrix,它表示一张图像。现在需要把这张图像顺时针旋转 90 度,并且要求在原地完成,不能额外创建一个同样大小的新矩阵。 这题的重点不只是“转过去”,而是要在不借助额外矩阵的前提下,直接修改原数组。 知识边界 我一开始对“原地旋转矩阵”这件事的直觉并不强,尤其是不太容易一
题目描述 给你一个 m 行 n 列的矩阵 matrix,要求按照顺时针螺旋顺序返回矩阵中的所有元素。 这题的关键不在于怎么“转弯”,而在于如何在不断缩小的边界里,按固定顺序把每一圈完整走完,并且避免重复访问。 思路 这份解法用四个边界来描述当前还没有遍历过的矩形区域:left、right、top、bottom。一开始它
SQSD 一种良性微调 云存储环境下基于 数据加密 SafeVLA
题目描述 给定一个 m x n 的矩阵,如果某个位置的元素为 0,就把它所在的整行和整列都改成 0。 这题的限制在于要使用原地算法,也就是说不能再开一个同样大小的新矩阵来保存答案,必须直接在原矩阵上修改。 知识边界 这题真正容易卡住的地方是“原地”要求。用两个布尔数组记录哪些行、哪些列要清零,做起来并不难,但空间复杂度
MySQL 可重复读解决幻读了么? 在 MySQL 的 InnoDB 存储引擎中,默认的事务隔离级别为 可重复读(Repeatable Read),它通过使用 Read View 来实现对幻读的解决。 尽管可重复读很大程度上解决了幻读问题,但在某些特定场景下,仍然存在幻读现象。 可重复读如何解决幻读? 主要通过两种手段
Read View 是什么? Read View(读视图)是 InnoDB 存储引擎中实现 MVCC(多版本并发控制) 的核心数据结构。 本质 Read View 本质上是一个事务快照,记录了某个时刻系统中活跃事务的状态,用来判断某条记录的哪个版本对当前事务是可见的。 Read View 的结构 type Read
题目描述 在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。 返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望下标数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。 思路 这道题的核心思想是利用余数配对: 两个数之和能被 6
题目描述 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum,判断这棵树中是否存在一条从根节点到叶子节点的路径,使得路径上所有节点值之和恰好等于 targetSum。 这里的叶子节点指的是没有左右子节点的节点。只要存在任意一条满足条件的根到叶路径,就返回 true;如果所有路径都不满足,就返回 f
题目描述 罗马数字包含以下七种字符:I、V、X、L、C、D 和 M。 | 字符 | 数值 | | ---- | ---- | | I | 1 | | V | 5 | | X | 10 | | L | 50 | | C | 100 | | D | 500 | |
题目描述 有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]。 对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr[Li] XOR arr[Li+1] XOR ... XOR arr[Ri])作为本次查询的结果。 返回一个包含给定查
题目描述 矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线,沿右下方向一直到矩阵末尾的元素。例如,矩阵 mat 有 6 行 3 列,从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。 给你一个 m * n 的整数矩阵 mat ,请
题目描述 有 n 个孩子站成一排,ratings[i] 表示第 i 个孩子的评分。 需要给每个孩子分发糖果,满足: 每个孩子至少分到 1 个糖果。 相邻孩子中评分更高的孩子必须获得更多糖果。 请计算满足条件时需要的 最少糖果数。 知识边界 贪心思想 题目本质是 相邻关系约束的最小分配问题。 如果评分连续上升: 1
题目描述 给你一个长度为 n 的链表,每个节点除了 next 指针之外,还有一个额外的 random 指针。这个指针可以指向链表中的任意节点,也可以是 nil。 现在需要构造这个链表的深拷贝。新链表中的每个节点都要重新创建,节点值与原节点一致,同时 next 和 random 的指向关系也要和原链表保持一致,并且不能再
题目描述 设计一个满足 LRU (最近最少使用) 约束的缓存结构。 它需要支持两类操作: get(key):如果 key 存在,返回对应的 value,否则返回 -1 put(key, value):如果 key 已存在,就更新它的值;如果不存在,就插入一组新的键值对;当容量超出限制时,要删除最近最少使用的那个 ke
题目描述 给你一个整数数组 nums 和一个整数 k。 每一步操作中,你需要从数组中选出和为 k 的两个整数,并将它们移出数组。 返回你可以对数组执行的最大操作数。 思路 通过一次遍历数组,和两数之和一样,每次先看看哈希表中是否有k−nums[i],有就去掉哈希表中的一个 k−nums[i],同时把答案加一,没有就把n
题目描述 给你一个整数数组 nums。定义一个子数组的和的绝对值为: abs(nums[l] + nums[l+1] + ... + nums[r]) 其中 abs(x) 的含义如下: 如果 x 是负整数,那么 abs(x) = -x 如果 x 是非负整数,那么 abs(x) = x 请你找出 nums 中和的绝对
题目描述 给你一个链表的头节点 head,要求删除链表的倒数第 n 个节点,并返回删除后的链表头节点。 这道题的关键不在于找到节点的值,而在于真正把目标节点从链表里摘掉,所以最后需要调整前后节点的指针连接关系。 思路 这份代码使用的是链表里很经典的双指针做法。先创建一个哑节点 dummy 指向原链表头部,这样即使要删除
题目描述 给定一个二叉树的根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 思路 站在右侧看二叉树,每一层只能看到最右边的那个节点。因此问题转化为:找出每一层的最后一个节点。 用 BFS 层序遍历,每次处理一整层的节点。遍历时记录当前层的节点总数 queueSize,当某个节
题目描述 给定一个只包括 (、)、{、}、[、] 的字符串 s,判断字符串是否有效。 有效字符串需要满足三个条件:左括号必须用相同类型的右括号闭合,左括号必须按照正确顺序闭合,并且每个右括号都要有对应的左括号。 思路 这道题的核心是用栈维护“当前还没有匹配完成的括号”。 遍历字符串时,遇到左括号就把它对应的右括号压入栈
题目描述 给定一个 n 行的二维数组 rectangles,其中每一行表示一个矩形: rectangles[i] = [width_i, height_i]。 如果存在一对矩形 i、j(i < j)满足: width_i / height_i == width_j / height_j(实数除法), 则称这两个矩形是
题目描述 Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补全和拼写检查。 请你实现 Trie 类: Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word。
题目描述 给你两个按升序排列的链表 list1 和 list2,要求把它们合并成一个新的升序链表并返回。 这里的“合并”不是重新创建所有节点,而是把两个链表中原有的节点按顺序接起来,最终得到一条有序的新链表。 思路 这份代码使用了一个很常见的链表技巧:先创建一个哑节点 dummy,再用 cur 指针始终指向新链表的尾部
题目描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 思路 第一眼看到题,咱第一反应就是——堆嘛!维护“目前为止最大的 k 个元素”,这种活儿不就是
题目描述 给定一个无重复元素的有序整数数组 nums,需要返回恰好覆盖数组全部数字的最小有序区间范围列表。 如果某个区间只有一个数字,就输出 "a";如果某个区间从 a 连续到 b,就输出 "a->b"。 知识边界 分组循环 这题适合用分组循环来做。因为数组已经有序,而且没有重复元素,所以只要相邻两个数满足 nums[
题目描述 给你一个下标从 0 开始的整数数组 nums。如果 i < j 且 j - i != nums[j] - nums[i],那么我们称 (i, j) 是一个坏数对。 请你返回 nums 中坏数对的总数目。 思路 直接统计坏数对的数量比较困难,可以转换思路:统计好数对的数量,然后用总数对减去好数对即可得到坏数对的
题目描述 给你一个链表头节点 head,要求每 k 个节点作为一组进行翻转,并返回处理后的新链表。 如果链表最后剩下的节点数量不足 k 个,那么这一段保持原来的顺序不动。题目还特别要求,不能只交换节点里的值,而是要真正调整链表节点之间的连接关系。 思路 这份代码依然先用了链表题里很常见的哑节点 dummy。不过这里的
题目描述 给你一个下标从 0 开始的字符串数组 words。如果两个字符串由相同的字符组成,则认为这两个字符串相似。例如,"abca" 和 "cba" 相似,因为它们都由字符 'a'、'b'、'c' 组成;然而,"abacba" 和 "bcfd" 不相似。请你找出满足字符串 words[i] 和 words[j] 相似
题目描述 给你一个下标从 0 开始的整数数组 nums。 一次操作中,你可以: 选择两个不同下标 i 和 j,满足 0 <= i, j < nums.length。 选择一个非负整数 k,满足 nums[i] 和 nums[j] 的二进制表示中第 k 位都是 1。 将 nums[i] 和 nums[j] 都减去 2^
题目描述 给定一个下标从 0 开始、大小为 m × n 的二维整数矩阵 grid,请你构造一个同样大小的矩阵 answer。 对于矩阵 answer 中的每个单元格 (r, c),其值按如下方式计算: topLeft[r][c] 表示在矩阵 grid 中,位于单元格 (r, c) 左上方向对角线上的所有元素中,不同值
题目描述 给定一个规律字符串 pattern 和一个字符串 s,判断它们是否满足同一套映射关系。 这里的关键是双向一一对应: pattern 中的每个字符都只能映射到一个唯一单词 s 中的每个单词也只能映射到一个唯一字符 不能出现两个字符映射到同一个单词,也不能出现两个单词映射到同一个字符 思路 先用 string
题目描述 咱来翻译下题面:需要实现一个 MedianFinder,它会不断接收数据流里的整数,并且随时返回当前所有数字的中位数。 如果当前数字个数是奇数,中位数就是排序后正中间的数字;如果是偶数,中位数就是中间两个数字的平均值。也就是说,addNum 负责把新数加进来,findMedian 要在已经加入的所有数里快速找
题目描述 给你一个二维 boolean 矩阵 grid 。 如果 grid 的 3 个元素的集合中,一个元素与另一个元素在 同一行,并且与第三个元素在 同一列,则该集合是一个 直角三角形。3 个元素 不必 彼此相邻。 请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目,且满足 3 个元素值 都 为 1
题目描述 给你两个长度相同的字符串 s 和 t,以及两个整数数组 nextCost 和 previousCost。 一次操作中,你可以选择 s 中的一个下标 i,执行以下操作之一: 将 s[i] 切换为字母表中的下一个字母,如果 s[i] == 'z' ,切换后得到 'a' 。操作的代价为 nextCost[j] ,
题目描述 给你一个整数数组 nums。该数组包含 n 个元素,其中 恰好 有 n - 2 个元素是 特殊数字。剩下的 两个 元素中,一个是所有 特殊数字 的 和,另一个是 异常值。 异常值 的定义是:既不是原始特殊数字之一,也不是表示元素和的那个数。 注意,特殊数字、和 以及 异常值 的下标必须 不同,但可以共享 相同
题目描述 给定一个二维整数数组 points,其中 points[i] = [x_i, y_i] 表示平面上的一个点。任意挑选四个不同的点,若能够构成至少一对水平边(平行 x 轴)的凸四边形,则称其为 水平梯形。请返回可以组成的水平梯形数量,对 1_000_000_007 取模。 思路 要形成水平梯形,至少需要两个不同
题目描述 给你两个整数数组 prices 和 strategy,其中: prices[i] 表示第 i 天某股票的价格。 strategy[i] 表示第 i 天的交易策略: -1 表示买入一单位股票 0 表示持有股票 1 表示卖出一单位股票 同时给你一个偶数整数 k,你可以对 strategy 进行最多一次修
题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 知识边界 这道题的核心是前缀最大值与后缀最大值。 对于任意位置 i,它最终能接的雨水高度,取决于: 左边最高的柱子 右边最高的柱子 只有左右两侧都足够高,当前位置才能存水。并且水位由两侧较矮的那一边决定,因
题目描述 给你一个大小为 m x n 的矩阵 mat ,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。 知识边界 对角线坐标特性:在二维矩阵中,同一条对角线(右上到左下方向)上的元素的行列坐标索引之和 i + j 是一个固定常数。 切片预分配:在 Go 语言中,通过 make([]int, 0, m*n)
哎呀,IPO 听着很唬人,其实咱只要盯住“当前能做里最赚钱的”就行啦。 题目描述 咱来翻译下题面:现在有 n 个项目,每个项目都有两个信息:完成后能获得的纯利润 profits[i],以及启动它之前必须拥有的最小资本 capital[i]。 一开始手里有资本 w,最多可以做 k 个不同项目。每做完一个项目
题目描述 给你一个整数数组 nums 和一个整数 k,判断是否存在一个长度至少为 2 的连续子数组,使得该子数组元素和是 k 的倍数。 等价地说,是否存在下标区间 [l, r](r - l + 1 >= 2),满足: (nums[l] + nums[l+1] + ... + nums[r]) % k == 0 如果
题目描述 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组是数组中的一个连续部分。 知识边界 这道题主要涉及数组遍历、前缀和和最值维护。 1. 数组与切片 在 Go 中,这类题通常使用切片 []int 表示整数序列。 例如: nums := []int{
题目描述 给你一个二叉搜索树的根节点 root,返回树中任意两不同节点值之间的最小差值。 思路 BST 的中序遍历结果是严格递增序列,相邻节点之差一定是所有节点对中最小的,因此只需要在中序遍历过程中比较当前节点与前一个节点的差值即可。 用 prenode 记录上一个访问节点的值,初始化为 math.MinInt / 2
题目描述 给定一个区间数组 intervals,其中 intervals[i] = [starti, endi] 表示一个闭区间。 需要把所有有重叠部分的区间合并起来,最终返回一个互不重叠、并且恰好覆盖原始所有区间的结果数组。 知识边界 排序后线性合并 这题的关键不在于暴力比较每一对区间,而是先按左端点排序。排完序之后
题目描述 给定一个非空二叉树的根节点 root,以数组的形式返回每一层节点的平均值。 思路 用 BFS 层序遍历,每次处理完整的一层。记录当前层的节点数 queueSize,遍历该层时累加所有节点值到 sum,最后将 sum / queueSize 追加到结果中。 每处理一个节点,把它的左、右子节点依次加入队列,保证下
题目描述 给定一个单词数组 words 和整数 maxWidth,需要把单词排成多行文本,并满足: 每行长度恰好为 maxWidth 除最后一行外,左右两端对齐 单词间空格尽量均匀分配;如果不能均分,左侧间隙比右侧多 最后一行左对齐,单词间只放一个空格,末尾补空格 知识边界 这题本质是贪心 + 字符串模拟。 核心思
题目描述 给定一个 Unix 风格的绝对路径 path,要求把它转换成规范路径。 规范路径需要满足:以 / 开头,目录之间只有一个 /,末尾不能带多余的 /,并且结果中不能保留 . 或 .. 这样的特殊目录标记。 思路 这道题也适合用栈来做,因为路径的处理过程本质上就是“进入一个目录”和“回到上一级目录”。 先用 st
题目描述 给你一个已经按升序排好的链表 head,要求把所有出现过重复的数字对应节点全部删除,只保留那些只出现一次的节点。 最后返回的链表仍然需要保持有序,所以关键在于识别“某个值是否重复出现”,并把这一整段重复值全部跳过去,而不是只删除其中一个节点。 思路 这份代码先创建了一个哑节点 dummy,让它指向原链表头部,
题目描述 给定一个由小写字母组成的字符串 s,以及一个同长度整数数组 shifts。 对于每个 shifts[i] = x,将 s 的前 i+1 个字符整体向后移位 x 次(字母表循环,z -> a)。 求应用全部移位操作后的最终字符串。 知识边界 这题的核心是前缀影响的反向累加(也可理解为后缀和思路): shift
题目描述 给你一个单链表的头节点 head,以及两个整数 left 和 right,其中 left <= right。 要求只反转链表中第 left 个位置到第 right 个位置之间的节点,其他部分保持原有顺序,最后返回新的链表头节点。 思路 这份代码先创建了一个哑节点 dummy,并让它指向原链表头部。这样做的好处
题目描述 给你一个二叉树的根节点 root,判断其是否是一个有效的二叉搜索树。 有效 BST 要求:左子树所有节点严格小于当前节点,右子树所有节点严格大于当前节点,且所有子树也满足此性质。 思路 BST 的中序遍历结果是严格递增序列,因此只需对树做中序遍历,同时用 pre 记录上一个访问节点的值,若当前节点值 ≤ pr
题目描述 设计一个算法,找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。 思路 仍然是经典的两数之和,不过我们需要把满足条件的所有数对都枚举出来。遍历数组时: 用哈希表 cnt 统计左侧每个数字尚能匹配的次数; 枚举当前数字 x 时,先看 need = target - x 是否仍有可用配对; 若可用
题目描述 请你设计一个数据结构,支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配。 实现词典类 WordDictionary: WordDictionary() 初始化词典对象。 void addWord(word) 将 word 添加到数据结构中,之后可以对它进行匹配。 bool search(wor
题目描述 给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words,返回所有二维网格上的单词。 单词必须按照字母顺序,通过 相邻的单元格 内的字母构成,其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。 思路 困难题?别怕别怕,
题目描述 咱来翻译下题面:给定两个正整数数组 arr1 和 arr2,要从 arr1 中选一个数 x,从 arr2 中选一个数 y,看它们从最左边开始能匹配多少位数字。 一个整数的前缀必须从第一位开始连续取,比如 123 是 12345 的前缀,但 234 不是。现在要在所有 (x, y) 数对里,找出最长公共前缀的长
题目描述 给你二叉树的根节点 root,返回其节点值的层序遍历结果,即逐层从左到右访问所有节点,每一层的节点值放在一个子数组中。 思路 BFS 层序遍历的经典模板。用队列维护当前层的所有节点,每次循环开始时记录 queueSize,表示当前层的节点数,然后只处理这么多个节点,处理完一层后 height 自增,进入下一层
题目描述 给你二叉树的根节点 root,返回其节点值的锯齿形层序遍历结果。即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行。 思路 在 102 题层序遍历的基础上加一个方向判断。用 height 记录当前层数(从 0 开始),偶数层从左往右正常追加,奇数层从右往左,只需在每层处理完后判断 heigh
题目描述 给定一个整数数组 nums,元素已经按升序排列。要求把它转换成一棵 平衡 二叉搜索树(任意节点左右子树高度差不超过 1)。 由于答案不唯一,只要满足 BST 性质并且高度平衡即可。 思路 升序数组其实就是 BST 的中序遍历结果。这就好办啦——既然中序遍历能唯一还原中序顺序,那么任意挑一个元素当根、左半边递归
题目描述 字典 wordList 中从单词 beginWord 到 endWord 的转换序列是一个序列 beginWord -> s1 -> s2 -> ... -> sk,其中: 每一对相邻单词只差一个字母 对于 1 <= i <= k,每个 si 都在 wordList 中(注意 beginWord 不必在 w
题目描述 给你一个 m x n 的矩阵 board,由 'X' 和 'O' 组成。将所有被 'X' 完全包围的 'O' 区域替换为 'X'。与棋盘边缘相连的 'O' 不算被围绕,不需要替换。 思路 正面找"被围绕的区域"不好判断,反过来找"安全的 'O'"更直接——只要一个 'O' 与边缘的 'O' 相连,它就一定不会
题目描述 给你无向连通图中一个节点的引用,返回该图的深拷贝。每个节点包含一个整数值 val 和邻居列表 Neighbors。 思路 深拷贝图的难点在于图可能有环——如果不加记录地递归,会无限循环。用一个 visited 哈希表把"原节点 → 克隆节点"的映射存起来,就能同时解决两个问题:避免重复访问,以及在处理邻居时直
题目描述 给定一个只包含数字 2-9 的字符串 digits,要求返回它能够表示的所有字母组合。数字和字母的对应关系与电话九宫格按键一致,其中 1 不对应任何字母。 如果输入为空字符串,就没有可以组合的内容,直接返回空数组。 思路 这题是很典型的回溯题:每个数字对应一组候选字母,我们要从每一组里选一个字母,按顺序拼成长
题目描述 给你一个由 '1'(陆地)和 '0'(水)组成的二维网格,计算网格中岛屿的数量。岛屿被水包围,只能由水平或竖直方向相邻的陆地连接而成,网格四条边均视为水域。 思路 遍历整个网格,遇到 '1' 就说明找到了一座新的岛屿,答案加一,同时对这个格子发起 DFS,把它所能连通的所有陆地格子都标记为 '2'("插旗")
题目描述 共有 numCourses 门课程(编号 0 到 numCourses - 1),部分课程有先修要求:prerequisites[i] = [ai, bi] 表示学 ai 之前必须先学 bi。判断是否能完成所有课程的学习。 思路 把课程之间的先修关系建成有向图:bi → ai 表示 bi 是 ai 的前置。问
题目描述 现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites,其中 prerequisites[i] = [ai, bi] 表示在选修课程 ai 前必须先选修 bi。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,只要返回
题目描述 给定一个整数 n,表示需要生成 n 对括号。要求返回所有可能的、并且有效的括号组合。 有效括号组合需要满足:任意位置之前的右括号数量不能超过左括号数量,并且最终左右括号数量都等于 n。 括号一多就容易盯着屏幕发愣,所以先抓住“前缀合法”这张照片~ 思路 这题可以把生成过程看成一棵回溯搜索树:每一
题目描述 给定一组等式 equations[i] = [Ai, Bi] 和对应的值 values[i],表示 Ai / Bi = values[i]。再给定一组查询 queries[j] = [Cj, Dj],求每个 Cj / Dj 的值。若无法确定或变量未定义,返回 -1.0。 思路 把每个变量看作图中的节点,每个等
题目描述 基因序列由 8 个字符组成,每个字符是 'A'、'C'、'G'、'T' 之一。一次基因变化指序列中恰好一个字符发生变化,且变化后的序列必须出现在基因库 bank 中。 给你起点 startGene、终点 endGene 和基因库 bank,求从 startGene 变到 endGene 所需的最少变化次数;不
题目描述 给定一个不含重复数字的数组 nums,要求返回它的所有可能全排列。答案可以按任意顺序返回。 全排列要求每个数字都使用一次,并且不同顺序算作不同结果。 思路 这题可以把排列看成“给每个位置选一个数”。path[i] 表示排列中第 i 个位置放什么数字,所以回溯函数 dfs(i) 就是在决定第 i 个位置要填 n
题目描述 哎呀,咱来翻译下题面~给你两个用字符串表示的二进制数 a 和 b,返回它们相加之后、同样用二进制字符串表示的结果。 输入只含 '0' 和 '1',而且除了 "0" 本身之外,开头不会有多余的前导零。 思路 咱第一眼看,这题别被"二进制"三个字唬住——它本质就是小学的竖式加法,只不过逢二进一而已。 既然是竖式,
题目描述 给定两个整数 n 和 k,要求从范围 [1, n] 中选出所有可能的 k 个数的组合。答案可以按任意顺序返回。 组合只关心选了哪些数,不关心选择顺序,所以 [1, 2] 和 [2, 1] 属于同一种组合。 思路 这题也是标准回溯题,不过重点不是“能不能选”,而是“怎样避免重复组合”。嘿嘿,如果把每个数字都当成
题目描述 给定一个 m x n 的二维字符网格 board 和一个字符串 word,判断 word 是否存在于网格中。 单词需要按顺序由相邻单元格中的字符组成,相邻只包含水平和垂直方向。同一个单元格在同一次搜索路径中不能被重复使用。 思路 这题可以把每个格子都当作单词的起点,然后从这个起点开始做深度优先搜索。递归函数
题目描述 哎呀,这题挺亲切的——给你一个整数 x,要是它正着读和倒着读一模一样,就返回 true,否则返回 false。比如 121 正反都是 121,是回文;123 倒过来成了 321,就不是啦。 思路 咱第一眼看,最直白的办法就是:把这个数整个倒过来,再跟原数比一比,相等就是回文。本姑娘这版走的就是这条路——纯数学
题目描述 给一个 n x n 的棋盘,格子按"转行交替"方式从 1 到 n² 编号,从左下角开始,奇数行从左往右、偶数行从右往左(从底部数)。每次掷骰子可以前进 1 到 6 格,落点若有蛇或梯子则强制跳转(只跳一次)。求从格子 1 到格子 n² 所需的最少掷骰次数,不可达则返回 -1。 思路 本题是无权图上的最短路径,
题目描述 给定一个链表的头节点 head,要求把链表按照 升序 排列,并返回排序后的新头节点。 进阶要求是时间复杂度 O(n log n),并且尽量使用常数级额外空间。 思路 链表不像数组能随机访问下标,所以适合数组的快排在链表上写起来不优雅。这里用 归并排序:分治三步走——把链表对半切,分别递归排序两半,再把两条有序
题目描述 欸,这题模拟的是咱小学列竖式的场景——给你一个数组 digits,从左到右按最高位到最低位存着一个大整数的每一位(没有前导 0)。咱要给这个大整数 加 1,再把结果按同样的格式返回成数组。 思路 咱第一眼看,这就是"末位加一 + 处理进位"的活儿。既然加的是 1,那咱只需要从最低位(数组末尾)开始往前扫,模拟
题目描述 给你一个 n * n 矩阵 grid,矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid,并返回根节点。 四叉树每个节点有两个属性: val:叶子节点所代表区域的值(1 对应 True,0 对应 False);非叶子节点的 val 任意。 isLeaf:当前节点是叶子时为 True,否则为 Fa
写在前面 哎呀,你来得正好——咱今天还没拉着人聊 BFS 呢~ 事情是这样的:刷到 433 最小基因变化 那天,咱盯着屏幕足足愣了半分钟。 "这题怎么看着这么眼熟……本姑娘是不是又在重新发明轮子?" 没错没错,又一次。岛屿数量、蛇
题目描述 给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。 思路 K 条链表一起排队?咱用分治抢先一步~ 最最直觉的写法是:拿第 1 条和第 2 条 merge,再拿结果跟第 3 条 merge……一路串糖葫芦下来。可这么干每多合并一条就要把已合好的长链表
题目描述 哎呀,这题别被名字唬住——给你两个整数 left 和 right,表示一个区间 [left, right](两端都算)。咱要返回的,是把这个区间里每一个整数全部 按位与 起来的结果。 举个例子,[5, 7] 就是 5 & 6 & 7。数字一多,挨个去与显然不现实,得找点规律。 思路 咱第一眼看,按位与有个很"
题目描述 给定一个整数数组 nums 和一个正整数 threshold,需要选择一个正整数作为除数 d。将数组中的每个元素都除以 d 并向上取整,再把这些结果求和。请你找到所有能让最终和不超过 threshold 的除数中,最小 的那个。 题目保证一定存在合法解。 思路 这是一道二分答案 “花费一个 log 的时间,
题目描述 给你两个整数数组 arr1 , arr2 和一个整数 d ,请你返回两个数组之间的 距离值 。 「距离值」 定义为符合此距离要求的元素数目:对于元素 arr1[i] ,不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。 思路 返回值规则 Arrays.binarySearc
题目描述 给定一个原本按升序排列、且元素互不相同的数组 nums。数组经过若干次旋转后,顺序可能变成类似 [4,5,6,7,0,1,2] 这样的样子。 现在需要找出并返回数组中的最小元素,并且要求时间复杂度为 O(log n)。哎呀,旋转数组又来啦,这次咱不找某个目标值,而是找那个“断开后重新开始”的最小点~
题目描述 给定一个整数数组 arr,需要支持以下操作: public int query(int left,int right,int value) 返回在区间 [left, right] 中,元素值等于 value 的个数。 同时需要多次查询,要求高效。 示例: arr = [1,3,1,2,3] query(0,
题目描述 给定一个整数数组 candies,其中 candies[i] 表示第 i 堆糖果的数量。你可以把每一堆糖果拆成任意数量的子堆,但不能将两堆重新合并。现在要给 k 个小孩分糖,要求每个小孩分到的糖果数量完全相同,且每个小孩至多拿走一堆。请问每个小孩最多能拿到多少糖果? 思路 依旧是“二分答案”的典型场景:我们关
题目描述 给定一个spell和potion,长度分别为n和m 有一个success,需要做到咒语和药水的能量强度相乘大于success 请你返回一个长度为 n 的整数数组 pairs,其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。 思路 先对potion进行排序,然后使用二分算法 当循环结束时,l
题目描述 给定二维数组 points,其中 points[i] = [x_i, y_i] 表示第 i 个点的坐标;再给定字符串 s,s[i] 表示第 i 个点的标签。若一个以原点为中心、边与坐标轴平行的正方形内不存在标签相同的两点(边上视为在内),则称其为合法正方形。请返回合法正方形内最多可以容纳的点数。正方形的边长允
题目描述 给定一个原本升序排列、且元素互不相同的整数数组 nums。数组在某个未知下标处发生了旋转,例如 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2]。 现在需要在旋转后的数组里查找 target。如果存在,就返回它的下标;如果不存在,就返回 -1。题目要求时间复杂度为 O(log n),所
题目描述 给定一个按非递减顺序排列的整数数组 nums,以及一个目标值 target。需要找出 target 在数组中第一次出现的位置和最后一次出现的位置。 如果数组中不存在 target,返回 [-1, -1]。题目要求时间复杂度为 O(log n),所以不能慢慢扫一遍啦,拜托,边界问题当然要交给二分查找嘛~
题目描述 给定一个已经按升序排列的数组 nums 和一个目标值 target,需要在数组中找到 target 的下标。 如果 target 不存在,就返回它按顺序插入时应该在的位置。题目要求时间复杂度必须是 O(log n),所以不能从头扫到尾啦,拜托,二分查找该出场了嘛~ 嘿嘿,排序数组已经排好队啦,咱只
题目描述 给定两个分别已经升序排好的数组 nums1 和 nums2,长度分别为 m 和 n,要找出这两个数组合在一起之后的中位数。题目对时间复杂度卡得很死,要求 O(log(m+n)),所以"合并再排序"的偷懒解法直接被毙掉啦——只能上二分。 两个数组都是排好序的,可中位数偏偏要"合并视角"才能看到,咱得
题目描述 给定一个 m x n 的整数矩阵 matrix,它满足两个条件: 每一行从左到右按非严格递增顺序排列。 每一行的第一个数都大于上一行的最后一个数。 现在要判断 target 是否存在于矩阵中。如果存在,返回 true;否则返回 false。嘿嘿,这个矩阵看起来是二维的,其实从整体顺序看,就像一条被折成好多
二分算法 当 while (left <= right) 退出时,必然满足: right + 1 == left 所以: right 是最后一个 不满足 条件的下标 left 是第一个 满足 条件的下标 “找第一个 ≥ target” 的场景里,结果应返回 left(即成功区间的起点)。 | 名称
遇到大根堆和小根堆的吟唱 container/heap 只提供算法,堆的「大小」由 Less 方法决定: Less(i, j) 返回 h[i] < h[j] → 小根堆(堆顶最小) Less(i, j) 返回 h[i] > h[j] → 大根堆(堆顶最大) 小根堆 sort.IntSlice 自带的 Less 就是
建立next数组 初始化 前后缀不相同 前后缀相同 next func buildNext(pattern string) []int { next := make([]int, len(pattern)) j := 0 for i := 1; i < len(pattern); i++ { for j
题目描述 欸,这题听着就带感——颠倒给定的 32 位整数的二进制位。也就是说,把这个数当成一串 32 位的 0/1,然后整串首尾翻转:原来的第 0 位变成第 31 位,第 1 位变成第 30 位,以此类推,再把翻转后的二进制读成一个新数返回。 思路 咱第一眼看,这题的关键词是"逐位搬运"。既然要把低位翻到高位,那就一位
题目描述 哎呀,这题名字怪可爱的——"位 1 的个数"。给你一个正整数 n,把它写成二进制后,数一数里头有多少个 1,返回这个数量就行。这个值还有个学名叫汉明重量(Hamming Weight)。 思路 咱第一眼看,这题就是"逐位检查"的活儿:把 n 的二进制位一个个看过去,是 1 就记一笔。 每一轮干两件事: n
题目描述 哎呀,这题听着就有点绕——给你一个整数数组 nums,里头除了某一个元素只出现 一次,其余每个元素都恰好出现 三次。咱要做的,就是把那个落单的家伙找出来返回。 而且题目还提了俩硬条件:时间得是 线性 的、空间只能用 常数级。也就是说,拿哈希表数次数那种 $O(n)$ 空间的偷懒办法,这回行不通哦。 思路 咱第