双指针
双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。
167. 两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
1
2
3
| 输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2
|
leetcode原题地址
解答
我们使用两个指针，一个指针从数组的左边开始，一个指针从数组的右边开始。
如果两个指针所指数据等于target，那么就直接返回；如果小于target，那么左指针右移动；
如果大于target，则右指针左移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int[] twoSum(int[] numbers, int target) {
int minIndex=0;
int maxIndex=numbers.length-1;
int[] result=new int[2];
while (minIndex<maxIndex){
int sum=numbers[minIndex]+numbers[maxIndex];
if(sum==target){
result[0]=++minIndex;
result[1]=++maxIndex;
return result;
}else if(sum>target){
maxIndex--;
}else{
minIndex++;
}
}
return result;
}
|
633.平方数之和
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
示例1:
1
2
3
| 输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
|
示例2:
leetcode原题地址
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public boolean judgeSquareSum(int c) {
int a=0;
int b=(int) Math.sqrt(c);
while (a<=b){
int tmp=a*a+b*b;
if(tmp==c){
return true;
}else if(tmp<c){
a++;
}else {
b--;
}
}
return false;
}
|
345. 反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
示例 2:
1
2
| 输入: "leetcode"
输出: "leotcede"
|
说明:
元音字母不包含字母”y”。
leetcode原题地址
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| private HashSet<Character> set=new HashSet<>(
Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
public String reverseVowels(String s) {
char[] chars = s.toCharArray();
int left=0;
int right=chars.length-1;
while (left<right){
while (right>=0&&!set.contains(chars[right])){
right--;
}
while (left<chars.length&&!set.contains(chars[left])){
left++;
}
if(left<right){
swap(chars,left,right);
left++;
right--;
}
}
return new String(chars);
}
private void swap(char[] chars,int a,int b){
char tmp=chars[a];
chars[a]=chars[b];
chars[b]=tmp;
}
|
680 验证回文字符串Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
示例 2:
1
2
3
| 输入: "abca"
输出: True
解释: 你可以删除c字符。
|
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
leetcode原题地址
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public boolean validPalindrome(String s) {
int start=0;
int end=s.length()-1;
while (start<end){
if(s.charAt(start)!=s.charAt(end)){
return isPalinerome(s,start,end-1)||isPalinerome(s,start+1,end);
}
start++;
end--;
}
return true;
}
private boolean isPalinerome(String str,int start,int end){
while (start<end){
if(str.charAt(start)!=str.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
}
|
141. 环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
1
2
3
| 输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
|
示例 2：
1
2
3
| 输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
|
示例 3：
1
2
3
| 输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
|
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
leetcode原题地址
解法
快慢指针法，一个指针一次只走一步，另一个指针一次走2步。如果链表中有环，那么它们一定会相遇。
1
2
3
4
5
6
7
8
9
10
11
12
| public boolean hasCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while (fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(fast==slow){
return true;
}
}
return false;
}
|
524.通过删除字母匹配到字典中最长单词
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
1
2
3
4
5
| 输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"
|
示例 2:
1
2
3
4
5
| 输入:
s = "abpcplea", d = ["a","b","c"]
输出:
"a"
|
说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。
leetcode原题地址
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public String findLongestWord(String s, List<String> d) {
String longestWord = "";
for (String target : d) {
int l1 = longestWord.length(), l2 = target.length();
if (l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)) {
continue;
}
if (isValid(s, target)) {
longestWord = target;
}
}
return longestWord;
}
private boolean isValid(String s,String target){
int i = 0, j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}
|