力扣刷题篇——双指针
目录
💟💟前言 友友们大家好，我是你们的小王同学😗😗 今天给大家带来的是力扣刷题篇双指针 希望能给大家带来有用的知识 觉得小王写的不错的话 麻烦动动小手 点赞👍 收藏⭐ 评论📄 小王的主页：小王同学🚗 小王的gitee：小王同学🏩 小王的github：小王同学💦
2000 题目描述🧤：
给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ，反转 word 中从下标 0 开始、直到下标 i 结束（含下标 i ）的那段字符。如果 word 中不存在字符 ch ，则无需进行任何操作。 例如，如果 word = "abcdefd" 且 ch = "d" ，那么你应该 反转 从下标 0 开始、直到下标 3 结束（含下标 3 ）。结果字符串将会是 "dcbaefd" 。 返回 结果字符串 。 示例 1： 输入：word = "abcdefd", ch = "d" 输出："dcbaefd" 解释："d" 第一次出现在下标 3 。 反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "dcbaefd" 。 示例 2： 输入：word = "xyxzxe", ch = "z" 输出："zxyxxe" 解释："z" 第一次也是唯一一次出现是在下标 3 。 反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "zxyxxe" 。 示例 3： 输入：word = "abcd", ch = "z" 输出："abcd" 解释："z" 不存在于 word 中。 无需执行反转操作，结果字符串是 "abcd" 。
解题思路🧤：
- 先查找以ch为指定下标
- 将字符串转化成数组
- 定义两个指针
- 从下标0开始直到 查找到ch才结束反转这段字符串
- 否则就直接返回字符串
代码附上🧤：
class Solution {
public String reversePrefix(String word, char ch) {
int index=word.indexOf(ch); //以ch为指定的下标开始search
if(ch>=0){
//当下标大于等于0的时候就开始reverse
char []arr=word.toCharArray(); //将字符串转化吃字符数组
//双指针
int left=0; int right=index;
while(left<right){ //当left<right的时候 每次交换两两 并且交换完 left++,right --
char tmp=arr[left];
arr[left]=arr[right];
arr[right]=tmp;
left++;
right--;
}
word=new String(arr);
}
return word;
}
}917 题目描述🧤：
给你一个字符串 s ，根据下述规则反转字符串： 所有非英文字母保留在原有位置。
- 所有英文字母（小写或大写）位置反转。
- 返回反转后的 s 。
示例 1： 输入：s = "ab-cd" 输出："dc-ba" 示例 2： 输入：s = "a-bC-dEf-ghIj" 输出："j-Ih-gfE-dCba" 示例 3： 输入：s = "Test1ng-Leet=code-Q!" 输出："Qedo1ct-eeLg=ntse-T!"
解题思路：
- 首先我们先根据题意定义一个判断是否为26个大小写英文字母的方法
- 然后定义两个指针 i 和 j
- i从最左边开始扫描字符串 j从最右边开始扫描字符串 如果i和j 都扫描到了字符串 就交换i和j
- 的位置 然后继续扫描 否则反转过程中结束 返回最后的字符串 注意格式输出
代码附上🧤：
class Solution {
private boolean check(char c){
return c>='a'&&c<='z'||c>='A'&&c<='Z';
}
public String reverseOnlyLetters(String s) {
int n=s.length();
char ch[]=s.toCharArray(); //将字符串转化成字符数组
int i=0;
int j=n-1;
while(i<j){
if(!check(ch[i])){
i++;
continue;
}
if(!check(ch[j])){
j--;
continue;
}
char tmp=ch[i];
ch[i]=ch[j];
ch[j]=tmp;
i++;
j--;
}
return String.valueOf(ch) ; //注意输出格式是字符串
}
}475 题目描述🧤：
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。 在加热器的加热半径范围内的每个房屋都可以获得供暖。 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。 示例 1: 输入: houses = [1,2,3], heaters = [2] 输出: 1 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。 示例 2: 输入: houses = [1,2,3,4], heaters = [1,4] 输出: 1 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。 示例 3： 输入：houses = [1,5], heaters = [2] 输出：3
解题思路🧤：
根据题目的意思就是找出每个房子落在哪个加热器之间，然后比较离他们较近的一个 思路就是用双指针 从左边开始一起移动
代码附上🧤：
class Solution {
public int findRadius(int[] houses, int[] heaters) {
// 其实就是要找每个房子落在哪个加热器之间，然后比较他们俩之中更近的那一侧。可以使用二分，也可以使用双指针，从头开始一起移动。
int res=0; //加热半经
for(int i=0;i<houses.length;i++){
int min=Integer.MAX_VALUE;
for(int j=0;j<heaters.length;j++){
min=Math.min(min,Math.abs(houses[i]-heaters[j]));
}
res=Math.max(res,min); //取所以房子中最大的半经
}
return res;
}
}面试16.06 题目描述🧤：
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差 示例： 输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8} 输出：3，即数值对(11, 8)
解题思路🧤：
这道题跟上面一道非常的相似 需要注意的就是数据的溢出 所以需要转化成long类型 特判差值为0的时候
代码附上🧤:
class Solution {
public int smallestDifference(int[] a, int[] b) {
//首先将两组数组排序
Arrays.sort(a);
Arrays.sort(b);
int i=0,j=0;
long min=Long.MAX_VALUE;
while(i<a.length&&j<b.length){
if(a[i]==b[j]) return 0;
else if(a[i]>b[j]){
min=Math.min(min,(long)a[i]-(long)b[j]);
j++;
}else{
min=Math.min(min,(long)b[j]-(long)a[i]);
i++;
}
}
return (int)min;
}
}题目 | 难度 |
|---|---|
2000. 反转单词前缀 | ★☆☆☆ |
917. 仅仅反转字母 | ★☆☆☆ |
475. 供暖器 | ★★☆☆ |
面试题 16.06. 最小差 | ★★☆☆ |
以上就是小王带给大家几道经典的双指针类型的题目 希望友友们统统 A掉
腾讯云开发者
