我在代码随想录|写代码Day10之双指针 -27. 移除元素,151. 反转字符串中的单词,206.反转链表

题目

代码

1

class Solution {
public:int removeElement(vector<int>& nums, int val) {int n = nums.size();for(int i=0;i<n;i++){if(nums[i]==val){for(int j=i+1;j<n;j++){nums[j-1]=nums[j];}n--;i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位}}return n;}
};

2.c语言解决

int removeElement(int* nums, int numsSize, int val) {int cnt=0;//双指针for(int i=0;i<numsSize;i++){if(nums[i]!=val) nums[cnt++]=nums[i];}return cnt;
}

题目

1

class Solution {
public:void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []for (int i = start, j = end; i < j; i++, j--) {swap(s[i], s[j]);}}void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。int slow = 0;   //整体思想参考for (int i = 0; i < s.size(); ++i) { //if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。s[slow++] = s[i++];}}}s.resize(slow); //slow的大小即为去除多余空格后的大小。}string reverseWords(string s) {removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。reverse(s, 0, s.size() - 1);int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。for (int i = 0; i <= s.size(); ++i) {if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。start = i + 1; //更新下一个单词的开始下标start}}return s;} 
};

$----------------------------------$

思路:$翻转，区间写法：左闭右闭[]$,去除所有空格并在相邻单词之间添加空格, 快慢指针,遇到非空格就处理，即删除所有空格,手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格,补上该单词，遇到空格说明单词结束,slow的大小即为去除多余空格后的大小,去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格,removeExtraSpaces后保证第一个单词的开始下标一定是0,到达空格或者串尾，说明一个单词结束。进行翻转,翻转，注意是左闭右闭 []的翻转,更新下一个单词的开始下标start

代码

1

/*** 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* reverse(ListNode* pre,ListNode* cur){if(cur == NULL) return pre;ListNode* temp = cur->next;cur->next = pre;// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步// pre = cur;// cur = temp;return reverse(cur,temp);}ListNode* reverseList(ListNode* head) {// 和双指针法初始化是一样的逻辑// ListNode* cur = head;// ListNode* pre = NULL;return reverse(NULL, head);}};

思路:双指针和虚拟头结点

2

/*** 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) {ListNode*cur=head;//这个指向头结点ListNode*pre = nullptr;//这个指向头结点前面的结点,//因为头结点前面的结点为空所以这个是空while(cur){//cur不断递归更新当cur指向为空的时候则反转完成ListNode*temp = cur->next;//记录下我们查找的结点cur->next = pre;//cur的下一位指向pre也就是cur的后一位,如此不断递归那么就可以将指向反转pre = cur;//然后pre向前移动cur = temp;//我们的cur也向前移动也就是我们刚刚记录下的节点}return pre;}
};

🔥如果此文对你有帮助的话，欢迎💗关注、👍点赞、⭐收藏、✍️评论，支持一下博主~