今天是第一天刷Leetcode，总题量：4，模块：双指针
26、已经排序的数组去除重复的元素 public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int i = 0; for (int j = 1; j < nums.length; j++) { if (nums[i] != nums[j]) { i++; nums[i] = nums[j]; } } return i + 1; } 总结：双指针的妙处就在于怎么能够i,j根据不同的场景进行最少的遍历获得正确结果。判断输出是否为空也要考虑到。刷题给我的感受就是，考虑空间复杂度和时间复杂度比较重要。 345、反转字符串中的元音字母 方法一： public String reverseVowels(String s) { char[] arr = s.toCharArray(); int n = arr.length; int l = 0; int r = n - 1; while (l < r) { while (l < n && !isVowel(arr[l])) { l++; } while (r >= 0 && !isVowel(arr[r])) { r–; } if (l >= r) { break; } swap(arr, l, r); l++; r–; } return new String(arr); } private void swap(char[] arr, int l, int r) { char temp = arr[l]; //注意是char类型 arr[l] = arr[r]; arr[r] = temp; } private boolean isVowel(char ch) { return ch == ‘a’ || ch == ‘e’ || ch == ‘i’ || ch == ‘o’ || ch == ‘u’ || ch == ‘A’ || ch == ‘E’ || ch == ‘I’ || ch == ‘O’ || ch == ‘U’; } 总结：这个方法利用双指针一前一后查找是否有元音字母，查找到了就比没有查找的时候多了个swap。 处理字符串问题的时候通常String s 要 s.toCharArray这样内存占用更少 方法二： public final static HashSet vowels = new HashSet<>( Arrays.asList(‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’)); public String reverseVowels2(String s) { if (s == null) return null; int i = 0, j = s.length() - 1; char[] result = new char[s.length()]; while (i < j) { char ci = s.charAt(i); char cj = s.charAt(j); if (!vowels.contains(ci)) { result[i++] = ci; } else if (!vowels.contains(cj)) { result[j–] = cj; } else { result[i++] = cj; result[j++] = ci; } return new String(result); } } 总结： 1.基本判断 if (s == null) return null; 2.元音数组用了HashSet vowels,判断的时候 vowels.contains(cj) //cj是char类型 3.char ci = s.charAt(i);，把String s 中的元素取出为char类型
633、你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。 方法一： public class SumofSquareNumbers633 { public boolean judgeSquareSum(int c ){//根据题目的提示，使用boolean的函数类型 for(long a = 0; a * a <= c; a++){ int b = c - (int)(a * a ); if(binary_search(0,b,b)) return true; } return false; } private boolean binary_search(long s, long e , int n) { if(s > e) return false; long mid = s + (e-s)/2; if(mid * mid == n) return true; if(mid * mid > n) return binary_search(s, mid-1,n); return binary_search(mid+1, e, n); } 总结：这个方法使用二分法，可以了解下二分法的步骤，注意要用long类型不然会溢出，s是范围的开头，e是二分法的结尾；二分法的精髓就在于使用递归的方式
方法二： public boolean judgeSquareSum2(int c ){ for(long a1 = 0; a1 * a1 <= c; a1++){ double b = sqrt(c-a1*a1); if(b==(int)b) return true; } return false; } 总结：这道题主要是使用了sqrt，思想跟方法一其实是一样的，关键的在于if(b==int(b))
方法三： public boolean judgeSquareSum3(int c ){ if(c<0) return false; int i = 0; int j = (int) sqrt©; while (i <= j){ if(ii == c- jj) //这里是全等于 return true; else if(c - jj <i i) j–; else i++; } return false; } 总结：相当于在[0,int(sqrt©)]的范围里寻找是否有i满足ii == c - jj
167、给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数 public class TowSum { public int[] twoSum(int[] numbers,int target){ if(numbers == null) return null; 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){ i++; }else{ j–; } } return null; } } 总结：使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。 如果两个指针指向元素的和 sum == target，那么得到要求的结果；如果 sum > target，移动较大的元素，使 sum 变小一些；如果 sum < target，移动较小的元素，使 sum 变大一些。数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。
今天双指针大多数题目都是两个指针i,j分别处于不同的位置，根据题目对i,j进行操作如果结果大于目标了则把指向小的数值的i++；反之j–。 最应该考虑的就是如何降低时间复杂度和空间复杂度。
