算法思想
双指针
167. 两数之和 II - 输入有序数组
双指针的典型用法
- 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
- 如果 sum > target，移动较大的元素，使 sum 变小一些；
- 如果 sum < target，移动较小的元素，使 sum 变大一些。
数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers==null)return null;
int i=0;
int j=numbers.length-1;
while(i<=j){
if(numbers[i]+numbers[j]>target)j--;
else if(numbers[i]+numbers[j]<target)i++;
else return new int[]{i+1,j+1};
}
return null;
}
}
633. 平方数之和
题目描述：判断一个非负整数是否为两个整数的平方和。
可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。
本题和 167. Two Sum II - Input array is sorted 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。
本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。
因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。
class Solution {
public boolean judgeSquareSum(int c) {
if(c<0) return false;
int i=0, j=(int)Math.sqrt(c);
while(i<=j){
int powSum =i*i+j*j;
if(powSum==c) return true;
else if(powSum>c) j--;
else i++;
}
return false;
}
}
345. 反转字符串中的元音字母
集合Set添加多个元素
方一
Integer[] x=new Integer[]{4,6,9,10};
Set<Integer> set = new HashSet<>() ;
Collections.addAll(set,x);
for(Integer ele:set){
System.out.println(ele);
}
方二
Set<Integer> set = new HashSet<>(Arrays.asList(4,6,9,10)) ;
使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。
为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。
- 时间复杂度为 O(N)：只需要遍历所有元素一次
- 空间复杂度 O(1)：只需要使用两个额外变量
class Solution {
public static HashSet<Character> set_char =new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
public String reverseVowels(String s) {
if (s == null) return null;
int i=0, j=s.length()-1;
char[] arr=s.toCharArray();
while(i<=j){
if(!set_char.contains(arr[i]))i++;
else if(!set_char.contains(arr[j]))j--;
else {
char temp=arr[i];
arr[i++]=arr[j];
arr[j--]=temp;
}
}
return new String(arr);
}
}
680. 验证回文字符串 Ⅱ
本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。
在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。
在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。
class Solution {
public boolean validPalindrome(String s) {
for(int i=0, j=s.length()-1; i<j; i++, j--){
if(s.charAt(i)!=s.charAt(j)){
return isPalindrome(s,i,j-1) || isPalindrome(s, i+1, j);
}
}
return true;
}
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
}
88. 合并两个有序数组
需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1=m-1, index2=n-1;
int indexMerge = m+n-1;
while(index1>=0 || index2>=0){
if(index1<0){
nums1[indexMerge--]=nums2[index2--];
}else if(index2<0){
nums1[indexMerge--]=nums1[index1--];
}else if (nums1[index1] > nums2[index2]) {
nums1[indexMerge--] = nums1[index1--];
} else {
nums1[indexMerge--] = nums2[index2--];
}
}
}
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len1 = m - 1;
int len2 = n - 1;
int len = m + n - 1;
while(len1 >= 0 && len2 >= 0) {
// 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码
nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
}
// 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
}
}
141. 环形链表
使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode cur1=head;
ListNode cur2=head.next;
while(cur1!=null && cur2 != null && cur2.next != null){
if (cur1 == cur2) {
return true;
}
cur1=cur1.next;
cur2=cur2.next.next;
}
return false;
}
}
524. 通过删除字母匹配到字典里最长单词
class Solution {
int max=-1;
String result="";
public String findLongestWord(String s, List<String> d) {
for(String str: d){
int j=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==str.charAt(j)){
j++;
if(j==str.length()){
break;
}
}
}
if(j==str.length()&&str.length()>max){
max=str.length();
result=str;
}
if(j==str.length()&&str.length()==max){
if(result.compareTo(str)>0){
result=str;
}
}
}
return result;
}
}
class Solution {
public String findLongestWord(String s, List<String> d) {
String str="";
for(String sstr:d){
for(int i=0,j=0;i<s.length()&&j<sstr.length();i++){
if(s.charAt(i)==sstr.charAt(j)) j++;
if(j==sstr.length()){
if(sstr.length()>str.length()||(sstr.length()==str.length()&&str.compareTo(sstr)>0))
str=sstr;
}
}
}
return str;
}
}