内存分配方法及字符(串)操作小结

一. 内存分配方法

  内存分配方法在不同的语言下有不同的方法,但是原理都大同小异。下面主要就 C 和 C++ 中的内存分配方法做分析。

  C 中的内存分配方法主要有 malloc/free 和 memset 这两种。malloc/free 也是动态申请内存和释放内存,具体使用很简单:

int **a;
a = (int **) malloc(m * sizeof(int *));
free(a);

而 memset 函数是在 C 语言的头文件 string.h 中包含的。需要谨慎使用这个函数,因为其是以字节为单位进行赋值(在 int 等类型是使用该函数时需要注意)的,同时在内存的连续性问题上也有一定的相关性。函数原型如下,其中指针p为所操作的内存空间的首地址,c为每个字节所赋的值,n为所操作内存空间的字节长度,也就是内存被赋值为c的字节数。(memset 更多使用在 bool 类型的赋值中)

void * memset (void * p,int c,size_t n);

  C++ 中内存分配的方法主要是 new/delete。其中 new 调用构造函数完成动态分配和初始化工作,而 delete 会调用对象的析构函数,清理和释放掉内存。delete 有两种用法,对于内建简单数据类型,delete 和 delete [] 的功能是相同的。对于自定义的复杂数据类型,delete 和 delete [] 就不能互用,简单说来,前者是删除一个指针,后者是删除一个数组。注意 new 和 delete 不是函数,而是 C++ 的运算符。具体使用如:

int a[10];
a = new int[10];//new int(7), namely the initial value is 7;
delete a; // or delete []a;

二. 字符(串)操作

  算法中常常会有字符(串)等的操作。需要注意的是字符(串)和其他基本类型如 int 型等操作有很大不同,特别是四则运算上,‘0’ 和 0 也有区别。。。

  C 语言处理主要几个函数有 strcpy(), strcat(), strcmp(), strlen() 等,比较死板,但是速度却很快。

  python 在处理字符(串)时,个人觉得还是比较不错的,代码简洁,但是却会有大量时间的代价。(之前对同一字符(串)操作分别用 c 和 python 写了两段代码,运行的结果是后者时间是前者的 4 倍)

  C++ 中可以使用 C 的字符(串)操作方法,包含头文件是 cstring.h。而 C++ 本身有一个 string.h 的库,也算是一个类(感觉几乎所有的 C 的方法都可以看作是一个类)。标准C++中提供的string类得功能也非常强大的,有赋值、比较、交换等等。(目前位置用的较少,补充待续)

  在具体的问题中,我目前为止还有一个问题未得到解决:如何将一个字符 a 接到一个字符串 s 的尾部去。现有的 strcat() 等方法都是针对 char * & char * 操作的,我后来还试着尝试了先赋值给一个 char * 对象,然后再用 strcat() 等,但是还是会出现一些乱码等现象(python可能会比较好解决,直接可以取指定区间的子字符串)。

质数求法及 a trick

  一般求质数方法就是判断数 n 在 sqrt(n) 中只存在因子 1,则 n 是素数。但是有时候这种求法在某些算法题目中时间占用太多,比较好的优化方法是使用筛选法。

求 n 以内的所有质数:

int isprime[n];

memset(isprime, 1, sizeof(isprime));

for(i = 4; i <= n; i += 2) {//筛掉大于2的偶数 
    isprime[i] = 0;
}
len = sqrt(n);
for(i = 3; i <= len; ++i) {
    if(isprime[i] == 0) {
        continue;
    }
    step = i << i; //筛掉大于质数 i 的所有非质数
    for(j = i * i; j < n; j += step) {
        isprime[j] = 0;
    }
}

  上述代码中 isprime[i] == 1 时,表示 i 即是一个质数。个人觉得代码中的精华应该是 step 的赋值

step = i << i

  这两天看到的一个算法题目,恰好我看了第一眼就觉得是求质数,但是,后来总是time out,甚至 error。题目贴出来如下:

Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food.
 Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of n integers.

A sequence a1, a2, ..., an, consisting of n integers, is Hungry if and only if:

1)Its elements are in increasing order. That is an inequality ai < aj holds for any two indices i, j (i < j).
2)For any two indices i and j (i < j), aj must not be divisible by ai. 

Iahub is in trouble, so he asks you for help. Find a Hungry sequence with n elements.

Input

The input contains a single integer: n (1 ≤ n ≤ 10^5).

Output

Output a line that contains n space-separated integers a1 a2, ..., an (1 ≤ ai ≤ 10^7), 
representing a possible Hungry sequence. Note, that each ai must not be greater than 10000000 (10^7) and less than 1.
If there are multiple solutions you can output any one.

Sample test(s)
Input

3

Output

2 9 15

  仔细分析这个题目,其实只是一个小 trick,特别要分析上述题目中给的范围。

(注:第 10000000 个素数是 1299743;Note:101 % 100 != 0)。

最大公约数和最小公倍数小结

  这个问题每个人都能很好的解决,但是很久没搞算法这一块,都忘了,所以在这里记录,方便以后温故而知新。

  欲求最小公倍数,可以先求出最大公约数。而求解最大公约数的最简方法在数论中称辗转相除法,也叫做欧几里得算法。该算法不需要因式分解。

  具体代码段如下(gcd 为最大公约数,lcm 为最小公倍数):

total = m * n;
while(n) {
    tmp = m % n;
    m = n;
    n = tmp;
}
gcd = m;
lcm = total / gcd;

或者如代码段:

gcd(int a, int b) {
    return b == 0? a: gcd(b, a % b);
}

  最大公约数可以这么求证明如下:

假设 a % b = t,则 a = kb + t;我们可以知道 t 和 a、b 的最大公约数是一致的,因为 a = m(gcd), b = n(gcd),上述式子进一步可以表示为 m(gcd) = kn(gcd) + t,则 (m - kn)gcd = t。所以求解 a 和 b 的最大公约数之需要求 b 和 t 的最大公约即可,如此下去,最后当 t = 0 时,结束查找,即可找到两者的最大公约数;得证。

 

C++ string && char * && int之间的关系及转换

    最近一直在忙别的事情,没有多少时间来写东西,今天算是抽出一点空闲,聒噪一下最近遇到的问题。

    开始之前,说下自己的感触。抽象一下计算机or程序,其实你会感觉很简单,输入,处理,输出。在输入这一块里,基本都是字符类型,所以搞清楚如何处理这种类型的数据很重要。甚至从我一直在学习的python来看,这个道理也非常适用!

    不说废话了!string其实是作为C++的一个类存在,我们在声明string str的时候,其实就是声明了一个类的对象。这个类有很多内建函数,例如+(链接字符串的操作),length()等等。而char是C/C++的一个基本类型,一个关键字(string不是C++的关键字),char *声明的是一个指针。

    因为在使用char *的时候,指针空间大小的分配需要注意,所以string的出现方便了这一系列的问题。至于string如何在char *以及int之间转换,其实也很简单,不过在谈论如何转换前,我们再说下stringstream(流的输入输出操作),它是C++新增的<sstream>库中定义的其中一个类,还有两个类分别是istringstream(流的输入操作), ostringstream(流的输出操作)。需要注意一点的是,<sstream>使用string对象来代替字符数组,这样可以避免缓冲区溢出的危险,而且,传入参数和目标对象的类型被自动推倒出来,即使使用了不正确的格式化符号也没有危险(但是如果你想多次使用同一个stringstream对象,记得每次使用前使用clear()方法——stringstream对象的构造和析构都非常耗用CPU时间,所以这样重复利用比较好)。

    int 转 string:

stringstream ss;
string str;
int n;
ss << n;
ss << str;

    string转int:

string str;
int n = atoi(str.c_str());

    string转char *:

string str;
char *a = str.c_str();

     char *转string:

string str;
char *a = "abc";
str(a);//初始化即可

    atoi()意思是array to int,而c_str()返回的是pointer,所以这里算是比较好理解把。

PS:推荐一个比较好的C++函数以及库的说明查找网站www.cplusplus.com.