【综合笔试题】难度 3/5,一道考察三个知识点的综合笔试题 ... |刷题打卡

简介: 【综合笔试题】难度 3/5,一道考察三个知识点的综合笔试题 ... |刷题打卡

题目描述



这是 LeetCode 上的1208. 尽可能使字符串相等,难度为 Medium。


给你两个长度相同的字符串:s 和 t。


将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。


用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。


如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。


如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。


示例 1:


输入:s = "abcd", t = "bcdf", cost = 3
输出:3
解释:s 中的 "abc" 可以变为 "bcd"。
开销为 3,所以最大长度为 3。
复制代码


示例 2:


输入:s = "abcd", t = "cdef", cost = 3
输出:1
解释:s 中的任一字符要想变成 t 中对应的字符,其开销都是 2。
因此,最大长度为 1。
复制代码


示例 3:


输入:s = "abcd", t = "acde", cost = 0
输出:1
解释:你无法作出任何改动,所以最大长度为 1。
复制代码


提示:


  • 1 <= s.length, t.length <= 10510^5105
  • 0 <= maxCost <= 10610^6106
  • s 和 t 都只含小写英文字母。


前缀和 + 二分 + 滑动窗口



给定了长度相同的 st,那么对于每一位而言,修改的成本都是相互独立而确定的。


我们可以先预处理出修改成本的前缀和数组 sum


当有了前缀和数组之后,对于任意区间 [i,j][i,j][i,j] 的修改成本,便可以通过 sum[j]−sum[i−1]sum[j] - sum[i - 1]sum[j]sum[i1] 得出。


那么接下来我们只需要找出成本不超过 maxCost 的最大长度区间,这个长度区间其实就是滑动窗口长度,滑动窗口长度的范围为 [1,n][1,n][1,n] (nnn 为字符串的长度)。


通过枚举来找答案可以吗?


我们可以通过数据范围大概分析一下哈,共有 nnn 个滑动窗口长度要枚举,复杂度为 O(n)O(n)O(n),对于每个滑动窗口长度,需要对整个前缀和数组进行滑动检查,复杂度为 O(n)O(n)O(n)。也就是整体复杂度是 O(n2)O(n^2)O(n2) 的。


数据范围是 10510^5105,那么单个样本的计算量是 101010^{10}1010,计算机单秒肯定算不完,会超时 ~


PS. 如果你对此分析方法比较陌生,可以去瞧一眼 4. 寻找两个正序数组的中位数(困难) 的总结部分 ~


因此我们直接放弃通过枚举的朴素做法。


那么如何优化呢?其实有了对于朴素解法的分析之后,无非就是两个优化方向:


  1. 优化第一个 O(n)O(n)O(n):减少需要枚举的滑动窗口长度
  2. 优化第二个 O(n)O(n)O(n):实现不完全滑动前缀和数组,也能确定滑动窗口长度是否合法


事实上第 2 点是无法实现的,我们只能「减少需要枚举的滑动窗口长度」。


一个 O(n)O(n)O(n) 的操作往下优化,通常就是优化成 O(log⁡n)O(\log{n})O(logn)O(log⁡n)O(\log{n})O(logn) 基本上我们可以先猜一个「二分」查找。


然后我们再来分析是否可以二分:假设我们有满足要求的长度 ans,那么在以 ans 为分割点的数轴上(数轴的范围是滑动窗口长度的范围:[1,n][1, n][1,n]):


  1. 所有满足 <= ans 的点的修改成本必然满足 <= maxCost
  2. 所有满足 > ans 的点的修改成本必然满足 > maxCost (否则 ans 就不会是答案)


因此 ans 在数轴 [1,n][1, n][1,n] 上具有二段性,我们可以使用「二分」找 ans


得证「二分」的合理性。


PS. 三叶一直强调二分的本质是二段性,而非单调性。33. 搜索旋转排序数组(中等) 是一个很好的例子


编码细节:


  1. 为了方便的预处理前缀和和减少边界处理,我会往字符串头部添加一个空格,使之后的数组下标从 1 开始
  2. 二分出来滑动窗口长度,需要在返回时再次检查,因为可能没有符合条件的有效滑动窗口长度


代码:


class Solution {
    public int equalSubstring(String ss, String tt, int max) {
        int n = ss.length();
        ss = " " + ss;
        tt = " " + tt;
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + Math.abs(s[i] - t[i]);
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(sum, mid, max)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return check(sum, r, max) ? r : 0;
    }
    boolean check(int[] nums, int mid, int max) {
        for (int i = mid; i < nums.length; i++) {
            int tot = nums[i] - nums[i - mid];
            if (tot <= max) return true;
        }
        return false;
    }
}
复制代码


  • 时间复杂度:预处理出前缀和的复杂度为 O(n)O(n)O(n);二分出「滑动窗口长度」的复杂度为 O(log⁡n)O(\log{n})O(logn),对于每个窗口长度,需要扫描一遍数组进行检查,复杂度为 O(n)O(n)O(n),因此二分的复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)。整体复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)
  • 空间复杂度:使用了前缀和数组。复杂度为 O(n)O(n)O(n)


相关阅读



二分的本质与模板代码:


29. 两数相除(中等)


33. 搜索旋转排序数组(中等)


复杂度/计算量推算是否超时分析:


4. 寻找两个正序数组的中位数


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1208 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:

github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
9天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
404 130
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
3天前
|
存储 安全 前端开发
如何将加密和解密函数应用到实际项目中?
如何将加密和解密函数应用到实际项目中?
197 138
|
9天前
|
人工智能 Java API
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
本文介绍AI大模型的核心概念、分类及开发者学习路径,重点讲解如何选择与接入大模型。项目基于Spring Boot,使用阿里云灵积模型(Qwen-Plus),对比SDK、HTTP、Spring AI和LangChain4j四种接入方式,助力开发者高效构建AI应用。
377 122
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
|
3天前
|
存储 JSON 安全
加密和解密函数的具体实现代码
加密和解密函数的具体实现代码
196 136
|
21天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1349 8
|
8天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
20天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1460 87