文章目录
1 字符串1.1【字符串】【双指针】剑指 Offer 05 - 替换空格1.2【字符串】剑指 Offer 58 - II. 左旋转字符串1.3 【双指针】【字符串】剑指 Offer 20 - 表示数值的字符串1.4 【双指针】【字符串】剑指 Offer 67 - 把字符串转换成整数
2 链表2.1 【回溯】【链表】剑指 Offer 06 - 从尾到头打印链表2.2 【双指针】【链表】剑指 Offer 24 - 反转链表2.3 【链表】【回溯】【哈希表】剑指 Offer 35 - 复杂链表的复制
3 双指针3.1 【链表】【双指针】剑指 Offer 18 - 删除链表的节点3.2 【双指针】剑指 Offer 22 - 链表中倒数第k个节点3.3 【递归】剑指 Offer 25 - 合并两个排序的链表3.4 【双指针】剑指 Offer 52 - 两个链表的第一个公共节点3.5 【双指针】剑指 Offer 21 - 调整数组顺序使奇数位于偶数前面3.6 【双指针】剑指 Offer 57 - 和为s的两个数字3.7 【双指针】剑指 Offer 58 - I - 翻转单词顺序
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 { 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 { 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 { 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 { //判断是否为数字 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 { 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 vector 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 vector 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* 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 { 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 i = 0 , j = nums.size()-1; while(i { 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 vector if(nums.size()==1) return ans; int left = 0 , right = nums.size()-1; while(left { 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 { if(s[start]!=' ') { //对应第二个功能 if(index!=0) s[index++] = ' '; int end = start; //对应第一个功能 while(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; } }; 相关文章
发表评论