您现在的位置是：首页 >学无止境 >【leetcode刷题之路】剑指Offer——字符串+链表+双指针网站首页学无止境
【leetcode刷题之路】剑指Offer——字符串+链表+双指针
1 字符串
1.1【字符串】【双指针】剑指 Offer 05 - 替换空格
https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
首先计算出字符串中的空格数量，然后对原字符串进行扩充，之后使用双指针i和j，i指向原字符串的尾部，j指向新字符串的尾部，然后双指针一起从尾部向前移动，如果此时i为空，则发生替换，否则直接挪到j的位置即可。
class Solution {
public:
string replaceSpace(string s) {
int length = s.size();
int count = 0;
for(int i=0;i<length;i++)
{
if(s[i]==' ') count++;
}
s.resize(length + 2 * count);
for(int i=length-1,j=s.size()-1;i>0,j>i;i--,j--)
{
if(s[i]==' ')
{
s[j] = '0';
s[j-1] = '2';
s[j-2] = '%';
j-=2;
}
else s[j] = s[i];
}
return s;
}
};
1.2【字符串】剑指 Offer 58 - II. 左旋转字符串
https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
（1）使用了额外的字符串来进行移动，左移n位可以看成右移length-n位，最后对length取余就是移动后的位置。
（2）直接在原字符串上修改，这里举一个例子来帮助大家理解：
我们假设s=‘abcde’,n=2,那么最后的结果应该是cdeab，我们把这个结果进行翻转可以得到baedc，而这个字符串与原来的abcde的区别就是ab进行对称翻转+cde进行对称翻转，把他们分开的点就是第n个字符的位置，所以我们可以基于这个发现，先对前n个字符进行翻转，再对剩下的字符进行翻转，最后对整个字符串进行翻转。
//方法1---借助额外字符串
class Solution {
public:
string reverseLeftWords(string s, int n) {
string ans = s;
int length = s.size();
for(int i=0;i<length;i++)
{
ans[(i+length-n)%length] = s[i];
}
return ans;
}
};
//方法2---在原字符串上修改
class Solution {
public:
string reverseLeftWords(string s, int n) {
//对前n个字符进行翻转
reverse(s.begin(),s.begin()+n);
//对剩下的字符进行翻转
reverse(s.begin()+n,s.end());
//对整个字符串进行翻转
reverse(s.begin(),s.end());
return s;
}
};
1.3 【双指针】【字符串】剑指 Offer 20 - 表示数值的字符串
https://leetcode.cn/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
首先通过双指针找到字符串中不为空的部分，对这部分内容进行数值判断
其实这道题的难点在于特殊符号±eE.的判断，如果是纯数字的组成一定是数值，下面对这些特殊符合分别进行分析
（1）小数点.
- 如果这个数值含有小数点的话，那么有且只能有一个小数点，且小数点的前后必须都是数字；
- 如果这个数值是科学计数法，那么小数点只能出现在e/E的前面，比如5.3e2；
（2）科学计数法e/E
如果这个数值采用科学计数法的话，那么e/E有且只能出现一次，并且e/E的前后必须都是数字；
（3）符号±
- 如果这个数值有符号的话，那么符号必须得在数值的第一位；
- 如果这个数值是科学计数法，那么符号的前一位可以是e/E，但是后一位绝对不能是e/E，比如-1E-16；
class Solution {
public:
bool isNumber(string s) {
int i = 0 , j = s.size()-1;
//找到字符串中第一个不为空的位置
for(;i<s.size();i++)
{
if(s[i]!=' ') break;
}
//从末尾找到字符串最后一个不为空的位置
for(;j>0;j--)
{
if(s[j]!=' ') break;
}
//判断是否为数值，以及是否有小数点和e/E
bool num_flag = false;
bool dot_flag = false;
bool e_flag = false;
for(int k=i;k<j+1;k++)
{
//判断是否为数字
if(isdigit(s[k]))
{
num_flag = true;
}
//判断是否为小数点，并且之前是否出现过小数点和e/E
else if(s[k]=='.' && !dot_flag && !e_flag)
{
dot_flag = true;
}
//判断是否为e/E，并且之前是否出现过e/E和数字
else if((s[k]=='e' || s[k]=='E') && !e_flag && num_flag)
{
e_flag = true;
//因为e/E的前后必须都是数字，所以如果找到了e/E就把num_flag设为false，
//遇到下一个数字再设为true，避免出现12e的情况
num_flag = false;
}
//判断是否为+-，并且符号是否在数值的首位，或者前一位是e/E
else if((s[k]=='+' || s[k]=='-') && (k==i || s[k-1]=='e' || s[k-1]=='E'))
{
continue;
}
//其他均为非法情况，输出false
else return false;
}
return num_flag;
}
};
1.4 【双指针】【字符串】剑指 Offer 67 - 把字符串转换成整数
https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/
这道题的思路其实不难想出来，就是找到数值的部分然后转化为整数，主要是需要考虑很多边界条件，这里列举我碰到的一些问题。
（1）只有一个字符，且该字符为空格或+或-，这种需要返回0；
（2）对于含有小数点的数值，比如3.1415，应该输出3，因为小数点在本题中属于多余字符；
（3）数值中间可能存在多余字符，比如123a456，应该输出123，注意识别其中的多余字符；
（4）开头有且只能有一个+或-，对于±1，应该输出0；
（5）注意int的边界条件，可能在字符串按序遍历*10的时候就已经超出int大小了，这里可以提前break循环。
class Solution {
public:
int strToInt(string str) {
//解题思路中第一种情况
if(str.size()==1 && (str[0]==' ' || str[0]=='+' || str[0]=='-')) return 0;
int i = 0 , j = str.size()-1;
//找出数值部分的第一个元素
for(;i<str.size();i++)
{
if(isdigit(str[i]) || str[i]=='+' || str[i]=='-') break;
else if(str[i]==' ') continue;
else return 0;
}
//找出数值部分的最后一个元素
for(;j>0;j--)
{
if(isdigit(str[j])) break;
}
//判断数值的正负
bool sym = true;
if(str[i]=='+' || str[i]=='-')
{
if(str[i+1]=='+' || str[i+1]=='-') return 0;
else
{
if(str[i]=='-') sym = false;
i++;
}
}
//判断是否超过int大小
long long num = 0;
bool overflow = false;
while(i<=j)
{
if(!isdigit(str[i])) break;
num = num * 10 + str[i] - '0';
if(num!=int(num))
{
overflow = true;
break;
}
i++;
}
//根据符号正负选择对应的输出
if(sym)
{
if(!overflow) return num;
else return pow(2,31)-1;
}
else
{
if(!overflow) return -num;
else return -pow(2,31);
}
}
};
2 链表
2.1 【回溯】【链表】剑指 Offer 06 - 从尾到头打印链表
https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
（1）常规思路，先正序存入一个数组中，然后再逆序存入另一个数组中，作为最后结果；
（2）回溯法，先找到链表的最后一个元素，然后一步步往前输出到数组中。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//常规思路
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> temp , ans;
ListNode *p = head;
while(p)
{
temp.push_back(p->val);
p = p->next;
}
for(int i=temp.size()-1;i>=0;i--)
{
ans.push_back(temp[i]);
}
return ans;
}
};
//回溯法
class Solution {
public:
vector<int> ans;
vector<int> reversePrint(ListNode* head) {
if(!head) return ans;
reversePrint(head->next);
ans.push_back(head->val);
return ans;
}
};
2.2 【双指针】【链表】剑指 Offer 24 - 反转链表
https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
定义两个指针，cur指向头结点，ans指向NULL，在每次遍历中都让cur的下一个元素指向ans，实现反转。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *cur = head , *ans = NULL;
while(cur)
{
ListNode *tmp = cur->next;
cur->next = ans;
ans = cur;
cur = tmp;
}
return ans;
}
};
2.3 【链表】【回溯】【哈希表】剑指 Offer 35 - 复杂链表的复制
https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
这道题目考察的是链表的深拷贝，这里借助哈希表来存储结点，而且这个链表有一个随机指针，所以普通的复制是行不通的，因此采用了回溯的方法，每一次先看待复制的结点是否在哈希表中，如果在的话才好复制random指向的结点。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
unordered_map<Node*,Node*> hash_map;
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
if(!hash_map.count(head))
{
Node *new_node = new Node(head->val);
hash_map[head] = new_node;
new_node->next = copyRandomList(head->next);
new_node->random = copyRandomList(head->random);
}
return hash_map[head];
}
};
3 双指针
3.1 【链表】【双指针】剑指 Offer 18 - 删除链表的节点
https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/
采用双指针，cur指向当前遍历的结点，pre指向cur的前一个结点，如果遇到val就直接删除，这里需要特殊判断一下头结点就是val的情况。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head->val == val) return head->next;
ListNode *pre = head;
ListNode *cur = head;
while(cur!=nullptr && cur->val!=val)
{
pre = cur;
cur = cur->next;
}
if(cur->val==val)
{
pre->next = cur->next;
}
return head;
}
};
3.2 【双指针】剑指 Offer 22 - 链表中倒数第k个节点
https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
双指针left和right，先让right遍历k个结点，然后和left同时向后遍历，但right到达尾结点时left即为倒数第k个结点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *left = head;
ListNode *right = head;
for(int i=0;i<k;i++)
{
right = right->next;
}
while(right)
{
left = left->next;
right = right->next;
}
return left;
}
};
3.3 【递归】剑指 Offer 25 - 合并两个排序的链表
https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
判断当前l1和l2的大小，如果l1较小，就从l1往后连接，并返回l1，同理l2。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==nullptr) return l2;
else if(l2==nullptr) return l1;
else if(l1->val < l2->val)
{
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}
else
{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
};
3.4 【双指针】剑指 Offer 52 - 两个链表的第一个公共节点
https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
利用双指针，定义pa和pb分别指向A和B的头节点，这里判断是否相交采用了一个非常有意思的方法，假设A和B相交节点前各有skipA和skipB个节点，而相交节点数为C，pa和pb同时开始遍历，如果pa遍历完了就指向headB，同理pb，那么到最后总会遍历相同次数，对于A：skipA+C+skipB，对于B：skipB+C+skipA，如果此时的节点一样的话，说明相交，否则说明都遍历到了各自的最后节点仍不相交，返回空指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr) return nullptr;
ListNode *pa = headA;
ListNode *pb = headB;
while(pa != pb)
{
pa = pa == nullptr ? headB : pa->next;
pb = pb == nullptr ? headA : pb->next;
}
return pa;
}
};
3.5 【双指针】剑指 Offer 21 - 调整数组顺序使奇数位于偶数前面
https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
定义双指针i和j分别指向数组的第一个元素和最后一个元素，然后i往后遍历，直到找到前半部分的第一个偶数，j向前遍历，直到找到后半部分的第一个奇数，然后交换i和j所在位置的数即可，如果想不改变奇数和偶数分别在数组中的原有排列位置，这里推荐采用快慢指针来实现，让两个指针同时从头开始遍历，分别找到第一个出现的偶数和奇数交换位置。
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int i = 0 , j = nums.size()-1;
while(i<j)
{
if(nums[i]%2==1)
{
i++;
continue;
}
if(nums[j]%2==0)
{
j--;
continue;
}
swap(nums[i++],nums[j--]);
}
return nums;
}
};
3.6 【双指针】剑指 Offer 57 - 和为s的两个数字
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
定义双指针left和right，分别指向数组的第一个元素和最后一个元素，如果两者之和大于target，则right向前移，如果两者之和小于target，则left向后移，直到两者之和等于target，输出结果。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
if(nums.size()==1) return ans;
int left = 0 , right = nums.size()-1;
while(left<right)
{
if(nums[left] + nums[right] < target) left++;
else if(nums[left] + nums[right] > target) right--;
else
{
ans.push_back(nums[left]);
ans.push_back(nums[right]);
break;
}
}
return ans;
}
};
3.7 【双指针】剑指 Offer 58 - I - 翻转单词顺序
https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/
定义双指针start和end，分别表示每个单词开始和结束。这道题的难点在于，如果两个单词之间存在不止一个空格应该怎么办，这里的做法是先把整个字符串反转，然后定义了index作为全局移动的指针，表示目前字符串遍历到哪里了，同时也借助index实现以下功能：
- 如果每个单词开始位置之前有多个空格，则去掉这些空格，使用的方法是挨个赋值代替这些空格，例如" abc"->“abcc”;
- 当每个单词的反转结束时，下一个字符一定是空格，例如"abcc"->"cba ";
- 当所有单词全部反转之后，会在字符串末尾留下一些空格，去掉它们，例如"cba "->“cba”。
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(),s.end());
int index = 0;
for(int start=0;start<s.size();start++)
{
if(s[start]!=' ')
{
//对应第二个功能
if(index!=0) s[index++] = ' ';
int end = start;
//对应第一个功能
while(end<s.size() && s[end]!=' ')
{
s[index++] = s[end++];
}
reverse(s.begin()+index-(end-start),s.begin()+index);
start = end;
}
}
//对应第三个功能
s.erase(s.begin()+index,s.end());
return s;
}
};
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述