学习日记--(复习qsort、学习枚举、指针)

标签：p2 p1 cur -- qsort int 枚举 nums1 nums2

1、两数之和

方法一：暴力枚举

思路：枚举数组中每一个数，寻找之后的数字是否存在target-x。

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {//不光要看数组中的x也就是每一个数都要检查一遍，还要对之后的数字进行检查，所以两层循环
            if (nums[i] + nums[j] == target) {
                int* ret = malloc(sizeof(int) * 2);//sizeof(int)意思是int数据类型的所占字节数，malloc分配内存函数对应的释放函数为free,malloc返回void*类型，地址赋给ret,ret是int类型的指针，指针是数组名，表示数组第一个元素的起始地址
                ret[0] = i, ret[1] = j;
                *returnSize = 2;//returnsize表示输出的值的个数，所以要赋值，因为要输出i,j，所以赋值为2
                return ret;
            }
        }
    }
    *returnSize = 0;//如果循环里没找出来，说明没有，就不用赋值了
    return NULL;
}

方法二：构建哈希函数，可惜目前只会数字计算哈希函数找出地址，不会代码

2、合并两个有序数组

方法一：直接合并后排序

用了刚学过的qsort函数，注意cmp函数的写法，还有题目没说要输出，只是要保存。

方法二：双指针

将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中

为两个数组分别设置一个指针p1,p2，作为队列的头部指针

 1 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
 2     int p1 = 0, p2 = 0;
 3     int sorted[m + n];//定义一个大小为m+n的名为sorted的数组
 4     int cur;//定义一个叫做cur的整型变量
 5     while (p1 < m || p2 < n) {//p1,p2相当于指针，虽然没给他分配内存
 6         if (p1 == m) {//说明此时（上一步更新的p1）已经走到nums1的尾部的后一个位置，接下去把nums2继续放入sorted数组就行
 7             cur = nums2[p2++];//此时cur=nums2[p2],p2=p2+1
 8         } else if (p2 == n) {//此时(上一步更新的p2)已经走到nums2尾部的后一个位置，把nums1的数值放到新数组就行
 9             cur = nums1[p1++];//此时cur=nums1[p1],p1=p1+1
10         } else if (nums1[p1] < nums2[p2]) {//选出小的更新sorted数组
11             cur = nums1[p1++];
12         } else {
13             cur = nums2[p2++];
14         }
15         sorted[p1 + p2 - 1] = cur;//用cur的数值更新sorted数组
16     }
17     for (int i = 0; i != m + n; ++i) {
18         nums1[i] = sorted[i];//根据题目要求，把sorted数组赋给nums1[]
19     }
20 

方法三：逆向双指针
p1、p2两个指针从nums1、nums2两个队列的末尾往前进行比较，较大的放到nums1的后面（在长度为m+n的n及之后的位置）

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = m - 1, p2 = n - 1;//从nums1(非0的最后一个数字的位置),nums2最后一个位置
    int tail = m + n - 1;//nums1的尾部位置为m+n-1
    int cur;
    while (p1 >= 0 || p2 >= 0) {
        if (p1 == -1) {//nums1已经遍历完了，用nums2[p2]更新nums1的尾部
            cur = nums2[p2--];
        } else if (p2 == -1) {//nums2已经遍历完了，用nums1[p1]更新
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {//选出较大的更新
            cur = nums1[p1--];
        } else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;//用变量cur更新nums1
    }
}

 

标签：p2,p1,cur,--,qsort,int,枚举,nums1,nums2
From： https://www.cnblogs.com/zhishiyigenicheng/p/16790101.html