[Algorithm][双指针][复写零][快乐数][盛水最多的容器][有效三角形的个数]详细解读 + 代码实现

1.复写零

1.题目链接

• 题目链接

2.算法原理讲解

1. 先找到最后一个"复写"的数
   • 先判断cur位置的值
   • 决定dest向后移动一步或者两步
   • 处理边界情况，if(num[n - 2] == 0)
     • num[n - 1] = 0
     • cur--;
     • dest -= 2;
   • 判断dest是否到末尾
   • cur++;
2. "从后向前"完成复写操作

3.代码实现

void DuplicateZeros(vector<int>& arr) 
{
    int cur = 0, dest = -1;
    int 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;
        cur--;
        dest -= 2;
    }

    // 从后往前复写
    while(cur >= 0)
    {
        if(arr[cur])
        {
            arr[dest--] = arr[cur--];
        }
        else
        {
            arr[dest--] = 0;
            arr[dest--] = 0;
            cur--;
        }
    }
}

2.快乐数

1.题目链接

• 题目链接

2.算法原理讲解

• 本题中，将快慢指针抽象了两个数
  • slow每次变化一次，fast每次变化两次，即可达到"快慢指针"效果
• "快慢指针"在此题中，用于判环
  • 由于两"指针"速度并不一样，在快指针总是会追上慢指针的

3.代码实现

class Solution {
public:
    int BitSum(int n)
    {
        int sum = 0;
        while(n)
        {
            int tmp = n % 10;
            sum += tmp * tmp;
            n /= 10;
        }

        return sum;
    }

    // 本题将双指针的"指针"抽象成了两个数
    bool isHappy(int n) 
    {
        int slow = n, fast = n;
        while((slow = BitSum(slow)) != (fast = BitSum(BitSum(fast))));

        return slow == 1;
    }
};

3.盛水最多的容器

1.题目链接

• 题目链接

2.算法原理讲解

• 为了⽅便叙述，假设「左边边界」⼩于「右边边界」

• 如果此时固定⼀个边界，改变另⼀个边界，⽔的容积会有如下变化形式：

  • 容器的宽度⼀定变⼩
  • 由于左边界较⼩，决定了⽔的⾼度
    • 如果改变左边界，新的⽔⾯⾼度不确定，因此容器的容积可能会增⼤
  • 如果改变右边界，⽆论右边界移动到哪⾥，新的⽔⾯的⾼度⼀定不会超过左边界
    • 也就是不会超过现在的⽔⾯⾼度，但是由于容器的宽度减⼩，因此容器的容积⼀定会变⼩的
      

• 由此可⻅，左边界和其余边界的组合情况都可以舍去

  • 所以可以left++跳过这个边界，继续去判断下⼀个左右边界

• 不断重复上述过程，每次都可以舍去⼤量不必要的枚举过程，直到left与right相遇

  • 期间产⽣的所有的容积⾥⾯的最⼤值，就是最终答案

3.代码实现

int MaxArea(vector<int>& height) 
{
    int left = 0, right = height.size() - 1;
    int maxV = 0;
    while(left < right)
    {
        int v = min(height[right], height[left]) * (right - left);
        maxV = v > maxV ? v : maxV;

        if(height[left] < height[right])
        {
            left++;
        }
        else
        {
            right--;
        }
    }

    return maxV;
}

4.有效三角形的个数

1.题目链接

• 题目链接

2.算法原理讲解

• 优化：对整个数组排序，可以简化比较模型，减少比较次数
• 在有序的情况下，只需较⼩的两条边之和⼤于第三边即可
• 设最⻓边枚举到max位置，区间[left, right]是max位置左边的区间(也就是⽐它⼩的区间)
  • if (nums[left] + nums[right] > nums[max])
    • 说明[left, right - 1]区间上的所有元素均可以与nums[right]构成⽐nums[max]⼤的⼆元组
    • 共有right - left种
    • 此时right位置的元素的所有情况相当于全部考虑完毕，right--，进⼊下⼀轮判断
  • if (nums[left] + nums[right] <= nums[max])
    • 说明left位置的元素是不可能与[left + 1, right]位置上的元素构成满⾜条件的⼆元组
    • left位置的元素可以舍去
    • left++进⼊下轮循环
      

3.代码实现

int TriangleNumber(vector<int>& nums) 
{
    // 优化：排序
    sort(nums.begin(), nums.end());

    int count = 0;
    for(int max = nums.size() - 1; max >= 2; max--) // 固定最大数
    {
        int left = 0, right = max - 1;
        while(left < right)
        {
            if(nums[left] + nums[right] > nums[max]) // 可以组成
            {
                count += right - left;
                right--;
            }
            else // 不可以组成
            {
                left++;
            }
        }
    }

    return count;
}