20. C和C++分配释放内存区别？ 0.属性
new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持。 1. 参教
使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计 算。而
malloc则需要显式地指出所需内有的尺寸。 2. 返回类型
new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进 行类型
转换，故“w是符合类型安全性的操作符。而malloc内存分配成功则是返回void *，需要通过强制类型转换将void吋旨针转换成我们需要的类型。
3. 分配失败
new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。 4. 自定又类型
new会先调用operator new |^|数，申请足够的内存（通常底层使用malloc实现）。然 后调用
类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用 析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。 malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对 象构造和析构工作。
5. 重载
C++允许重载new/delete操作符，特别依，布局new的就不需要为对象分配内存，而是 指定了
一个地址作为内存起始区域，new在这段内存上为对象调用构造函数完成初始化 工作，并返回此地址。而malloc不允许重载。
6. 内存区域
new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数 从堆上动
态分配内有。自由有储区是。淄于new操仲符的一个抽象概念，凡是通过rew 操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统 所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内 存，使用free释放已分配的对应内存。自由存储区不等于堆，如上所述，布局new就 可以不位于堆中。
21. 一个单词单词字母交换，可得另一个单词，如 army->mary,成为
兄弟单词。提供一个单词，在字典中找到 它的兄弟。描述数据结构和查询过程。
解法一：
使用hash_map和链表。
首先定义一个key,使得兄弟单词有相同的key,不是兄弟的单词有不同的key。例如, 将单词按字母从小到大重新排序后作为其key,比如bad的key为abd, good的key为 dgooo
使用链表将所有兄弟单词串在一起，hash_map的key为单词的key, value为链表的起 始地址。 幵始时，先遍历字典，将每个单词都按照key加入到对应的链表当中。当需要找兄弟单 词时，只需求取这个单词的key,然后到hash-map中找到对应的链表即可。
这样创建hash-map时时间复杂度为0 (n),查找兄弟单词时时间复杂度是0 (1)。 解法二：
同样使用hash_map和链表。
将每一个字母对应一个质数，然后让对应的质数相乘，将得到的值进行hash,这样兄 弟单词的值就是一样的了，并且不同单词的质数相乘积肯定不同。
使用链表将所有兄弟单词串在一起，hash-map的key为单词的质数相乘积,value为链 表的起始地址。
对于用户输入的单词进行计算，然后查找hash,将链表遍历输出就得到所有兄弟单词。 这样创建hash-map时时间复杂度为0 (n),查找兄弟单词时时间复杂度是0⑴。
#include
it inc lude
Sdefine MAX_SIZE 287 typedef struct hash^no de {
char *word;
struct hash_node *next; }hash_no de, *hash_map;
bin[!WLSIZE]= {MULL};
unsigned int get_index(char *pWord)//get hash index [
int lerFstrlen(pWord); int i;
unsigned int index=l; for(i=0;i index=index* (pWord [i]' A’ +1；; //这里如果是大写字母的话就会使负值,所 以要 根据情况而定 return index%I.tAX_SIZE; } void ins er t_wor d(char *pWord) //insert word, if collision happens, use link list [ unsigned int index=get_index(pWord); printf(\— index); hash_node *p; for (p=bin[index] ;pJ=NULL;p=p->xiext) if (strcmp (p~>word, pWord) ==0： return; p=(hash_no de*)malloc(sizeof(hash_node)); p->word=(char*)malloc(strlen(pWord) +1); strcpy (p>word, pWord); - p->word[strlen(pWord)] \\0‘; p->next=b in [index];// 不断的插入到表头就好,this will be efficient bin[index]=p; =, } void search_brother(char *pWord) //search brother words [ unsigned int index=get_index(pWord); hash_node *p; for(p=bin[index];pJ=NULL;p=p->next) if (strcmp (pWord, p->word) !=0； printfp->word); } void main。 [ char *string [] = {\— \— 〃:ramy〃}; int lerFsizeof (string)/sizeof (char*); int i; for(i=0;i ins er t_wor d (str ing [i]); char wordf]=mary; search__brother (word); zz z/ 22.数组al[O,mid-l]和al[mid,num-l],都分别有序。将其 merge成有序 数组al[O,num-1],要求空间复杂度0(1). 首先把给定的数组分成两部分,前一部分包括A m]中的元素，而后者则包括(m口]中的 元素。然后找到第一个数组中的中间值，也就是ql=(l侦)/2, ql位置的元素就是我们 要找的元素，大家可以举个例子自己算一下,当找到ql的时候,Q1前面的元素有Q1个, 这对接下来的编程很有影响，所以这点一定要弄清楚。这样第一个数组我们就分为了两 部分。接下来我们用Q1去划分(人工】这段元素，也是分成两部分。建议在取元素范围的 时候，(叫工】这段的前一部分个数为(q2-l-m)个，后一部分为(r - q2 +1)个,这样 约定后思路会清晰。接下来划分好了之后就是交换，有一种叫做block swapping的算 法，这个算法能在。(1)的空间复杂度下交换两个长度不相同的相邻存储区的数组。 #include Siiic lude^assert. void swap (int *a, int low, int high； { while(low < high) { int temp = *(a + low); *(a + low) = *(a + high); *(a + high) = temp; low++; high—; void block_exchange (int swap (a, low, mid); swap (a, mid + 1$ high); swap (a, low, high); int b inar y_s e ar ch (int value, int *a, int low, int high) { /* int low, int mid, int high) { 如果数组中存在要查找的元素，那么返回high的位置的前后都有可能等于value 的值： a： 1, 2, 4,4, 7,9 value=4 mid=2返回的high位置的元素后有值等于value b: 1, 2, 4,4, 7,9,10 value=4 mid=3.返回的high位置的元素前有值等于value c： 1,2, 7,9 value=4 high=3,返回的high值之前的元素都小于value,包括high 在内的以 后得元素都大于value */ assert(a != NULL); while(low < high) { int mid = low + (high - low： / 2; if(value 仁 a[mid]) high = mid; else low = mid + 1; } return high; void merge__iri_place (int *a, int low, int mid, int high) { int length! = mid 一 low +1; int length2 = high - mid; if(J(lengthl >= 0 && length2 >= 0)) return ; if (lengthl >= length2) { if (leng th2 <= 0) return; int ql = (low + mid) / 2; int qZ = binary^sear ch (a [ql., a, mid 十 1 , high); int q3 = ql + (q2 - 1 - mid；; bio ck_ex chang e (a, merge_in_place (a, merge_in_place if (leng thl <= 0) return; int ql = (mid + 1 + high) /2; int q2 = binary_search(a[ql_, a, low, mid); ql, mid, q2 - 1); low, ql - 1, q3 - 1); q3 + 1, q2 - 1, high); } else {
2020年京东精选50面试题及答案
