算法(三)—— 双指针

news/2024/10/17 6:27:11/

文章目录

  • 27 移除元素
  • 344 反转字符串(手写reverse)
  • 剑指 Offer 05 替换空格
  • 19 删除链表的倒数第N个节点
  • 面试题 02.07. 链表相交
  • 15 三数之和
  • 二、使用步骤
    • 1.引入库
    • 2.读入数据
  • 总结


27 移除元素

题目:原地移除数组中值为val的元素
思路:快慢指针
循环
{
每步都要做的:将fast的值给slow,同时slow++看,fast++
例外的:当fast指向val时,不赋值,只fast++
}
在这里插入图片描述

344 反转字符串(手写reverse)

原地反转字符串
思路:左右指针

void reverseString(vector<char>& s) {int left = 0;int right = s.size() - 1;while(right - left >= 1){swap(s[left], s[right]);/*char temp = s[left];s[left] = s[right];s[right] = temp;*/right--;left++;}
}

剑指 Offer 05 替换空格

题目:原地将字符串的所有空格替换为 “%20”
思路:
1、首先扩充数组到每个空格替换成"%20"之后的大小。
2、然后从后向前替换空格,也就是双指针法:前后指针
在这里插入图片描述

19 删除链表的倒数第N个节点

删除倒数第n个节点
思路:前后指针
让front移动n步,然后让front和back同时移动,直到front指向链表末尾。删掉back所指向的节点就可以了。

该题使用虚拟头节点,为了通过输入只有一个节点链表

ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyhead = new ListNode(999);   // 为了通过只有一个节点的链表dummyhead->next = head;ListNode* front = dummyhead;ListNode* back = dummyhead;while(front->next != nullptr){if(n > 0){front = front->next;n--;}else{front = front->next;back = back->next;}}back->next = back->next->next;return dummyhead->next;
}

面试题 02.07. 链表相交

双指针需要推导的题

使用哈希set吧

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> visited;ListNode *temp = headA;while (temp != nullptr) {visited.insert(temp);temp = temp->next;}temp = headB;while (temp != nullptr) {if (visited.count(temp)) {return temp;}temp = temp->next;}return nullptr;
}

15 三数之和

此题在算法——回溯1中也有展现,但是会超时
在这里插入图片描述

vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());// 找出a + b + c = 0// a = nums[i], b = nums[left], c = nums[right]for (int i = 0; i < nums.size(); i++) {// 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if (nums[i] > 0) {return result;}// 错误去重a方法,将会漏掉-1,-1,2 这种情况/*if (nums[i] == nums[i + 1]) {continue;}*/// 正确去重a方法if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.size() - 1;while (right > left) {// 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组/*while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;*/if (nums[i] + nums[left] + nums[right] > 0) right--;else if (nums[i] + nums[left] + nums[right] < 0) left++;else {result.push_back(vector<int>{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后,对b 和 c去重while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;// 找到答案时,双指针同时收缩right--;left++;}}}return result;
}

二、使用步骤

1.引入库

代码如下(示例):

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import warnings
warnings.filterwarnings('ignore')
import  ssl
ssl._create_default_https_context = ssl._create_unverified_context

2.读入数据

代码如下(示例):

data = pd.read_csv('https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())

该处使用的url网络请求的数据。


总结

提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。


http://www.ppmy.cn/news/206107.html

相关文章

ggplot2、RMySQL、httpuv、shiny、miniUI、devtools、recharts安装问题

本文章 主要解决 install.packages("ggplot2") install.packages("RMySQL") install.packages("httpuv") install.packages("shiny") install.packages("miniUI") install.packages("devtools") install.packages…

支持向量机练习

练习5&#xff1a;支持向量机 介绍 在本练习中&#xff0c;我们将使用支持向量机&#xff08;SVM&#xff09;来构建垃圾邮件分类器。 在开始练习前&#xff0c;需要下载如下的文件进行数据上传&#xff1a; data.tgz -包含本练习中所需要用的数据文件 其中&#xff1a; e…

装饰器Python】进阶知识点

要明白装饰器首先得知道闭包 闭包&#xff1a;是内部函数对外部函数作用域的引用&#xff0c;并且一般外部函数函数的返回值是内部函数的函数名 def outer(x): # 外部函数 a x * 2 def inter(b) # 内部函数 …

R9 6900HX和i7 10875h选哪个

r9 6900hx采用Zen 3构架 6nm制作工艺 八核心 十六线程CPU主频 3.3GHz- 4.9GHz三级缓存 16MB热设计功耗(TDP) 45W 内存类型 DDR5集成显卡 选r9 6900hx还是i7 10875h这些点很重要看过你就懂了 http://www.adiannao.cn/dy i7-10875H是一款高端笔记本电脑处理器&#xff0c;具有基…

计算机专业选i5八代还是i7八代,七代酷睿i7与第八代酷睿i5哪个好

最近有很多童鞋都在给狗狗留言&#xff0c;问游戏本应该选七代酷睿i7&#xff0c;还是选择八代酷睿i5&#xff1f;这个问题其实很有代表性&#xff0c;随着H系列八代酷睿处理器的上市&#xff0c;老平台游戏本的价格也在缓缓回落&#xff0c;最终出现了七代i7和八代i5基本持平或…

java 笔记本i7 i5_笔记本i7好还是i5好_笔记本i5和i7哪个好-系统城

我们在选购笔记本的时候&#xff0c;常常会因为市场上笔记本的种类太多而感到烦恼&#xff0c;同时也会对i5处理器和i7处理器的选择产生犹豫。那么笔记本电脑是i5好还是i7好呢&#xff1f;其实这两者之间还是会有很大的区别的&#xff0c;接下来小编就给大家讲讲笔记本电脑i5和…

计算机专业笔记本用i5还是i7,玩游戏笔记本i5和i7的区别_笔记本电脑游戏用i5还是i7...

笔记本i5和i7有什么区别呢&#xff1f;我们在买新笔记本电脑的时候&#xff0c;通常都会对处理器进行挑选&#xff0c;特别是那些追求配置的用户&#xff0c;可是在遇到i5和i7笔记本时&#xff0c;有的用户不知道用i5好还是i7好&#xff0c;也不知道它们之间的区别&#xff0c;…

i7-10875H 怎么样 相当于什么水平

i7-10875H是一款高端笔记本电脑处理器&#xff0c;具有基于Comet Lake架构&#xff08;CML-H&#xff0c;第四代Skylake&#xff09;的八个内核。 i7-10875H 怎么样看完你就知道了 https://list.jd.com/list.html? 该处理器的频率在2.1到4.5 GHz之间&#xff0c;可能在4.5 GHz…