2014年11月

1、Single Number:Given an array of integers, every element appears twice except for one. Find that single one.
异或,不仅能处理两次的情况,只要出现偶数次,都可以清零。

int singleNumber(int A[], int n) 
{
    // 数字范围不清楚,bitmap失败
    int x=0;
    for(size_t i=0;i<n;++i)
        x^=A[i];
    return x;
}

- 阅读剩余部分 -

字符串匹配:有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?

一、strstr()函数
strstr() 函数搜索一个字符串在另一个字符串中的第一次出现。找到所搜索的字符串,则该函数返回第一次匹配的字符串的地址;如果未找到所搜索的字符串,则返回NULL。
strstr(const char *s1,const char *s2)函数从串s1首部开始逐个比较s2,并判断是否为s1的子串,算法复杂度为O(mn)。

一种实现方式:

char* substr(const char *str,const char *substr)
{
    int m=strlen(str);
    int n=strlen(substr);
    if(m<n)
        return NULL;
    else
    {
        for(int i=0;i<=m-n;i++)
        {
            int k=i,j=0;
            while(str[k++]==substr[j++] && k<m && j<n);
            if(j==n)
                return (char*)(str+i);
        }
        return NULL;
    }
}

- 阅读剩余部分 -

动态规划和贪心算法是常见的分治策略,将问题分解成若干规模较小的相同问题,通过合并求解相对容易的子问题得到原问题的解。

一、最长公共子序列(LCS)
给定两个字符序列,不要求所求的字符序列在所给的字符串中是连续的,求解最大公共序列。
设序列X=<x0,x1,x2,...xm>和Y=<y0,y1,y2,...yn>,最长子序列为Z=<z0,z1,z2,...,zk>
(1)xm==yn,必然有xm==yn==zk,<z0,z1,z2,...,zk-1>是<x0,x1,x2,...xm-1>和<y0,y1,y2,...yn-1>的子序列;
(2)xm!=yn且xm!=zk,<z0,z1,z2,...,zk>是<x0,x1,x2,...xm-1>和<y0,y1,y2,...yn>的子序列;
(3)xm!=yn且ym!=zk,<z0,z1,z2,...,zk>是<x0,x1,x2,...xm>和<y0,y1,y2,...yn-1>的子序列;
即:
LCS(Xm,Yn)=LCS(Xm-1,Yn-1),当xm==yn;
LCS(Xm,Yn)=max{LCS(Xm-1,Yn),LCS(Xm,Yn-1)},当xm!=yn;
转化为递推式:
3.jpg

- 阅读剩余部分 -

昨天碰到一个棘手的问题,项目生成Release版本,本地运行Release都没有问题,到了用户那边提示dll文件加载不成功,初步判断dll文件导入失败。于是换了几台电脑测试,结果都可以运行。考虑到用户那边没有开发环境,在服务器上新建了一个新账户,没有任何开发环境,Release版本出现dll加载不成功。

初步判断是由于电脑却少某些开发组件导致程序运行异常,但通常碰到dll文件加载不成功的情况大多是文件路径错误。尝试了三种路径格式:
(1)Qt资源文件(.qrc)存储dll文件,开发环境下失败,貌似QLibrary不支持.qrc文件存储的dll文件;
(2)反斜杠方式(\),转义字符双斜杠,开发环境成功,普通PC失败;
(3)斜杠路径(/),开发环境成功,普通PC失败;推荐使用这种路径格式,不需要考虑转义!

尽管尝试失败,基本可以忽略路径这个不存在的bug,接下来我又考虑了相对路径,相对路径是相对工作目录而言,结果也没问题。

- 阅读剩余部分 -

转自:http://blog.csdn.net/hguisu/article/details/7880288

1、Bit Map算法简介
来自于《编程珠玑》。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

2、Bit Map的基本思想
我们先来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0,如下图:
1.jpg

- 阅读剩余部分 -