每日回顾：用C写简单的数组OJ题

移除元素

分析：需要遍历数组；要求原地移除，就在原数组上修改；使用前后两个指针即可解决

int removeElement(int* nums, int numsSize, int val) {
	int des = 0, src = 0;
	while (src < numsSize) {
		if (nums[src] == val) {
			src++;
		}
		else {
			nums[des++] = nums[src++];
		}
	}
	return des;
}

删除有序数组中的重复项

分析：是上一个题的变体，依然是原地修改的思想，不过前后下标指针的初始化注意一下

int removeDuplicates(int* nums, int numsSize) {
	int des = 0, src = 1;
	while (src < numsSize) {
		if (nums[src] == nums[des]) {
			src++;
		}
		else {
			nums[++des] = nums[src++];
		}
	}
	return des + 1;
}

合并两个有序数组

分析：依然是之前题的变体；需要三个下标指针辅助移动元素，比较和移动同时进行；如果从前往后移动，发现会有覆盖，那么从后往前移动，就可以解决问题。

注意：src1 和 src2 都可能发生越界，如果 src2 先越界，由于 nums1 中剩余元素已有序，合并结束；如果 src1 先越界，需要将 nums2 的所有元素依次移动到 nums1 的前面

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
	int des1 = m + n - 1, src1 = m - 1, src2 = n - 1;
	while (src2 >= 0 && src1 >= 0) {
		if (nums2[src2] > nums1[src1]) {
			nums1[des1--] = nums2[src2--];
		}
		else {
			nums1[des1--] = nums1[src1--];
		}
	}
	while (src2 >= 0) {
		nums1[des1--] = nums2[src2--];
	}
}

轮转数组

分析：凡是出现类似左右轮转操作的，都可以尝试使用经典的三次反转数组的方法解决；如果使用三次反转，空间复杂度为 O(1)；

但是如果经验比较少，可能最先想到的就是使用额外的数组来暂时存储被轮转的元素，然后将原数组的前 numsSize-k 个元素向后移动 k 位；

解法一：使用额外数组

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
	int* tmp = (int*)malloc(sizeof(int) * k);
	
	//移动后 k 个元素
	int i = numsSize - k;
	int j = 0;
	while (i < numsSize) {
		tmp[j++] = nums[i++];
	}

	//前 numsSize-k 个元素向后移动
	int des = numsSize - 1, src = numsSize - 1 - k;
	while (src >= 0) {
		nums[des--] = nums[src--];
	}

	//tmp 数组拷贝到原数组
	for (int i = 0; i < k; i++) {
		nums[i] = tmp[i];
	}
}

解法二：三次反转

void reverse_array(int* a, int begin, int end) {
	//区间不正确
	if (begin >= end) {
		return;
	}
	while (begin < end) {
		int tmp = a[begin];
		a[begin] = a[end];
		a[end] = tmp;
		begin++;
		end--;
	}
}

void rotate(int* nums, int numsSize, int k) {
	if (numsSize <= 1) {
		return;
	}
	k = k % numsSize;
	//逆序整个数组
	reverse_array(nums, 0, numsSize - 1);
	//逆序前 k 个元素
	reverse_array(nums, 0, k - 1);
	//逆序后 numsSize-k 个元素
	reverse_array(nums, k, numsSize - 1);
}

数组形式的整数加法

分析：初步想法如代码一，将 num 转换为整数，与 k 相加后，再转换回数组，但即使 使用了 long long 长整型，还是被 num = [9,9,9,9,9,9,9,9,9,9] 的测试用例卡住了；

代码一 

void reverse_array(int* a, int begin, int end) {
	//区间不正确
	if (begin >= end) {
		return;
	}
	while (begin < end) {
		int tmp = a[begin];
		a[begin] = a[end];
		a[end] = tmp;
		begin++;
		end--;
	}
}

int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
	//num 转换为整数 sum
	long long sum = 0;
	for (int i = 0; i < numSize; i++) {
		sum = sum * 10 + num[i];
	}

	//num + k
	sum = sum + k;

	//结果转换为数组
	//1、sum 有 cnt 位
	int tmp = sum, cnt = 0;
	while (tmp) {
		tmp = tmp / 10;
		cnt++;
	}
	//2、取出 sum 的每一位存进数组
	int* ps = (int*)malloc(sizeof(int) * cnt);
	tmp = sum;
	for (int i = 0; i < cnt; i++) {
		ps[i] = tmp % 10;
		tmp /= 10;
	}
	//此时，ps 中是逆序存放的
	reverse_array(ps, 0, cnt - 1);
	*returnSize = cnt;
	return ps;

}

第二种常规想法：将 k 直接转换成数组，然后将 num 和 k 的数组元素逐个相加，但是还需要考虑进位问题

代码二

写的太挫，直接放上官解

int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
    int* res = malloc(sizeof(int) * fmax(10, numSize + 1));
    *returnSize = 0;
    for (int i = numSize - 1; i >= 0 || k > 0; --i, k /= 10) {
        if (i >= 0) {
            k += num[i];
        }
        res[(*returnSize)++] = k % 10;
    }

    for (int i = 0; i < (*returnSize) / 2; i++) {
        int tmp = res[i];
        res[i] = res[(*returnSize) - 1 - i];
        res[(*returnSize) - 1 - i] = tmp;
    }
    return res;
}

作者：力扣官方题解