面试经典150题刷题——双指针部分
- 验证回文串
简单
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。
注意for循环的坑，这里对字符大小写进行变化时，不可以使用另一种形式的for循环，因为for(char ch : chs)中的ch只是一个局部变量，并不会对chs数组中的元素进行更新
class Solution {
public boolean isPalindrome(String s) {
// 1. 数据预处理一下
// 2. 去掉所有空格
// 3. 然后双指针一个从前，一个从后面
String str = s.replaceAll("[^a-zA-Z0-9]", ""); // 去掉所有非字母数字字符
char[] chs = str.toCharArray();
int n = chs.length;
for(int i = 0; i < n; i++) {
if(chs[i] >= 'A' && chs[i] <= 'Z') {
chs[i] = (char)(chs[i] + 32);
}
}
System.out.print(n);
for(int i = 0,j = n-1; i < n/2; i++,j-- ) {
if(chs[i] != chs[j]) {
System.out.print(chs[i] + " " + chs[j]);
return false;
}
}
return true;
}
}判断子序列
简单
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
class Solution {
public boolean isSubsequence(String s, String t) {
/**
判断s 是不是 t的子序列
思路：双指针法，使用两个指针依次匹配即可
*/
if(s.length() == 0) return true;
for(int i =0,j =0; j < t.length(); j++) {
if(s.charAt(i) == t.charAt(j)) {
if(++i == s.length()) { // 已经匹配完s了
return true;
}
}
}
return false; // s还有没有匹配完的，说明不是子序列
}
}- 两数之和 —— 输入有序数组 —— O(n)
给你一个下标从 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] 。
167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
class Solution {
public int[] twoSum(int[] numbers, int target) {
// 如果求和小于 目标值；说明 A[0] + A[j] 小的，应该用 A[1] + A[j] 故 i++
// 如果求和大于 目标值：说明 A[0] + A[j] 大于target，则说明其大了，应该用 A[0] + A[j-1]的内容尝试，故 j--
// 遍历这个numbers; // 双指针思想
// 原来的空间是一个二维的矩阵 （朴素算法）
int n = numbers.length;
int i = 0 , j = n-1;
while(i < n && j > 0){
int sum = numbers[i] + numbers[j];
if(sum < target) {
i ++;
}else if(sum > target) {
j --;
}else { // sum == target
return new int[]{i+1,j+1};
}
}
return new int[]{-1,-1}; // 没有找到
}
}- 盛最多水的容器
给定一个长度为 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。
参考题解：
class Solution {
public int maxArea(int[] height) {
/**
装最多的水，就是在求这个矩形的最大面积
矩形的长为后面的下标减去前面的下标；矩形的宽为两个长条中更小的一个
朴素算法：———— 超时
用一个变量记录最大值
然后以左边第一个为左柱子，依次遍历右边的柱子，计算面积
下一轮以左边第二个为右柱子
双指针思想：
同样的是在一个n*n空间内部搜索
得到O(n)的思想，必须要通过双指针，指针每一次移动，意味着排除掉一根柱子
如果左边的柱子较短，那么相当于左边的柱子全部被使用了
此时如果固定左边的柱子，然后移动右边的柱子，此时水的高度一定不会增加；相当于排除了左柱子
当把这些柱子对称过来时，之前的左柱子不就相当于现在的右柱子；
所以也是同理，如果右边较小，则排除了一次右柱子
总之：就是每次拿两端比较，排除较小一端的柱子,双指针中就是通过 i++,j-- 实现
*/
// return method1(height);
return doublePointerMethod(height);
}
private int doublePointerMethod(int[] height) {
int n = height.length;
int i = 0, j = n-1;
int ans = 0;
while(i < n-1 && j > 0) {
int area = 0;
if(height[i] <= height[j]) {
// 左边的柱子更小，记录左边柱子的情况，然后排除这根柱子
area = height[i] * (j-i);
i ++;
}else { // 右边柱子更小，记录右边柱子的情况，然后排除这根柱子
area = height[j] * (j-i);
j --;
}
ans = Math.max(area, ans);
}
return ans;
}
public int method1(int[] height) {
int ans = 0;
int n = height.length;
for(int i = 0; i < n-1; i++) {
for(int j = i+1; j < n; j++) {
int area = Math.min(height[i],height[j]) * (j-i);
ans = Math.max(area,ans); // 更新ans
}
}
return ans;
}
}搜索二维矩阵 Ⅱ
中等
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true
- 三数之和 —— 固定一个，用双指针遍历下一层
中等
给你一个整数数组 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] 。 注意，输出的顺序和三元组的顺序并不重要。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 是否存在三个数不重复(可以相等)，但是三个数却可以相加为0
/**
朴素思想： 三重for循环：固定第一个参数，然后下一个，然后固定第二个参数，继续下一个，遍历最后一个
思路2：可不可以先进行排序，然后对排序的结果进行操作，如果第一个和第二个参数大于0了，就不用判断第三个了，但这只是剪枝；
思路3：固定第一个k,然后对后面两个使用双指针，这样优化到O(n); 而第一次有n个，所以总时间复杂度为O(n^2)
操作为先排序
*/
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int k = 0; k < nums.length - 2; k++) {
if(nums[k] > 0) break;
// 如果当前的k与之前的相同，则跳过，因为已经把nums[k]的所有组合加入到结果中了
if(k > 0 && nums[k] == nums[k - 1]) continue;
// 使用双指针遍历下面两个元素nums[i] , nums[j]
int i = k + 1, j = nums.length - 1;
while(i < j) {
int sum = nums[k] + nums[i] + nums[j];
if(sum < 0) { // 结果小0，增大nums[i],且去掉所有相同的nums[i]，因为已经不满足case了
while(i < j && nums[i] == nums[++i]);
}else if(sum > 0) { // 结果大0，减小nums[j],且去掉所有相同的nums[j]
while(i < j && nums[j] == nums[--j]);
}else { // = 0 收集结果,并进入下一个元素
res.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));
while(i < j && nums[i] == nums[++i]);
while(i < j && nums[j] == nums[--j]);
}
}
}
return res;
}
}原文地址：https://blog.csdn.net/m0_47411815/article/details/144307813
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！