LeetCode题解_双指针
双指针
leetcode_167_middle
-
问题描述
给定非递减顺序排列的整数数组 numbers 和目标数 target ，找出相加满足 target 的两个整数下标，答案唯一且元素不重复输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] -
解法：双指针算法
建立两个指针(索引) i、j ，i从前往后搜索，j从后往前搜索，当 sum > target 时 j 往前，sum < target 时 i 往后，直到成功或不存在。
-
原理
双指针算法常用在有序数组的查找中，相比暴力解法采用两层循环时间复杂度 o($n^2$) ，双指针只遍历一遍时间复杂度为 o($n$)。
算法的原理在于在有序数组中，假定存在符合答案的下标 i,j ，那么如果 sum > target ，只有可能是 j 往前移动，而不是 i 往前，因为 i 由最小的数往后移动而来，说明 i 前面的数已经不满足 target 要求；同理如果 sum < target ，i 往后，因为 j 由最大的数往前移动而来，说明 j 后面的数已经不满足 target 要求。
-
代码
public int[] twoSum(int[] numbers, int target) { int[] res = new int[2]; int i = 0; int j = numbers.length - 1; while (i < j) { if (numbers[i] + numbers[j] == target) { res[0] = i + 1; res[1] = j + 1; return res; } if (numbers[i] + numbers[j] > target) { j--; continue; } else { i++; continue; } } return null; }
leetcode_633_middle
-
问题描述
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 $a^{2} + b^{2} = c$输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5 -
解法：双指针算法
-
原理
该题是寻找从0-sqrt(c)的满足平方和的两个整数a,b。隐含条件是 0-sqrt(c)为递增有序数组，因此可以用双指针算法。
题目默认的范围是0 <= c <= $2^{31} - 1$,在int范围之内，但是如果定义i,j为int型会有样例
c=2147483600不通过，这是因为存在a=297，b=46340，使得平方和2147483809超过了int范围，因此需要使用long型。 -
代码
public boolean judgeSquareSum(int c) { //开根号转long自动取整,防止溢出 long i=0,j=(long)Math.sqrt(c*1.0); while(i<=j) { if(i*i+j*j==c) { System.out.println(i+"/"+ j); return true; } if(i*i+j*j>c) { j--; } else { i++; } } return false; }
leetcode_345_easy
-
问题描述
给你一个字符串s，仅反转字符串中的所有元音字母，并返回结果字符串。元音字母包括'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。输入：s = "hello" 输出："holle" -
解法：双指针算法
-
原理
采用双指针算法，当头尾分别找到符合的元音字符时，交换他们的位置
-
代码
char[] compares= {'a','e','i','o','u','A','E','I','O','U'}; private boolean compare(char c) { for(char comp:compares) { if(comp==c) return true; } return false; } public String reverseVowels(String s) { String rever_s = ""; char[] tmp =s.toCharArray(); int i = 0, j = s.length() - 1; while(i<j) { while (i < j && (!compare(tmp[i]) || !compare(tmp[j]))) { if (compare(tmp[i])) { j--; } else { i++; } } if(i<j) { //swap char c=tmp[i]; tmp[i]=tmp[j]; tmp[j]=c; i++;j--; } } rever_s=String.valueOf(tmp); return rever_s; }
leetcode_680_easy
-
问题描述
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。输入: s = "abca" 输出: true 解释: 你可以删除c字符。 -
解法：双指针算法
-
原理
采用双指针算法，头尾两字符相等则移动指针。
问题的关键在于当字符不匹配时，删除头或者尾的字符都可能出现回文字符串，因此两种情况都应该进行尝试，例如
"cupxpucu"，删头会出现暂时的字符匹配，删尾才是正确答案。 -
代码
public boolean validPalindrome(String s) { char[] tmp = s.toCharArray(); int i = 0, j = s.length() - 1; while (i < j) { if (tmp[i] == tmp[j]) { i++; j--; } else return validDeletedPalindrome(tmp, i + 1, j) || validDeletedPalindrome(tmp, i, j - 1); } return true; } public boolean validDeletedPalindrome(char[] tmp, int i, int j) { while (i < j) { if (tmp[i] == tmp[j]) { i++; j--; } else return false; } return true; }