优选算法——双指针

优选算法

一、leetcode283.移动零

题目分析：

​ 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

算法原理：

​ 快排原理：

​ 数组划分或者数组分块：即在一定的规则下将数组划分成若干个区间；在原数组上进行处理；

​ 解决方法：使用双指针；在数组中是利用数组下标来充当指针；双指针一个负责条件就绪通知另一个指针，另一个指针负责处理任务；

​ 解决过程：cur负责遍历数组，可以划分为处理过和未处理过区域，当前位置之前是处理过的区域，之后到数组结尾是未处理区域；dest负责在一处理过的数组区域之中根据规则划分数组块，一开始没有划分已处理区域所以指向为空，数组中就是-1；在遍历的过程中保持数组块的划分规则是保持不变的；

​ 当遍历完数组之后就得到最终需要的结果；

代码实现：

void moveZeroes(vector<int>& nums) {
    int cur=0;
    int dest=-1;
    for(;cur<nums.size();cur++)
    {
        if(nums[cur]==0)
        {
            continue;
        }
        swap(nums[++dest],nums[cur]);
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二、leetcode1089.复写零

题目分析：

​ 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

算法原理：

​ 双指针算法，先异地操作，然后优化成双指针下的就地操作；

​ 异地操作：一个指针负责遍历数组检查是否触发条件，另一个数组负责将符合条件的数组数据拷贝到一个新的数组当中；

​ 就地操作：先找到最后一个复写位置的数(使用双指针)，检查此时的dest位置是否越界，cur指向此位置，dest从最后一个位置开始向前遍历；

代码实现：

void duplicateZeros(vector<int>& arr) {
    int cur = 0;
    int pos = -1;
    for (; cur < arr.size(); cur++) {
        if (arr[cur]) {
            pos++;
        } else {
            pos += 2;
        }
        if (pos >= arr.size() - 1) {
            break;
        }
    }
    if (pos == arr.size()) {
        arr[arr.size()-1]=0;
        cur--;
        pos-=2;
    }
    while (cur>=0) {
        if (arr[cur]) {
            arr[pos--] = arr[cur--];
        } else {
            arr[pos--] = arr[cur];
            arr[pos--] = arr[cur];
            cur--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

三、leetcode202.快乐数

题目分析：

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

「快乐数」 定义为：

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

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

算法原理：

​ 使用快慢双指针，找到环上重复的值是否是1；由于抽屉原理可知

代码实现：

int bitsum(int n) {
        int sum = 0;
        while (n) {
            sum += ((n % 10) * (n % 10));
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = bitsum(slow);
            fast = bitsum(fast);
            fast = bitsum(fast);
        } while (slow != fast);
        if (slow == 1) {
            return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

四、leetcode11.盛最多水的容器

题目分析：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

算法原理：

​ 利用单调性使用双指针解决问题，上世纪就按复杂度是On；开始两个指针指向数组的两边，不断往中间逼近并且记录容积，相遇时比较所有容积中最大的；往两边逼近时，去较小或者相等的一个数；

代码实现：

int maxArea(vector<int>& height) {
    int left = 0;
    int right = height.size() - 1;
    int ret = 0;
    vector<int> v;
    ret=height[left] < height[right]?height[left]:height[right];
    v.push_back((right-left)*ret);
    while (left != right) {
        if (height[left] > height[right]) {
            ret = (right - left) * height[right];
            v.push_back(ret);
            right--;
        } else {
            ret = (right - left) * height[left];
            v.push_back(ret);
            left++;
        }
    }
    int max = v[0];
    for (auto& e : v) {
        if (max < e) {
            max = e;
        }
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26