Leetcode | 双指针I 167/633/345/680 | java实现
167. 两数之和 II - 输入有序数组
问题描述
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例:
输入:
numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2 。
参考代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers == null) return null;
else{
int i = 0;
int j = numbers.length-1;
while(i<j){
if(numbers[i] + numbers[j] == target) return new int[]{i+1, j+1};
else{
if(numbers[i] + numbers[j] < target) i++;
else j--;
}
}
}
return null;
}
}NOTES
- 时间复杂度O(n)，空间复杂度O(1)
- 最初的思路是两层for循环嵌套，显然采用双指针将大大降低时间复杂度
633. 平方数之和
问题描述
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
示例1:
输入: 5 输出: True 解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3 输出: False
参考代码
class Solution {
public boolean judgeSquareSum(int c) {
if(c<0) return false;
else{
int i = 0;
int j = (int)Math.sqrt(c);
while(i<=j){
int temp = i*i + j*j;
if(temp == c) return true;
else if(temp<c) i++;
else if(temp>c) j--;
}
return false;
}
}
}NOTES
- 时间复杂度O(n)，空间复杂度O(1)
- 对c开根号，穷举小于根号c的所有数
而不是穷举小于c的所有数 - 采用双指针，若结果小于c，则左指针向右移；若结果大于c，则右指针向左移
- 应考虑到c为0和1的情况，所以左指针应从0开始
- while的循环条件应为左指针<=右指针，若仅仅为"<"，就没有考虑到c=2的情况
345. 反转字符串中的元音字母
问题描述
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
输入: “hello” 输出: “holle”
示例 2:
输入: “leetcode” 输出: “leotcede”
说明:
元音字母不包含字母"y"。
参考代码
class Solution {
//private static final HashSet<String> vowels = new HashSet<>("aeiouAEIOU");
// private final static HashSet<Character> vowels = new HashSet<>(
// Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
public boolean isVowel(char c){
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U')
return true;
else return false;
}
public String reverseVowels(String s) {
if(s==null) return null;
else{
char[] result = new char[s.length()];
int i = 0;
int j = s.length()-1;
while(i<=j){
char ci = s.charAt(i);
char cj = s.charAt(j);
if(!isVowel(ci)){
result[i++] = ci;
}
else if(!isVowel(cj)){
result[j--] = cj;
}
else{
result[i++] = cj;
result[j--] = ci;
}
}
return new String(result);
}
}
}NOTES
-
时间复杂度O(n)，空间复杂度O(1)
-
本题算法类似于快速排序算法，左右指针一首一尾向中移动，遇到元音字母停下交换位置
-
注意while的循环条件仍为左指针<=右指针
若为“<”，结果如下：输入 “hello”
输出 “hol\u0000e”
预期结果 “holle”Step 左指针 i 右指针 j 操作 Result Explain 1 0 4 Move “h _ _ _ _” 2 1 4 Exchange “h o _ _ e” ij都遇到元音字母，交换 3 2 3 Move “h o l _ e” 4 3 3 跳出循环 “h o l _ e” 不满足 i < j -
另外不要忘记大写的元音字母！
680. 验证回文字符串 Ⅱ
问题描述
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: “aba”
输出: True
示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
参考代码
class Solution {
//判断子字符串是否为回文
public boolean isPalindrome(String s){
if(s==null) return false;
else{
int i = 0;
int j = s.length()-1;
while(i<j){
if(s.charAt(i) == s.charAt(j)){
i++;
j--;
}
else return false;
}
return true;
}
}
public boolean validPalindrome(String s) {
int i = 0;
int j = s.length()-1;
while(i<j){
if(s.charAt(i) != s.charAt(j))
return isPalindrome(s.substring(i+1, j+1)) ||
isPalindrome(s.substring(i, j));
else{
i++;
j--;
}
}
return true;
}
}NOTES
-
时间复杂度O(n)，空间复杂度O(1)
-
本题算法为左右指针一首一尾，若相等则向中间移动，若不等则判断字符串的 i+1 到 j 的子字符串是否为回文 以及 i 到 j-1 的子字符串是否为回文。
按照逻辑，调用substring方法的参数应为 (i+1, j) 和 (i, j-1)，
但是 注意 substring()方法 的参数：- beginIndex – 起始索引（包括）, 索引从 0 开始。
- endIndex – 结束索引（不包括）。
因此代码如下：if(s.charAt(i) != s.charAt(j)) return isPalindrome(s.substring(i+1, j+1)) || isPalindrome(s.substring(i, j));
说明
语言：Java
如有错误，还望指正