剑指offer

发表于 | 分类于

1，定义空类型，里面没有任何变量和成员函数，求sizeof，得到结果是1。因为声明该类型实例时，他在内存中要占有一定空间；

添加构造函数和析构函数后，得到结果还是1，构造函数和析构函数的调用只需要知道地址，而与类型实例无关；

把析构函数标记为虚函数，c++编译器会生产虚函数表，为每一个实例添加指向虚函数表的指针，在32位机器上指针占4个字节。

2，c++不允许复制构造函数传值参数，应该为引用；如

classA（classA other）{value=other->value};

会导致复制构造函数里面调用构造函数，形成死循环，改为

classA（const classA& other）{value=other->value};

3，赋值运算符函数

1
2
3
4
5
6
7
8
9
Mystring& Mystring::operator=(const Mystring &str)
{
    if(this==&str) return *this;
    delete []Data;
    Data=NULL; //此时Data为空，接下来分配失败会很危险，因为Data还是空
    Data=new char[strlen(str.Data)+1];
    strcpy(Data,str.Data);
    return *this;
}

如果内存不足，new char将抛出异常，使Data为空指针，这十分容易使系统崩溃，

办法一：先new再delete

办法二：创建临时实例

4，替换空格

思路：从后向前复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void blank_replace(char* string,int length)//length 为string的总长度
{
    if(string==NULL||length<=0) return;
    int original_length=0;
    int blank_count=0;
    int i=0;
    while(string[i]!=NULL)
    {
        original_length++;
        if(string[i]==' ') blank_count++;
        i++;
    }
    
    int new_length=original_length+blank_count*2;
    if(new_length>length) return;//大于限定的长度则直接返回
    
    int index_newlength=new_length;
    int index_originallength=originallength;
    while(index_originallength>0&&index_originallength<index_newlength)
    {
        if(string[index_originallength]=' ') 
        {
            string[index_newlength--]='0';
            string[index_newlength--]='2';
            string[index_newlength--]='%';
        }
        else
            string[index_newlength--]=string[index_originallength--];
        index_originallength--;
    }
}

5，从尾到头打印链表

思路一：不能改变链表结构，使用栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void list_reverse(listnode* phead)
{
    if(phead==NULL) return;
    stack<listnode*> nodes;
    listnode* pnode=phead;
    while(pnode!=NULL)
    {
        nodes.push(pnode);
        pnode=pnode->next;
    }
    while(!nodes.empty())
    {
        pnode=nodes.top();
        printf("%d\t",pnode->value);
        nodes.pop();
    }
}

思路二：使用递归，递归本质上是一个栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void list_reverse(listnode* phead)
{
    listnode* pnode=phead;
    if(pnode!=NULL)
    {
        if(pnode->next!=NULL)
        {
            list_reverse(pnode->next);
        }
        printf("%d\t",pnode->value);
    }
    else 
        return;
}

6，除法的效率比移位运算低得多，实际编程尽量使用移位运算代替除法

​ 注意：右移容易引起死循环，比如0x0011右移4e位后变为0x1111，此时采用标志位左移再与的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//计算1的个数，如1101中1的个数
//方法一：会引起死循环
while(n)
{
  if(n & 1)  count ++;
  n=n>>1;
}
//方法二：
while(flag)
{
  if(n & flag)  count ++;
  flag=flag<<1;
}
//方法三：总结规律得出的方法
while(n)
{
    count++;
    n=(n-1) & n;
}