【笔记】语言实例比较 3. 无重复字符的最长子串 C++ Rust Java Python
语言实例比较 3. 无重复字符的最长子串 C++ Rust Java Python
C++
C++: 9ms O ( N 2 ) O(N^2) O(N2), 8.68MB mem O ( 1 ) O(1) O(1)
滑动窗口循环
class Solution
{
public:int lengthOfLongestSubstring(const string s) {//s[start,end) 前面包含 后面不包含int res(0);for (int start(0), end(0); end < s.size(); ++end) {for (int i = start; i < end; ++i)if (s[end] == s[i]) {start = i + 1;break;}res = max(res, end - start + 1);}return res;}
};
滑动窗口动态规划哈希表:12ms O ( N ) O(N) O(N), mem 10.88MB O ( N ) O(N) O(N)
窗口左右指针索引
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> last_pos_dic;int i = 0, res = 0, len = s.size();for(int j = 0; j < len; j++) {auto p = last_pos_dic.find(s[j]);if (p != last_pos_dic.end())i = max(i, p->second + 1); // 更新左指针last_pos_dic[s[j]] = j; // 哈希表记录res = max(res, j - i + 1); // 更新结果}return res;}
};
滑动窗口动态规划哈希表:14ms
仅保存窗口右指针和size
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> hash;int result = 0;for (int i = 0, window_size = 0; i < s.size(); ++i) {int last_pos = hash.find(s[i]) == hash.end() ? -1 : hash.find(s[i])->second; //获取索引hash[s[i]] = i;window_size = window_size < i - last_pos ? window_size + 1 : i - last_pos; //发现重复就挪新窗口result = max(window_size, result);}return result;}
};//https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/2361797/3-wu-zhong-fu-zi-fu-de-zui-chang-zi-chua-26i5/
Rust
impl Solution {pub fn length_of_longest_substring(s: String) -> i32 {let chars = s.as_bytes();let mut ans = 0;let mut left = 0;let mut window = vec![false; 128]; // 也可以用 HashSet,这里为了效率用的 Vecfor (right, &c) in chars.iter().enumerate() {let c = c as usize;while window[c] { // 加入 c 后,窗口内会有重复元素window[s[left] as usize] = false;left += 1;}window[c] = true;ans = ans.max(right - left + 1); // 更新窗口长度最大值}ans as i32}
}
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
Java
time O ( N ) O(N) O(N) mem O ( N ) O(N) O(N)
class Solution {public int lengthOfLongestSubstring(String s) {char[] chars = s.toCharArray(); // 转换成 char[] 加快效率(忽略带来的空间消耗)int n = chars.length, ans = 0, left = 0;boolean[] has = new boolean[128]; // 也可以用 HashSet<Character>,这里为了效率用的数组for (int right = 0; right < n; ++right) {char c = s[right];while (has[c]) // 加入 c 后,窗口内会有重复元素has[s[left++]] = false;has[c] = true;ans = Math.max(ans, right - left + 1); // 更新窗口长度最大值}return ans;}
}链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
Go
time O ( N ) O(N) O(N) mem O ( N ) O(N) O(N)
func lengthOfLongestSubstring(s string) (ans int) {window := [128]bool{} // 也可以用 map,这里为了效率用的数组left := 0for right, c := range s {for window[c] { // 加入 c 后,窗口内会有重复元素window[s[left]] = falseleft++}window[c] = trueans = max(ans, right-left+1) // 更新窗口长度最大值}return
}func max(a, b int) int { if b > a { return b }; return a }链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
相关文章:
【笔记】语言实例比较 3. 无重复字符的最长子串 C++ Rust Java Python
语言实例比较 3. 无重复字符的最长子串 C Rust Java Python C C: 9ms O ( N 2 ) O(N^2) O(N2), 8.68MB mem O ( 1 ) O(1) O(1) 滑动窗口循环 class Solution { public:int lengthOfLongestSubstring(const string s) {//s[start,end) 前面包含 后面不包含int res(0);for (…...
int的大小你知道时4个字节,那么类的大小你知道怎么计算吗?
文章目录 1、如何计算类对象的大小2、类对象的存储方式猜测3、结构体内存对齐规则1、如何计算类对象的大小 class A { public: void PrintA() { cout<<_a<<endl; } private: char _a; };问题: 类中既可以有成员变量,又可以有成员函数,那么一个类的对象中包含了…...
OpenCV学习笔记(十一)——利用Sobel算子计算梯度
Sobel算子是基于一阶导数的离散差分算子,其中Sobel对于像素值的变化是十分敏感的,在进行边缘检测的时候,Sobel算子常用于对周围像素的重要性进行检测。 Sobel算子包括检验水平方向的算子和检测竖直方向的算子 计算机梯度值的操作如下&#x…...
扩展一下BenchmarkSQL,新增支持ASE/HANA/DB2/SQLServer,可以随便用了
1 背景 提到数据库的性能,自然就避不开性能测试。有专用于测试OLTP的,也有偏重于OLAP的。本文介绍的BenchmarkSQL就属于测试OLTP中的一个,基于TPCC的。网上有很多介绍TPC*的相关测试的文章,大家可以自行脑补。而PostgreSQL自带的pgbench是属于TPCC的前一个基准测试程序,偏…...
Android 静默安装成功后自启动
近期开发上线一个常驻app,项目已上线,今天随笔记录一下静默安装相关内容。我分三篇静默安装(root版)、静默安装(无障碍版)、监听系统更新、卸载、安装。 先说说我的项目需求:要求app一直运行&am…...
计算机二级真题讲解每日一题:《format格式化》
描述 在右侧答题模板中修改代码,删除代码中的横线,填写代码,完成如下功能。 接收用户输入的一个小于 20的正整数,在屏幕上逐行递增显示从 01 到该正整数,数字显示的宽度为 2,不足位置补 0,后面追…...
RabbitMQ问题
如何实现顺序消费? 消息放入到同一个队列中消费 如何解决消息不丢失? 方案: 如上图:消息丢失有三种情况,解决了以上三种情况就解决了丢失的问题 1、丢失1--->消息在到达交换机的时候;解决࿱…...
flutter->Scaffold左侧/右侧侧边栏和UserAccountsDrawerHeader的使用
//appBar的 leading/actions 和 Scaffold的drawer/endDrawer 冲突只能存在一个 import package:flutter/material.dart;void main() {runApp(MyApp()); }class MyApp extends StatelessWidget {const MyApp({super.key});overrideWidget build(BuildContext context) {retur…...
vulnhub prime1通关
目录 环境安装 1.信息收集 收集IP 端口扫描 目录扫描 目录文件扫描 查找参数 打Boss 远程文件读取 木马文件写入 权限提升 方法一 解锁密钥 方法二: linux内核漏洞提权 总结 环境安装 Kali2021.4及其prime靶机 靶机安装:Prime: 1 ~ Vul…...
JVM快速入门(1)JVM体系结构、运行时数据区、类加载器、线程共享和独享、分区、Java对象实例化
5.1 JVM体系结构 线程独占区-程序计数器(Program Counter Register) 程序计数器是一块较小的内存空间,它可以看做是当前线程所执行的字节码的行号指示器;在虚拟机的概念模型里,字节码解释器工作时就是通过改变这个计数…...
CSS3新属性(学习笔记)
一、. 圆角 border-radius:; 可以取1-4个值(规则同margin) 可以取px和% 一般用像素,画圆的时候用百分比:border-radius:50%; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8&q…...
41-Vue-webpack基础
webpack基础 前言什么是webpackwebpack的基本使用指定webpack的entry和output 前言 本篇开始来学习下webpack的使用 什么是webpack webpack: 是前端项目工程化的具体解决方案。 主要功能:它提供了友好的前端模块化开发支持,以及代码压缩混淆、处理浏览…...
数据仓库的分层理论
数据仓库的分层理论是为了更好地组织和管理数据,支持复杂的数据分析和决策支持。在这一理论中,数据仓库被分为多个层次,每个层次都有其特定的作用和设计原则。以下是每一层的详细介绍,以及以销售人员为例的Doris建表实例。 ODS层…...
MySQL 8.0-索引- 不可见索引(invisible indexes)
概述 MySQL 8.0引入了不可见索引(invisible index),这个在实际工作用还是用的到的,我觉得可以了解下。 在介绍不可见索引之前,我先来看下invisible index是个什么或者定义。 我们依然使用拆开来看,然后再把拆出来的词放到MySQL…...
Uibot6.0 (RPA财务机器人师资培训第3天 )财务招聘信息抓取机器人案例实战
训练网站:泓江科技 (lessonplan.cn)https://laiye.lessonplan.cn/list/ec0f5080-e1de-11ee-a1d8-3f479df4d981https://laiye.lessonplan.cn/list/ec0f5080-e1de-11ee-a1d8-3f479df4d981https://laiye.lessonplan.cn/list/ec0f5080-e1de-11ee-a1d8-3f479df4d981(本博…...
Eureka和Nacos的关系
目录 它们的比较: 结论: Eureka和Nacos都是服务发现和注册中心,它们在微服务架构中扮演着关键角色,但它们是由不同的组织开发的,服务于类似但不完全相同的目的。以下是它们之间的关系: Eureka:…...
极简自建web视频会议,私有云,rtmp/rtsp/webrtc一键参会直播会议互动方案
随着视频互动深入工作日常,很多客户需要自建一个会议,监控的交互平台,目前外面不管是开源还是非开源的平台,都是极为复杂,一般linux安装库关联部署复杂,非技术人员根本没办法使用,不方便集成部署…...
5G智能网关助力工业铸造设备监测升级
随着物联网技术的迅猛发展和工业4.0浪潮的推进,传统工业正面临着严峻的转型升级压力。在这一背景下,铸造行业——这一典型的传统重工业领域,也必须积极探索借助5G、物联网、边缘计算等技术提升生产经营效率的新路径。 本文就基于佰马合作伙伴…...
奇舞周刊第523期:来自 rust 生态的强烈冲击?谈谈 Leptos 在语法设计上的精妙之处...
奇舞推荐 ■ ■ ■ 来自 rust 生态的强烈冲击?谈谈 Leptos 在语法设计上的精妙之处 过去很长一段时间,前端框架们都在往响应式的方向发展。同时又由于 React hooks 的深远影响,函数式 响应式成为了不少前端心中最理想的前端框架模样。Solid …...
《边缘计算:连接未来的智慧之桥》
随着物联网、5G等技术的快速发展,边缘计算作为一种新兴的计算模式,正逐渐引起人们的广泛关注。边缘计算通过将数据处理和存储功能放置在距离数据产生源头更近的位置,实现了更快速、更可靠的数据处理和交换,为各行各业带来了前所未…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
