关键词:
(学习参考书:LeetCode101)
双指针
双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。也可以延申多个数组的多个指针。
若两个指针指向同一数组,遍历方向相同且不会相交,则称为滑动窗口,常用于区间搜索。
若两个指针指向同一个数组,但是遍历方向相反,则可用于进行搜索,被搜索的数组往往是排好序的。
力扣例题
167.两数之和2-输入有序数组
分析:
因为数组已经排好序,我们可以采用方向相反的双指针来寻找这两个数字,一个初始执行最小的元素,即数组最左边,向右遍历;一个初始执行最大的元素,即数组最右边。当两个指针相加等于目标数,那即为结果;当相加小于目标数,左指针++;当相加大于目标数,右指针++;
题解:
class Solution
public:
vector<int> twoSum(vector<int>& numbers, int target)
vector<int> result(2);
int left = 0,right = numbers.size()-1;
while(left<right)
if(numbers[left]+numbers[right]==target)
result[0] = left+1;
result[1] = right+1;
break;
else if(numbers[left]+numbers[right]<target)
++left;
else if(numbers[left]+numbers[right]>target)
--right;
return result;
;
class Solution
public int[] twoSum(int[] numbers, int target)
int result[] = new int[2];
int left = 0;
int right = numbers.length-1;
while(left<right)
if(numbers[left]+numbers[right]<target)
++left;
else if(numbers[left]+numbers[right]>target)
--right;
else
result[0] = left+1;
result[1] = right+1;
break;
return result;
633.平方数之和
分析:
与167题类似,同样使两个数位于可能得到答案的最前端和最末端。如果当前两数平方相加小于c,前数++;如果当前两数平方相加大于c,后数- -;
题解:
class Solution
public:
bool judgeSquareSum(int c)
long left = 0,right = (long)sqrt(c);//后数最大也不会超过c开平方
while(left<=right)
if(left*left+right*right==c)
return true;
else if(left*left+right*right<c)
++left;
else if(left*left+right*right>c)
--right;
return false;
;
class Solution
public boolean judgeSquareSum(int c)
long left = 0;
long right = (long) Math.sqrt(c);
while(left<=right)
long sum = left*left+right*right;
if(sum==c)
return true;
else if(sum<c)
++left;
else if(sum>c)
--right;
return false;
680.验证回文字符串2
分析:
在允许最多删除一个字符的情况下,同样可以使用双指针。初始化两个指针分别指向字符串的第一个字符和最后一个字符。同时向中间遍历,当遇到对称字符不相等时,则尝试删除左边或右边一个字符来继续遍历,如果不删除或删除一次后遍历至left==right,则说明可以为回文串;如果遍历任然有对称位置字符不等,则不能为回文串。
题解:
class Solution
public:
bool validPalindrome(string s)
int result = 1;
int left = 0,right = s.length()-1;
while(left<right)
if(s[left]==s[right])
left++;
right--;
else
return (checkPalindrome(s,left+1,right)|checkPalindrome(s,left,right-1));
return true;
bool checkPalindrome(string& s, int left, int right)
for (int i = left, j = right; i < j; ++i, --j)
if (s[i] != s[j])
return false;
return true;
;
class Solution
public boolean validPalindrome(String s)
int left = 0;
int right = s.length()-1;
while(left<right)
if(s.charAt(left)==s.charAt(right))
++left;
--right;
else
return checkPalindrome(s,left+1,right)||checkPalindrome(s,left,right-1);
return true;
public boolean checkPalindrome(String s,int left,int right)
while(left<right)
if(s.charAt(left)==s.charAt(right))
++left;
--right;
else
return false;
return true;
88.合并两个有序数组
分析:
因为两个数组有序,且nums1有预留空间。所以可以每次将nums1和nums2中最大的数比较,较大的一个放在nums1预留空间的最末尾,然后将nums1有效数字末尾指针和nums2末尾指针和nums1预留空间末尾指针前移一位,循环比较和存放。
当nums1比较完后,还需将nums2中剩余的数放入剩下的空间;当nums2比较完后,因为nums1原本的元素本来有序,所以不用再做其他处理。
题解:
class Solution
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
int last = m+n-1;
--m;
--n;
while(m>=0&&n>=0)
nums1[last--] = nums1[m]>nums2[n]?nums1[m--]:nums2[n--];
while(n>=0)
nums1[last--] = nums2[n--];
;
class Solution
public void merge(int[] nums1, int m, int[] nums2, int n)
int last = m+n-1;
--m;
--n;
while(m>=0&&n>=0)
nums1[last--] = nums1[m]>nums2[n]?nums1[m--]:nums2[n--];
while(n>=0)
nums1[last--] = nums2[n--];
142.快慢指针
分析:
对于链表找路问题,有一个通用的解法——快慢指针。即一个fast指针一个slow指针。每次fast前进2步,每次slow前进1步,如果存在环路则他们必定相遇。
相遇时的slow指针走过的路程为slow = a+b;
相遇时的fast指针走过的路程为fast = a+b+c+b;
因此差值运算可知:a = c;
因此将fast指针重新置为head,并每次走一步,则刚好在入环点与slow相遇。
题解:
/**
* Definition for singly-linked list.
* struct ListNode
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL)
* ;
*/
class Solution
public:
ListNode *detectCycle(ListNode *head)
ListNode *fast = head,*slow = head;
do
if(!fast||!fast->next)
return NULL;
fast = fast->next->next;
slow = slow->next;
while(fast!=slow);
fast = head;
while(fast!=slow)
fast = fast->next;
slow = slow->next;
return fast;
;
public class Solution
public ListNode detectCycle(ListNode head)
ListNode fast = head;
ListNode slow = head;
do
if (fast==null||fast.next==null)
return null;
fast = fast.next.next;
slow = slow.next;
while (fast!=slow);
fast = head;
while (fast!=slow)
fast = fast.next;
slow = slow.next;
return fast;
leetcode刷题之双指针(c++&java)(代码片段)
...;则可用于进行搜索,被搜索的数组往往是排好序的。力扣例题167.两数之和2-输入有序数组分析:因为数组已经排好序,我们可以采用方向相反的双指针来寻找这两个数字,一个初始执行最小的元素,即数组最... 查看详情
力扣刷题之贪心算法(c++)(代码片段)
...求解每一个子集的最优解将局部最优解迭代成全局最优解力扣例题455.分发饼干分析:因为饥饿度最小的孩子最容易吃 查看详情
力扣刷题:三数之和(java实现)(代码片段)
题目:给你一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a+b+c=0?请你找出所有和为0且不重复的三元组。标签:数组,双指针,排序注意:答案中不可以包... 查看详情
力扣刷题:填充每个节点的下一个右侧节点指针(java实现)(代码片段)
题目:给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:structNodeintval;Node*left;Node*right;Node*next;填充它的每个next指针,让这个指针指向其下一个右侧节点。如果... 查看详情
leetcode刷题之贪心算法(c++&java)(代码片段)
...求解每一个子集的最优解将局部最优解迭代成全局最优解力扣例题455.分发饼干分析:因为饥饿度最小的孩子最容易吃 查看详情
力扣刷题:括号生成(java实现)(代码片段)
数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。有效括号组合需满足:左括号必须以正确的顺序闭合。示例1:输入:n=3输出:["((()))","(()())",&... 查看详情
力扣刷题:合并区间(java实现)(代码片段)
题目描述:以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。示例1:输入:in... 查看详情
力扣刷题每日打卡(代码片段)
力扣刷题:重新排列数组:/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情
力扣刷题每日打卡(代码片段)
力扣刷题:重新排列数组:/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情
力扣刷题:岛屿数量(java实现)(代码片段)
给你一个由'1'(陆地)和'0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以... 查看详情
力扣刷题:全排列(java实现)(代码片段)
题目:给定一个不含重复数字的数组nums,返回其所有可能的全排列。你可以按任意顺序返回答案。示例1:输入:nums=[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例2:输入:nums=[0,1]输出... 查看详情
力扣刷题:字母异位词分组(java实现)(代码片段)
题目:给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母都恰好只用一次。示例1:输入:strs=["eat... 查看详情
力扣刷题:寻找峰值(java实现)(代码片段)
题目:峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。你可以假设nums[-1]=nums[n]=... 查看详情
力扣刷题:单词搜索(java实现)(代码片段)
题目:给定一个mxn二维字符网格board和一个字符串单词word。如果word存在于网格中,返回true;否则,返回false。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相... 查看详情
力扣刷题:四数之和(c#)(代码片段)
给你一个由n个整数组成的数组nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]](若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d<... 查看详情
力扣刷题:四数之和(c#)(代码片段)
给你一个由n个整数组成的数组nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]](若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d<... 查看详情
力扣刷题:四数之和(c++)(代码片段)
给你一个由n个整数组成的数组nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]](若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d<... 查看详情
力扣刷题:四数之和(c++)(代码片段)
给你一个由n个整数组成的数组nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]](若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d<... 查看详情