数据结构与算法 - 双指针

news/2024/10/20 14:20:13/

一、移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]输出: [0]

提示:

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

进阶：你能尽量减少完成的操作次数吗？

解法一：双指针法

在循环中，右指针right向右移动，如果当前元素不为0，则将其与左指针指向的元素交换，并且左指针向右移动。 

class Solution {public void moveZeroes(int[] nums) {int i = 0, j = 0;while(j < nums.length) {if(nums[j] != 0) {// 如果当前元素不为0，则将其与左指针指向的元素交换，并且左指针向右移动int t = nums[i];nums[i] = nums[j];nums[j] = t;i++;}j++;}}
}

二、两数之和Ⅱ - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers 按 非递减顺序 排列
  • -1000 <= target <= 1000
  • 仅存在一个有效答案

解法一：双指针法。执行耗时1ms

class Solution {public int[] twoSum(int[] numbers, int target) {int i = 0, j = numbers.length - 1;while (i < j) {int sum = numbers[i] + numbers[j];if (sum == target) {return new int[] { i + 1, j + 1 };} else if (sum < target) {i++;} else {j--;}}return new int[] {};}
}

三、三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

解法一：由三数之和转变为两数之和

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {// 跳过重复元素if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 变为两数之和int target = -nums[i];int left = i + 1;int right = nums.length - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum < target) {left++;} else if (sum > target) {right--;} else {List<Integer> triplet = new ArrayList<>();triplet.add(nums[i]);triplet.add(nums[left]);triplet.add(nums[right]);result.add(triplet);// 跳过重复的元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;}}}return result;}
}

或：

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> result = new LinkedList<>();dfs(3, 0, nums.length - 1, 0, nums,new LinkedList<>(), result);return result;}static void dfs(int n, int i, int j, int target, int[] nums,LinkedList<Integer> stack,List<List<Integer>> result) {if (n == 2) {// 套用两数之和求解twoSum(i, j, nums, target, stack, result);return;}for (int k = i; k < j - (n - 2); k++) {// 检查重复if (k > i && nums[k] == nums[k - 1]) {continue;}// 固定一个数字，再尝试 n-1 数字之和stack.push(nums[k]);dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);stack.pop();}}static int count;static public void twoSum(int i, int j, int[] numbers, int target,LinkedList<Integer> stack,List<List<Integer>> result) {count++;while (i < j) {int sum = numbers[i] + numbers[j];if (sum < target) {i++;} else if (sum > target) {j--;} else { // 找到解ArrayList<Integer> list = new ArrayList<>(stack);list.add(numbers[i]);list.add(numbers[j]);result.add(list);// 继续查找其它的解i++;j--;while (i < j && numbers[i] == numbers[i - 1]) {i++;}while (i < j && numbers[j] == numbers[j + 1]) {j--;}}}}
}

四、四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

解法一：双指针法

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();int n = nums.length;if (n < 4) {return result;}Arrays.sort(nums);for (int i = 0; i < n - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {// 处理重复元素continue;}for (int j = i + 1; j < n - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}int left = j + 1;int right = n - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum < target) {left++;} else if (sum > target) {right--;} else {List<Integer> quadruplet = new ArrayList<>();quadruplet.add(nums[i]);quadruplet.add(nums[j]);quadruplet.add(nums[left]);quadruplet.add(nums[right]);result.add(quadruplet);// 处理重复元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;}}}}return result;}
}

五、盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

解法一：双指针法

class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1;int result = 0;while (left < right) {result = Math.max(result, (right - left) * Math.min(height[left], height[right]));if (height[left] > height[right]) {--right;} else {++left;}}return result;}
}

六、反转字符数组

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 10^5
  • s[i] 都是 ASCII 码表中的可打印字符

解法一：双指针法

class Solution {public void reverseString(char[] s) {int i = 0, j = s.length - 1;while (i < j) {swap(s, i, j);i++;j--;}}private void swap(char[] s, int i, int j) {char t = s[i];s[i] = s[j];s[j] = t;}
}

七、反转字符串Ⅱ

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 10^4
  • s 仅由小写英文组成
  • 1 <= k <= 10^4

解法一：双指针法

class Solution {public String reverseStr(String s, int k) {int n = s.length();char[] chars = s.toCharArray();for (int i = 0; i < n; i += 2 * k) {// 只反转前k个字符int start = i;int end = Math.min(i + k - 1, n - 1);while (start < end) {swap(chars, start, end);start++;end--;}}return new String(chars);}private void swap(char[] s, int i, int j) {char t = s[i];s[i] = s[j];s[j] = t;}
}


http://www.ppmy.cn/news/1511665.html

相关文章

HTTP/1.1

HTTP/1.1

目录 一、比较HTTP/1.0的优点 二、请求报文 1.请求报文 &#xff08;1&#xff09;格式 2.get请求 &#xff08;1&#xff09;请求行 &#xff08;2&#xff09;请求头 &#xff08;3&#xff09;请求体 3.post请求 &#xff08;1&#xff09;请求行 &#xff08;2&…
阅读更多...
Gene_processing_system-v2.0使用之环境变量配置

Gene_processing_system-v2.0使用之环境变量配置

Gene_processing_system-v2.0环境变量配置 在D盘路径解压上述文件《Gene_processing_system-v2.0.zip》&#xff0c;解压后&#xff0c;对内置Python3.9环境变量进行配置。操作如下&#xff1a; 环境变量配置 第一步&#xff1a;复制python3.9路径值&#xff0c;复制路径值为…
阅读更多...
使用Dynamic Provision的PV需要Kubernetes集群管理员和用户分别做什么？

使用Dynamic Provision的PV需要Kubernetes集群管理员和用户分别做什么？

使用Dynamic Provision的PV需要Kubernetes集群管理员和用户分别做什么&#xff1f; A. Kubernetes集群管理员创建不同类型存储所需的不同的StorageClass对象 B. 用户创建PVC对象声明存储需求&#xff0c;并在PVC对象中通过storageClassName字段说明需要的存储类型 C. 用户在Pod…
阅读更多...
Spring Boot 3.3 【四】Spring Boot 整合JPA

Spring Boot 3.3 【四】Spring Boot 整合JPA

&#x1f31f; 技术人聊管理 请关注 【技术管理修行】 一、JPA 简介 Spring Data JPA 是 Spring Data 项目的一部分&#xff0c;它为使用 Java Persistence API (JPA) 进行数据库访问提供了一种非常简便的方式。Spring Data JPA 的主要目的是简化基于 JPA 的数据访问层的开发工…
阅读更多...
PyTorch之TensorBoard使用

PyTorch之TensorBoard使用

接回上一篇&#xff1a;PyTorch深度学习框架-CSDN博客 在学习这篇之前建议先按照上一篇搭建好整个PyTorch环境 然后这一篇讲怎么用TensorBoard&#xff0c;这个玩意是Tensorflow官方推出的一个可视化工具&#xff0c;当使用Tensorflow训练大量深层的神经网络时&#xff0c;我们…
阅读更多...
如果忘记了 Apple ID 密码，如何重设

如果忘记了 Apple ID 密码，如何重设

“我忘记了我的 Apple ID 密码&#xff0c;如何恢复我的帐户&#xff1f;”为了方便用户&#xff0c;Apple 允许每个人使用唯一的 Apple ID 和密码激活设备并访问所有 Apple 服务。然而&#xff0c;实际上&#xff0c;手动选择某项并忘记它似乎很容易。例如&#xff0c;许多 Ap…
阅读更多...
2024年8月19日（静态文件共享，playbook剧本）

2024年8月19日（静态文件共享，playbook剧本）

一、静态文件共享 1、编写脚本 [rootm0 ~]# vim /etc/tset000.sh #!/bin/bash mkdir /tmp/three touch /tmp/three/test echo I am echo at mttt > /tmp/three/test echo well done 2、将mysql_master.sh 复制到被控制的主机上并下载nfs和rpcbind包 [rootm0 ~]# ansible -s…
阅读更多...
python 列表

python 列表

列表是最常用的 Python 数据类型&#xff0c;它可以作为一个方括号内的逗号分隔值出现。列表的数据项不需要具有相同的类型&#xff0c;创建一个列表&#xff0c;只要把逗号分隔的不同的数据项使用方括号括起来即可。如下所示&#xff1a; list1 [Google, Runoob, 1997, 2000…
阅读更多...
最新文章

Copyright @ 2022~2023