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

使用快慢指针，快慢指针的模板

1. 定义快慢指针，s=0、q=1
2. 快指针在外层循环 q < numsSize
3. s、q指向相等值时让快指针++，如果s、q指向不同值时，q值给s+1，因为之前它俩一样，但是s是慢值，所以它指向某值第一次出现位置，所以下一个是可覆盖位置。
4. 返回个数s+1，因数组0起始原因

int removeDuplicates(int* nums, int numsSize)
{
	int q = 1, s = 0;
	// 快指针外层走完一圈
	while (q < numsSize)
	{
		// 相等和不相等
		if (nums[q] != nums[s])
		{
			// 快给慢 先让s到前面去，当前s位置为某个数第一次出现位置
			nums[++s] = nums[q++];
		}
		else
		{
			q++;
		}
	}
	// s指向位置是size-1
	return s+1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

27. 移除元素

顺序表做删除，使用快慢指针模板

1. q = 0, s = 0 (这个q要从0开始，因为每一位都要对比是不是val)
2. 外层：q
3. nums[q] == val，则：q++；反之给s，s相当于数组当前位置，重新写入所有新元素
4. 注意s越界，提交后通过vs调试可发现。
5. 直接返回s，因为使用了s++

int removeElement(int* nums, int numsSize, int val) {
	int q = 0, s = 0;
	while (q < numsSize)
	{
		if (nums[q]==val)
		{
			q++;
		}
		else
		{
			if (s < numsSize)
			{
				nums[s++] = nums[q++];
			}
		}
	}
	return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

88 合并两个有序数组

题目要求：nums1总是较大用0留位置或为空，当nums1不为空，挪动2到1种

1. 定义3个指针：end1，end2，以及要倒着在nums1中放元素，创建nums1的末位指针i=end1+end2-1。比较end1，谁大，谁的指针- -，并放到nums1的末位指针处。
2. 但是上面步骤要在end1和end2都大于等于0做，当出现某一方完了应该停止。
3. 当end1完后如下1情况，可以结束，但是end2需要再做。

ex1：
【1，2，3，0，0，0】 【2，5，6】
2的6大【1，2，3，0，0，6】
2的5大【1，2，3，0，5，6】
1的3大【1，2，3，3，5，6】
2的2大【1，2，2，3，5，6】 // 尽量不动1 等于算nums2大
nums2做完了，就能结束
ex2：
【1，2，3，0，0，0】 【-1，0，6】
2的6大【1，2，3，0，0，6】
1的3大【1，2，3，0，3，6】
1的2大【1，2，3，2，3，6】
1的1大【1，2，1，2，3，6】
nums1做完了，但是nusm2还剩余
发现需要继续让nums2的值给nums1
【-1，0，1，2，3，6】

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
// 若一个没有，则返回另外一个
if (nums1[0])
{
;
}
// 两个指针
int end1 = m-1, end2 = n-1;
int i = m + n - 1;
while (end1 >= 0 && end2 >= 0)
{
if (nums1[end1] > nums2[end2])
{
// 因为升序，谁大，给末尾放谁，有一个完，就停止
nums1[i–] = nums1[end1–];
}
else
{
nums1[i–] = nums2[end2–];
}
}
// nums2结束，不需要动，nums1结束
while (end2>=0)
{
nums1[i–] = nums2[end2–];
}
}

189 轮转数组

思路：
当右旋后，原始数组中本在i位置的元素到了** (i+k)%n **位置

void rotate(int* nums, int numsSize, int k){
    int newArr[numsSize];
	for (int i = 0;i < numsSize; i++)
	{
		newArr[(i+k)%numsSize] = nums[i];
	}
	for (int i = 0; i < numsSize; i++)
	{
		nums[i] = newArr[i];
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

989 数组形式的整数加法

思路：
数组中从末位挨个读取，然后挨个拿k的末位，求和的值放入新数组：res[size++]

注意：

1. 必须拿新数组res存，因为可能有进位，num不能再开，此题returnSize是求和得到的值位数。所以malloc新的大小空间数组
2. malloc多大？因为k最大10^4，所以最多4位，当nums较小或k较小，可能影响nums从4到5，当nums较大，只可能影响nums进1位，所以这里选fmax(5, size+1); 尽量开大一点点也没事。
3. 这里包含了交换数组的写法：i=0，i
4. 下面写法中，第一波for循环，做挨个加法，第二波，怕数组完了k还没加完。
5. 最后再逆转，因为我们res的值是从左到右的。res[numsize++] = ；

// 算法最low的且必须要会的就是解决溢出，不要企图用变量来存任何运算结果
int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
    int* res = malloc(sizeof(int) * fmax(5, numSize + 1));
    // 一位位运算
    int per = 0;
    int sum_per = 0;
    int i = 0;
    *returnSize = 0;
    for (i = numSize-1; i >= 0; i--)
    {
        sum_per = num[i] + k%10;
        res[(*returnSize)++] = sum_per % 10;
        // k是加的数，每加1位，除以10，如果有进位，k+1，学习这种做法 ，有进位，直接k+1
        // 如果k成了0 上面也不会再+k的部分，上面的res运算会是num[i]
        k /= 10;
        if (sum_per > 10)
        {
            k++;
        }
    }
    // 可能k没加完
    while (k > 0)
    {
        res[(*returnSize)++] = k % 10;
        k /= 10;
    }

    // 再交换一下
    int t;
    for (int i = 0;i < (*returnSize)/2; i++)
    {
        t = res[i];
        res[i] = res[(*returnSize)-1-i];    // size-1-i就是倒数第i个
        res[(*returnSize)-1-i] = t;
    }
    return res;
}


int main()
{	
	int nums[4] = { 1,2,0, 0 };
    int b = 0;
    int* m = addToArrayForm(nums, 4, 34, &b);
    for (int i = 0; i < b; i++)
    {
        printf("%d ", m[i]);
    }
    return 0;
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51