【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组

​🌠 作者：@阿亮Joy
🎆专栏：《阿亮爱刷题》
🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

👉移动零👈

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1
  
  

进阶：你能尽量减少完成的操作次数吗？

思路一

利用下标 src 找到不为0的元素，再借助中间变量 tmp 将下标为 dst 的元素和 下标为 src 的元素进行交换。遍历数组之后，所有0就被移动到数组的末尾。具体移动操作：当 nums[src] == 0 时，src++；而当 nums[src] != 0 时，进行交换操作后，src++ dst++。

void moveZeroes(int* nums, int numsSize)
{

   int dst=0;
   int src=0;
   while(src<numsSize)
   {
       if(nums[src]!=0)
       {
           int tmp=nums[src];
           nums[src]=nums[dst];
           nums[dst]=tmp;
           src++;
           dst++;
       }
       else
           src++;
   }
}

思路二

利用下标 src 找不是零的元素，将不是零的元素放在下标 dst 的位置上，然后再将数组末尾的元素全部赋值为零。

void moveZeroes(int* nums, int numsSize)
{
    int src = 0;
    int dst = 0;
    while (src < numsSize)
    {
        if (nums[src] != 0)
        {
            nums[dst++] = nums[src++];
        }
        else
        {
            src++;
        }
    }
    //将数组末尾的元素赋值为0
    while (dst < numsSize)
    {
        nums[dst++] = 0;
    }
}

👉调整奇数偶数顺序👈

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

提示：

• 0 <= nums.length <= 50000
• 0 <= nums[i] <= 10000

思路：跟移动零的思路一样，只是判断条件变了。

int* exchange(int* nums, int numsSize, int* returnSize)
{
    int index=0;
    int pos=0;
    while(index<numsSize)
    {
        if(nums[index]%2)
        {
            int tmp=nums[index];
            nums[index]=nums[pos];
            nums[pos]=tmp;
            index++;
            pos++;

        }
        else
            index++;
    }
    *returnSize=numsSize;
    return nums;

}

👉颜色分类👈

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2
  
  

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

思路：这道题如果使用 qsort 库函数来解的话，将会显得很简单。在这里，博主就不介绍这种方法了。在这里给大家介绍另一种方法，见下图：

void sortColors(int* nums, int numsSize)
{
    int left = 0;
    int right = numsSize - 1;
    int src = 0;
    while (src <= right)
    {
        if (nums[src] < 1)
        {
            int tmp = nums[src];
            nums[src] = nums[left];
            nums[left] = tmp;
            left++;
            src++;
        }
        else if (nums[src] == 1)
            src++;
        else
        {
            int tmp = nums[src];
            nums[src] = nums[right];
            nums[right] = tmp;
            right--;
        }

    }
}

分析：这道题其实推而广之，num的值可以为任意整数。只不过这道题的num值为1。最需要注意的就是，循环条件是src <= left。如果循环条件错了的话，就无法通过测试了。还需要注意的是，nums[src] 和 num 的大小关系不同，对应着不同的情况。

👉有序数组的平方👈

给你一个按非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序 排序。

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：
平方后，数组变为 [16,1,0,9,100]；排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104 nums 已按 非递减顺序 排序
  
  

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

思路一

先将数组中的元素先平方，然后再利用快排对数组进行排序。时间复杂度为O(N+N*logN)，空间复杂度为O(1)。

int cmp(int* a, int* b)
{
    return *a - *b;
}
int* sortedSquares(int* nums, int numsSize, int* returnSize) 
{
    int* num = (int*)malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++)
    {
        nums[i] = nums[i] * nums[i];
    }
    qsort(nums, numsSize, sizeof(int), cmp);
    *returnSize = numsSize;
    return nums;
}

思路二

数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。见下图分析：

int* sortedSquares(int* nums, int numsSize, int* returnSize) 
{
    int* num = (int*)malloc(sizeof(int) * numsSize);
    if(num == NULL)
    {
        *returnSize = 0;
        return num; 
    }
    int left = 0;
    int right = numsSize - 1;
    int index = numsSize - 1;
    while (left <= right)
    {
        if ((nums[left] * nums[left]) > (nums[right] * nums[right]))
        {
            num[index--] = nums[left] * nums[left];
            left++;
        }
        else
        {
            num[index--] = nums[right] * nums[right];
            right--;
        }
    }
    *returnSize = numsSize;
    return num;
}

👉有效的山脉数组👈

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：

• arr.length >= 3
• 在 0 < i < arr.length - 1 条件下，存在 i 使得：
  • arr[0] < arr[1]< ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例 1：

输入：arr = [2,1]
输出：false

示例 2：
输入：arr = [3,5,5]
输出：false

示例 3：
输入：arr = [0,3,2,1]
输出：true

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

思路：判断是山峰，主要就是要严格地保证从左边到中间和从右边到中间是递增的。这样可以使用两个指针，left 和 right，让其按照如下规则移动，如图：

注意：因为left和right是数组下标，移动的过程中注意不要数组越界。如果left或者right没有移动，说明是一个单调递增或者递减的数组，依然不是山峰。

bool validMountainArray(int* arr, int arrSize)
{
    if (arrSize < 3)
        return false;
    int left = 0;
    int right = arrSize - 1;
    //防止越界
    while ((left < arrSize - 1) && (arr[left] < arr[left + 1]))
    {
        left++;
    }
    //防止越界
    while ((right > 0) && (arr[right] < arr[right - 1]))
    {
        right--;
    }
    //如果left或者right在起始位置，说明不是山峰
    if ((left == right) && (left != 0) && (right != arrSize - 1))  return true;
    return false;
}

👉总结👈

本篇博客主要讲了五道题目，这五道题目或多或少都运用到了双指针的思想。双指针这个思想非常地重要，希望大家能够学会！如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！！！💖💝❣️