五月集训（第5天）——双指针

前言：

五月集训，前面为学习内容，想要一起学习的可以看一看，最后的才是五月集训每天的作业。

一、知识点

双指针主要应用于数组以及链表问题中；
对于数组而言，就是定义两个指针，相向移动，不断进行问题的求解和判断，最终得到问题的解。
对于链表而言，就是定义一快一慢（即快慢针）两个指针，不断进行迭代求解问题。

二、课堂习题

这里的题均出自《算法零基础100讲》
我们先对数组的双指针问题进行练习，在数组中，双指针相向移动时，可能是同速的，也可能是不同速的，先做几道不同速的题。
344. 反转字符串

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

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

i指针放在头部，j指针放在尾部，相向移送的同时不断交换元素即可。

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

2108. 找出数组中的第一个回文字符串

给你一个字符串数组 words ，找出并返回数组中的 第一个回文字符串 。如果不存在满足要求的字符串，返回一个 空字符串 “” 。

回文字符串 的定义为：如果一个字符串正着读和反着读一样，那么该字符串就是一个 回文字符串 。

将每个字符串提取出来，然后依次做回文串判断。

class Solution {    public String firstPalindrome(String[] words) { for(String str : words){     int i = 0,j = str.length()-1;     boolean f = true;;     while(i < j){  if(str.charAt(i) == str.charAt(j)){      ++i;--j;  }else{      f = false;      break;  }     }      if(f){  return str;     } } return "";    }}

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” 。

遍历一遍字符串的元素，找到第一个目标字符小标j，然后i=0与j相向移动反转字符串前缀。

class Solution {    public String reversePrefix(String word, char ch) { char[] words = word.toCharArray(); int i = 0,j = 1; for(j = 0;j < words.length;++j){     if(words[j] == ch){  break;     } } if(j == words.length){     return word; } while(i < j){     char temp = words[i];     words[i] = words[j];     words[j] = temp;     ++i;--j; } return new String(String.valueOf(words));    }}

151. 颠倒字符串中的单词

给你一个字符串 s ，颠倒字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串
s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = “the sky is blue” 输出：“blue is sky the”
示例 2：
输入：s = " hello world " 输出：“world hello” 解释：颠倒后的字符串中不能存在前导空格和尾随空格。
示例3：
输入：s = “a good example” 输出：“example good a”
解释：如果两个单词间有多余的空格，颠倒后的字符串需要将单词间的空格减少到仅有一个。

将解题过程分为三个部分：
将整体字符串翻转，正常反转就可以；
每个单词进行翻转，需要双指针，依次找到每个单词的开头和结尾，并进行翻转；
删除多余的空格。

class Solution {    public String reverseWords(String s) { char[] words = s.toCharArray(); int i = 0,j = words.length-1; reverse(words,i,j); word_reverse(words); return delete(words);    }    public void reverse(char[] words,int i,int j){ while(i < j){     char temp = words[i];     words[i] = words[j];     words[j] = temp;     ++i;--j; }    }    public void word_reverse(char[] words){ int n = words.length; int i = 0,j = 0; while(j < n){     while(i < n && words[i] == ' '){  ++i;     }     j = i;     while(j < n && words[j] != ' '){  ++j;     }     reverse(words,i,j-1);     i = j; }    }    public String delete(char[] words){ int n = words.length; int i = 0,j = 0; while(j < n){     while(j < n && words[j] == ' '){  ++j;     }     while(j < n && words[j] != ' '){  words[i++] = words[j++];     }     while(j < n && words[j] == ' '){  ++j;     }     if(j < n){  words[i++] = ' ';     } } return String.valueOf(words).substring(0,i);    }}

三、作业

917. 仅仅反转字母
167. 两数之和 II - 输入有序数组
165. 比较版本号
443. 压缩字符串
解题思路：
1.
（1）定义i,j两个指针，i指向字符串开头，j指向结尾；
（2）当指向的元素不是字母是，不断相向移动；
（3）将字母交换。
2.
(1)定义两个指针i,j指向数组的两端；
(2)和等于目标值，则返回下标+1，大于目标值–j,小于目标值++i。
3.
(1)定义两个指针分别指向两个版本号；
(2)以’.'为分界，进行计数；
(3)两个版本号不相等则按照题意返回答案。
4.
(1)定义两个指针i,j一个记录一种字符的开始，一个记录结束；
(2)定义一个下标指针用来放改变后的元素；
(3)种类不同时将这种元素放入数组，并判断重复次数是否>1，是的话将数字放进去。
需要注意，数字有可能>10,需要取余循环放入。
代码以及结果：
1.

class Solution {    public String reverseOnlyLetters(String s) { char[] words = s.toCharArray(); int n = words.length; int i = 0,j = n - 1; while(i < j) {     while (i < j && !Character.isLetter(words[i])) i++;     while (i < j && !Character.isLetter(words[j])) j--;     if (i < j) {  char temp = words[i];  words[i++] = words[j];  words[j--] = temp;     } } return String.valueOf(words);    }}

2.

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){  --j;     }else{  ++i;     } } return null;    }}

3.

class Solution {    public int compareVersion(String version1, String version2) { int n1 = version1.length(),n2 = version2.length(); int i = 0,j = 0; while(i < n1 || j < n2){     int temp1 = 0;     while(i < n1 && version1.charAt(i) != '.'){  temp1 = temp1*10 + version1.charAt(i) - '0';  ++i;     }     ++i;     int temp2 = 0;     while(j < n2 && version2.charAt(j) != '.'){  temp2 = temp2*10 + version2.charAt(j) - '0';  ++j;     }     ++j;     if(temp1 != temp2){  return temp1 > temp2 ? 1 : -1;     } } return 0;    }}

4.

class Solution {    public int compress(char[] chars) { int n = chars.length; int i = 0, j = 0; int index = 0; while(j < n){     j = i;     while(j < n && chars[i] == chars[j]){  ++j;     }     int cnt = j - i;     chars[index++] = chars[i];     if(cnt > 1){  int start = index,end = index;  while(cnt != 0){      chars[end++] = (char)((cnt % 10) + '0');      cnt /= 10;  }  reverse(chars,start,end-1);  index = end;     }     i = j; } return index;    }    void reverse(char[] chars, int start, int end) { while (start < end) {     char t = chars[start];     chars[start] = chars[end];     chars[end] = t;     start++; end--; }    }}

四、总结

对于算法的掌握还是不够熟练，需要进行反复训练！
另外，剩下的课堂训练题目留到下个月的集训啦(●ˇ∀ˇ●)