算法练习
设计一个函数需要注意 “严进宽出”
严禁是对参数的严格检查 指针 和长度 空值等等
宽出是???
1.求一个整数二进制数中有多少个1
常规解法:
判断这个位是否为1 是则计数++
代码:
int GetDwordBitForOne_EX_EX(unsigned int num)
{
int count = 0;
while(num)
{
if(1 == (num & 1))
count++;
num >>= 1;
}
return count;
}
基于这个思想 可以想到 如果这个位为0则不加 1则加
那么我们可以用于计数
代码：
int GetDwordBitForOne_EX(unsigned int num)
{
int count = 0;
while(num)
{
count += (num&1);
//count = count + (num & 1);
num >>=1;
}
return count;
//01110011 0001 0000
}
还有一种几点的算法 就是异或比整数小1的数
比如:8(1000) & 7 (0111)就是去除8最右边的1
会找到最右边的1并去除 原因是相邻两个二进制是+1 -1的关系 进行与操作会把这个位置0 最后这个数肯定会变为0 只要num不是0 就一直去除最右边的1 同时计数
代码：
int GetDwordBitForOne(int num)
{
int count = 0;
while(num)
{
count++;
num = num&(num-1);/*num & (num - 1) 会找到最右边的1并去除 原因是相邻两个二进制也是+1 进行与操作会把这个位置0 最后这个数肯定会变为0 只要num不是0 就一直去除最右边的1 同时计数*/
}
return count;
}
关于负数
只要将值取反+1即可(补码求负数)
代码：
int GetDwordBit(int num)
{
// -10 10
if(num < 0)
num = ~num + 1;
return GetDwordBitForOne(num);
}
2.实现一个strlen
常规方法:判断！= \0即可
代码：
int _strlen(const char *str)
{
int count = 0;
if(str==NULL)
{
return 0;
}
while(*str!='\0')
{
str++;
count++;
}
return count;
}
使用三木运算符 + 递归一句搞定
int _strlen2(const char *str)
{
return (str==NULL || *str=='\0')?0:1+_strlen2(str+1);
}
3.逆置字符串
使用递归可以很快解决这个问题
代码：
void Reserver_str(char* str,int len)
{
if(NULL == str|| len <= 1)
return;
char strtemp = *str;
*str = *(str + len - 1);
*(str + len - 1) = strtemp;
Reserver_str(str+1,len-2);
}
也可以使用循环
void reverse_str(char* str)
{
if(str==NULL)
{
return;
}
intlen = _strlen(str);
for(inti = 0; i < len/2; i++)
{
chartmp;
tmp = str;
str= str;
str=tmp;
}
}
4.逆置单词
思路是 先整体逆置一遍 然后将是空格的地方分开来分别逆置
代码：
void ReverseByWord(char* pchSentence)
{
if(NULL == pchSentence)
{
return;
}
//字符串整体逆置
Reserver_str(pchSentence,strlen(pchSentence));
//两个指针一前一后
char*pFirst , *pSecond = pchSentence;
while(' ' == *pSecond)//如果第一个就是空格特殊
{
++pSecond;
}
if('\0'== *pSecond)
{
return;
}
pFirst = pSecond;
for( ; *pSecond != '\0'; ++pSecond)
{
if(*pSecond != ' ')
{
continue;
}
Reserver_str(pFirst, pSecond - pFirst);
//再寻找下一个单词的开始位置,以空格作为判断
while(' ' == *pSecond)
++pSecond;
if('\0'== *pSecond)
{
break;
}
pFirst = pSecond;
}
Reserver_str(pFirst,pSecond - pFirst);
}
5.左旋字符串
思路：
逆序排列abcd：abcd1234 → dcba1234；
逆序排列1234：dcba1234 → dcba4321；
全部逆序：dcba4321 → 1234abcd。
即：分别逆序排序 > 全部逆置
代码：
void MoveWord_Left(char* str,int MoveNum)
{
if( NULL == str || *str == '\0'|| 0 == MoveNum)
return;
/*
逆序排列abcd：abcd1234 → dcba1234；
逆序排列1234：dcba1234 → dcba4321；
全部逆序：dcba4321 → 1234abcd。
*/
size_t len = strlen(str);
Reserver_str(str,MoveNum);
Reserver_str(str + MoveNum,len - MoveNum);
Reserver_str(str,len);
//左旋 -- 思路 ：分别逆序排序 > 全部逆置
}
6.右旋字符串
思路：
全部逆序 abcd1234 -> 4321dcba
逆序排序 4321 :4321dcba -> 1234dcba
逆序排序 dcba :1234dcba -> 1234dcba
即:全部逆置 — >单个逆置
代码：就是上面代码 全部逆序排序提前
void MoveWord_Right(char* str,int MoveNum)
{
if( NULL == str || *str == '\0'|| 0 == MoveNum)
return;
size_t len = strlen(str);
Reserver_str(str,len);
Reserver_str(str + MoveNum,len - MoveNum);
Reserver_str(str,MoveNum);
//右旋 -- 思路 : 全逆置 - > 分别逆置
}
7:改变一个整数的大小端存储
0×12345678 -> 0×78563412
思路：是用一个0值来临时存储数据 使用 |=
把整数的第1字节，第2字节，第3字节，第四4字节一次左移24位，16位，8位和0位 并 |=临时变量
代码：
void change_save(int* num)
{
inti = 0,ret = 0;
char* p = NULL;
if(num == NULL || *num == 0)
return;
p = (char*)num;//指向整数的低地址，取一个字节
i = sizeof(int) - 1;
while(i>=0)
{
ret |= *p <<(i*8);//把整数的第1字节，第2字节，第3字节，第四4字节一次左移24位，16位，8位和0位
//printf("%x\n",ret);
p ++ ;
i --;
}
*num = ret;
}
也可以是使用递归来解决这个问题 这个问题跟逆置字符串一致
需要注意的是这个len是不包括\0的
void change_save_Ex_dowrd(char* num,int len)
{
if( NULL == num || len <=1)
return;
char temp = *num;
*num = *(num + len - 1);
*(num + len -1) = temp;
change_save_Ex_dowrd(num + 1,len - 2);
}
8:判断当前大小端存储 即是算法也是面试
如果是低位优先 则1在最后一位 如果是高位优先 则1在第一位 以此来判断大小端处理
int i = 1;
低位优先：0×00000001
高位优先：0×10000000
思路：i的指针的第一位如果是1则高位 反之低位
代码：
BOOL is_integer_lower_store()
{
int i = 0x1;
char *p = (char*)&p;
if(*p == 1)
return true;
else
return false;
//如果是低位优先 则1在最后一位 如果是高位优先 则1在第一位 以此来判断大小端处理
}
也可以通过共用体来实现判断
代码：
typedef union{
charc;
inta;
}U;
BOOL is_integer_lower_store_Ex()
{
U u;
u.a = 1;
if(u.c == 1)
return true;
else
return false;
//原理同上
}
页:
[1]