【C语言刷题】找单身狗、模拟实现atoi

一、找单身狗

题目描述：给定一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

比如：[1,1,2,2,3,3,4,4,5,6]

单身狗是：5和6

1.暴力循环法

对于这道题，我们最容易想到的方法就是暴力循环遍历了。

我们设置两个下标或者两个指针，两层for循环来进行遍历求解。

但是缺陷是时间复杂度过大。当数据量很大的时候，效率很低

这种方法的代码实现也比较简单，这里也就不在赘述了

2.分组异或法

我们其实在前面的文章种已经讲解过一个找单身狗的问题了，只不过那个问题是一个数组中只有一个单身狗。我们可以根据异或操作符的特性，直接将整个数组进行异或就可以求解问题。

但是这道题目，我们发现有两个单身狗。因此我们不能单纯的将整体数组进行异或从而进行求解。

但是我们可以采用类似的思路。巧妙的使用异或操作符

我们是这样思考的，我们有没有什么办法能将两个单身狗给分离出去呢？也就是说将一个数组给分割成两个数组

每一个数组都需要满足这两个条件，两个单身狗需要在两个数组中，不能再、在一个数组中，其次我们还需要满足相同的两个数在同一组中

分成了两组以后，那么问题就简单了，两组分别异或，就得到了两个单身狗

那么如何将一个数组分割成满足这些条件的两个数组呢？我们要根据什么进行分组呢？

其实我们仍然可以根据异或操作符进行分组

我们对整个数组进行使用异或操作符，那么我们就可以得到两个单身狗异或的结果。这个结果的二进制序列中有1的位就是这两个单身狗的区别。根据这个区别，我们就可以将整个数组中，对应的这个位为1的分为一组，对应的这个位为0的分为一组。这样我们就完成了分组

比如说：[1,1,2,2,3,3,4,4,5,6]这个数组中

第一步：将整体异或得到101^110=011

第二步：我们发现011中有两个位不一样，我们随便选定一个即可，我们选定第一位

第三步分组：将上面的数组全部写成二进制的形式

       [001,001,010,010,011,011,100,100,101,110]

       根据第一位的不同分组结果如下：

       第一组：[001,001,011,011,101]，即[1,1,3,3,5]

       第二组：[010,010,100,100,110]，即[2,2,4,4,6]

第四步：分别异或

第一组异或为5，第二组异或为6

最终代码如下：

#include<stdio.h>
void find_signal_dog(int* arr, int sz, int* p)
{
  int i = 0;
  int ret = 0;
  for (i = 0; i < sz; i++)
  {
    ret ^= arr[i];
  }
  int pos = 0;
  for (i = 0; i < 32; i++)
  {
    if (((ret >> i) & 1 )== 1)
    {
      pos = i;
      break;
    }
  }
  for (i = 0; i < sz; i++)
  {
    if (((arr[i] >> pos) & 1 )== 1)
    {
      p[0] ^= arr[i];
    }
    else
    {
      p[1] ^= arr[i];
    }
  }
}
int main()
{
  int arr[] = { 1,1,2,2,3,3,4,4,5,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int signal_dog[2] = { 0 };
  find_signal_dog(arr, sz, signal_dog);
  printf("%d %d", signal_dog[0], signal_dog[1]);
  return 0;
}

二、模拟实现atoi

1.atoi函数的功能

如下图所示，atoi的功能是将一个字符串转化为整型数字

2.模拟实现atoi

如何模拟实现atoi是一个难点

因为我们会遇到很多种情况

1.如果遇到空指针

2.如果遇到空字符串

3.如果遇到空白字符

4.如果遇到+-

5.如果遇到数据溢出

为了解决上面的问题，我们可以一点一点来思考，首先是空指针，我们直接使用断言即可

然后当我们遇到一个空字符串也就是''\0''的时候，我们可以直接返回0，但是这时候，我们会发现一个问题，这个0也有可能是正儿八经的'0'字符转化得到的，所以我们要进行区分

我们定义一个状态值。用来加以区分。我们默认是非法的数据

当我们遇到空白字符的时候，我们需要跳过这些空白字符，当我们遇到+- 的时候，我们就需要判断正负号了

处理完这些情况以后，就是正常的转化了，在转化的时候，我们先要保证str还有值，然后我们使用isdigit函数判断是否为数字字符，如果是，则直接转化，在转化的时候要注意越界，为了判断是否越界，我们将ret设置为longlong类型，这样就可以根据int的最大最小值进行判断了。处理好了以后，如果str所指向的为非数字字符，那么就是说，转化完成了，我们直接就可以返回这个ret了，这里的ret我们认为是非法的字符串转化得到的。最后当str遇到\0的时候，那么也是转化完成了，这样的转化我们认为是合法的。所以设置状态值为VALID，返回ret

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<ctype.h>
enum State
{
  VALID,
  INVALID
}state=INVALID;//默认是非法的
int my_atoi(const char* str)
{
  assert(str);
  if (str == '\0')
  {
    return 0;
  }
  //跳过空白字符
  while (isspace(*str))
  {
    str++;
  }
  //确认正负号
  int flag = 1;
  if (*str == '+')
  {
    flag = 1;
    str++;
  }
  if (*str == '-')
  {
    flag = -1;
    str++;
  }
  long long ret = 0;
  while (*str)
  {
    if (isdigit(*str))
    {
      ret = ret*10 + flag * (*str - '0');
      if (ret > INT_MAX)
      {
        return INT_MAX;
      }
      else if (ret < INT_MIN)
      {
        return INT_MIN;
      }
    }
    else
    {
      return ret;
    }
    str++;
  }
  state = VALID;
  return (int)ret;
}
int main()
{
  char* p = "1234";
  int a = my_atoi(p);
  if (state == VALID)
  {
    printf("%d\n", a);
  }
  else
  {
    printf("不合法的字符串：%d\n", a);
  }
  return 0;
}

本节内容就到这里

如果对你有帮助的话，不要忘记点赞加收藏哦！！！

想获得更多优质内容，一定要关注我哦！！！