算法训练-双指针

双指针

leetcode392. 判断子序列

 法一：动态规划

法二：双指针

leetcode876. 链表的中间结点

 法一：链表数组

 法二：快慢指针

leetcode160. 相交链表

 法一：双指针

leetcode167. 两数之和 II - 输入有序数组

 法一：二分查找

法二：双指针

leetcode142. 环形链表 II

 法一：快慢指针

 leetcode151. 反转字符串中的单词

 法一：双指针

法二：分割+倒序

leetcode3. 无重复字符的最长子串

 法一：滑动窗口

法二：动态规划

leetcode15. 三数之和

法一：排序+双指针 

leetcode239. 滑动窗口最大值

法一：单调队列 

leetcode392. 判断子序列

392. 判断子序列icon-default.png?t=O83Ahttps://leetcode.cn/problems/is-subsequence/

 法一：动态规划

public class Method01 {// 检查字符串 s 是否为字符串 t 的子序列public boolean isSubsequence(String s, String t) {// 获取字符串 s 和 t 的长度int n = s.length();int m = t.length();// 创建一个布尔数组 dp，长度为 n+1，表示是否匹配到当前字符boolean[] dp = new boolean[n + 1];// 初始化 dp[0] 为 true，表示空字符串 s 一定是任意字符串 t 的子序列dp[0] = true;// 遍历字符串 tfor (int i = 1; i <= m; i++) {// 遍历字符串 sfor (int j = 1; j <= n; j++) {// 如果 dp[j] 为 true，说明这个字符已经匹配成功，继续下一个字符if (dp[j]) {continue;}// 如果 s 的当前字符与 t 的当前字符匹配if (s.charAt(j - 1) == t.charAt(i - 1)) {// 记录当前状态，如果匹配，说明可以通过 dp[j-1] 的状态来更新 dp[j]dp[j] = dp[j - 1];break; // 匹配成功后退出内层循环，继续检查 t 的下一个字符}}}// 返回 s 是否完整匹配到 treturn dp[n];}
}

法二：双指针

public class Method02 {// 检查字符串 s 是否为字符串 t 的子序列public boolean isSubsequence(String s, String t) {// 初始化两个指针，i 指向 s，j 指向 tint i = 0, j = 0;// 当 i 小于 s 的长度且 j 小于 t 的长度时继续循环while (i < s.length() && j < t.length()) {// 如果 s 和 t 当前字符匹配if (s.charAt(i) == t.charAt(j)) {i++; // 移动 s 的指针，匹配下一个字符}j++; // 始终移动 t 的指针，继续检查下一个字符}// 如果 i 等于 s 的长度，则说明所有字符均被匹配，返回 truereturn i == s.length();}
}

leetcode876. 链表的中间结点

876. 链表的中间结点icon-default.png?t=O83Ahttps://leetcode.cn/problems/middle-of-the-linked-list/

 法一：链表数组

public class Method01 {// 找到链表的中间节点public ListNode middleNode(ListNode head) {// 创建一个 ListNode 数组，用于存储链表的节点ListNode[] arr = new ListNode[100]; // 假设链表的最大长度不会超过 100int i = 0;// 遍历链表，将每个节点存入数组while (head != null) {arr[i++] = head; // 将当前节点赋值给数组head = head.next; // 移动到下一个节点}// 返回中间节点，如果链表节点数为偶数，则返回第二个中间节点return arr[i / 2];}
}

 法二：快慢指针

public class Method02 {// 找到链表的中间节点public ListNode middleNode(ListNode head) {ListNode slow = head; // 初始化慢指针ListNode fast = head; // 初始化快指针// 使用快慢指针找到中间节点while (fast != null && fast.next != null) {slow = slow.next;       // 慢指针每次移动一步fast = fast.next.next;  // 快指针每次移动两步}// 返回慢指针指向的中间节点return slow;}
}

leetcode160. 相交链表

160. 相交链表icon-default.png?t=O83Ahttps://leetcode.cn/problems/intersection-of-two-linked-lists/

 法一：双指针

public class Method01 {// 找到两个链表的交点public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA = headA; // 指针 pA 初始化为链表 A 的头节点ListNode pB = headB; // 指针 pB 初始化为链表 B 的头节点// 当两个指针还未相遇时，继续遍历while (pA != pB) {// 如果 pA 到达链表 A 的末尾，则将其指向链表 B 的头节点pA = pA == null ? headB : pA.next;// 如果 pB 到达链表 B 的末尾，则将其指向链表 A 的头节点pB = pB == null ? headA : pB.next;}// 返回相遇的节点（交点），如果没有交点，则返回 nullreturn pA;}
}

leetcode167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组icon-default.png?t=O83Ahttps://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

 法一：二分查找

public class Method01 {// 找到数组中两个数的索引，使得这两个数的和等于目标值public int[] twoSum(int[] numbers, int target) {// 创建一个数组用于存储结果，长度为2int[] result = new int[2];// 遍历数组，外层循环固定一个元素for (int i = 0; i < numbers.length - 1; i++) {// 设置左右指针，左指针指向当前元素的下一个位置，右指针指向数组末尾int left = i + 1;int right = numbers.length - 1;// 使用二分查找找到与固定元素相加等于目标值的另一个元素while (left <= right) {// 计算中间位置int mid = (left + right) / 2;// 检查当前元素和中间元素的和是否等于目标值if (numbers[i] + numbers[mid] == target) {result[0] = i + 1; // 记录第一个元素的索引（加1以符合题目要求）result[1] = mid + 1; // 记录第二个元素的索引（加1以符合题目要求）return result; // 返回结果}// 如果和小于目标值，移动左指针向右else if (numbers[i] + numbers[mid] < target) {left = mid + 1;}// 如果和大于目标值，移动右指针向左else {right = mid - 1;}}}// 如果没有找到符合条件的两个元素，返回结果return result;}
}

法二：双指针

public class Method02 {// 找到数组中两个数的索引，使得这两个数的和等于目标值public int[] twoSum(int[] nums, int target) {int left = 0; // 初始化左指针，指向数组的开始int right = nums.length - 1; // 初始化右指针，指向数组的末尾// 当左指针小于右指针时，继续查找while (left < right) {int sum = nums[left] + nums[right]; // 计算当前左指针和右指针指向元素的和// 如果和等于目标值，返回两个指针索引（加1以符合题目要求）if (sum == target) {return new int[]{left + 1, right + 1};}// 如果和小于目标值，移动左指针向右else if (sum < target) {left++;}// 如果和大于目标值，移动右指针向左else {right--;}}// 如果没有找到符合条件的两个元素，返回一组表示未找到的索引return new int[]{-1, -1};}
}

leetcode142. 环形链表 II

142. 环形链表 IIicon-default.png?t=O83Ahttps://leetcode.cn/problems/linked-list-cycle-ii/

 法一：快慢指针

public class Method01 {// 找到链表中的环的起始节点，如果没有环则返回 nullpublic ListNode detectCycle(ListNode head) {ListNode slow = head; // 初始化慢指针，指向链表的头节点ListNode fast = head; // 初始化快指针，指向链表的头节点// 使用快慢指针找环while (fast != null && fast.next != null) {slow = slow.next;       // 慢指针每次移动一步fast = fast.next.next;  // 快指针每次移动两步// 如果慢指针和快指针相遇，说明链表有环if (slow == fast) {// 从链表头开始，另一个指针也从相遇点开始slow = head; // 将慢指针重新指向头节点// 匹配两个指针，相遇的点就是环的起始点while (slow != fast) {slow = slow.next; // 慢指针向前移动一步fast = fast.next; // 快指针向前移动一步}return slow; // 返回环的起始节点}}// 如果没有环，返回 nullreturn null;}
}

 leetcode151. 反转字符串中的单词

151. 反转字符串中的单词icon-default.png?t=O83Ahttps://leetcode.cn/problems/reverse-words-in-a-string/

 法一：双指针

public class Method01 {// 反转给定字符串中的单词顺序public String reverseWords(String s) {// 去除字符串首尾的空白字符s = s.trim();StringBuilder sb = new StringBuilder(); // 创建一个 StringBuilder 用于构建结果字符串int i = s.length() - 1; // 设置指针 i 指向字符串的最后一个字符int j = i; // 设置指针 j，初始化为 i// 遍历字符串，从后往前反转单词while (i >= 0) {// 找到当前单词的开始位置while (i >= 0 && s.charAt(i) != ' ') {i--;}// 提取当前单词并追加到 StringBuilder 中，后面加一个空格sb.append(s.substring(i + 1, j + 1) + " ");// 跳过空格，移动指针到下一个单词的开头while (i >= 0 && s.charAt(i) == ' ') {i--;}j = i; // 更新指针 j 为当前指针 i}// 返回构建的字符串，去掉最后的多余空格return sb.toString().trim();}
}

法二：分割+倒序

public class Method02 {// 反转给定字符串中的单词顺序public String reverseWords(String s) {// 去除字符串首尾的空白字符s = s.trim();// 用空格分割字符串，得到单词数组String[] str = s.split(" ");// 创建一个 StringBuilder 用于构建结果字符串StringBuilder sb = new StringBuilder();// 从后往前遍历单词数组for (int i = str.length - 1; i >= 0; i--) {// 跳过空字符串（可能由于多空格导致拆分产生空元素）if (str[i].equals("")) continue;// 追加单词到 StringBuilder，后面加一个空格sb.append(str[i]).append(" ");}// 返回构建的字符串，去掉最后的多余空格return sb.toString().trim();}
}

leetcode3. 无重复字符的最长子串

3. 无重复字符的最长子串icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-substring-without-repeating-characters/

 法一：滑动窗口

public class Method01 {// 找到给定字符串中不重复字符的最长子串的长度public int lengthOfLongestSubstring(String s) {int i = 0; // 右指针，遍历字符串int j = -1; // 左指针，表示当前无重复字符子串的起始位置int max = 0; // 记录最大无重复字符子串的长度// 创建一个 HashMap，用于存储字符及其最新出现的位置Map<Character, Integer> map = new HashMap<>();// 遍历字符串，直到右指针 i 到达字符串末尾while (i < s.length()) {// 如果字符 s[i] 已经在 map 中，更新 j 为它上次出现的位置if (map.containsKey(s.charAt(i))) {j = Math.max(j, map.get(s.charAt(i)));}// 更新当前无重复字符子串的最大长度max = Math.max(max, i - j);// 存储当前字符及其最新出现的位置map.put(s.charAt(i), i);i++; // 移动右指针}// 返回找到的最大长度return max;}
}

法二：动态规划

public class Method02 {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();int temp = 0, res = 0;for (int i = 0; i < s.length(); i++) {int j;if (map.containsKey(s.charAt(i))) {j = map.get(s.charAt(i));}else {j=-1;}map.put(s.charAt(i), i);temp = temp<i-j?temp+1:i-j;if (temp > res) {res = temp;}}return res;}
}

leetcode15. 三数之和

15. 三数之和icon-default.png?t=O83Ahttps://leetcode.cn/problems/3sum/

法一：排序+双指针 

public class Method01 {// 找到所有和为0的三元组public List<List<Integer>> threeSum(int[] nums) {// 对数组进行排序Arrays.sort(nums);int n = nums.length; // 数组长度List<List<Integer>> res = new ArrayList<>(); // 存储满足条件的三元组// 遍历数组，外层循环选定第一个数字for (int i = 0; i < n - 2; i++) {// 如果当前数字大于0，直接结束循环，因为后面的数字也都大于0，无法构成和为0的三元组if (nums[i] > 0) {break;}// 跳过重复元素以避免重复的三元组if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 内层使用双指针法，j 指向 i 后面的元素，k 指向数组的最后一个元素int j = i + 1, k = n - 1;while (j < k) {// 计算三个数的和int sum = nums[i] + nums[j] + nums[k];// 如果和为0，找到一个三元组if (sum == 0) {res.add(Arrays.asList(nums[i], nums[j], nums[k])); // 添加三元组到结果列表j++; // 移动左指针k--; // 移动右指针// 跳过重复的元素，避免添加重复的三元组while (j < k && nums[j] == nums[j - 1]) {j++;}while (j < k && nums[k] == nums[k + 1]) {k--;}} else if (sum < 0) {// 如果和小于0，说明需要更大的数，移动左指针j++;} else {// 如果和大于0，说明需要更小的数，移动右指针k--;}}}// 返回所有找到的和为0的三元组return res;}
}

leetcode239. 滑动窗口最大值

239. 滑动窗口最大值icon-default.png?t=O83Ahttps://leetcode.cn/problems/sliding-window-maximum/

法一：单调队列 

public class Method01 {public int[] maxSlidingWindow(int[] nums, int k) {// 如果输入数组为空或窗口大小为0，则返回空数组if (nums.length == 0 || k == 0) return new int[0];// 使用双端队列来存储当前窗口的元素Deque<Integer> deque = new LinkedList<>();// 结果数组，长度为输入数组长度 - 窗口大小 + 1int[] res = new int[nums.length - k + 1];// 未形成完整窗口的情况，填充前 k 个元素for (int i = 0; i < k; i++) {// 移除队列中比当前元素小的所有元素while (!deque.isEmpty() && deque.peekLast() < nums[i]) {deque.removeLast(); // 去掉队尾元素}// 将当前元素添加到队列的尾部deque.addLast(nums[i]);}// 将队列的首部元素（当前窗口的最大值）存入结果数组res[0] = deque.peekFirst();// 从第 k 个元素开始，开始滑动窗口for (int i = k; i < nums.length; i++) {// 如果队列的首部元素是滑出窗口的元素，则将其移除if (deque.peekFirst() == nums[i - k]) {deque.removeFirst();}// 移除队列中所有比当前元素小的元素while (!deque.isEmpty() && deque.peekLast() < nums[i]) {deque.removeLast(); // 去掉队尾元素}// 将当前元素添加到队列的尾部deque.addLast(nums[i]);// 将队列的首部元素（当前窗口的最大值）存入结果数组res[i - k + 1] = deque.peekFirst();}return res; // 返回记录最大值的数组}
}

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

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

相关文章

零基础学指针（上）

零基础学指针（上）

系列文章目录 &#x1f388; &#x1f388; 我的CSDN主页:OTWOL的主页&#xff0c;欢迎&#xff01;&#xff01;&#xff01;&#x1f44b;&#x1f3fc;&#x1f44b;&#x1f3fc; &#x1f389;&#x1f389;我的C语言初阶合集&#xff1a;C语言初阶合集&#xff0c;希望能…
阅读更多...
shell编程之sed

shell编程之sed

sed 是一种流编辑器&#xff0c;它是文本处理中非常有用的工具&#xff0c;能够完美的配合正则表达式使用&#xff0c;处理时&#xff0c;把当前处理的行存储在临时缓冲区中&#xff0c;称为模式空间&#xff0c;接着用sed 命令处理缓冲区中的内容&#xff0c;处理完成 后&…
阅读更多...
一文学习开源框架OkHttp

一文学习开源框架OkHttp

OkHttp 是一个开源项目。它由 Square 开发并维护&#xff0c;是一个现代化、功能强大的网络请求库&#xff0c;主要用于与 RESTful API 交互或执行网络通信操作。它是 Android 和 Java 开发中非常流行的 HTTP 客户端&#xff0c;具有高效、可靠、可扩展的特点。 核心特点 高效…
阅读更多...
多目标优化算法：多目标极光优化算法（MOPLO）求解ZDT1、ZDT2、ZDT3、ZDT4、ZDT6，提供完整MATLAB代码

多目标优化算法：多目标极光优化算法（MOPLO）求解ZDT1、ZDT2、ZDT3、ZDT4、ZDT6，提供完整MATLAB代码

一、极光优化算法 极光优化算法&#xff08;Polar Lights Optimization, PLO&#xff09;是2024年提出的一种新型的元启发式优化算法&#xff0c;它从极光这一自然现象中汲取灵感。极光是由太阳风中的带电粒子在地球磁场的作用下&#xff0c;与地球大气层中的气体分子碰撞而产…
阅读更多...
【贪心算法第二弹——2208.将数组和减半的最小操作数】

【贪心算法第二弹——2208.将数组和减半的最小操作数】

1.题目解析 题目来源 2208.将数组和减半的最小操作数——力扣 测试用例 2.算法原理(贪心策略) 3.实战代码 class Solution { public:int halveArray(vector<int>& nums) {priority_queue<double> hash;double sum 0.0;for(auto e : nums){hash.push(e);sum …
阅读更多...
2024最新python使用yt-dlp

2024最新python使用yt-dlp

2024最新python使用yt-dlp下载YT视频 1.获取yt的cookie1&#xff09;google浏览器下载Get cookies.txt LOCALLY插件2&#xff09;导出cookie 2.yt-dlp下载[yt-dlp的GitHub地址](https://github.com/yt-dlp/yt-dlp?tabreadme-ov-file)1&#xff09;使用Pycharm(2024.3)进行代码…
阅读更多...
深入理解下oracle 11g block组成

深入理解下oracle 11g block组成

深层次说&#xff0c;oracle数据库的最少组成单位应该是块&#xff0c;一般默认情况下&#xff0c;oracle数据库的块大小是8kb&#xff0c;其中存储着我们平常所需的数据。我们在使用过程中&#xff0c;难免会疑问道&#xff1a;“oracle数据块中到底是怎样组成的&#xff0c;平…
阅读更多...
2024年12月Gesp七级备考知识点拾遗第一期（图的定义及遍历）

2024年12月Gesp七级备考知识点拾遗第一期（图的定义及遍历）

目录 总序言 知识点拾遗​编辑 度数 环 二叉树 图的遍历 深度优先 广度优先 连通与强连通 有什么不同 构成分别至少需要几条边&#xff08;易错题&#xff09;&#xff1f; 无向连通图 有向强连通图 完全图 什么是完全图 无向完全图最少边数 有向完全图最少边…
阅读更多...
家庭智慧工程师：如何通过科技提升家居生活质量

家庭智慧工程师：如何通过科技提升家居生活质量

在今天的数字化时代&#xff0c;家居生活已经不再只是简单的“住”的地方。随着物联网&#xff08;IoT&#xff09;、人工智能&#xff08;AI&#xff09;以及自动化技术的快速发展&#xff0c;越来越多的家庭开始拥抱智慧家居技术&#xff0c;将他们的家变得更加智能化、便捷和…
阅读更多...
图像处理实验报告

图像处理实验报告

实验一 图像处理的MATLAB基础 实验目的&#xff1a;熟悉数字图象处理的基本软件工具和操作 实验内容&#xff1a;Matlab应用复习&#xff0c;矩阵产生、操作&#xff1b;矩阵运算以及字符运算。 1.利用增量产生向量[0,2,4,6,8,10]。 2.利用magic(n)函数产生7维魔鬼矩阵A&am…
阅读更多...
SpringBoot+SpringCloud面试题整理附答案

SpringBoot+SpringCloud面试题整理附答案

什么是SpringBoot&#xff1f; 1、用来简化spring初始搭建和开发过程使用特定的方式进行配置(properties或者yml文件) 2、创建独立的spring引用程序main方法运行 3、嵌入Tomcat无需部署war包&#xff0c;直接打成jar包nohup java -jar – & 启动就好 4、简化了maven的配置 …
阅读更多...
Linux之管道，system V的共享内存，消息队列和信号量

Linux之管道，system V的共享内存，消息队列和信号量

Linux之管道&#xff0c;systemV共享内存和信号量 一.进程间通信1.1进程间通信的目的1.2进程间通信的方式 二.管道2.1管道的概念2.2匿名管道2.3命名管道 三.system V3.1共享内存3.2消息队列3.3信号量 一.进程间通信 在我们之前有关Linux指令的学习时我们使用过“|”这个命令&a…
阅读更多...
Figma入门-基本操作制作登录页

Figma入门-基本操作制作登录页

Figma入门-基本操作制作登录页 前言 在之前的工作中&#xff0c;大家的原型图都是使用 Axure 制作的&#xff0c;印象中 Figma 一直是个专业设计软件。 最近&#xff0c;很多产品朋友告诉我&#xff0c;很多原型图都开始用Figma制作了&#xff0c;并且很多组件都是内置的&am…
阅读更多...
Django实现智能问答助手-数据库方式读取问题和答案

Django实现智能问答助手-数据库方式读取问题和答案

扩展 增加问答数据库&#xff0c;通过 Django Admin 添加问题和答案。实现更复杂的问答逻辑&#xff0c;比如使用自然语言处理&#xff08;NLP&#xff09;库。使用前端框架&#xff08;如 Bootstrap&#xff09;增强用户界面 1.注册模型到 Django Admin&#xff08;admin.py…
阅读更多...
SQL注入--文件读写注入--理论

SQL注入--文件读写注入--理论

什么是文件读写注入&#xff1f; MySQL中有 读取文件的函数&#xff1a;load_file() 写入文件的函数&#xff1a;Into outfile&#xff08;能写入多行&#xff0c;按格式输出&#xff09;和 into dumpfile&#xff08;只能写入一行且没有输出格式&#xff09; 利用这些函数在S…
阅读更多...
《最小生成树算法详解：Kruskal的优雅实现》

《最小生成树算法详解：Kruskal的优雅实现》

前置知识和本篇介绍 前置知识&#xff1a; 数据结构-优先级队列&#xff0c; 数据结构-并查集。 Kruskal算法不需要建图&#xff0c; 因此不会建图的模板也没事。 本篇介绍一最小生成树的概念和Kruskal算法。 有关prim算法&#xff08;另一种最小生成树的算法&#xff09;&am…
阅读更多...
云计算-华为HCIA-学习笔记

云计算-华为HCIA-学习笔记

笔者今年7月底考取了华为云计算方向的HCIE认证&#xff0c;回顾从IA到IE的学习和项目实战&#xff0c;想整合和分享自己的学习历程&#xff0c;欢迎志同道合的朋友们一起讨论&#xff01; 第二章&#xff1a;服务器基础 服务器是什么&#xff1f; 服务器本质上就是个性能超强的…
阅读更多...
uniapp接入高德地图

uniapp接入高德地图

下面代码兼容安卓APP和H5 高德地图官网&#xff1a;我的应用 | 高德控制台 &#xff0c;绑定服务选择《Web端(JS API)》 /utils/map.js 需要设置你自己的key和安全密钥 export function myAMap() {return new Promise(function(resolve, reject) {if (typeof window.onLoadM…
阅读更多...
C++：探索AVL树旋转的奥秘

C++：探索AVL树旋转的奥秘

文章目录 前言 AVL树为什么要旋转&#xff1f;一、插入一个值的大概过程1. 插入一个值的大致过程2. 平衡因子更新原则3. 旋转处理的目的 二、左单旋1. 左单旋旋转方式总处理图2. 左单旋具体会遇到的情况3. 左单旋代码总结 三、右单旋1. 右单旋旋转方式总处理图2. 右单旋具体会遇…
阅读更多...
文小言1：

文小言1：

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023