C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！
文章目录
一、移除元素（力扣27）二、反转字符串（力扣344）三、替换数字（卡码网 54）四、翻转字符串里的单词（力扣151）五、反转链表（力扣206）六、删除链表的倒数第 N 个结点（力扣19）七、链表相交（力扣面试题 02.07）八、环形链表 II（力扣142）九、三数之和（力扣15）十、四数之和（力扣18）
一、移除元素（力扣27）
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
class Solution {public: int removeElement(vector<int>& nums, int val) { // 利用快慢指针进行删除 // 1. 判断是否只有零个或一个元素，防止索引超出数组长度 if(nums.size()==1){ if(nums[0]==val){ return 0; } else{ return 1; } } if (nums.size()==0){ return 0; } int slow =0; for(int fast=0;fast<nums.size();fast++){ if(nums[fast]!=val){ nums[slow] = nums[fast]; slow++; } } return slow; }};
二、反转字符串（力扣344）
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：
输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]
提示：
1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符
class Solution {public: void reverseString(vector<char>& s) { // 双指针解决 int begin =0; int end = s.size()-1; while(begin<end){ // 交换 char temp = s[begin]; s[begin] = s[end]; s[end] = temp; begin++; end--; } }};
三、替换数字（卡码网 54）
题目描述
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
输入描述
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出描述
打印一个新的字符串，其中每个数字字符都被替换为了number
输入示例
a1b2c3
输出示例
anumberbnumbercnumber
提示信息
数据范围：
1 <= s.length < 10000。
#include <iostream>using namespace std; int main() { string inputS; cin >> inputS; int count = 0; // 遍历原来数组,记录其中数字的个数 for (int i = 0; i < inputS.length(); i++) { if (inputS[i] <= '9' && inputS[i]>='0') { count++; } } int FLength = inputS.length(); // resize 原来的字符串 inputS.resize(FLength + count * 5); // 替换原来字符串中的字符，从后向前替换 int j = inputS.length()-1; for (int i = FLength - 1; j>i; i--,j--) { if (inputS[i] <= '9' && inputS[i]>='0') { // 是数字要替换 inputS[j] = 'r'; inputS[j-1] = 'e'; inputS[j-2] = 'b'; inputS[j-3] = 'm'; inputS[j-4] = 'u'; inputS[j-5] = 'n'; j -= 5; } else { inputS[j] = inputS[i]; } } cout << inputS << endl; system("pause"); return 0; }
四、翻转字符串里的单词（力扣151）
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
class Solution {public: string reverseWords(string s) { // 去除空格 removeSpace(s); // // 翻转整个句子 reverse(s.begin(), s.end()); // 翻转每个单词 // 首先找到每个单词的位置 int slow=0; for(int fast=0;fast<s.length();fast++){ if(s[fast+1]==' ' || fast==s.length()-1){ reverseWord(s,slow,fast); slow = fast+2; } } return s; } // 翻转每个单词 void reverseWord(string& s, int begin, int end) { while (begin < end) { swap(s[begin], s[end]); begin++; end--; } } // 去除字符串中多余的空格 void removeSpace(string& s) { // 快慢指针去除空格 int slow = 0; for (int fast = 0; fast < s.length(); fast++) { if (s[fast] != ' ') { // 不为空格才进行下面的操作 // 添加每个单词之间的空格，句子开头不加 if (slow != 0) { s[slow] = ' '; slow++; } while (fast<s.size() && s[fast] != ' ') { s[slow] = s[fast]; slow++; fast++; } } } s.resize(slow); }};
五、反转链表（力扣206）
/** * 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* reverseList(ListNode* head) { if(head==NULL||head->next==NULL){ // 只有一个结点 return head; } // 定义两个指针，一个指前面的，一指后面的 ListNode *pre = NULL; ListNode *cur = head; while(cur!=NULL){ // 用一个值去接收cur ListNode *temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; }};
六、删除链表的倒数第 N 个结点（力扣19）
/** * 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==NULL){ return head; } ListNode * dummyNode = new ListNode(0); dummyNode->next = head; // 使用快慢指针 ListNode* fast = dummyNode; ListNode* slow = dummyNode; while(n--){ // 快指针先走n个 fast = fast->next; } while(fast!=NULL&&fast->next!=NULL){ fast = fast->next; slow = slow->next; } // 删除元素 ListNode * temp = slow->next; slow->next = slow->next->next; delete temp; // 删除 return dummyNode->next; }};
七、链表相交（力扣面试题 02.07）
/** * 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==NULL||headB==NULL){ return NULL; } int lenA =1; int lenB =1; ListNode * curA = headA; ListNode * curB = headB; while(curA->next!=NULL){ lenA++; curA = curA->next; } while(curB->next!=NULL){ lenB++; curB = curB->next; } // 找最短的链表 int minLen =min(lenA,lenB); // AB需要移动的长度 int needA= lenA-minLen; int needB = lenB - minLen; // 右对齐两个节点 while(needA--){ headA = headA->next; } while(needB--){ headB = headB->next; } // 比较之后的链表是否相同 while(headA!=NULL||headB!=NULL){ if(headA== headB){ return headA; } else{ headA = headA->next; headB = headB ->next; } } return NULL; }};
八、环形链表 II（力扣142）
/** * 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 * first = head; ListNode * slow = head; while(first!=NULL&&first->next!=NULL){ first = first->next->next; slow = slow->next; if(first==slow){ // 此时相遇 ListNode * index1 = first; ListNode * index2 = head; // 找入环口 while(index1!=index2){ index1 = index1->next; index2 = index2->next; } return index1; } } return NULL; }};
九、三数之和（力扣15）
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { // 先对数组排序 sort(nums.begin(),nums.end()); // 定义结果数组 vector<vector<int>> result; // 剪枝操作 if(nums[0]>0){ return {}; // 第一个元素都大于0了，说明不可能加起来等于0，直接返回空 } for(int i=0;i<nums.size();i++){ // 定义两个指针 int begin = i+1; int end = nums.size()-1; // 去重操作 if(i>0&&nums[i]==nums[i-1]){ // 当前的i和i-1的元素是一样的 continue; // 跳过当前循环 } while(begin<end){ if((nums[i]+nums[begin]+nums[end])==0){ result.push_back({nums[i],nums[begin],nums[end]}); while(begin<end&&nums[begin]==nums[begin+1]){ begin++; } while(begin<end&&nums[end]==nums[end-1]){ end--; } begin++; end--; } else if((nums[i]+nums[begin]+nums[end])>0){ end--; } else{ begin++; } } } return result; }};
十、四数之和（力扣18）
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { // 先排序 sort(nums.begin(),nums.end()); // 定义最终返回数组 vector<vector<int>> result; // 类似于三数之和，多了一层循环 for (int i=0;i<nums.size();i++){ // 剪枝 if(nums[0]>=0&&nums[0]>target){ break; } // 去重 if(i>0&&nums[i]==nums[i-1]){ continue; } for(int j=i+1;j<nums.size();j++){ // 剪枝 if(nums[i]+nums[j]>target&&nums[j]>=0){ break; } // 去重 if(j>i+1&&nums[j]==nums[j-1]){ continue; } // 类似于三数之和 int begin = j+1; int end = nums.size()-1; while(begin<end){ if((long) nums[i]+nums[j]+nums[begin]+nums[end]==target){ // 找到符合要求的数组，记录 result.push_back({nums[i],nums[j],nums[begin],nums[end]}); while(begin<end&&nums[begin]==nums[begin+1]){ begin++; } while(begin<end&&nums[end]==nums[end-1]){ end--; } begin++; end--; } else if((long)nums[i]+nums[j]+nums[begin]+nums[end]>target){ end--; } else{ begin++; } } } } return result; }};