1、两数之和 || ->167.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
- 题目描述：在有序数组中找出两个数，使它们的和为 target
- 题解：使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
- 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
- 如果 sum > target，移动较大的元素，使 sum 变小一些；
- 如果 sum < target，移动较小的元素，使 sum 变大一些。
- 数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。
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){
i++;
}else{
j--;
}
}
return null;
}
2、平方数之和->633.
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
- 题目描述：判断一个非负整数是否为两个整数的平方和。
- 题解：可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。
- 本题和上面那道题类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。
- 本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。
- 复杂度分析：因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。
public boolean judgeSquareSum(int c) {
int i=0,j=(int)Math.sqrt((double)c);
while(i<=j){
if((i*i+j*j)==c){
return true;
}else if((i*i+j*j)>c){
j--;
}else{
i++;
}
}
return false;
}
3、反转字符串中的元音字符->345.
Given s = "leetcode", return "leotcede".
- 题解：使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。
- 时间复杂度为 O(N)：只需要遍历所有元素一次
- 空间复杂度 O(1)：只需要使用两个额外变量
- 注意：这里并不是位置对应的，如果是位置对应的可以使用两个StringBuilder来分别接收从小到大，和从大到小的两个字符串，最后反转一下拼接。
private static final HashSet<Character> vowel=new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
public String reverseVowels(String s) {
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(!vowel.contains(ci)){
result[i++]=ci;
}else if(!vowel.contains(cj)){
result[j--]=cj;
}else{
result[i++]=cj;
result[j--]=ci;
}
}
return new String(result);
}
4、回文字符串->680
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
- 题目描述：可以删除一个字符，判断是否能构成回文字符串。
- 所谓的回文字符串，是指具有左右对称特点的字符串，例如 "abcba" 就是一个回文字符串。
- 题解
- 本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。
- 注意：在出现不相等的时候不能简简单单的判断一下是否和下一个相等就可以了，还要判断后面全部的是不是相等，因此这里使用函数的调用比较好。
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;
}
5、归并两个有序数组->88
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
- 题目描述：把归并结果存到第一个数组上。。
- 题解
- 需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。
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--];
}
}
}
6、判断链表是否存在环->141
- 题解
- 使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode l1 = head, l2 = head.next;
while (l1 != null && l2 != null && l2.next != null) {
if (l1 == l2) {
return true;
}
l1 = l1.next;
l2 = l2.next.next;
}
return false;
}
