双指针

双指针的应用场景比较明显。

1,两数之和||-输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> twoSum(vector<int>& numbers, int target) {
/**
思路:左右夹(题目说了有且仅有唯一的答案,那就少了一些判断了)
*/
int left = 0 , right = numbers.size()-1;
vector<int> result(2);
while(left<right)
{
if(numbers[left]+numbers[right] == target)
break;
if(numbers[left]+numbers[right] < target)
{
left++;
}
else
{
right--;
}
}
//因为说了有唯一的解,这里就不判断了
result[0] = left+1;
result[1] = right+1;
return result;
}

2,平方数之和

给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c。
示例1:
输入: 5
输出: True
解释: 1 1 + 2 2 = 5
示例2:
输入: 3
输出: False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool judgeSquareSum(int c) {
/**
也是左右夹
*/
int left = 0 ,right = sqrt(c);//这里还是加上sqrt好
while(left<=right)
{
if(left*left+right*right == c)
return true;
else if(left*left+right*right < c)
left++;
else
right--;
}
return false;
}

3,反转字符串中的元音字母

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
示例 1:
给定 s = “hello”, 返回 “holle”.
示例 2:
给定 s = “leetcode”, 返回 “leotcede”.
注意:
元音字母不包括 “y”.

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
bool check(char c1)
{
char cc[] ={'a','e','i','o','u','A','E','I','O','U'};
for(auto temp:cc)
{
if(temp == c1)
return true;
}
return false;
}
string reverseVowels(string s) {
int left = 0 ,right = s.size()-1;
while(left<right)
{
while(left<right&&!check(s[left]))
left++;
while(left<right&&!check(s[right]))
right--;
if(left<right)
{
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
return s;
}

4,验证回文字符串||

给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: “aba”
输出: True
示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

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
bool check(string s,int left, int right)
{
while(left<right)
{
if(s[left]!=s[right])
return false;
left++;
right--;
}
return true;
}
bool validPalindrome(string s) {
/**
最多删一个字符,,所以可以两边夹
*/
int left =0, right =s.length()-1;
while(left<right)
{
if(s[left]!=s[right])
return check(s,left+1,right)||check(s,left,right-1);
left++;
right--;
}
return true;
}

5,合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
来源: https://leetcode-cn.com/problems/merge-sorted-array/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
/**
从后面排序移动的会更少
*/
int index = m+n-1;
m--;
n--;
while(m>=0&&n>=0)
{
if(nums1[m]>nums2[n])
nums1[index--] = nums1[m--];
else
nums1[index--] = nums2[n--];
}
while(n>=0)
{
nums1[n]=nums2[n];
n--;
}
}

6,环形链表

给定一个链表,判断链表中是否有环。
进阶:
你能否不使用额外空间解决此题?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool hasCycle(ListNode *head) {
/**
快慢指针
*/
if(head == NULL|| head->next == NULL) return false;
ListNode* left =head,*right=head->next;
while(left!=NULL&&right!=NULL&&right->next!=NULL)
{
if(left == right)
return true;
left=left->next;
right=right->next->next;
}
return false;
}

7,单词中的最长子序列

Input:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]
Output:
“apple”
题目描述:删除 s 中的一些字符,使得它构成字符串列表 d 中的一个字符串,找出能构成的最长字符串。如果有多个相同长度的结果,返回按字典序排序的最大字符串。

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
string findLongestWord(string s, vector<string>& d) {
/**
原本想的是d排序,然后在s中查找是否存在该序列
*/
auto comp = [](const string& p1, const string& p2){
return p1.length()>p2.length()?true:(p1.length()==p2.length()?p1<p2:false);
};
sort(d.begin(), d.end(), comp);
for(auto& temp : d)
{
int indexs=0,indext=0;
while(indexs<s.size()&&indext<temp.size())
{
if(s[indexs]==temp[indext])
{
indexs++;
indext++;
}
else
{
indexs++;
}
}
if(indext==temp.size())
return temp;
}
return "";
}