《剑指offer》笔记
替换空格为%20
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy.
背景
在网络编程中，如果URL参数中含有特殊字符，如空格、#等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在%后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20,因此空格被替换成%20。再比如 # 的ASCII码为35，即十六进制的0x23，它在URL中被替换为%23.
初始思路
这个是我想出来的单指针法，首先先遍历一次字符串，获得空格的个数，然后根据空格的个数确定改变之后的字符串的长度！
首先我定义了两个len用来获取关检位置的指针，还是先将字符逐个移动，然后遇到空格的时候需要一定的指针运算才能实现！
void my_replace(char * str)
{
int k_num = 0;//定义空格数目
int add_num = 0;
int len = 0;//新字符串的长度
int len2 = 0;
char *m_str = str;
assert(str != NULL);
while (*m_str++)
{
if (*m_str == ' ')
k_num++;
}
len2 = strlen(str) + 2 * k_num;
len = strlen(str);
int i = 0;
m_str = str + len;
while (*m_str != *str)
{
//如果遇到的不是空格
if (*m_str != ' ')
*(m_str + 2*k_num) = *m_str;
else
{
*m_str = '%';
*(m_str + 1) = '2';
*(m_str + 2) = '0';
for (i = 2; i >=0; i--)
*(m_str + i + 2) = *(m_str + i);
}
m_str--;
}
}
但是这种实现方式不太容易理解，代码量也是非常多！
更加高效的解法
我们可以先遍历一次字符串，这样就能统计出字符串中空格的总数，可以山此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2,因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。我们还是以前面的字符串"We are happy.”为例，"We are happy.”这个字符串的长度是14(包括结尾符号’\0’)，里面有两个空格，因此替换之后字符串的长度是18！
使用两个指针轻松解决此问题：
如图，p1指针指向\0，p2指针指向我们预期结果的字符串的末尾：
- 逐个字符复制，p1向前走一步同时p2向前走一步就复制一个字符，直到p1遇到空格就停止
- 当p1遇到空格的时候，p2连续做三次减法，同时分别赋值为
%、2、0，p1在向前走一步准备开始下一轮复制字符 - 同样的道理循环开始下一轮复制，p1指针一直再往前走，只要p1走到字符串开头的位置便停止循环
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
void my_replace2(char * str)
{
char *p1 = NULL;
char *p2 = NULL;
int len = 0;
assert(str != NULL);
len = strlen(str);
p1 = str + len;
p2 = str + len + 4;
while (*p1 != *str)
{
if (*p1 != ' '){
*p2 = *p1;
p2--;
p1--;
}
else
{
p1--;
*(p2--) = '0';
*(p2--) = '2';
*(p2--) = '%';
}
}
}
int main(void)
{
char str[30] = "we are happy";
// "we%20are%20happy";
printf("%s\n",str);
my_replace2(str);
printf("%s\n", str);
system("pause");
}
考点
1、考查对字符串的编程能力。
2、考查分析时间效率的能力。我们要能清晰地分析出不同方法的时间效率各是多少。
3、考查对内存覆盖是否有高度的警惕。在分析得知字符串会变长之后，我们能够意识到潜在的问题，并主动和面试官沟通以寻找问题的解决方案。
4、考查思维能力。在从前到后替换的思路被面试官否定之后，我们能迅速想到从后往前替换的方法，这是解决此题的关键。
原文地址：https://zouchanglin.github.io/2018/05/04/2018050401/
菲波那切数列的第n项
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为”兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>2，n∈N*）
递归解法（教科书解法）
很多C语言的教科书在讲述递归函数的时候，都会把菲波那切数列当成一个非常经典的例子，因此很多人要是看到这种问题心里一定忍不住一整窃喜，并且能够很快的写出代码：
int get_fibonacci(int num){
if (num <= 0)
return 0;
if (num == 1)
return 1;
return get_fibonacci(num - 1)+get_fibonacci(num-2);
}
虽然教科书反复的把这个例子当做讲解递归函数的典例，然而并不能说明这个问题就真的适合这道题目，大家都知道递归函数的可读性很强，但是效率却成了大问题，当我要用这个函数求get_fibonacci(100)的时候，我听见电脑的风扇在咆哮！！！而且迟迟得不到结果，最后我试了一下，在计算get_fibonacci(40)的时候电脑就已经比较吃力了！
我们就以f(10)来分析递归的求解过程，想要求f(10)，需要先求f(9)和f(8)，同样的道理，要求f(9)需要先求f(8)和f(7)，很明显f(8)多求了一次，如此递归下去会有很多重复的部分…
递归之所以慢的原因有两处
- 使用递归的方式求解重复计算的地方太多
- 使用递归在不停的调用函数，开销很大，导致速度慢
int get_fibonacci(int num){
if (num <= 0){
return 0;
}
if (num == 1 || num == 2){
return 1;
}
int a = 1;
int b = 1;
int c = 2;
int i = 0;
for (i = 2; i < num; i++){
c = a + b;
a = b;
b = c;
}
return b;
}
数学公式法
斐波那契数列是可以通过数学归纳法得出公式的，我们只需要求解后面的矩阵即可得到f(n)，只不过这种方法不是很常用
#include<math.h>
int get_fibonacci(int n){
return (pow((1 + sqrt(5.0)) / 2, n) - pow((1 - sqrt(5.0)) / 2, n)) / sqrt(5.0);
}
斐波那契数列和青蛙跳台阶问题:
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求青蛙跳到一个n级的台阶总共有多少种跳法？
首先我们思考最简单的情况，如果只有一级台阶，很显然只有一种跳法。如果有两级台阶，那么就有两种跳法：一种是一次跳2级，另一种是分两次跳，每次跳一级。
我们将跳法数目当做是台阶数目的函数f(n),当有n级台阶的时候，第一次跳就有两种不同的选择，如果是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1),如果是第一次就跳2级，此时跳法数目等于后面的n-2级台阶的跳法数目，即为f(n-2)。则n级台阶的跳法数目就是f(n) = f(n-1) + f(n-2)，不难看出这就是斐波那契数列了！
函数递归时一定要在可读性和效率上面权衡
遇到复杂的问题先从最简单的情况入手，找规律
杨氏矩阵的元素查找
在一个二维数组中每一行的元素都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，请完成这样一个函数，输入这个二维数组和要查找的元素，判断数组中是否存在该整数！
如果只是简单的完成这个函数的功能我们只需要将这个二维数组遍历一遍便可以得出结果，但是还要考虑查找效率的话就必须另辟蹊径了。通过题目我们可以得到数组中每行元素和每列元素都是递增的，看似复杂的问题我们只需要先将它具体化，比如存在一个这样的二维数组：
1 2 8 9 11
2 4 9 12 15
4 7 10 13 17
6 8 11 15 19
7 9 12 16 22
在数组中间选择一个数(黑色方格),根据它的大小判断数字可能出现的区域
通过分析我们知道，首先选取数组右上角的数字，如果该数字等于要查找的数字，则查找结束；如果该数字大于这个数字所在的列，就剔除这个数字所在的列；如果该数字小于这个数字所在的列，就剔除这个数字所在的行。也就是说，如果查找的数字不在数组的右上角，则每一次都在数组查找的范围中剔除一行或者一列，这样的话每一步都在缩小查找的范围，直到找到为止，或者查找范围为空！
这个方法用到了返回型参数，行列通过x和y传入，如果找到匹配的元素就通过x和y返回，找不到就返回(-1,-1)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void find(int arr[3][3], int *px, int * py, int key){
assert((arr != NULL)&&(*px != 0)&&(*py != 0));
int x = 0;
int y = *py-1;
while((x<=*px)&&(y>=0)){
if(arr[x][y] == key){
*px = x;
*py = y;
return;
}
else if(arr[x][y]>key){
y--;
}
else{
x++;
}
}
*px = -1;
*py = -1;
}
下面这种写法是将二维数组的地址传入，并且把二维数组当做是一维数组考虑，传入的是数组地址，行数和列数，以及要查找的值，返回值是bool型，表示有没有找到
注意：早期的标准C语言是没有bool类型的，C语言的bool类型只有在C99标准或者C99标准之后才有的数据类型。如果考虑到兼容性的话不太建议这种用法
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
bool find(int* arr, int rows, int cols, int key){
bool ret = false;
if (arr != NULL && rows > 0 && cols > 0){
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0){
if (arr[row*cols + col] == key){
ret = true;
break;
}
else if (arr[row*cols + col] > key){
--col;
}
else{
++row;
}
}
}
return ret;
}
我的另一种实现方式
先将要查找的元素在每一行的范围进行对比如果在此行范围内，则对此行进行二分查找，return 1表示找到，return 0 表示未找到
int find_num(int arr[3][3],int x,int y,int key){
assert((arr != NULL)&&(x != 0)&&(y != 0));
//遍历每行首元素和尾元素
int i = 0;
int j = 0;
//逐行遍历
for (i = 0; i < x; i++){
//说明在这一行中
if (key >= arr[i][0] && key <= arr[i][y - 1]){
//开始二分查找
int left = 0;
int right = y - 1;
while (left <= right){
register int mind = (right - left) / 2 + left;
if (arr[i][mind]== key){
return 1;
}
else if (arr[i][mind] < key){
left = mind + 1;
}
else{
right = mind - 1;
}
}
}
}
return 0;
}
结语
二维数组在内存中仍然是连续的空间，在内存中从上到下存储各行元素，在同一行中是从左到右的顺序存储，所以我们可以根据行号和列号计算出相对于数组首地址的偏移量，从而找到对应的元素!
当解决这种复杂问题的时候先把问题具体化、简单化、从中寻找规律从而找到解决问题的突破口!
原文地址：https://zouchanglin.github.io/2018/05/28/2018052801/
自定义函数实现atoi
atoi函数是用来把一个字符串转化为一个整数，比如输入“1234”，那么就会得到1234这个数字，如果中途遇到非数字字符，那么从那里就开始中断解析，比如输入“1234A567”，得到的结果就是1234。这是库函数的实现方式，接下来我们需要自己实现一个atoi函数！
代码<初始版本>
很多人认为这个问题非常简单，非常轻松地就写出了代码：
int my_atoi(char* str)
{
int num = 0;
while (*str)
{
num = num * 10 + * str - '0';
str++;
}
return num;
}
然后这段代码经过测试之后确实是漏洞百出，比如我们输入“1234A567”，我们得到的结果并不是1234，不仅仅是这样的问题，连输入字符串是空指针的情况也是没有检查的！
实际上，在本示例中，我们应该考虑到如下的情况：
1、输入的字符指针为空指针
2、输入的字符指针指向为一个空串，虽然不是空指针，但是还是无法从中转换出任何数字
3、对于中间0~9、-、+之外的非法输入，并没有作出任何判断和处理
4、首字符不是数字，比如是+或者-，这样的数字表示正数和负数，也应该被合法解析
5、传入的参数字符串是不应该被修改的，但是此处没有被const修饰
6、如果传入的是空格，那么函数返回的是0，如果传入的是0那么也是返回0，我们需要区分这两种情况
代码<优化版本>
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
int is_num = 1;//1表示正确转换
int my_atoi2(const char *str)
{
int num = 0;
//先断言是否是空指针
assert(str != NULL);
//断言是否是空串
assert(strlen(str) != 0);
//先判断第一个字符是否是非法值
if (*str == '-') //负数执行负数加法
{
while ((*++str) && (*str <= '9') && (*str >= '0'))
{
num = num * 10 - (*str - '0');
}
return num;
}
else if (*str == '+') //正数执行正数加法
{
while ((*++str) && (*str <= '9') && (*str >= '0'))
{
num = num * 10 + (*str - '0');
}
return num;
}
else{
if (!((*str <= '9') && (*str >= '0')))//非法字符就返回0，并且把is_num置为0
{
is_num = 0;//非法输入
return 0;
}
else //普通数字直接执行正数加法
{
while ((*str) && (*str <= '9') && (*str >= '0'))
{
num = num * 10 + (*str - '0');
str++;
}
return num;
}
}
}
int main(void){
int ret = my_atoi2("-1024K2048");
if (is_num)
{
printf("%d\n", ret);
}
else
{
printf("转换出错\n");
}
system("pause");
return 0;
}
结语
需要改进的地方还有很多，比如字符串太长倒置数据溢出，我们需要分两种情况来判断整数是否发生上溢出或者下溢出。
当去实现一个函数的时候，应该尽可能的去增加代码的鲁棒性，多次进行测试！
本示例中我的代码还是比较冗余，显得不够简洁！以后再慢慢改进！
前言
今天聊聊一个有趣的问题： 一个数组中只有一个数字不是成对出现，请查找出这个数字！ 使用蛮力当然是可以求出结果的，但是要追求效率的话还是需要使用异或运算，计算机存储的本来就是二进制位，对计算机来说，当然是使用它们的最原始的算法就最快了！
异或运算快速查找
这个道理很容易理解，每个数字异或它本身都会得到0，0根任意数字异或都会得到与之异或的那个数字!
例如：2^2 = 0; 2^0 = 2;
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main(void){
int arr[] = { 1, 2, 7, 1, 2 };
int len = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int ret = 0;
for (; i < len; i++){
ret ^= arr[i];
}
printf(“ret = %d\n”,ret);
system(“pause”);
return 0;
}
题目拓展
题目一
在一个数组中，只有两个数字不是成对出现的，请找出这两个数字！
分析
首先，对数组进行遍历，遍历的同时我们做一个数组元素的异或，这样一遍的遍历下来，我们就得到了两个仅仅出现一次的数字的异或的结果，然后我们根据二进制异或的原理最终结果的二进制位是第一次出现1的位置，对两个数字相应的二进制位的位置，出现的数字一定是不同的。这样我们可以根据最终结果的第一次二进制位是1的位置，来将这两个数字分开，相当于分到两个数组中。分别异或下去就有了结果。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
//arr是要查找的数组，len为数组长度，x和y是查找的结果
void find_2num(int* arr, int len,int *x,int *y){
int num = 0;//两个不同的数进行^操作之后得到的数
int key = 0;//num的二进制位中第一个为1的位置，根据此位置就可以把数组中的数分成两组
int ret1 = 0;
int ret2 = 0;
* x = 0;
* y = 0;
int i = 0;
assert(arr != NULL);
for (i = 0; i < len; i++){
num ^= arr[i];
}
for (i = 0; i < 32; i++){
if (((num >> i) & 1) == 1){
break;
}
else{
key++;
}
}
for (i = 0; i < len; i++){
if (((arr[i] >> key) & 1) == 1){
ret1 ^= arr[i];
}
else{
ret2 ^= arr[i];
}
}
* x = ret1;
* y = ret2;
}
int main(void){
int arr[] = { 1, 2, 3, 4, 9, 0, 1, 2, 3, 4 };
int len = sizeof(arr) / sizeof(arr[0]);
int ret1 = 0;
int ret2 = 0;
my_find(arr, len, &ret1, &ret2);
printf("ret1 = %d,ret2 = %d\n",ret1,ret2);
system("pause");
return 0;
}
题目二
在一个数组中，只有三个数字不是成对出现的，请找出这三个数字中的一个，这是一道小米校招的笔试题！
分析
首先这个数组元素个数一定为奇数，而且那要求的三个数一定不可能每一个二进制位都相同，所以我们可以找到其中一个二进制位不同，可以把那三个数字分出来，而且可以很推出三个数肯定可以分到两组不同的数组里面去，基于这样的思路就可以找出这三个不同的数字。找到三个数字一个数的第一个二进制位和其它二个不一样的数就可以找出其中一个数字！
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
//奇数返回1，偶数返回0
int isEven(int n){
return n & 1;
}
int main(void){
int arr[] = {1,2,3,1,2,3,4,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int num = 0;
int key = 0;
for (i = 0; i < len; i++){
num ^= arr[i];
}
for (i = 0; i < 32; i++){
if (((num >> i) & 1) == 1){
break;
}
key++;
}
int ret1 = 0;
int ret2 = 0;
int odd = 0;
for (i = 0; i < len; i++){
if (((arr[i] >> key)&1)==1){
ret1 ^= arr[i];
odd++;
}
else{
ret2 ^= arr[i];
}
}
//如果是奇数那么，分出的一个数组中只是存在一个不是成对出现的数字，就是异或的结果
if (isEven(odd)){
printf("其中一个数字是:%d\n", ret1);
}
else{
printf("其中一个数字是:%d\n",ret2);
}
system("pause");
return 0;
}
查找数组中非成对出现的数字
一个数组中只有一个数字不是成对出现，请查找出这个数字
分析
和只找出一个数字是一样的，只不过比题目二要多几个步骤，首先我在在第一次分离数组的时候，需要分别统计操作次数，我们根据操作次数的奇偶性就可以区分出这样两个数组：①数组元素有奇数个，那么该数组肯定只包含我们的一个目标值，对本数组元素这个异或就可以得出我们要求出的其中一个结果；②数组元素有偶数个，我们剩下两个要求出的元素就包含在其中
这样分析过后问题就会变得非常简单，我们只要根据情况分别提取数组，但是在本例中我只是对剩余偶数个元素的数组进行了提取，因为奇数个元素的我直接异或得出的结果，对于①数组我们直接异或得出结果其实我们在题目二中用的就是这样的方案但是这样只能得出奇数个元素的数组的异或值，对于②数组我们直接使用题目一中的函数就OK了！
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//奇数返回1，偶数返回0
int isEven(int n){
return n & 1;
}
//arr是要查找的数组，len为数组长度，*x和*y是查找的结果
void find_2num(int *arr, int len, int *x, int *y){
int num = 0;//两个不同的数进行^操作之后得到的数
int key = 0;//num的二进制位中第一个为1的位置，根据此位置就可以把数组中的数分成两组
int i = 0;
//先对传入的结果进行初始化
*x = 0;
*y = 0;
//先获取所有数字的异或结果
for (i = 0; i < len; i++){
num ^= arr[i];
}
//看看num的二进制位中第一个1出现的位置，记为key
for (i = 0; i < 32; i++){
if (((num >> i) & 1) == 1){
break;//一旦找到位置为1就退出循环
}
else{
key++;
}
}
//根据上一步求出的第一个二进制位第一次出现1的位置将数组分为两组，分别进行亦或操作
for (i = 0; i < len; i++){
if (((arr[i] >> key) & 1) == 1){
(*x) ^= arr[i];
}
else{
(*y) ^= arr[i];
}
}
}
//arr是要查找的数组，len为数组长度，*x、*y、*z是查找的结果
void find_3num(int *arr, int len, int *x, int *y, int *z){
int i = 0;
int num = 0; //所有的数字异或的结果
int key = 0; ////num的二进制位中第一个为1的位置，根据此位置就可以把数组中的数分成两组
for (i = 0; i < len; i++){
num ^= arr[i];
}
for (i = 0; i < 32; i++){
if (((num >> i) & 1) == 1){
break;
}
key++;
}
int ret1 = 0; //两种情况下的结果之一
int ret2 = 0; //两种情况下的结果之一
int odd = 0; //统计其中一组元素的个数
int even = 0; //统计其中一组元素的个数
for (i = 0; i < len; i++){
if (((arr[i] >> key) & 1) == 1){
ret1 ^= arr[i];
odd++;
}
else{
ret2 ^= arr[i];
even++;
}
}
int index = 0;
int* other_arr = NULL;
//如果odd是奇数,那么那么这个分出来的数组中只有一个数字不是成对出现的
if (isEven(odd)){
*x = ret1; //这样我们就拿到了第一个数字
//提取出剩下的数字
other_arr = (int*)malloc(sizeof(int)* even);
for (i = 0; i < len; i++){
if (((arr[i] >> key) & 1) != 1){
other_arr[index] = arr[i];
index++;
}
}
//提取出来之后的数组就只是包含两个不是成对出现的数字，直接调用find_2num就可以得出结果
find_2num(other_arr, even, y, z);
}
else{
//如果odd不是奇数，我们就拿出另外一组数字组成新的数组，直接调用find_2num就可以得出结果
*x = ret2;
other_arr = (int*)malloc(sizeof(int)* odd);
for (i = 0; i < len; i++){
if (((arr[i] >> key) & 1) == 1){
other_arr[index] = arr[i];
index++;
}
}
find_2num(other_arr, odd, y, z);
}
free(other_arr);
other_arr = NULL;
}
int main(void){
int arr[] = { 1, 2, 3};
int len = sizeof(arr) / sizeof(arr[0]);
int x = 0;
int y = 0;
int z = 0;
find_3num(arr, len, &x, &y, &z);
printf("%d %d %d\n",x,y,z);
system("pause");
return 0;
}
结语
1、注意代码的优化问题，比如判断奇偶数的时候使用上面定义的 isEven() 函数就会快一些！
2、在malloc()之后记得在合适的时候释放内存，避免造成内存泄漏！
3、注意函数的封装问题，在拿参数当做函数返回值的时候，注意参数只是作为返回值使用还是有其他功能，如果不只是作为返回值使用，那么应该在使用前应该进行必要的初始化！
4、注意在返回结构体类型还是通过参数返回之间权衡利弊，代码尽量简洁！
字符串左右旋转问题
实现一个函数，可以左旋字符串中的k个字符。例如”ABCD”左旋一个字符得到”BCDA”,”ABCD”左旋两个字符得到”CDAB”！
普通操作方式
先把问题简单化，假设要左旋一个字符
首先需要将第一个字符存储起来，然后才能保证在左旋的过程中首字符能够被正确的转移到最后
接着就是逐个字符的向左移动操作
逐个前移，为了保证字符’\0’始终在最后的位置，在逐个前移的时候只要循环到’\0’就停止，这样就保证了’\0’字符永远在最后不会被移动
推广到左移num位，只需要逐次循环就可以达到目的
//arr是要左移的字符串，num是旋转个数
void my_swap(char* arr, int num){
assert(arr != NULL);
if (num <= 0){
return;
}
//左旋多少次就总体移位多少次
int i = 0;
for (i = 0; i < num; i++){
int j = 0;
//先将首元素存储起来
char tmp = *arr;
//向左一次移动
while (*(arr + 1 + j)){
*(arr + j) = *(arr + 1 + j);
j++;
}
//将之前存储的元素放在最后
*(arr + j) = tmp;
}
}
三次翻转的做法
还是假设存在这样一个被操作字符串”ABCDEF”,假定还是左移两个字符，如下图所示
第一次就先把要左旋的字符做翻转
第二次把不参与左旋的字符做翻转
第三次把整个字符串做翻转
//只需传入首尾指针就可以完成交换
void my_reverse(char* left,char* right){
assert((left != NULL)&&(right != NULL));
while (left < right){
char ch = *left;
*left = *right;
*right = ch;
left++;
right--;
}
}
//arr是要左移的字符串，num是旋转个数
void my_swap(char* arr, int num){
my_reverse(arr, arr + num-1);
my_reverse(arr + num, arr + strlen(arr) - 1);
my_reverse(arr, arr + strlen(arr) - 1);
}
问题推广
判断一个字符串是否为另外一个字符串旋转之后的字符串
枚举的方式
根据第一个问题得出的结果我们很容易通过枚举的方式来判断是否是另一个字符串旋转之后得到的结果枚举的方式虽然是可以比较的，但是不够快，最坏的情况下需要把每一种情况都列举出来，这是非常影响效率的，所以看看接下来这种方式
int is_revolved(char* src, char* cmp){
assert(src != NULL);
assert(cmp != NULL);
//长度不等必定不是，直接返回0
int src_length = strlen(src);
int cmp_length = strlen(cmp);
if (src_length != cmp_length){
return 0;
}
int i = 0;
for (i = 0; i < src_length; i++){
my_swap(src,i);
if (strcmp(src, cmp) == 0){
return 1;//return 1表示是旋转得来的
}
}
return 0;//return 0表示不是旋转得来的
}
巧妙查找
不难看出”ABCDEF”左旋或者右旋的所有情况只需要一个字符串就可以列出所以情况————“ABCDEFABCDEF”
首先我们需要拼接这样一个字符串
char str[20] = “ABCDEF”;
strcat(str,str);
这里要注意，这里的strcat(str,str)会引起死循环，因为strcat是以’\0’结束符判断在何处追加，这种给自身追加的时候就永远找不到’\0’，所以就会引起死循环，造成追加失败，解决方案是使用strncat()函
数
//找到就返回1，未找到则返回0
int find(char* src,char* cmp){
assert(src != NULL&&cmp != NULL);
int src_len = strlen(src);
int cmp_len = strlen(cmp);
//长度不相等直接返回
if (src_len != cmp_len){
return 0;
}
//开始拼接字符串
strncat(src, src, strlen(src));
//开始对比
if (strstr(src, cmp) != NULL){
return 1;
}
return 0;
}
考查字符串和字符数组的相关操作，注意在没有明确指定是否允许使用库函数的时候，就默认允许使用库函数，在不允许的情况下需要自定义实现这些函数（本题中只需要自定义实现strlen()、strstr()、strcat()这些函数），这样就很OK了！
指定位置0或置1操作
void bit_set(unsigned char *p_data,unsigned char position,int flag)
{
int i = 0;
if(1 == flag){
*p_data |= (1<<(position-1));}else if(0 == flag)
{
*p_data &= ~(1<<(position-1));
}
}
p_data是要修改的数据，position是要指定的位，flag是0/1
判断一个数的二进制序列包含多少个1
方式一
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main(void)
{
int num = 15;
int count = 0;
int i = 0;
//int包含32个二进制位，逐个后移并与1，如果结果等于1，那么倒数第i位就肯定是1
for (i = 0; i < 32; i++){
if (((num >> i) & 1) == 1){
count++;
}
}
printf("count = %d\n",count);
system("pause");
return 0;
}
方式二
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main(void)
{
int num = 15;
int count = 0;
while (num){
num &= (num - 1);
count++;
}
//与运算：两位同时为“1”，结果才为“1”，否则为0
//0000 0000 0000 0000 0000 0000 0000 1111 15
//0000 0000 0000 0000 0000 0000 0000 1110 15-1 = 14
//0000 0000 0000 0000 0000 0000 0000 1110 15&14 = 14 --->count++
//0000 0000 0000 0000 0000 0000 0000 1101 14-1 = 13
//0000 0000 0000 0000 0000 0000 0000 1100 14&13 = 12 --->count++
//0000 0000 0000 0000 0000 0000 0000 1011 12-1 = 11
//0000 0000 0000 0000 0000 0000 0000 1000 12&11 = 8 --->count++
//0000 0000 0000 0000 0000 0000 0000 0111 8-1 = 7
//0000 0000 0000 0000 0000 0000 0000 0000 8&7 = 0 --->count++
//0000 0000 0000 0000 0000 0000 0000 0000 0 退出循环
printf("count = %d\n",count);
printf("%d\n",15&14);
printf("%d\n", 8&7);
system("pause");
return 0;
}
方式三
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int count_one_bit(unsigned int n){
int count = 0;
while (n){
if (n % 2 == 1){
count++;
n /= 2;
}
}
return count;
}
int main(void){
printf("count = %d\n", count_one_bit(-1));
system("pause");
return 0;
}
方式二是最优解，二进制序列有多少个1就循环多少次，最大限度的减少了运算过程！
同时通过方式二的运算方法，也很容易求出一个数是否是2的n次方：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(void)
{
int num = 31;
if ((num & (num - 1)) == 0){
printf("%d是2的n次方\n",num);
}
else{
printf("%d不是2的n次方\n", num);
}
//与运算：两位同时为“1”，结果才为“1”，否则为0
//0000 0000 0000 0000 0000 0000 0010 0000 32
//0000 0000 0000 0000 0000 0000 0001 1111 31
//0000 0000 0000 0000 0000 0000 0000 0000 32&31
//0000 0000 0000 0000 0000 0000 0001 0000 16
//0000 0000 0000 0000 0000 0000 0000 1111 15
//0000 0000 0000 0000 0000 0000 0000 0000 16&15
system("pause");
return 0;
}
上一篇： 机房收费系统概要设计说明书
下一篇： MMORPG战斗系统设计(2)伤害