目录

• 1. leetcode 203.移除数组元素
• • 解法一
  • 解法二
• 2. leetcode 26. 删除有序数组中的重复项
• • 解法
• 3. leetcode88. 合并两个有序数组
• • 解法一
  • 解法二(推荐)
• 4. 189. 旋转数组
• • 解法一
  • 解法二
• 5. 989. 数组形式的整数加法
• • 解法

1. leetcode 203.移除数组元素

/*203. 移除数组元素
* 
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

https://leetcode-cn.com/problems/remove-element/

该题分三种思路

解法一

  数组中元素多少是固定的，可以通过遍历数组的方法，将数组遍历一编，将满足条件的元素继续放入数组中，不满足条件的元素不放入数组，最后返回数组与数组大小。

// 遍历数组，将不用删除的元素放入数组
int removeElement1(int* nums, int numsSize, int val) {
    int j = 0;
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] != val)
        {
            nums[j++] = nums[i];
        }
    }
    return j;
}

解法二

  使用计数器记录待删除元素出现次数，判断当前元素是否为待删除元素，如果是，则计数器自增1，如果不是，将该元素向前搬移计数器大小步，，计数器大小代表了当前元素应向数组的什么位置存放数据

// 使用计数器记录元素出现个数，如果当前值不是删除的元素则将该元素向前移动count步
int removeElement2(int* nums, int numsSize, int val)
{
    int count = 0;

    for (int i = 0; i < numsSize; i++)
    {
        if (val == nums[i])
            count++;
        else
            nums[i - count] = nums[i];
    }

    return numsSize - count;
}

2. leetcode 26. 删除有序数组中的重复项

* 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
* https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

解法

  原地搬移数组中元素，因为数组为有序数组，则使用两个指针，两个指针都指向数组头，一个指针用来表示已存放数据的多少，一个指针用来表示当前遍历到数组的第几位。通过两个指针进行判断。
  第一步，将数组第一位直接放入数组，第二步，判断待加入数组与以放入数组的元素是否相同，相同则跳过。

// 因为数组有序，则将第一项加入数组，判断新加入项是否等于已构造好的数组最后一项，相同则不加入
int removeDuplicates(int* nums, int numsSize) 
{
	// 如果长度为1 则数组不重复
	if (numsSize < 2)
		return numsSize;

	int count = 0;

	//nums[count++] = nums[0];
	for (int i = 1; i < numsSize; i++)
	{
		if (nums[count] != nums[i])
			nums[++count] = nums[i];
	}

	return ++count;
}

3. leetcode88. 合并两个有序数组

 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1] 

提示：
	nums1.length == m + n
	nums2.length == n
	0 <= m, n <= 200
	1 <= m + n <= 200
	-109 <= nums1[i], nums2[i] <= 109

* https://leetcode-cn.com/problems/merge-sorted-array/

解法一

  根据题目要求，要将所有数据放入num1数组中，所以使用双指针来进行计算。
  两个指针分别遍历两个数组，其中比较两个下标位置元素值大小，哪个元素小，就将哪个元素放入数组。直到遍历完一个数组，最后将没有遍历完的数组元素一次放入num1中。
  该方法需要新开辟一个数组空间，空间复杂度较高。

// 1. 使用两个下标，分别遍历两个数组，哪个下标的元素小，就将哪个小标元素放入数组\
// 需要辅助空间，不然在比较时会导致错误的数据读取
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
	int pnums1 = 0;
	int pnums2 = 0;
	int count = 0;
	int* arr = (int*)malloc(sizeof(int) * (m + n));

	// 逐个比较，将较大值放入数组
	while (pnums1 < m && pnums2 < n)
	{
		if (nums1[pnums1] >= nums2[pnums2])
		{
			arr[count++] = nums2[pnums2++];
		}
		else
		{
			arr[count++] = nums1[pnums1++];
		}
	}

	// 判断两个数组中哪个没有完成数据的转移，将剩余数据进行转移
	while (pnums1 < m)
		arr[count++] = nums1[pnums1++];
	while(pnums2 < n)
		arr[count++] = nums2[pnums2++];

	nums1 = arr;
}

解法二(推荐)

  该方法与上述方法大致相同，但是不用开辟新的空间。
  因为nums1中的空间已经足够存储，所以从两个数组的最后开始遍历，将较大元素放入，num1中的最后一个位置。

// 2.同样使用两个下标，第一个下标指向第一个数组的最后一个元素的位置，第二个下标指向第二个数字中最后一个元素的位置
// 使用一个指针指向最后一个空间的位置，将两个下标指向的元素最大值放到，空间最后一个位置处
void merge2(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int end = m + n - 1;
	int i = m - 1;
	int j = n - 1;

	// nums1 数组长度较长，所以数据会存储在该数组中，存储时数据有序，所以在比对完nums2时，nums1有可能没有比对到头的位置
	// 要保证nums2全部插入到nums1中，nusm1中本身按照顺序存有数据，所以nums1 没有比对到头也不影响结果
	while (j >= 0)
	{
		if (i >= 0 && nums1[i] > nums2[j])
		{
			nums1[end--] = nums1[i--];
		}
		else
		{
			nums1[end--] = nums2[j--];
		}
	}
}

4. 189. 旋转数组

189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

* https://leetcode-cn.com/problems/rotate-array/

解法一

  可以将旋转个数的元素，进行存储，最后对原数组内容进行移动，最后将旋转的元素存入数组中

解法二

采用先局部逆置，后整体逆置的思想进行解决

void reverse(int* nums, int start, int end)
{
	while (start < end)
	{
		int num = nums[start];
		nums[start] = nums[end];
		nums[end] = num;
		start++;
		end--;
	}
}

// 先局部逆置元素，最后整体逆置数组元素，即可达到旋转效果
void rotate(int* nums, int numsSize, int k) 
{
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, numsSize - k, numsSize - 1);
	reverse(nums, 0, numsSize - 1);
}

5. 989. 数组形式的整数加法

989. 数组形式的整数加法
* 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

示例 1：
输入：A = [1,2,0,0], K = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：
输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：
输入：A = [2,1,5], K = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

示例 4：
输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
输出：[1,0,0,0,0,0,0,0,0,0,0]
解释：9999999999 + 1 = 10000000000

提示：
1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
如果 A.length > 1，那么 A[0] != 0

https://leetcode-cn.com/problems/add-to-array-form-of-integer/

解法

1. 申请存储空间，因为待加数长度不定，所以要申请足够的空间
	`size > 5 ? szie+1 : 5+1`
2. 取出数组中的最后一位与数字的个位，进行相加，将加数地位存入数组，并存储进位
3. 判断待加数是否为0，如果k不为0，并且数组中元素已经加完，则将待加数按位存入数组
4. 判断数组中最前方元素是否含有空余位置，如果有则将数组向前搬移

// 输入：A = [1,2,0,0], K = 34
// 思路：取出数组最后一个元素，和k中的个位数值相加，有进位则将进位存储到进位标志位中，并且将计算结果放入数组
int* addToArrayForm(int* num, int numSize, int k, int* returnSize) 
{
	// 申请保存数据的空间
	int size = numSize > 5 ? numSize + 1 : 5 + 1;

	int* returnArr = (int*)calloc(size, sizeof(int));

	int arrLen = size - 1;
	int count = 0;
	// 按位计算
	while(numSize > 0)
	{
		k += num[numSize - 1];
		returnArr[arrLen] = k % 10;
		k /= 10;
		arrLen--;
		count++;
		numSize--;
	}

	// 如果k没有被除尽
	while (k > 0)
	{
		returnArr[arrLen--] = k % 10;
		k /= 10;
		count++;
	}

	// 判断是否用完了申请的空间，如果有空余空间没有使用，则将后方数据向前移动
	if (*returnSize < size)
	{
		memmove(returnArr, returnArr+(size - count), sizeof(int) * count);
	}
	*returnSize = count;

	return returnArr;
}