看流星社区

 找回密码
 注册账号
查看: 2069|回复: 0

算法练习

[复制链接]

该用户从未签到

发表于 2017-6-1 13:34:23 | 显示全部楼层 |阅读模式


设计一个函数需要注意 “严进宽出”
严禁是对参数的严格检查 指针 和长度 空值等等
宽出是???
1.求一个整数二进制数中有多少个1
常规解法:
判断这个位是否为1 是则计数++
代码:


int GetDwordBitForOne_EX_EX(unsigned int num)
{
    int count = 0;
    while(num)
    {
        if(1 == (num & 1))
            count++;
        num >>= 1;
    }
    return count;
}[/code]



基于这个思想 可以想到 如果这个位为0则不加 1则加

那么我们可以用于计数
代码:


int GetDwordBitForOne_EX(unsigned int num)
{
    int count = 0;
    while(num)
    {
        count += (num&1);
        //count = count + (num & 1);
        num >>=1;
    }
    return count;
     
    //0111  0011 0001 0000
}[/code]



还有一种几点的算法 就是异或比整数小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;
     
}[/code]


关于负数

只要将值取反+1即可(补码求负数)
代码:


int GetDwordBit(int num)
{
    // -10 10
    if(num < 0)
        num = ~num + 1;
    return GetDwordBitForOne(num);
}[/code]







2.实现一个strlen
常规方法:判断!= \0即可
代码:


int _strlen(const char *str)
{
    int count = 0;

    if(str==NULL)
    {
        return 0;
    }
    while(*str!='\0')
    {
        str++;
        count++;
    }
    return count;
}[/code]



使用三木运算符 + 递归一句搞定


int _strlen2(const char *str)
{
    return (str==NULL || *str=='\0')?0:1+_strlen2(str+1);
}[/code]


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);
}[/code]


也可以使用循环


void reverse_str(char* str)
{
    if(str==NULL)
    {
        return;
    }

    intlen = _strlen(str);

    for(inti = 0; i < len/2; i++)
    {
        chartmp;
        tmp = str;
        str= str[len-i-1];
        str[len-i-1]=tmp;
    }
}[/code]



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);
}[/code]



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);
    //左旋 -- 思路 :分别逆序排序 > 全部逆置


}[/code]
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);

    //右旋 -- 思路 : 全逆置 - > 分别逆置
}[/code]
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;
}[/code]
也可以是使用递归来解决这个问题 这个问题跟逆置字符串一致


需要注意的是这个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);
}[/code]



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在第一位 以此来判断大小端处理
}[/code]
也可以通过共用体来实现判断


代码:


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;
    //原理同上
}[/code]
点击按钮快速添加回复内容: 支持 高兴 激动 给力 加油 苦寻 生气 回帖 路过 感恩
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

小黑屋|手机版|Archiver|看流星社区 |网站地图

GMT+8, 2024-3-19 16:04

Powered by Kanliuxing X3.4

© 2010-2019 kanliuxing.com

快速回复 返回顶部 返回列表