都匀住房与城乡建设部网站,新网站优化怎么做,服装品牌建设网站的目的,外贸电商网站模板目录 一、找单身狗
1.暴力循环法
2.分组异或法
二、模拟实现atoi
1.atoi函数的功能
2.模拟实现atoi 一、找单身狗 题目描述#xff1a;给定一个数组中只有两个数字是出现一次#xff0c;其他所有数字都出现了两次。 编写一个函数找出这两个只出现一次的数字。 比如…目录 一、找单身狗
1.暴力循环法
2.分组异或法
二、模拟实现atoi
1.atoi函数的功能
2.模拟实现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^110011 第二步我们发现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 最终代码如下
#includestdio.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 #includestdio.h
#includestdlib.h
#includeassert.h
#includectype.h
enum State
{VALID,INVALID
}stateINVALID;//默认是非法的
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;
} 本节内容就到这里
如果对你有帮助的话不要忘记点赞加收藏哦
想获得更多优质内容一定要关注我哦
