1.两数之和+167. 两数之和 II+11. 盛最多水的容器+240. 搜索二维矩阵 II+1099. 小于 K 的两数之和+5. 最长回文子串+15. 三数之和...
·
零
所有代码都AC了
^ _ ^
1. 两数之和
经典题永不过时
^ - ^
代码
//思路 :
//用unordered_map<int,int>mp记录已经遍历的数组元素
//如果已经遍历的它的另一半,直接返回
//没有就记录遍历的元素
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>mp;
for(int i=0;i<nums.size();++i){
if(mp.find(target-nums[i])==mp.end() ){
mp[nums[i]]=i;
}else{
return {mp[target-nums[i]],i};
}
}
return {};
}
};
167. 两数之和 II - 输入有序数组
哈希表法—时间复杂度O(n),空间复杂度O(n)
题目要求空间复杂度O(1),这个代码不满足
//思路 :
//注意,题目保证只有一个解
//用一个unoordered_map<int,int>mp记录已经遍历的数组元素,<键(元素值),值(下标)>
//每遍历一个元素,看看有没有遍历到它的另一半
//如果遍历到了它的另一半,直接返回
//没有遍历到就用unordered_map<int,int>mp记录遍历到了这个元素
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
unordered_map<int, int> mp;//记录已经遍历过的数组元素
for (int i = 0; i < numbers.size(); ++i) {//遍历数组
//下面我要看一下,有没有遍历它的另一半
if (mp.find(target - numbers[i]) == mp.end() ) {//如果它的另一半没有遍历到
mp[numbers[i]] = i;//记录遍历到的元素及其元素下标
} else {//如果遍历到了它的另一半
return {mp[target-numbers[i]]+1,i+1 };//返回,注意要保证顺序正确
}
}
return {};
}
};
双指针法—时间复杂度O(n),空间复杂度O(1)
满足题目要求空间复杂度O(1)
//思路 :
//初始 : 左指针指向0下标,右指针指向数组末尾下标
//双指针逼近,计算int sum=numbers[left]+numbers[right];
//如果sum<target,说明sum偏小,需要把sum变大,只有左指针向右移动才可以
//如果sum>target,说明sum偏大,需要把sum变小,只有右指针向左移动才可以
//如果sum==target,说明可以返回了(题目保证只有一个解)
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left=0;//初始化左指针
int right=numbers.size()-1;//初始化右指针
while(left<right){//循环停止条件
int sum=numbers[left]+numbers[right];//计算sum
if(sum<target){
left++;//sum<target,左指针右移
}else if(sum>target){
right--;//sum>target,右指针左移
}else{
return {left+1,right+1};//返回
}
}
return {};
}
};
11. 盛最多水的容器
双指针逼近法
//思路 :
//容器盛多少水是由min(height[left],height[right])决定的
//双指针逼近时,容器的宽一定是变小的,所以尽可能让高变大
//如果height[left]<height[right],只能left++才有可能找到更大的值
//如果height[right]>hieght[left],只能right--才有可能找到更大的值
class Solution {
public:
int maxArea(vector<int>& height) {
int left=0;
int ans=0;
int right=height.size()-1;
while(left<right){
ans=max( min(height[left],height[right] )*(right-left),ans) ;
if(height[left]<height[right]){
left++;
}else{
right--;
}
}
return ans;
}
};
240.搜索二维矩阵II
代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty() )return false;
for(int i=0;i<matrix.size();++i){
if(matrix[i][0]<=target&&matrix[i].back()>=target){//根据规律定位行
auto it=lower_bound(matrix[i].begin(),matrix[i].end(),target);//二分搜索定位列
if(it!=matrix[i].end()&&*it==target)return true;//找到了返回true
}
}
return false;
}
};
双指针解法
//思路 :
//每一行最后一个元素是每一行中的最大值
//每一列第一个元素是每一列中的最小值
//子矩阵边界是[左下角,右上角]
//i,j分别是右上角的行,列
//如果matrix[i][j]>target,说明这一列都大于target,j--
//如果matrix[i][j]<target,说明这一行都小于target,i++
//如果matrix[i][j]==target,返回true
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty() )return false;
int i=0,j=matrix[0].size()-1;
while(i<matrix.size()&&j>=0){
if(matrix[i][j]>target){
j--;
}else if(matrix[i][j]<target){
i++;
}else return true;
}
return false;
}
};
1099. 小于 K 的两数之和
暴力解法
//思路 :
//初始化ans=-1
//一个一个遍历计算sum
//如果sum<k,更新ans
class Solution {
public:
int twoSumLessThanK(vector<int>& nums, int k) {
int ans=-1;
for(int i=0;i<nums.size();++i){
for(int j=i+1;j<nums.size();++j){
int sum=nums[i]+nums[j];
if(sum<k){
ans=max(ans,sum);
}
}
}
return ans;
}
};
双指针解法
//双指针解法
//先排序
//初始化 left=0,right=nums.size()-1,ans=-1
//之后计算sum=nums[left]+nums[right]
//如果sum<k,就left++,更新ans
//如果sum>=k,就right--,
class Solution {
public:
int twoSumLessThanK(vector<int>& nums, int k) {
if(nums.empty() )return -1;
sort(nums.begin(),nums.end() );//排序
int ans=-1;
int left=0;
int right=nums.size()-1;
while(left<right){
int sum=nums[left]+nums[right];
if(sum<k){//sum<k,可以更新ans
left++;
ans=max(ans,sum);
}else{//sum>=k,要寻找更小的sum,right--
right--;
}
}
return ans;
}
};
5. 最长回文子串
中心拓展法
// 遍历s字符串
// 分别 以i为正中心 , 以i为偏左中心 返回最长回文串的边界[left,right]
// 更新答案
// 注意 :
// expanAroundCenter()函数return回文子串的边界[left,right],那么这个回文子串的长度是right-left+1
class Solution {
public:
pair<int, int> expandAroundCenter(int left, int right, string s) {
while (left >= 0 && right < s.size() &&
s[left] == s[right]) { // 如果不越界&&可以拓展
left--; // left向左扩展
right++; // right向右拓展
}
return {left + 1, right - 1}; // 返回回文子串[left,right]下标
}
string longestPalindrome(string s) {
string ans = ""; // 初始化ans
for (int i = 0; i < s.size(); ++i) {
auto it = expandAroundCenter(i, i, s); // 从正中心拓展
if (it.second - it.first + 1 > ans.size() ) { // 这个回文子串长度>ans.size()
ans = s.substr(it.first, it.second - it.first + 1); // 更新ans
}
if (i + 1 < s.size() && s[i] == s[i + 1]) { // 判断偏左中心有没有回文子串
it = expandAroundCenter(i, i + 1, s); // 从偏左的中心扩展
if (it.second - it.first + 1 > ans.size() ) { // 这个回文子串长度>ans.size()
ans = s.substr(it.first, it.second - it.first + 1); // 更新ans
}
}
}
return ans; // 返回ans
}
};
中心扩展法(加强版)
class Solution {
public:
pair<int, int> expandAroundCenter(int left, int right, string s) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return {left + 1, right - 1}; // 返回字符串[起始,结束]下标
}
string longestPalindrome(string s) {
if (s.empty())
return s;
string ans = "";
// update函数
auto update = [&](pair<int, int>& it) {
if (it.second - it.first + 1 > ans.size()) {
ans = s.substr(it.first, it.second - it.first + 1);
}
return;
};
// 中心扩展法
for (int i = 0; i < s.size(); ++i) {
auto it = expandAroundCenter(i, i, s);
update(it);
if (i + 1 < s.size() && s[i] == s[i + 1]) {//注意 : 最后一个字符也要判断
it = expandAroundCenter(i, i + 1, s);
update(it);
}
}
return ans; // 返回
}
};
15. 三数之和
双指针解法
//思路 :
//双指针移动
//排序
//遍历nums的每一个元素
//left=i+1,right=nums.size()-1;
//计算sum=nums[i]+nums[left]+nums[right];
//如果sum<0,就要让sum变大,left++
//如果sum>0,就要让sum变小,right--
//如果sum==0,说明找到了符合条件的三元组,ans.push_back(nums[i],nums[left],num[right]);
//注意 : 不能重复,需要跳过所有重复的元素
//
//优化 : 如果nums[i]+nums[left]+num[left+1]>0,之后都是大于0,直接break(因为后面的nums[i],nums[left],nums[left+1]都变大了)
// 如果nums[i]+num[right-1]+num[right]<0,之后的都是小于0,直接进入下一个i
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if(nums.empty() )return {};
sort(nums.begin(),nums.end() );
vector<vector<int>>ans;
for(int i=0;i<nums.size()-2;++i){
if(i-1>=0&&nums[i]==nums[i-1])continue;
int left=i+1;
int right=nums.size()-1;
//优化部分
if(left+1<nums.size()&&nums[i]+nums[left]+nums[left+1]>0)break;
if(nums[i]+nums[right-1]+nums[right]<0)continue;
//
while(left<right){
int sum=nums[i]+nums[left]+nums[right];
if(sum<0){
left++;
}else if(sum>0){
right--;
}else {
ans.push_back({nums[i],nums[left],nums[right]});
left++;
right--;
while(left<nums.size()&&nums[left]==nums[left-1])left++;
while(right>=0&&nums[right]==nums[right+1])right--;
}
}
}
return ans;
}
};
16. 最接近的三数之和
双指针解法
//思路 :
//排序
//双指针移动
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if(nums.size()<3)return 0;
sort(nums.begin(),nums.end() );//排序
int ans=nums[0]+nums[1]+nums[2];//初始化ans为三数之和
//
auto update=[&](int sum){//更新答案ans
if(abs(target-ans)>abs(target-sum) )
ans=sum;
};
//
for(int i=0;i<nums.size()-2;++i){
if(i-1>=0&&nums[i]==nums[i-1])i++;
int left=i+1;
int right=nums.size()-1;
while(left<right){
int sum=nums[left]+nums[right]+nums[i];
update(sum);
if(sum<target){
left++;
}else if(sum>target){
right--;
}else return target;
}
}
return ans;
}
};
18. 四数之和
双指针解法
class Solution {
#define ll long long
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if(nums.size()<4)return {};
sort(nums.begin(),nums.end() );
vector<vector<int>>ans;
for(int i=0;i<nums.size()-3;++i){
if(i-1>=0&&nums[i]==nums[i-1])continue;
for(int j=i+1;j<nums.size()-2;++j){
if(j-1>=i+1&&nums[j]==nums[j-1])continue;
int left=j+1;
int right=nums.size()-1;
//优化
if((ll)nums[i]+nums[j]+nums[left]+nums[left+1]>target)break;
if((ll)nums[i]+nums[j]+nums[right-1]+nums[right]<target)continue;
//
while(left<right){
ll sum=(ll)nums[i]+nums[j]+nums[left]+nums[right];
if(sum<target){
left++;
}else if(sum>target){
right--;
}else{
ans.push_back({nums[i],nums[j],nums[left],nums[right]} );
left++;
right--;
while(left<nums.size()&&nums[left]==nums[left-1])left++;
while(right>=0&&nums[right]==nums[right+1])right--;
}
}
}
}
return ans;
}
};
19. 删除链表的倒数第 N 个结点
创建空节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head==nullptr)return head;//空链表直接返回
ListNode*dummy=new ListNode();//创建头节点
dummy->next=head;//连接头节点和第一个节点
ListNode*slow=dummy;//慢指针
ListNode*fast=dummy;//快指针
while(n--&&right){//先让快指针在第n个节点位置
fast=fast->next;
if(fast==nullptr)return head;//根本没有正数第n个节点,直接返回
}
//开始slow在第0个节点,fast在正数第n个节点
//一起移动之后,当fast在空节点时,slow在倒数第n个节点
//当fast在最后一个节点时,slow在倒数第n-1个节点
while(fast->next!=nullptr){//一起移动
fast=fast->next;
slow=slow->next;
}
//安全删除倒数第n个节点
ListNode*temp=slow->next;
slow->next=slow->next->next;
delete temp;
//安全删除头节点
temp=dummy->next;
delete dummy;
return temp;
}
};
26. 删除有序数组中的重复项
双指针解法
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int allright=0;//已经填号的下标
for(int i=1;i<nums.size();++i){
while(i<nums.size()&&nums[i]==nums[allright])
i++;//找到下一个填充的nums[i]
if(i<nums.size() ){//填充
allright++;
nums[allright]=nums[i];
}
}
return allright+1;
}
};
或者
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int allright=1;//allright是下一个需要填充的位置下标
for(int i=1;i<nums.size();++i){
while(i<nums.size()&&nums[i]==nums[i-1])i++;//找到下一个填充的数据
if(i<nums.size() ){
nums[allright]=nums[i];//填充
allright++;//移动allright
}
}
return allright;//allright是下一个需要填充的位置,就是最后一个填充的下标+1
}
};
栈思想解法
//思路 :
//使用栈的思想
//假设我们有一个空栈stack
//遍历数组nums[i]
//利用有序数组这个特点
//如果nums[i]与栈顶元素相等 即stack.top()==nums[i],跳过
//如果不相等,入栈,栈中元素数量++
//但是现在要求在原地移动元素
//我们可以使用stackSize=0初始化栈
//由于第一个元素一定可以入栈,直接入栈就行了,所以stackSize初始化为1
//栈顶元素就是nums[stackSize-1]
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int stackSize=1;//stackSize是栈的大小,也是下一个待填充的位置
for(int i=1;i<nums.size();++i){
if(nums[stackSize-1]!=nums[i]){//栈顶元素与nums[i]不相等,可以入栈
nums[stackSize++]=nums[i];//入栈操作
}
}
return stackSize;//返回栈的大小
}
};
27.移除元素
二分查找
//这道题与二分查找有异曲同工之妙,^ _ ^
//思路 :
//left的左边都是!=val的
//right的右边都是==val的
//使用二分查找的模板
//循环结束时
//left==数组最后一个元素下标+1
//right=数组最后一个元素下标
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left=0;
int right=nums.size()-1;
while(left<=right){
while(right>=0&&nums[right]==val)right--;
while(left<nums.size()&&nums[left]!=val)left++;
if(left<right){
swap(nums[left],nums[right]);
left++;
right--;
}
}
return right+1;//或者return left;
}
};
栈思想解决
//思路 :
//使用栈思想解决
//假设我们创建一个栈stack
//遍历整个数组
//如果遇到nums[i]!=val,直接入栈
//否则,不入栈
//但是要想原地修改
//可以初始化stackSize=0是栈的大小,也是下一个待填充位置的下标
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int stackSize=0;//初始化栈的大小
for(int i=0;i<nums.size();++i){//遍历数组
if(nums[i]!=val){//遇到!=val的数值
nums[stackSize++]=nums[i];//入栈 (注意:入栈后需要stackSize++)
}
}
return stackSize;//返回栈的大小
}
};
31. 下一个排列
left,right指针解答
//思路 :
//[4,5,2,6,3,1]这个排列
//要想数字的组合值尽可能的小,又要比原来大
//先找到一个left,right
//left记录一个左边较小的值 (这个较小,较大,是left与right相比较而言)
//right记录一个右边较大的值
//nums[left]与nums[right]只要交换就可以实现数值变大
//但是怎么找这个left和right呢?
//要想让整个数值尽可能变大的小,就要让left尽可能偏右
//找1,显然不行,因为还有right要找
//找3,不行,因为right就找不到较大的数了
//找6,同样不行
//找2,可以,因为right的值为3就行了
//所以 : left就是从右往左遍历,第一个降序数
// right就是从left右边最小的比left的值大的数
//交换nums[left],nums[right]之后,一定实现了变大
//但是要保证变大的幅度最小,需要重新排列left右边的所有数字(从小到大)
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int left=nums.size()-2;
while(left>=0&&nums[left]>=nums[left+1])left--;//从右到左,找到第一个降序数nums[left]
if(left==-1){//如果left==-1,说明整个数组时从大到小排序的
sort(nums.begin(),nums.end() );//重新从小到大排序即可
return ;
}
int right=nums.size()-1;
while(nums[right]<=nums[left])right--;//找到left的右边的一个比left大,但是最接近left的值
swap(nums[left],nums[right]);//交换
sort(nums.begin()+left+1,nums.end() );//排序left右边的所有值
return ;
}
};
42. 接雨水
左右最大值维护解法
//思路 :
//每一个格子的储水量=min(左边最大值,右边最大值)-nums[i];
//需要两个数组
//分别存储一个元素左边最大值,一个元素右边最大值(包含整个元素)
class Solution {
public:
int trap(vector<int>& height) {
vector<int>leftMax(height.size(),height[0] );//存储左边最大值
vector<int>rightMax(height.size(),height.back() );//存储右边最大值
int ans=0;//初始化为0
for(int i=1;i<height.size();++i){
leftMax[i]=max(leftMax[i-1],height[i]);
}
for(int i=height.size()-2;i>=0;--i){
rightMax[i]=max(rightMax[i+1],height[i]);
}
for(int i=0;i<height.size();++i){
ans+=(min(leftMax[i],rightMax[i])-height[i]);//公式计算ans
}
return ans;
}
};
双指针解法
//思路 :
//公式 : 每一个格子储水量=min(左边最大值,右边最大值)-nums[i]
//eg: 7,.........,6
// leftMax,left, ...,right,rightMax
//这种情况下,
//如果leftMax>rightMax,这个right位置的6可以计算了
//(因为这个right位置,右边最大值无论是多少,都要依据左边最大值计算)
//反之,如果leftMax<rightMax,left位置可以算了
class Solution {
public:
int trap(vector<int>&nums) {
int left=0;
int right=nums.size()-1;
int leftMax=0;
int rightMax=0;
int ans=0;
while(left<right){
//更新leftMax,rightMax
leftMax=max(leftMax,nums[left]);
rightMax=max(rightMax,nums[right]);
if(leftMax<rightMax){
ans+=(leftMax-nums[left] );
left++;
}else{
ans+=(rightMax-nums[right]);
right--;
}
}
return ans;
}
};
61. 旋转链表
两个指针解法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//思路 :
//先连接首尾节点,同时计算节点数量cnt
//此时last在尾部节点
//向右移动1位,找到尾节点需要last移动cnt-k次
//所以向右移动k位,找到尾节点,需要last移动k*(cnt-1)次,同时对cnt取模
//就是需要last移动k*(cnt-1)%cnt次
//找到尾节点之后就是需要断开尾部节点
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head==nullptr)return head;
ListNode*last=head;//last
int cnt=1;//初始换last在首节点
while(last->next){//一直移动到last是最后一个节点
last=last->next;//last移动
cnt++;//同时cnt++
}
last->next=head;//连接首尾节点
k%=cnt;
int temp=( (cnt-1)*k)%cnt;//计算移动k次之后,找到尾部节点需要移动几次
ListNode*slow=last;
while(temp--){
last=last->next;
slow=slow->next;//slow就是新的尾部节点
}
last=last->next; //last就是新的头节点
slow->next=nullptr;//把新的尾部节点指针指向nullptr
return last;//返回首部节点
}
};
75. 颜色分类
单指针解法
//ptr是待填充的位置下标
//两次遍历,从左到右
//第一次,遇到0,就交换到ptr位置
//第二次,遇到1,就交换到ptr位置
class Solution {
public:
void sortColors(vector<int>& nums) {
int ptr=0;
for(int i=0;i<nums.size();++i){
if(nums[i]==0){
swap(nums[i],nums[ptr]);
ptr++;
}
}
for(int i=0;i<nums.size();++i){
if(nums[i]==1){
swap(nums[i],nums[ptr]);
ptr++;
}
}
return ;
}
};
计数解法
//思路:
//初始化p0=0,p1=0,p2=0
//p0是0的数量,也是需要填充的下标
//p1是0和1的数量,也是需要填充的下标
//p2是0,1,2的数量,也是需要填充的下标
class Solution {
public:
void sortColors(vector<int>& nums) {
int p0=0,p1=0,p2=0;
for(int it:nums){
nums[p2++]=2;//先默认改为2
if(it<=1)nums[p1++]=1;
if(it==0)nums[p0++]=0;
}
return ;
}
};
80. 删除有序数组中的重复项 II
用栈的思想模拟解决
//思路 :
//想象创建了一个栈stack
//如果stack的顶部元素的下方元素==nums[i],就不可以入栈,否则可以入栈
//返回这个stack就行了
//但是这个题要求原地修改
//我们可以把数组想象位一个栈
//stackSize就是栈的大小
//nums[stackSize-2]就是栈顶元素的下方元素
//入栈时只需要nums[stackSize++]=num[i]就行了
//注意 : (nums[0]和nums[1]一定是可以入栈的,
// 所以直接把stackSize初始化为2即可)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()<2)return 1;
int stackSize=2;
for(int i=2;i<nums.size();++i){
if(nums[stackSize-2]!=nums[i]){
nums[stackSize++]=nums[i];
}
}
return stackSize;
}
};
1886. 判断矩阵经轮转后是否一致
矩阵转置解法
//思路 :
//一个矩阵顺时针转4次之后一定与原来一样
//所以顺时针转4次,每一次都与target相比较
//如果相等就返回true
//4次都不一样就返回false
//关于如何转90°--->矩阵转置之后,再行翻转,就行了
class Solution {
public:
void rotate(vector<vector<int>>&mat ){
for(int i=0;i<mat.size();++i){
for(int j=i+1;j<mat[i].size();++j){//遍历对角线以上的元素(不包含对角线)
swap(mat[i][j],mat[j][i]);//转置操作
}
reverse(mat[i].begin(),mat[i].end() );//行翻转
}
return ;
}
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
for(int i=0;i<4;++i){
if(mat==target)return true;
rotate(mat);
//for循环中改为 :
// rotate(mat);
// if(mat==target)return true;
//也行
}
return false;
}
};
82. 删除排序链表中的重复元素 II
一次遍历解法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//思路 :
//创建一个头节点dummy,连接head
//指针cur遍历链表
//如果cur的后面两个节点val相等,记录x=val,删除一直到cur->next->val!=x
//如果cur的后面两个节点val不相等,curr=curr->next (往后走)
//注意 : cur==nullptr||curr->next==nullptr的判断,不要越界
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head==nullptr||head->next==nullptr)return head;//提前返回
ListNode*dummy=new ListNode(0,head);//创建头节点
ListNode*cur=dummy;//遍历链表的cur指针
while(cur->next&&cur->next->next){
if(cur->next->val==cur->next->next->val){
int x=cur->next->val;//记录重复值
while(cur->next&&cur->next->val==x){//循环一直到cur后面的值不是x
cur->next=cur->next->next;//删除节点
if(cur->next==nullptr)break;//越界直接break
}
}else{
cur=cur->next;
}
}
return dummy->next;
}
};
86. 分隔链表
使用两个链表解法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//使用两个链表,分别存储 <x的节点 和 >=x的节点
//最后连接两个链表
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(head==nullptr||head->next==nullptr)return head;
ListNode*smallDummy=new ListNode(0);
ListNode*largeDummy=new ListNode(0);
ListNode*small=smallDummy;
ListNode*large=largeDummy;
for( ;head;head=head->next){
if(head->val<x){
small->next=head;
small=small->next;
}else{
large->next=head;
large=large->next;
}
}
large->next=nullptr;
small->next=largeDummy->next;
ListNode*temp=smallDummy->next;
delete smallDummy;
delete largeDummy;
return temp;
}
};
88. 合并两个有序数组
逆序双指针解法
//思路 :
//逆向双指针
//p1指向nums1的末尾
//p2指向nums2的末尾
//index是待填充的位置
//比较两个数组的最大值
//如果nums1的最大值>nums2的最大值,
//说明nums1的最大值就是整体的最大值,填充到nums1[index]位置
//如果nums2的最大值>nums1的最大值,
//说明nums2的最大值就是整体的最大值,填充到nums1[index]位置
//注意 : 可能会出现nums1用完了,但是nums2没有用完,所以结束要将剩余的nums2填充到nums1空余位置
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1=m-1;
int p2=n-1;
int index=m+n-1;
while(p2>=0&&p1>=0){
if(nums1[p1]>nums2[p2]){
nums1[index--]=nums1[p1--];
}else{
nums1[index--]=nums2[p2--];
}
}
while(p2>=0){
nums1[index--]=nums2[p2--];
}
return ;
}
};
125. 验证回文串
双指针逼近解法
//思路 :
//双指针逼近
//左指针left=0
//右指针right=s.size()-1
//左右指针逼近时,跳过非数字和非字母项
//比较小写字符
//
//注意 :
//你是不是认为 :( 最后有两种情况跳出循环--->left==right或者left==right+1,
//反正只要跳出循环了,一定就是回文串了
//所以你认为return true和return left==right||left=right+1是等效的 )
//不对,这样的思路是错误的 ^ - ^
//因为,当left<right&&nums[left]==nums[right]之后,还要经过while循环跳过无用项,可能会导致left>right,之后跳出循环,这样的情况也是true
//所以要写return true (我栽跟头了,磨了半个小时,^ - ^)
class Solution {
public:
bool isPalindrome(string s) {
int left=0;
int right=s.size()-1;
while(left<right){
while(left<right
&& !isalpha(s[left])
&& !isdigit(s[left]) )left++;
while(left<right
&& !isalpha(s[right])
&& !isdigit(s[right]) )right--;
if(left<=right&&tolower(s[left]) != tolower(s[right]) )return false;
left++;
right--;
}
return true;
}
};
141. 环形链表
快慢指针解法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==nullptr||head->next==nullptr)return false;
if(head->next==head)return true;
ListNode*slow=head;
ListNode*fast=head;
while(true){
if(fast==nullptr||fast->next==nullptr)return false;
slow=slow->next;
fast=fast->next->next;
if(slow==fast)return true;
}
}
};
更多推荐
6
0- 0
已为社区贡献4条内容
所有评论(0)