优选算法 - 1 ( 双指针 移动窗口 8000 字详解 )

一:双指针

1.1 移动零

题目链接:283.移动零

在这里插入图片描述

在这里插入图片描述

class Solution {public void moveZeroes(int[] nums) {for(int cur = 0, dest = -1 ; cur < nums.length ; cur++){if(nums[cur] == 0){}else{dest++; // dest 先向后移动⼀位int tmp = nums[cur];nums[cur] = nums[dest];nums[dest] = tmp;}}}
}

在这里插入图片描述

这类题目的本质就是数组划分,根据某个规则将数组分成若干个区间,在此题中,我们可以使用双指针算法划分数组的区间,用数组下标充当指针,两个指针会划分成3个区间

1.2 复写零

题目链接:复写零

在这里插入图片描述

请添加图片描述

class Solution {public void duplicateZeros(int[] arr) {int length = arr.length;int cur = 0; // 最后一个复写数的长度int i;// 第一步:先获取最后一个复写数的索引for (i = 0; i < length; i++) {if (arr[i] == 0) {cur += 2;  // 遇到 0 占两个位置} else {cur++;  // 非 0 占一个位置}if (cur >= length) {break;}}// 第二步:开始操作,从右向左复制数据int dest = length - 1;// 细节:检查最后一个位置是否是一个完整的 0if (cur > length) {if (arr[i] == 0) {arr[dest--] = 0; // 如果 cur 超过数组长度,最后一个 0 只复制一次,防止越界}i--; // 减少 i 以便继续处理剩下的部分}// 从右到左进行实际复制while (i >= 0) {if (arr[i] == 0) {arr[dest--] = 0; // 复制第一个 0arr[dest--] = 0; // 复制第二个 0} else {arr[dest--] = arr[i]; // 复制非零元素}i--;}}
}

在这里插入图片描述

1.3 快乐数

题目链接:快乐数
在这里插入图片描述

请添加图片描述

class Solution {//封装一个求 n 每一位的平方和的函数public int bitsum(int n){int sum = 0;while(n > 0){int bit = n % 10;sum += bit * bit;n /= 10;}return sum;}public boolean isHappy(int n) {//先让快指针走一步int slow = n;int fast = bitsum(n);while(slow != fast){//慢指针走一步,快指针走两步slow = bitsum(slow);fast = bitsum(bitsum(fast));}      return fast == 1;}
}

在这里插入图片描述

1.4 盛水最多的容器

题目链接: 盛水最多的容器

在这里插入图片描述

请添加图片描述

class Solution {public int maxArea(int[] height) {// left 是左指针, right 是右指针,ret存储最大的体积结果int left = 0;int right = height.length - 1;int ret = 0;while(left < right){int v = Math.min(height[left], height[right]) * (right - left);ret = Math.max(ret,v);if(height[left] < height[right]) left++;else right --;}return ret;}
}

在这里插入图片描述

1.5 有效三角形的个数

题目链接:有效三角形的个数

在这里插入图片描述
请添加图片描述

class Solution {public int triangleNumber(int[] nums) {//首先先对数组排序,并用 ret 存储有效三角形的个数Arrays.sort(nums);int ret= 0;int n = nums.length - 1;//先固定一个最大的数,最大的数最小的下标应该是 2for(int i = n ; i >= 2 ; i --){int left = 0;int right = i - 1;while (left < right) {    //如果左指针加上右指针的值大于固定数的值if(nums[left] + nums[right] > nums[i]){ret += (right - left);right--;}else{left++;}}    }return ret;}
}

在这里插入图片描述

1.6 和为 s 的两个数字

题⽬链接:和为s的两个数字

在这里插入图片描述
请添加图片描述

class Solution
{public int[] twoSum(int[] nums, int target){int left = 0, right = nums.length - 1;while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else return new int[] {nums[left], nums[right]};}// 照顾编译器return new int[]{0};}
}

在这里插入图片描述

1.7 三数之和

题目链接:三数之和

在这里插入图片描述

请添加图片描述

import java.util.*;class Solution {public List<List<Integer>> threeSum(int[] nums) {// 先对数组进行排序Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();int n = nums.length;// 固定一个数,从左往右固定,最少保留两个数for (int i = 0; i < n - 2; i++) {// 跳过固定数的重复情况if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = n - 1, target = -nums[i];while (left < right) {int sum = nums[left] + nums[right];if (sum > target)  right--; else if (sum < target)  left++;else {// 找到符合条件的三元组ret.add(Arrays.asList(nums[i], nums[left], nums[right]));left++; right--;// 跳过重复的 left 和 right 元素,防止结果重复while (left < right && nums[left] == nums[left - 1]) left++;while (left < right && nums[right] == nums[right + 1]) right--;}}}return ret;}
}

在这里插入图片描述

1.8 四数之和

题目链接:四数之和

在这里插入图片描述

请添加图片描述

import java.util.*;class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {//先对数组进行排序Arrays.sort(nums);int n = nums.length;List<List<Integer>> ret = new ArrayList<>();//接着固定两个数for(int i = 0 ; i < n   ;){for(int j = i + 1 ; j < n ; ){int left = j + 1 , right = n - 1;long aim = (long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum > aim) right--;else if(sum < aim) left++;else{ret.add(Arrays.asList(nums[i], nums[j], nums[left++],nums[right--]));//接着进行去重while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}//循环执行完毕后,让第二个固定的数加 1j++;while(j < n && nums[j] == nums[j - 1]) j++;}i++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;}
}

在这里插入图片描述

二: 移动窗口

2.1 长度最小的子数组

题目链接:长度最小的子数组

在这里插入图片描述

请添加图片描述

class Solution {public int minSubArrayLen(int target, int[] nums) {// size 用于记录最小子数组的长度,sum 用于存储子数组的和int n = nums.length, sum = 0, size = Integer.MAX_VALUE;int left = 0, right = 0;while(right < n){//进窗口sum += nums[right];//出窗口while(sum >= target){size = Math.min(size,right - left + 1);sum -= nums[left++];} //一次迭代完成后让右指针继续走right++;}//判断一下 size 是否被更新过return size == Integer.MAX_VALUE ? 0 : size;}
}

在这里插入图片描述

2.2 无重复字符的最长子串

题目链接:无重复字符的最长子串

在这里插入图片描述

请添加图片描述

class Solution {public int lengthOfLongestSubstring(String ss) {//先把字符转为字符数组char[] s = ss.toCharArray();//用数组模拟一个哈希表int[] hash = new int[128];int left = 0, right = 0 , n = ss.length();int maxsize = 0;while(right < n){//进窗口,先拿到下标为 left 的字符,让这个字符所在的 hash 数组中的位置的值 +1 ,代表这个字符已经存入hash[s[right]]++;//出窗口while(hash[s[right]] > 1){hash[s[left]]--;left++;}maxsize = Math.max(maxsize,right - left + 1);right++;}return maxsize;}
}

在这里插入图片描述

2.3 最大连续 1 的个数 III

题目链接:最大连续 1 的个数 III

在这里插入图片描述
请添加图片描述

class Solution {public int longestOnes(int[] nums, int k) {//定义左右指针和计数器 zero ,用于统计 0 的个数int left = 0, right = 0 ,zero = 0, n = nums.length,ret = 0;while(right < n){//进窗口if(nums[right] == 0) zero++;//出窗口while(zero > k){               if(nums[left++] == 0) zero--;}ret = Math.max(ret,right - left + 1);right++;}return ret;}
}

在这里插入图片描述

2.4 将 x 减到 0 的最小操作数

题目链接:将 x 减到 0 的最小操作数

在这里插入图片描述

请添加图片描述

class Solution {public int minOperations(int[] nums, int x) {int sum = 0, left = 0, right = 0, n = nums.length;for(int a : nums) sum += a;int target = sum - x , total = 0, len = -1;// 如果 target 小于 0,直接返回 -1if (target < 0) return -1;  while(right < n){//进窗口total += nums[right];//出窗口while(total > target) total -= nums[left++];//更新 lenif(total == target) len = Math.max(len,right - left + 1);right++;}if(len == -1) return len;else return n - len;}
}

在这里插入图片描述

2.5 水果成篮

题目链接:水果成篮

在这里插入图片描述

请添加图片描述

class Solution {public int totalFruit(int[] fruits) {//创建一个哈希表,用于存储水果的种类和数量Map<Integer, Integer> hash = new HashMap<>();int left = 0, right = 0, n = fruits.length, max = 0;while(right < n){//进窗口int ch1 = fruits[right];hash.put(ch1, hash.getOrDefault(ch1,0) + 1);//出窗口while(hash.size() > 2){int ch2 = fruits[left];hash.put(ch2, hash.get(ch2) - 1); //踢出元素的时候,可能会让这个元素变空,此时要踢出去if(hash.get(ch2) == 0) hash.remove(ch2);left++;}//更新结果max = Math.max(max, right - left + 1);right++;}return max;}
}

2.6 找到字符串中所有字母异位词

题目链接:找到字符串中所有字母异位词

在这里插入图片描述

请添加图片描述
请添加图片描述

class Solution {public List<Integer> findAnagrams(String ss, String pp) {List<Integer> ret = new ArrayList<>();//不合理的情况,直接返回一个空的if(pp.length() > ss.length()) return ret;//接着把 s 和 p 转换为字符数组,并用 hash1 和 hash2 分别记录 s 和 p 中出现过的字符和次数,count 统计有效字符的个数char[] s = ss.toCharArray();char[] p = pp.toCharArray();int[] hash1 = new int[26];int[] hash2 = new int[26];for(int ch : p) hash2[ch - 'a']++;int left = 0, right = 0, count = 0, n = s.length;while(right < n){//进窗口 + 维护 countchar in = s[right];hash1[in - 'a']++;if(hash1[in - 'a'] <= hash2[in - 'a']) count ++;//出窗口 + 维护 countif(right - left + 1 > p.length) {char out = s[left];//这两行可以合并,但是为了代码的可读性就不进行合并了hash1[out - 'a']--;if(hash1[out -'a'] < hash2[out - 'a']) count--;left++;} //更新结果if(count == p.length) ret.add(left);right++;}return ret;}
}

在这里插入图片描述

2.7 串联所有单词的子串

题目链接:串联所有单词的子串

在这里插入图片描述

请添加图片描述

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<>();if (words.length == 0 || s.length() < words.length * words[0].length()) return ret;// 存储 words 中每个字符串的频率Map<String, Integer> hash1 = new HashMap<>();for (String str : words) {hash1.put(str, hash1.getOrDefault(str, 0) + 1);}int len = words[0].length(), m = words.length, windowSize = len * m;// 遍历所有可能的起始点for (int i = 0; i < len; i++) {Map<String, Integer> hash2 = new HashMap<>();int left = i, right = i, count = 0;// 滑动窗口while (right + len <= s.length()) {String in = s.substring(right, right + len);right += len;// 更新窗口内单词频率计数hash2.put(in, hash2.getOrDefault(in, 0) + 1);// 如果 in 的频率不超过 hash1 中的频率,增加 countif (hash2.get(in) <= hash1.getOrDefault(in, 0)) {count++;}// 当窗口大小等于 windowSize 时,检查并可能出窗口if (right - left == windowSize) {if (count == m) ret.add(left); // 找到符合条件的子串String out = s.substring(left, left + len);left += len;// 更新窗口内单词频率计数if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {count--;}hash2.put(out, hash2.get(out) - 1);// 如果频率为 0,从 hash2 中移除该单词if (hash2.get(out) == 0) {hash2.remove(out);}}}}return ret;}
}

在这里插入图片描述

2.8 最小覆盖子串

题目链接:最小覆盖子串

在这里插入图片描述

请添加图片描述

class Solution {public String minWindow(String ss, String tt) {// 将字符串转换成字符数组char[] s = ss.toCharArray();char[] t = tt.toCharArray();// 用 hash1 存储字符串 t 中每个字符的频率int[] hash1 = new int[128];int uniqueChars = 0; // 统计 t 中不同字符的种类数for (char ch : t) {if (hash1[ch]++ == 0) uniqueChars++;}// hash2 用来统计窗口内的字符频率int[] hash2 = new int[128];int minLen = Integer.MAX_VALUE, start = -1;int left = 0, matchedCount = 0;// 右指针移动for (int right = 0; right < s.length; right++) {char in = s[right];hash2[in]++;// 如果当前字符频率与 t 中相等,则增加匹配计数if (hash2[in] == hash1[in]) matchedCount++;// 当所有字符频率匹配时,尝试收缩窗口while (matchedCount == uniqueChars) {// 如果当前窗口更小,则更新最小窗口的长度和起始位置if (right - left + 1 < minLen) {minLen = right - left + 1;start = left;}// 出窗口char out = s[left++];if (hash2[out] == hash1[out]) matchedCount--;hash2[out]--;}}// 根据最小窗口的位置和长度返回结果return start == -1 ? "" : ss.substring(start, start + minLen);}
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/468607.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

qt配合映美精取图开发

最近开发一个项目&#xff0c;用映美精相机配合halcon做取图开发&#xff0c;由于网上资料小特意写个记录。到映美精官网下载驱动&#xff0c;映美精官网&#xff0c;下载映美精的工具开发包SDK 映美精的SDK下载SDK后找到classlib文件夹 里面就是SDK新建一个qt程序&#xff0c…

华为云计算HCIE-Cloud Computing V3.0试验考试北京考场经验分享

北京试验考场 北京考场位置 1.试验考场地址 北京市海淀区北清路156号中关村环保科技示范园区M地块Q21楼 考试场选择北京&#xff0c;就是上面这个地址&#xff0c;在预约考试的时候会显示地址&#xff0c;另外在临近考试的时候也会给你发邮件&#xff0c;邮件内会提示你考试…

LeetCode 509.斐波那契数

动态规划思想 五步骤&#xff1a; 1.确定dp[i]含义 2.递推公式 3.初始化 4.遍历顺序 5.打印dp数组 利用状态压缩&#xff0c;简化空间复杂度。在原代码中&#xff0c;dp 数组保存了所有状态&#xff0c;但实际上斐波那契数列的计算只需要前两个状态。因此&#xff0c;我们…

反向代理开发

1 概念 1.1 反向代理概念 反向代理是指以代理服务器来接收客户端的请求&#xff0c;然后将请求转发给内部网络上的服务器&#xff0c;将从服务器上得到的结果返回给客户端&#xff0c;此时代理服务器对外表现为一个反向代理服务器。 对于客户端来说&#xff0c;反向代理就相当于…

RabbitMQ — 异步调用

RabbitMQ 是一个开源的消息代理中间件&#xff0c;它使用高级消息队列协议&#xff08;AMQP, Advanced Message Queuing Protocol&#xff09;来实现不同系统之间的消息传递。它以 Erlang 语言编写&#xff0c;具有高可靠性、灵活性和易于扩展的特点&#xff0c;被广泛应用于异…

2025 年使用 Python 和 Go 解决 Cloudflare 问题

作为一名从事网络自动化和爬取工作的开发者&#xff0c;我亲眼目睹了日益复杂的安全性措施带来的挑战。其中一项挑战是 Cloudflare 的 Turnstile CAPTCHA 系统&#xff0c;目前该系统已在全球 2600 多万个网站上使用。这种先进的解决方案重新定义了我们对机器人检测的处理方式&…

大数据的实时处理:工具和最佳实践

在当今的数字世界中&#xff0c;数据以前所未有的速度从无数来源生成&#xff0c;包括社交媒体、物联网设备、电子商务平台等。随着组织认识到这些数据的潜在价值&#xff0c;他们越来越多地转向实时处理&#xff0c;以获得即时、可操作的见解。但是&#xff0c;实时处理大数据…

104、Python并发编程:基于事件Event实现多线程间的同步

引言 继续介绍关于多线程同步的实现方式&#xff0c;本文将介绍基于Event的线程同步方式。 本文的主要内容有&#xff1a; 1、什么是Event 2、Event的使用场景 3、Event的代码实例 4、Event与Condition的比较 什么是Event 在Python的多线程编程中&#xff0c;Event是一个…

第2章2.3立项【硬件产品立项的核心内容】

硬件产品立项的核心内容 2.3 硬件产品立项的核心内容2.3.1 第一步&#xff1a;市场趋势判断2.3.2 第二步&#xff1a;竞争对手分析1.竞争对手识别2.根据竞争对手分析制定策略 2.3.3 第三步&#xff1a;客户分析2.3.4 第四步&#xff1a;产品定义2.3.5 第五步&#xff1a;开发执…

ReactPress数据库表结构设计全面分析

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress 欢迎Star。 ReactPress是一个基于React框架开发的开源发布平台和内容管理系统&#xff08;CMS&#xff09;。它不仅支持用户在支持React和MySQL数据库的服务器上搭建自己的博客和网站&#…

ANDROIDWORLD: A Dynamic BenchmarkingEnvironment for Autonomous Agents论文学习

这个任务是基于androidenv的。这个环境之前学过&#xff0c;是一个用来进行强化学习的线上环境。而这篇文章的工作就是要给一些任务加上中间的奖励信号。这种训练环境的优点就是动态&#xff0c;与静态的数据集&#xff08;比如说我自己的工作&#xff09;不同&#xff0c;因此…

华为ENSP--ISIS路由协议

项目背景 为了确保资源共享、办公自动化和节省人力成本&#xff0c;公司E申请两条专线将深圳总部和广州、北京两家分公司网络连接起来。公司原来运行OSFP路由协议&#xff0c;现打算迁移到IS-IS路由协议&#xff0c;张同学正在该公司实习&#xff0c;为了提高实际工作的准确性和…

python-26-Python ORM系列之pymysql实现对数据库的增删改查及新建表

python-26-Python ORM系列之pymysql实现对数据库的增删改查及新建表 一.简介 在Python基础系列ORM部分我们为大家介绍了如何搭建MySQL数据和MySQL一些访问配置&#xff0c;同时细节的同学应该已经了解到了ORM的2个库pymysql和sqlalchemy&#xff1b; PyMySQL — MySQL 数据库…

ADSP21489 M25P16启动后无法使用USBi的问题

项目背景是ADSP21489 使用SPI MASTER 启动模式,程序存储在M25P16中 编译cces产生运行代码 第二步,插上USBi仿真器下载sigma topo 发现无法正常下载 操作多次发现需要目标板重新上点后需要拔插usbi才能下载和启动dsp程序 原因分析: 就是第一次插上usbi后,在给目标板上电,可…

量子计算包kaiwu安装过程踩过的坑

目录 1 安装过程 2 官方代码测试 3 踩坑说明 首先&#xff0c;目前的kaiwu版本仅支持python3.8&#xff0c;所以必须要下载python3.8才能运行kaiwu 1 安装过程 step1: 在页面的SDK标签下&#xff0c;找到对应操作系统的kaiwu包。 step2: 下载python3.8到本地&#xff0c;可…

线程相关概念

线程概念 线程是操作系统中一种基本的执行单元&#xff0c;是程序的最小调度单位。一个程序可以包含多个线程&#xff0c;每个线程代表一个独立的执行路径&#xff0c;使得程序可以并发地处理多个任务。 线程的基本概念 线程与进程的区别&#xff1a; 进程是资源分配的单位&…

SSH实验5密钥登录Linuxroot用户(免密登录)

当用户尝试通过SSH连接到远程服务器时&#xff0c;客户端会生成一对密钥&#xff1a;公钥和私钥。公钥被发送到远程服务器&#xff0c;并存储在服务器的~/.ssh/authorized_keys文件中。而私钥则由客户端保管&#xff0c;不会传输给服务器。 在连接过程中&#xff0c;客户端使用…

域名邮箱推荐:安全与稳定的邮件域名邮箱!

域名邮箱推荐及绑定攻略&#xff1f;最好用的域名邮箱服务推荐&#xff1f; 域名邮箱&#xff0c;作为一种个性化且专业的电子邮件服务&#xff0c;越来越受到企业和个人的青睐。烽火将详细介绍域名邮箱登录的全过程&#xff0c;从注册到登录&#xff0c;帮助您轻松掌握这一重…

政治经济学笔记

【拯救者】政治经济学速成&#xff08;基础习题&#xff09; 研究生产关系必须联系生产力和上层建筑 1.生产力与生产关系 生产力代表生产的物质内容&#xff0c;生产关系是生产的社会形式。生产力决定生产关系&#xff0c;生产关系对生产力具有 反作用 *其中的”反作用”指的是…

《TCP/IP网络编程》学习笔记 | Chapter 7:优雅地断开套接字连接

《TCP/IP网络编程》学习笔记 | Chapter 7&#xff1a;优雅地断开套接字连接 《TCP/IP网络编程》学习笔记 | Chapter 7&#xff1a;优雅地断开套接字连接基于 TCP 的半关闭单方面断开连接带来的问题套接字和流针对优雅断开的 shutdown 函数为何需要半关闭&#xff1f;基于半关闭…