永久免费建站地址深圳网站设计 创同盟

永久免费建站地址,深圳网站设计 创同盟,制作俄语网站,港港网app下载最新版注意#xff1a;这里的双指针指的不是C和C的原生指针#xff08;指针数据类型#xff09;#xff0c;你可以把这里的指针理解为数组下标#xff0c;这会帮助你更好地理解本文 概念 左右指针#xff0c;听名字就知道是两个指针#xff0c;一个在左#xff0c;一个在右…注意这里的双指针指的不是C和C的原生指针指针数据类型你可以把这里的指针理解为数组下标这会帮助你更好地理解本文概念左右指针听名字就知道是两个指针一个在左一个在右。左右指针特别适用于处理数组和字符串问题。和快慢指针不同左右指针同时从两边向中间移动形成对称扫描。二分法二分查找是对左右指针最直接的运用起码看上去比较像初始状态-左指针为 0 右指针为 n - 1终止条件-左指针大于右指针基础模板int l 0 , r n - 1; while(l n){ if(){ //当左边满足条件 l; } if(){ //当右边满足条件 r--; } }例题两数之和167. 两数之和 II - 输入有序数组https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/这是来自力扣的一道题目题目给定一个已按非降序的整数数组请你从数组中找出两个数让它们的和等于目标数target假设每个输入有且只有一个解且不能重复使用相同的元素注意这题的下标从 1 开始暴力写法class Solution { public: vectorint twoSum(vectorint numbers, int target) { for(int i 1 ; i numbers.lenght() ; i){ for(int j i 1 ; j numbers.lenght() ; j){ if(numbers[i] numbers[j] target){ return {i 1 , j 1}; } } } return {-1 , -1}; } };但是很明显如果你使用暴力的话复杂度就来到了O()想都不用想包超时的左右指针写法利用给定数组非降序的特性我们可以确定左右指针移动的条件当左右两数和大于 target 时左指针向右移动当左右两束小于 target 时右指针向左移。class Solution { public: vectorint twoSum(vectorint numbers, int target) { int l 0 , r numbers.size() - 1; while(l r){ if(numbers[l] numbers[r] target){ l; }else if(numbers[l] numbers[r] target){ r--; }else{ return {l 1 , r 1}; } } return {l , r}; } };通过双指针我们就成功地将复杂度降到O(n)了反转字符串P5705 【深基2.例7】数字反转题目描述输入一个不小于 100 且小于 1000同时包括小数点后一位的一个浮点数例如 123.4 要求把这个数字翻转过来变成 4.321 并输出。输入123.4输出4.321这道题其实不用双指针也行因为这道题其实用纯语法知识也可以做常规写法#includeiostream using namespace std; int main(){ float n; cinn; int ge,shi,bai,xiao; bai(int)(n)/100; shi(int)(n)/10%10; ge(int)(n)%10; xiao(int)(n*10)%10; cout(float)(xiaoge/10.0shi/100.0bai/1000.0); return 0; }左右指针写法#includeiostream using namespace std; int main(){ string temp; cin temp; int l 0 , r temp.length() - 1; while(l r){ char t temp[l]; temp[l] temp[r]; temp[r] t; l; r--; } cout temp endl; return 0; }这题用左右指针真有点莫名其妙了其实可以用 swap 函数直接交换不需要 l 和 r 这两个变量总结本文只是对左右指针的概念进行描述对其过于具体的使用暂不赘述但左右指针毫无疑问是比较重要的模板之一。