企业官网建设流程全解析

双指针的基本思想：

用两个指针在序列上移动，配合条件减少循环次数，把 O (n²) 暴力优化到 O (n)，一般只用一趟或者两趟遍历。

两个指针通常叫左指针、右指针（慢指针、快指针），按移动方式分成两类：

1. 快慢指针（同向双指针）两个指针朝同一个方向走，一个走得快、一个慢。 常见场景：链表找环、链表中点、滑动窗口、移除数组元素。 核心：快指针负责探测，慢指针标记有效位置。
2. 对撞指针（相向双指针）左指针在开头，右指针在末尾，往中间靠拢。 前提：数组有序。 常见场景：两数之和、三数之和、反转数组、判断回文。 核心：根据当前和 / 大小关系，决定移左还是移右。

关键点

• 双指针本质：利用单调性，避免重复枚举
• 不一定同时移动，每次只动其中一个
• 适用：数组、字符串、链表；大多要求有序或者有单调性质

练习题：

移动零

底层逻辑：设置dest 和 cur 把，数组分为三个部分，dest 之前的数组为无0原顺序的数组，dest 和 cur 的都为储存0元素，cur 到 数组末的部分为还未检查部分，cur == nums.size()，检查完毕

dest 和 cur 运行逻辑：

cur 如果不为0的元素那么就与 dest 的位置进行 swap 调换，dest ++，如果是为0不做调换，cur每次进行++操作确保不会死循环。

代码展示：

class Solution { public: void moveZeroes(vector<int>& nums) { size_t dest,cur; dest = cur = 0; while(cur!=nums.size()) { if(nums[cur]!=0) { std::swap(nums[dest++],nums[cur]); } cur++; } } };

复写零

1089. 复写零 - 力扣（LeetCode）

给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]输出：[1,0,0,2,3,0,0,4]解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3]输出：[1,2,3]解释：调用函数后，输入的数组将被修改为：[1,2,3]

我的想法：

通过消耗空间，建一个目标数组，在进行拷贝给arr数组，达到目的。

class Solution { public: void duplicateZeros(vector<int>& arr) { vector<int> Marr; for(size_t i = 0,j=0;j<arr.size(),i!=arr.size();i++) { if(arr[i]==0) { j+=2; Marr.push_back(0); Marr.push_back(0); } else { Marr.push_back(arr[i]); j++; } } for(size_t i = 0;i<arr.size();i++) { arr[i]=Marr[i]; } } };

最优解法：

class Solution { public: void duplicateZeros(vector<int>& arr) { int dest = -1,cur = 0,n = arr.size(); while(cur < n ) { if(arr[cur]) dest++; else dest+=2; if(dest >= n - 1) break; cur++; } if(dest == n) { arr[n - 1] = 0; dest -= 2,cur--; } while(cur>=0 && dest != cur) { if(arr[cur])arr[dest--]=arr[cur--]; else { arr[dest--]=0; arr[dest--]=0; cur--; } } } };

快乐数：

202. 快乐数 - 力扣（LeetCode）

编写一个算法来判断一个数n是不是快乐数。

「快乐数」定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
• 如果这个过程结果为1，那么这个数就是快乐数。

如果n是快乐数就返回true；不是，则返回false。

我的思路：

正常解题，一步一步解析分析出2为什么不是快乐数，进行计算。

发现：

2->4->16->37->58->89->145->42->20->4这个死循环里面，发现如果数据一旦到了4的时候就是死循环，就符合非快乐数，所以进行循环4的拦截。

class Solution { public: bool isHappy(int n) { int count,_n; while(n!=1 && n!=4) { count = 0; while(n!=0) { _n = n%10; count +=(_n*_n); n/=10; } n = count; } return n == 1; } };

但缺点也很明显，需要计算，而却也不能真的确定真的就是4会导致死循环，有可能还存在其他死循环的可能性，不能真的解决问题。

快慢指针解题：

如果是非快乐数就会在一定的有序的数字之间跳动，类似循环，快乐数就会排到一定的数值都会变成1，1，1的循环，有快慢指针解决的话，在有循环的数值又快指针追到慢指针或者在1的循环快指针追到慢指针，也确实可以实现证明是否为快乐数。

class Solution { public: int isfun(int n) // 返回 n 这个数每⼀位上的平⽅和 { int sum = 0; while(n) { int t = n % 10; sum += t * t; n /= 10; } return sum; } bool isHappy(int n) { int slow = n, fast = isfun(n); while(slow != fast) { slow = isfun(slow); fast = isfun(isfun(fast)); } return slow == 1; } };