C++数据结构与算法——双指针法

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;
    }
};

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/390267.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Flutter 动画(显式动画、隐式动画、Hero动画、页面转场动画、交错动画)

前言 当前案例 Flutter SDK版本&#xff1a;3.13.2 显式动画 Tween({this.begin,this.end}) 两个构造参数&#xff0c;分别是 开始值 和 结束值&#xff0c;根据这两个值&#xff0c;提供了控制动画的方法&#xff0c;以下是常用的&#xff1b; controller.forward() : 向前…

【开源】在线办公系统 JAVA+Vue.js+SpringBoot+MySQL

目录 1 功能模块1.1 员工管理模块1.2 邮件管理模块1.3 人事档案模块1.4 公告管理模块 2 系统展示3 核心代码3.1 查询用户3.2 导入用户3.3 新增公告 4 免责声明 本文项目编号&#xff1a; T 001 。 \color{red}{本文项目编号&#xff1a;T001。} 本文项目编号&#xff1a;T001。…

前端vue3实现本地及在线文件预览(含pdf/txt/mp3/mp4/docx/xlsx/pptx)

一、仅需实现在线预览&#xff0c;且文件地址公网可访问 &#xff08;一&#xff09;微软office免费预览&#xff08;推荐&#xff09; 支持doc/docx/xls/xlsx/ppt/pptx等多种office文件格式的免费预览 //示例代码//​在https://view.officeapps.live.com/op/view.aspx?src…

骨传导耳机是什么?如何选择骨传导耳机不会踩雷?

骨传导耳机是利用骨传导技术研发而成一种新型蓝牙耳机&#xff0c;其传声方式很独特&#xff0c;不通过空气传导&#xff0c;而是通过人体骨骼来传递声音。 详细传声原理请看下图&#xff1a; 随着骨传导耳机逐渐热门&#xff0c;如何选购耳机成为了问题&#xff0c;下面跟大家…

计算机设计大赛 深度学习YOLO图像视频足球和人体检测 - python opencv

文章目录 0 前言1 课题背景2 实现效果3 卷积神经网络4 Yolov5算法5 数据集6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习YOLO图像视频足球和人体检测 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非…

1_opencv3环境搭建与测试

之前2020年5月写过一次&#xff0c;时隔3年多&#xff0c;有机会再重新写一次。相比之前&#xff0c;应该是有一点儿进步的。之前是使用默认安装路径&#xff0c;所以无需配置共享库的搜索路径。这次是自定义安装路径&#xff0c;略有区别。随着写程序的时间增长&#xff0c;编…

Dockerfile 常用指令

1、FROM 指定base镜像。 2、Docker history 显示镜像的构建历史&#xff0c;也就是Dockerfile的执行过程。 Missing 表示无法获取IMAGE ID&#xff0c;通常从Docker Hub下载的镜像会有这个问题。 3、调试Dockerfile&#xff0c;使用sudo docker run -it XXXX&#xff0c;XXXX…

036-安全开发-JavaEE应用第三方组件Log4j日志FastJson序列化JNDI注入

036-安全开发-JavaEE应用&第三方组件&Log4j日志&FastJson序列化&JNDI注入 #知识点&#xff1a; 1、JavaEE-组件安全-Log4j 2、JavaEE-组件安全-Fastjson 3、JavaEE-基本了解-JNDI-API 演示案例&#xff1a; ➢Java-三方组件-Log4J&JNDI ➢Java-三方组件-Fa…

【开源】SpringBoot框架开发大学生相亲网站

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 查询会员4.2 查询相亲大会4.3 新增留言4.4 查询新闻4.5 新增新闻 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的大学生相亲网站&#xff0c;包含了会员管理模块、新闻管…

炬芯ATS2819 soundbar音响系统开发完全手册

加我微信hezkz17,可申请加入数字音频系统研究开发交流答疑群,赠送音频项目核心开发资料 ATS2819音响系统开发完全手册 1 硬件原理实现 图1 硬件原理框图 2 SOC ATS2819介绍 3 E800 板子项目实物…

黑群晖一键修复:root、AME、DTS、转码、CPU型号等

食用方法&#xff1a;SSH连接群晖使用临时root权限执行 AME3.x激活补丁 只适用于x86_64的&#xff1a;DSM7.x Advanced Media Extensions (AME)版本3.0.1-2004、3.1.0-3005 激活过程需要下载官方的解码包&#xff0c;过程较慢&#xff0c;耐心等待。。。 DSM7.1和7.2的AME版…

【前端设计】炫酷导航栏

欢迎来到前端设计专栏&#xff0c;本专栏收藏了一些好看且实用的前端作品&#xff0c;使用简单的html、css语法打造创意有趣的作品&#xff0c;为网站加入更多高级创意的元素。 html <!DOCTYPE html> <html lang"en"> <head><meta charset&quo…

Java 和 JavaScript 的奇妙协同:语法结构的对比与探索(中)

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

家人们,比赛打完了

啊&#xff0c;终于打完一场比赛了&#xff0c;但还有三场…… 先看看我的战绩&#xff1a; 共八题&#xff0c;AC6题&#xff0c;总共3902分&#xff0c;3.7k人参加&#xff0c;第980名 来看看第一&#xff1a; A8题&#xff0c;我只有2题没做出&#xff0c;相差4000多分&am…

wsl连接USB设备

参考教程&#xff1a;连接 USB 设备 | Microsoft Learn 1.安装usbipd-win WSL 本身并不支持连接 USB 设备&#xff0c;因此你需要安装开源usbipd-win项目【下载Releases dorssel/usbipd-win (github.com)】 2.共享USB设备 通过以管理员模式打开PowerShell或者CMD并输入以下…

吐血整理!操作系统【处理机调度】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;OS从基础到进阶 1 基本概念1.1 总览1.2 什么是调度1.2.1 调度1.2.2 处理机调度 1.3 调度的三个层次1.3.1 高级调度1.3.2 中级调度&#xff08;内存调度&#xff09;1.3.3 低级调度&#xf…

学生成绩管理系统|基于Springboot的学生成绩管理系统设计与实现(源码+数据库+文档)

学生成绩管理系统目录 目录 基于Springboot的学生成绩管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员功能模块 2、学生功能模块 3、教师功能模块 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源…

Medical Boundary Diffusion Modelfor Skin Lesion Segmentation

皮肤病灶分割的医学边界扩散模型 摘要 由于多尺度边界关注和特征增强模块的进步&#xff0c;皮肤镜图像中的皮肤病变分割最近取得了成功。然而&#xff0c;现有的方法依赖于端到端学习范式&#xff0c;直接输入图像和输出分割图&#xff0c;经常与极其困难的边界作斗争&#…

009集——vba实现内存中大小端序的转换(附不同进制转换代码)

小端序为很多系统默认的数据存储方式&#xff0c;但有些数据格式为大端序模式解读文件&#xff0c;因此我们需将小端序字节颠倒排序&#xff0c;这样用大端序模式解读此文件&#xff0c;最后即可读取我们想要的内容。方法如下&#xff1a; Function SwapEndian(ByVal value As…

问题:在额定电压500V以下的电路中,使用的各种用电设备,一般称为(_ _ _)用电设备 #媒体#媒体#媒体

问题&#xff1a;在额定电压500V以下的电路中,使用的各种用电设备,一般称为&#xff08;_ _ _)用电设备 参考答案如图所示