力扣思维题——寻找重复数
题目链接:https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked

这题的思维难度较大。一种是利用双指针法进行计算环的起点,这种方法在面试里很难说清楚,也很难想到。大致做法就是,定义快慢指针,由于数字都是1-n,一共n+1个所以一定存在环。快慢指针一定会相遇,但是相遇的点并不是重复数字的点,所以再将fast放到起点,每次移动一格,再次和慢指针相遇的时候就是环的起点,两个指针每次都是一样快了。
class Solution {public int findDuplicate(int[] nums) {//快慢指针//所有的数字一定是1-n个一个还有一个重复的数字//环的入口就是重复的整数int slow = 0;int fast = 0;slow = nums[slow];fast = nums[nums[fast]];while(slow != fast){slow = nums[slow];fast = nums[nums[fast]];}int newslow = 0;while(newslow != slow){slow = nums[slow];newslow = nums[newslow];}return slow;}
}
另:二分查找法。推荐面试时候写这种,一来和面试官好解释,二来里面涉及常规算法能扯皮。
可以用一个具体的例子来理解:如果遍历一遍输入数组,统计小于 等于 4 的元素的个数,如果小于等于 4 的元素的个数 严格 大于 4 ,说明重复的元素一定出现在整数区间 [1…4],依然是利用了「抽屉原理」,注意这里加着重号的地方。
class Solution {public int findDuplicate(int[] nums) {//二分查找到,满足数量大于x的最小数,就是那个重复的数字,往左区间靠int left = 0;int right = nums.length-1;while(left<right){int mid = (left+right)/2;int count = 0;for(int i=0;i<nums.length;i++){if(nums[i]<=mid){count++; }}if(count>mid)right = mid;//mid==count说明,mid包括mid前面一定不存在重复的数字else left = mid+1;}return left;}
}
相关文章:
力扣思维题——寻找重复数
题目链接:https://leetcode.cn/problems/find-the-duplicate-number/description/?envTypestudy-plan-v2&envIdtop-100-liked 这题的思维难度较大。一种是利用双指针法进行计算环的起点,这种方法在面试里很难说清楚,也很难想到。大致做…...
基于Kubernetes的jenkins上线
1、基于helm 部署jenkins 要求:当前集群配置了storageClass,并已指定默认的storageClass,一般情况下,创建的storageClass即为默认类 指定默认storageClass的方式 # 如果是新创建默认类: apiVersion: storage.k8s.io/v1…...
每日一题——轮转数组
1. 题目描述 给定一个整数数组nums,将数组中的元素向右轮转k个位置,其中k是非负数。 示例1: 输入:nums [1,2,3,4,5,6,7],k 3 输出:[5,6,7,1,2,3,4] 解释: 向右轮转 1步:[7,1,2,3,4,5,6] 向右…...
Unity手机移动设备重力感应
Unity手机移动设备重力感应 一、引入二、介绍三、测试成果X Y轴Z轴横屏的手机,如下图竖屏的手机,如下图 一、引入 大家对重力感应应该都不陌生,之前玩过的王者荣耀的资源更新界面就是使用了重力感应的概念,根据手机的晃动来给实体…...
nodejs微信小程序+python+PHP基于推荐算法的电影推荐系统-计算机毕业设计推荐django
目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1 1.1背景及意义 1 1.2 国内外研究概况 1 1.3 研究的内容 1 第2章 相关技术 3 2.1 nodejs简介 4 2.2 express框架介绍 6 2.4 MySQL数据库 4 第3章 系统分析 5 3.1 需求分析 5 3.2 系统可行性分析 5 3.2.1技术可行性:…...
Linux 配置 swap 区
Linux 配置 swap 区 很多时候我们需要配置 swap 主要的原因是物理内存太贵了, 服务器也是一样, 当内存不够用时, 系统会卡死, 因此我们宁愿牺牲一点性能也要让系统正常运行。 当然, 在系统物理内存足够的条件下&#x…...
AG16KDDF256 User Manual
AGM AG16KDDF256 是由 AGM FPGA AG16K 与 DDR-SDRAM 叠封集成的芯片,具有 AG16K FPGA的可编程功能,提供更多可编程 IO,同时内部连接大容量 DDR-SDRAM。 FPGA 外部管脚 FBGA256 封装,管脚说明请见下表 Table-1: Tab…...
w15初识php基础
一、计算100之内的偶数之和 实现思路 所有的偶数除2都为0 代码实现 <?php # 记录100以内的偶数和 $number1; $num0; while($number<100){if($number%20){ $num$number;}$number1; } echo $num; ?>输出的结果 二、计算100之内的奇数之和 实现思路 所有的奇数除…...
powerbuilder Primary! Delete! Filter! 三个缓冲区的作用
Primary! 主缓存区,放正在使用的数据。 Delete! 删除缓存区,放将要删除但还没有提交到数据库的数据。 Filter! 筛选缓存区,放不符合筛选条件的数据。 最后在update的时候根据你的update设置生成相应的SQL语句。行的状态和所在的缓存区决定生…...
Confluent 与阿里云将携手拓展亚太市场,提供消息流平台服务
10 月 31 日,杭州云栖大会上,阿里云云原生应用平台负责人丁宇宣布,Confluent 成为阿里云技术合作伙伴,合作全新升级,一起拓展和服务亚太市场。 本次合作伙伴签约,阿里云与消息流开创领导者 Confluent 将进一…...
【一起学Rust | 框架篇 | Tauri2.0框架】Tauri2.0环境搭建与项目创建
文章目录 前言一、搭建 Tauri 2.0 开发环境二、创建 Tauri 2.0 项目1.创建项目2.安装依赖4. 编译运行 三、设置开发环境四、项目结构 前言 Tauri在Rust圈内成名已久,凭借Rust的可靠性,使用系统原生的Webview构建更小的App 以及开发人员可以灵活的使用各…...
算法基础之01背包问题
01背包问题 核心思想: 二维数组普通写法: #include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N 1010;int f[N][N]; //存 i个物品 容量不超过j 的总价值int v[N],w[N];int n,m;int main(){cin>>n>…...
Git的总体认知与具体实现
GIt概念 是一种分布式控制管理器 tips:敏捷开发 -> 先上线,后续开发再继续开发 集中式和分布式 集中式的版本控制系统每次在写代码时都需要从服务器中拉取一份下来,并且如果服务器丢失了,那么所有的就都丢失了,你本机客户端仅…...
Hadoop入门学习笔记——三、使用HDFS文件系统
视频课程地址:https://www.bilibili.com/video/BV1WY4y197g7 课程资料链接:https://pan.baidu.com/s/15KpnWeKpvExpKmOC8xjmtQ?pwd5ay8 Hadoop入门学习笔记(汇总) 目录 三、使用HDFS文件系统3.1. 使用命令操作HDFS文件系统3.1.…...
JavaWeb—html, css, javascript, dom,xml, tomcatservlet
文章目录 快捷键HTML**常用特殊字符替代:****标题****超链接标签****无序列表、有序列表****无序列表**:ul/li 基本语法**有序列表ol/li:****图像标签(img)**** 表格(table)标签****表格标签-跨行跨列表格****form(表单)标签介绍****表单form提交注意事项**div 标签p 标签sp…...
LangChain 31 模块复用Prompt templates 提示词模板
LangChain系列文章 LangChain 实现给动物取名字,LangChain 2模块化prompt template并用streamlit生成网站 实现给动物取名字LangChain 3使用Agent访问Wikipedia和llm-math计算狗的平均年龄LangChain 4用向量数据库Faiss存储,读取YouTube的视频文本搜索I…...
深入理解 Git 分支管理:提升团队协作与开发效率
目录 前言1 什么是分支2 分支的好处2.1 并行开发的支持2.2 独立性与隔离性2.3 灵活的版本控制2.4 提高安全性和代码质量2.5 项目历史的清晰记录 3 Git 分支操作命令3.1 git branch -v3.2 git branch 分支名称3.3 git checkout 分支名称3.4 git merge 分支名称3.5 git rebase 分…...
WPF StackPanel
StackPanel是一个控件容器,它按照一个方向(水平或垂直)堆叠子元素,使得它们沿一个轴线对齐。你可以在StackPanel中放置其他控件,如按钮、标签、文本框、图片等等。这些控件的排列方式由StackPanel按照指定的方向自动确…...
由正规表达式构造DFA,以及DFA的相关化简
目录 1.由正规式到DFA 首先讲如何从正规式到NFA 如何从NFA到DFA 2.DFA的化简 3.DFA和NFA的区别 1.由正规式到DFA 正规式--->NFA---->DFA 首先讲如何从正规式到NFA 转换规则: 例题1:这里圆圈里面的命名是随意的,只要能区别开就可以了 如何…...
模式识别与机器学习(九):Adaboost
1.原理 AdaBoost是Adaptive Boosting(自适应增强)的缩写,它的自适应在于:被前一个基本分类器误分类的样本的权值会增大,而正确分类的样本的权值会减小,并再次用来训练下一个基本分类器。同时,在…...
Node.js——util工具模块
util工具模块1、util模块概述2、util模块的使用2.1、格式化输出字符串2.2、将对象转换为字符串(调试)2.3、实现对象间的原型继承2.4、转换异步函数的风格2.5、判断是否为指定类型的内置对象2.6、其它方法1、util模块概述 util模块是Node.js的内置模块&a…...
DFT工程师的隐藏技巧:深入解读TestMAX中Shared与Dedicated Wrapper Cell的选择策略
DFT工程师的隐藏技巧:深入解读TestMAX中Shared与Dedicated Wrapper Cell的选择策略 在芯片设计的可测试性设计(DFT)领域,Wrapper Cell的选择往往被视为一项"黑盒"操作——工程师们习惯依赖EDA工具自动完成,却…...
从真题到实战:拆解CCF-GESP C++三级核心考点与避坑指南
1. 数据编码:从ASCII到UTF-8的实战解析 在CCF-GESP C三级考试中,数据编码是必考的核心知识点。很多同学第一次接触这个概念时容易懵圈——不就是存个字符吗,怎么还有这么多门道?其实理解编码就像学外语,ASCII是基础英语…...
告别重复编码:用快马AI一键生成团队协作网盘高效开发框架
最近在开发一个团队协作网盘系统时,发现很多基础功能其实都是重复性工作。比如权限管理、文件版本控制这些模块,每个项目都要从头写一遍。后来尝试用InsCode(快马)平台的AI生成功能,效率提升特别明显。这里分享下我的实践心得: 权…...
终极指南:5分钟掌握TegraRcmGUI Switch注入工具的核心能力
终极指南:5分钟掌握TegraRcmGUI Switch注入工具的核心能力 【免费下载链接】TegraRcmGUI C GUI for TegraRcmSmash (Fuse Gele exploit for Nintendo Switch) 项目地址: https://gitcode.com/gh_mirrors/te/TegraRcmGUI TegraRcmGUI是一款专为Nintendo Switc…...
OpenAPI状态机建模指南:用有限状态机设计RESTful API的终极方法 [特殊字符]
OpenAPI状态机建模指南:用有限状态机设计RESTful API的终极方法 🚀 【免费下载链接】OpenAPI-Specification The OpenAPI Specification Repository 项目地址: https://gitcode.com/gh_mirrors/op/OpenAPI-Specification OpenAPI Specification 是…...
如何编写全面的golang-lru单元测试:覆盖所有边界条件的完整指南
如何编写全面的golang-lru单元测试:覆盖所有边界条件的完整指南 【免费下载链接】golang-lru Golang LRU cache 项目地址: https://gitcode.com/gh_mirrors/go/golang-lru 在Go语言开发中,缓存是提升性能的关键组件,而golang-lru作为一…...
忍者像素绘卷惊艳效果:宇智波佐助千鸟刃×16-Bit闪电特效像素动效展示
忍者像素绘卷惊艳效果:宇智波佐助千鸟刃16-Bit闪电特效像素动效展示 1. 作品概览 忍者像素绘卷是基于Z-Image-Turbo深度优化的图像生成工作站,它将传统忍者文化与16-Bit复古游戏美学完美融合。这款工具特别适合创作具有强烈视觉冲击力的像素风格动漫角…...
从ChatGPT到文心一言:揭秘大语言模型背后的Decoder-only架构设计
从ChatGPT到文心一言:大语言模型的Decoder-only架构设计哲学 当ChatGPT在2022年末掀起全球AI对话风暴时,一个关键设计选择引起了技术界的广泛讨论:为什么这些最先进的大语言模型都选择了纯Decoder架构?这背后隐藏着怎样的技术哲学…...
VxLAN网络如何“破圈”?聊聊Type5路由在云网融合中的真实应用场景
VxLAN Type5路由:云网融合时代的智能连接引擎 在数字化转型浪潮中,企业网络架构正经历着从传统三层架构向云原生网络的跃迁。VxLAN作为新一代网络虚拟化技术的代表,其Type5路由功能正在成为打通云网边界的关键推手。想象一下这样的场景&#…...
