【C/C++ 力扣leetcode】4道简单题

前言

刷题之——Leetcode道简单题，通过这4道简单题，C/C++有新的理解，提高你的编程能力。

leetcode地址

一、寻找正序数组的中位数

中位数的概念

中位数是一组数据中的一个特殊值，可以将这组数据划分为两个部分，其中一部分的数值比中位数小，另一部分的数值比中位数大。换句话说，中位数将数据集合分成了两部分，使得左右两边的数据量相等或差距很小。

在一个有序的数据集合中，中位数就是位于中间位置的值。如果数据集合的个数是奇数，那么中位数就是处于中间位置的那个数；如果数据集合的个数是偶数，那么中位数是中间两个数的平均值。

举个例子，假设有以下一组数据：2, 4, 7, 9, 11。这组数据中共有5个数，是奇数个。中位数就是处于中间位置的那个数，也就是7。

再举个例子，假设有以下一组数据：1, 3, 6, 8, 10, 12。这组数据中共有6个数，是偶数个。中位数就是中间两个数的平均值，(6+8)/2 = 7。

中位数是描述数据集中的典型值，它具有一定的抗干扰能力，因为中位数不受极端值的影响。在统计学、数据分析和排序算法等领域，中位数是一个常用的指标，能够帮助我们更好地了解数据的分布和趋势

C语言版

• 当为偶数时：n/2的下标数据加n/2-1的下标数据相加除以2就是结果。
• 当为奇数时：n/2的下标就是结果。

判断奇偶：

• 当数据个数除以2取余数为0，就是偶数count % 2 == 0
• 当数据个数除以2取余数为1，就是偶数count % 2 == 1

//nums需要寻找的数组
//size 得到nums数组元素个数 
double findMedianSortedArray(int *nums,int size)
{
  double ret = 0;
  /*判断奇偶*/
  if(size % 2 == 0)
  {
    ret += nums[size/2];
    ret += nums[size/2-1];
    ret /= 2;//取平均数
  }
  else
  {
    ret += nums[size/2];
  }
  return ret;
}

测试代码如下:

int main()
{
    int vec[5] = {1,2,3,4,5};
    printf("%lf",findMedian(vec,5));
    system("pause");
    return 0;
}

C++版

在C++版本我们可以用vector来替代参数1、2，如下代码：

double findMedian(vector<int> &v) 
{
    double  ret = 0;
    vector<double> tmp = v;
    int size = v.size();
    if(size % 2 == 0)//偶数
    {
        ret += tmp.at(size/2-1);
        ret += tmp.at(size/2);
        ret /= 2;
    }
    else
    {
        ret = tmp.at(size/2);
    }
    return ret;
}

在此不用size的原因：vector有成员函数得到数组的大小：vector<type>::size()

测试代码如下:

int main()
{
    vector<int> v{1,2,3,4,5,6};
    cout << findMedian<int>(v) << endl;
    system("pause");
    return 0;
}

在C++中，我们可以使用函数模板tempname <typename T,typename U>来扩大识别范围,扩大函数的使用范围,并且我们可以初始化模板来提高函数的便携性tempname <typename T = int,typename U = double>。代码如下所示：

template <typename T = int,typename U = double>
U findMedian(vector<T> &v) 
{
    U ret = 0;
    vector<T> tmp = v;
    int size = v.size();
    if(size % 2 == 0)//偶数
    {
        ret += tmp.at(size/2-1);
        ret += tmp.at(size/2);
        ret /= 2;
    }
    else
    {
        ret = tmp.at(size/2);
    }
    return ret;
}

测试代码如下:

int main()
{
    vector<int> v{1,2,3,4,5,6};
    cout << findMedian(v) << endl;
    system("pause");
    return 0;
}

二、寻找无序数组的中位数

相对于上面的找有序数组，我们无序数组只需要给他排序一下即可放入上面的函数获取结果。

在此我们使用最简单的冒泡排序

冒泡排序的概念

当我们需要对一组数据进行排序时，冒泡排序是一种常用且直观的排序算法。

冒泡排序的原理很简单，类似于我们在冒泡的时候，大的气泡会不断向上升，小的气泡会向下沉一样。

具体步骤如下：

1.首先，我们将待排序的数据分为两部分：已排序部分和未排序部分。

2.然后，从未排序部分的第一个元素开始，通过比较相邻的两个元素的大小，让较大的往后移动，较小的往前移动。这样一轮下来，最大的元素就会像气泡一样浮到了未排序部分的最后面。

3.接下来，重复上述步骤，不断地进行多轮比较和交换，直到所有的元素都按照从小到大的顺序排列好，也就是未排序部分已经变成了空集合。

冒泡排序的核心思想是通过不断比较和交换相邻元素的位置来达到排序的目的。每一轮比较都会让一个最大（或最小）的元素冒泡到正确的位置，所以称之为冒泡排序。

冒泡排序可能在每一轮中都进行多次比较和交换，直到没有需要交换的元素为止。尽管冒泡排序的效率较低，但它非常简单易懂，适用于简单的排序需求或者作为其他排序算法的一部分。

如果不好理解可以看下面视频动画理解：

C语言版

冒泡排序实现：

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

在这里我不讲冒泡排序，各位可以直接复制下来。在之后的课程中我会讲到。

double findOutOfOrderMidiean(int *nums,int size)
{
  bubbleSort(nums,size);//调用排序函数
  return findMedianSortedArray(nums,size);//调用寻找中位数函数，并返回
}

C++版

相对于C语言，C++简单多了，不需要写sort函数，因为C++已经提供给我们了。使用std::sort()函数即可排序头文件为#include <algorithm> using namespace std;

我们只需要放入**vector.begin()和vector.end()**即可排序。

排序代码如下:

template <typename T = int,typename U = double>
U findOutOfOrderMidiean(vector<T> &v) 
{
    U ret = 0;
    vector<T> tmp = v;
    sort(tmp.begin(),tmp.end());
    return findMedian(tmp);
}

三、整数反转

代码实现

int reverseInteger(int num) {
    int reversed = 0;
    while (num != 0) {
        int remainder = num % 10;
        if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && remainder > 7))
            return 0;
        if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && remainder < -8))
            return 0;
        reversed = reversed * 10 + remainder;
        num /= 10;
    }
    return reversed;
}

原理详解

代码解释如下：

当我们传入一个整数 num 给 reverseInteger 函数时，这段代码的目的是将该整数反转后返回。

1.int reversed = 0;: 创建一个变量 reversed，用于存储反转后的整数，默认值为0。

2.while (num != 0) {: 进入一个循环，只要原始整数不等于0，就会执行循环内的代码。

3.int remainder = num % 10;: 通过取原始整数的末位数字，得到一个变量 remainder，它存储了要添加到反转后整数的数字。

4.if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && remainder > 7)) return 0;: 这个条件判断用于检查反转过程中是否会导致整数溢出。如果反转后的整数 reversed 大于 INT_MAX 的十分之一，或者等于 INT_MAX 的十分之一并且 remainder 大于7（因为反转后的整数乘以10后再加上 remainder，如果大于 INT_MAX 就会溢出），则返回0，表示无法完成反转。

5.if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && remainder < -8)) return 0;: 类似于上一步，这个条件判断用于检查反转过程中是否会导致整数溢出。如果反转后的整数 reversed 小于 INT_MIN 的十分之一，或者等于 INT_MIN 的十分之一并且 remainder 小于-8（因为反转后的整数乘以10后再加上 remainder，如果小于 INT_MIN 就会溢出），则返回0，表示无法完成反转。

6.reversed = reversed * 10 + remainder;: 将原始整数的末位数字 remainder 加到 reversed 的末尾，同时将 reversed 扩大10倍。

7.num /= 10;: 除以10，将原始整数去除末位数字，以便进行下一轮循环。

8.当原始整数的所有位数都被处理完毕（等于0）时，退出循环。

9.return reversed;: 返回反转后的整数 reversed。

这段代码的关键在于通过每次取余和除以10的操作，将原始整数的末位数字逆序地添加到反转后的整数中，直到原始整数的所有位数都被处理完毕。同时，还加入了检查反转过程中是否会导致整数溢出的保护措施。

四、字符串转整数

原理详解

实现技巧：

在我们印象中，只需要实现转换符号和数字部分就可以了，如下图：

如图的分割线。

但其实我们实现还需要跳过数字前面的空格和不是数字的字符。

1、跳过空格

下列的i为此时的下标

while (str[i] == ' ') {
        i++;
    }

2、处理正负号

我们需要添加一个sign来最后计算最后是否需要添加符号。

原理：正正得正，正负得负，负负得正

int sign = 1;
if (str[i] == '-' || str[i] == '+') {
        sign = (str[i] == '-') ? -1 : 1;
        i++;
    }

3、转换数字：

/*循环条件使其必须是数字才转换*/
while (str[i] >= '0' && str[i] <= '9') {
        result = result * 10 + (str[i] - '0');
        i++;
    }

result = result * 10 + (str[i] - ‘0’);算法解释：

在代码中，result = result * 10 + (str[i] - ‘0’) 的目的是将字符串中的数字字符转换为对应的整数。

str[i] - ‘0’ 的运算实际上是将数字字符转换为对应的数值。在ASCII码中，数字字符的字符编码是连续的，即字符 ‘0’ 的编码是最小的，其后的字符 ‘1’、‘2’、‘3’、… 依次递增。所以，用字符 ‘0’ 的 ASCII 码值减去字符 ‘0’ 的 ASCII 码值，可以得到一个相对的数字值。

例如，对于字符 ‘5’ 而言，‘5’ - ‘0’ 的结果就是整数 5。这是因为 ‘5’ 的 ASCII 码值是 53，而 ‘0’ 的 ASCII 码值是 48，所以 53 - 48 等于 5。

通过将字符转换为数字值，我们可以将每一位的数字逐个添加到 result 中。通过不断乘以10，实现了将新的数字添加到个位、十位、百位等不同的位置上，最终得到整个整数。

例如，对于字符串 “12345”，代码会依次执行以下步骤：

1.result = result * 10 + (str[0] - ‘0’)：初始时，result 的值为0，将字符 ‘1’ 转换为整数1，并将其赋值给 result。

2.result = result * 10 + (str[1] - ‘0’)：此时，result 的值为1，将字符 ‘2’ 转换为整数2，并将其添加到 result 的十位上。

3.result = result * 10 + (str[2] - ‘0’)：此时，result 的值为12，将字符 ‘3’ 转换为整数3，并将其添加到 result 的百位上。

4.result = result * 10 + (str[3] - ‘0’)：此时，result 的值为123，将字符 ‘4’ 转换为整数4，并将其添加到 result 的千位上。

5.result = result * 10 + (str[4] - ‘0’)：此时，result 的值为1234，将字符 ‘5’ 转换为整数5，并将其添加到 result 的万位上。

所以，通过每次将新的数字乘以10并加到 result 上，最终可以得到反转后的整数值

代码实现

int myAtoi(const char *str)
{
    int result = 0;
    int sign = 1;
    int i = 0;
    // 跳过空格
    while (str[i] == ' ') {
        i++;
    }
    // 处理正负号
    if (str[i] == '-' || str[i] == '+') {
        sign = (str[i] == '-') ? -1 : 1;
        i++;
    }
    // 转换数字
    while (str[i] >= '0' && str[i] <= '9') {
        result = result * 10 + (str[i] - '0');
        i++;
    }
    return result * sign;
}

总结

博主能力有限。可能一些题有更优的做法，不过目前博主是个菜鸟，能做出来就ok了。同时，我们也应该多去总结一下，方便自己的复习的同时，也分享自己的学习过程，这样也挺不错的呀。这次就先到这里结束了，感谢游览。