Fork me on GitHub

《剑指 Offer》笔记二

发表于 | 分类于
字数统计: 3.3k 字 | 阅读时长 ≈ 13 分钟

《剑指 Offer》中字符串和链表的基础部分

数据结构

引言

数据结构一直是面试的重点，大多数会围绕着数组、字符串、链表、树、栈、队列等几种常见的数据结构展开，因此我们需要熟练掌握这几种数据结构。
数组和字符串是两种最为基础的数据结构，它们利用连续的内存存放数字和字符。而链表和树则是面试频率相对较高的数据结构。由于操作链表和树时需要操作相当数量的指针，因此在解决相关问题时，要特别重视相应的鲁棒性，否则容易出现程序崩溃的问题。栈与递归密切相关，而队列也和 BFS（广度优先遍历算法）密切相关，深刻理解这几种数据结构可以帮助我们解决很多问题。

数组

参照《剑指 offer》笔记一

字符串

基础概念

字符串是由若干字符组成的序列。由于字符串在编程时使用的频率非常高。为了优化，许多语言会对它做特殊的规定，下面，我们从C/C++的字符串入手，讨论下它的特性。
C/C++字符串以\0作为结尾，这使得我们能够很方便地定位其尾部；同时因为这个特点，我们很容易造成字符串的越界，例如：

1
2
3
4
char str[10];
// 我们先声明一个长度为 10 的字符数组
strcpy(str, "0123456789");
// 将字符串 0123456789 复制到字符数组中

这段代码的问题出在哪里呢？

查看解析
"01234569789"这段字符串看起来只有10个字符，但实际上末尾还有一个\0字符，因此其实际长度为11字节。要正确地复制其，str的长度至少应为11。
 

为了节省内存，C/C++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，它们实际上会指向同样的内存地址。但是若用常量内存初始化数组，情况则会有所不同，考虑如下代码，它的运行结果是什么？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main(int argc, char *argv[]) {
    char str1[] = "hello world";
    char str2[] = "hello world";

    char *str3 = "hello world";
    char *str4 = "hello world";

    if (str1 == str2) {
        printf("str1 == str2\n");
    } else {
        printf("str1 != str2\n");
    }

    if (str3 == str4) {
        printf("str3 == str4\n");
    } else {
        printf("str3 != str4\n");
    }

    return 0;
}
查看答案与解析
答案是：
str1 != str2
str3 == str4
str1和str2是两个字符串数组，我们会为它们分配两个长度为 12 字节的空间，并将 "hello world" 的内容分别复制到数组中去。这是两个初始地址不同的数组。故str1和str2的值不相同，第一行输出 str1 != str2
str3和str4是两个指针，我们无须为它们分配内存，而只需要将它们指向"hello world"在内存中的地址就可以了。由于 "hello world" 是一个常量字符串，在内存中仅有一个拷贝，因此str3和str4的值相同，第二行输出 str3 == str4

题目分析

题目一

下面，我们来看一道题目：

题目：请实现一个函数，把字符串的每个空格替换为 %20。
示例输入：
“We are happy”
示例输出：
“We%20are%20happy”

题目背景题外话
在网络编程中，如果 URL 参数中含有特殊字符，例如空格、#等，则可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转化为服务器可以识别的字符。通常是在%后跟上ASCII码的两位十六进制表示。例如空格的ASCII码为 32，也即是0x20，因此替换其为%20。同样的，#的ASCII码为35，也即是0x23，故替换为%23。
 

看到这道题目，我们首先想到的是，一个空格字符替换成了%20，替换之后，整个数组在变长。如果是原地算法，就会覆盖字符串在后面的内存。若是创建新字符串，则可以分配足够多的空间，这就对应了两种解决方案。在这里，我们假设采用原地算法来解决这个问题。

什么是原地算法？
在计算机科学中，一个原地算法（in-place algorithm）基本上不需要额外辅助的数据结构，然而，允许少量额外的辅助变量来转换资料的算法。当算法运行时，输入的资料通常会被要输出的部分覆盖掉。
 

当然，在这里我也给出一个自己写的非原地代码，这是较为简单的处理方案。

非原地算法示例代码

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
void replaceBlankToNewStr(const char *oriStr, int length, char *newStr) {
     // length for oriStr
     if (oriStr == nullptr || length <= 0) {
         return;
     }
     int spaceNum = 0;
     for (int i = 0; i < length; ++i) {
         if (oriStr[i] == ' ') {
             spaceNum++;
         }
     }
     int newLength = length + spaceNum * 2;
     int indexOfOrigin = 0, indexOfNew = 0;
     while (indexOfNew < newLength && indexOfOrigin < length) {
         if (oriStr[indexOfOrigin] == ' ') {
             newStr[indexOfNew++] = '%';
             newStr[indexOfNew++] = '2';
             newStr[indexOfNew++] = '0';
             indexOfOrigin++;
         } else {
             newStr[indexOfNew++] = oriStr[indexOfOrigin++];
         }
     }
     newStr[indexOfNew] = '\0';
 }


现在我们考虑如何执行替换操作，最直观的做法从头到尾扫描字符串，若是遇到空格，便将空格后的所有字符向后移动两位，再将一个空格替换为三个字符。显然，这种方法是不够高效的。假设字符串长度为 n。对每个空格字符，需要移动后面$O(n)$个字符，若对于含有$O(n)$个空格字符的字符串而言，总的时间效率是$O(n^2)$。那么问题出在哪里呢？
我们发现很多字符移动了多次，能不能减少这个移动次数呢？答案是肯定的。我们将思维逆转过来，由从前向后替换，变成从后向前替换。
我们可以先遍历一次字符串，这样就能统计出空格总数，然后计算出替换的总长度。我们从字符串的末尾开始复制替换。首先准备两个指针，一个指向原始字符串末尾，一个指向替换之后的末尾。分别称其为$P_1$和$P_2$。接下来我们向前移动$P_1$，逐个复制其指向内容到$P_2$，直到遇到空格。当遇到空格后，$P_1$向前移动一格，$P_2$向前移动三格，插入%20。这样一来，每个字符只复制（移动）一次，总的时间复杂度为$O(n)$，比上述直观做法更快。

示例代码

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
32
33
void replaceBlank(char string[], int length) {
     if (string == nullptr || length <= 0) {
         return;
     }

     int originalLength = 0;
     int numberOfBlank = 0;
     int i = 0;
     while (string[i] != '\0') {
         ++originalLength;
         if (string[i] == ' ') {
             ++numberOfBlank;
         }
         i++;
     }

     int newLength = originalLength + numberOfBlank * 2;
     if (newLength > length) {
         return;
     }
     int indexOfOriginal = originalLength;
     int indexOfNew = newLength;
     while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) {
         if (string[indexOfOriginal] == ' ') {
             string[indexOfNew--] = '0';
             string[indexOfNew--] = '2';
             string[indexOfNew--] = '%';
         } else {
             string[indexOfNew--] = string[indexOfOriginal];
         }
         --indexOfOriginal;
     }
 }


课后习题

现有两个排序的数组$A_1$和$A_2$，内存在$A_1$的末尾有足够多的空余空间容纳$A_2$。请实现一个函数，把$A_2$所有数字插入$A_1$,并且所有数字是排序的。

解题思路
和前面的例题一致，直观的想法是在$A_1$中从头到尾复制数字，但这也会出现多次复制一个数字的情况。最好的方法是从尾到头比较$A_1$和$A_2$中的数字，并把较大数字复制到$A_1$中的合适位置。
 
示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void linkSortedArray(int a1[], const int a2[], int elemOfA1, int elemOfA2, int lengthOfA1) {
    // Assert a1 is longer enough to storage a2
    if (elemOfA1 + elemOfA2 > lengthOfA1) {
        return;
    }
    int pA1 = elemOfA1 - 1;
    int pA2 = elemOfA2 - 1;
    int pA = elemOfA1 + elemOfA2 - 1;
    while (pA >= 0) {
        if (pA1 < 0) {
            a1[pA--] = a2[pA2--];
        } else if (pA2 < 0) {
            a1[pA--] = a1[pA1--];
        } else {
            if (a1[pA1] < a2[pA2]) {
                a1[pA--] = a2[pA2--];
            } else {
                a1[pA--] = a1[pA1--];
            }
        }
    }
}


链表

基础概念

链表应该是考察较为频繁的数据结构。它的结构很简单，它由指针把若干节点连接成链状结构。链表的创建、插入节点、删除节点等操作都只需要 20 行左右的代码即可实现。另外，由于其是一种动态数据结构，需要对指针进行操作，因此需要有良好的编程功底才能写好相关代码。
为什么说链表是动态结构？我们在创建链表时，不需要知道它的长度。当插入一个节点时，我们只需要为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表当中。内存分配不是在创建链表时一次性完成的，而是每添加一个节点分配一次内存。由于没有限制内存，链表的空间效率比数组高。如果单向链表的结构定义如下：

1
2
3
4
struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
};

那么往该链表末尾添加一个节点的 C++ 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void addToTail(ListNode **pHead, int value){
    ListNode* pNew = new ListNode();
    pNew -> m_nValue = value;
    pNew -> m_pNext = nullptr;

    if(*pHead == nullptr){
        *pHead = pNew;
    }else{
        ListNode *pNode = *pHead;
        while(pNode -> m_pNext != nullptr){
            pNode = pNode -> m_pNext;
        }
        pNode -> m_pNext = pNew;
    }
}

在这段代码中，我们要特别注意第一个参数pHead是指向指针的指针。当我们往一个空链表插入节点时，新插入的节点就是链表的头指针。此时会改动头指针，因此必须将pHead参数设为指向指针的指针，否则出了函数后pHead仍然是一个空指针。
由于链表内存不是一次性分配的，因而我们无法保证链表内存和数组的连续性。因此，若要在链表内找到其第 i 个节点，我们只能从头开始，逐个遍历链表，时间效率为$O(n)$，对应的，数组的时间效率为$O(1)$。下面是在链表中寻找第一个含有某值的节点并删除之的代码：

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
void removeNode(ListNode **pHead, int value){
    if(pHead == nullptr|| *phead == nullptr){
        return;
    }

    ListNode *pToBeDeleted = nullptr;
    if((*pHead) -> m_nValue == value){
        pToBeDeleted = *pHead;
        *pHead = (*pHead) -> m_pNext;
    }else{
        ListNode *pNode = *pHead;
        while(pNode -> m_pNext != nullptr && pNode ->m_pNext->m_nValue != value){
            pNode = pNode -> m_pNext;
        }
        if(pNode -> m_pNext != nullptr && pNode -> m_pNext -> m_nValue == value){
            pToBeDeleted = pNode -> m_pNext;
            pNode -> m_pNext = pNode -> m_pNext -> m->pNext;
        }
    }

    if(pToBeDeleted != nullptr){
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
    }
}

题目分析

题目一

下面，我们看一道例题：

题目：输入一个链表的头节点，从尾到头反过来打印出每个节点，链表节点定义如下：

1
2
3
4
struct ListNode{
    int m_nKey;
    ListNode* m_pNext;
};

通常来讲，打印是一个只读操作，我们不希望打印时修改内容。因此在这里我们不能修改链表的结构。

题外话
除了题目中的这种结构，还存在一种常用的链表结构，称之为双向链表。它的每个节点都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。有时候也会构造双向循环链表（首尾相连）。它的节点结构通常是这样的：

1
2
3
4
5
struct ListNode{
    int m_nKey;
    ListNode* m_pNext;
    ListNode* m_pPrev;
};


解析与示例代码
我们很容易地想到解决这个问题需要遍历链表，顺序是从头到尾，而遍历却是从尾到头。这就是典型的“先进后出”，因此可以考虑使用栈这种数据结构来实现。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void printListNodeReversinglyIteratively(ListNode *pHead) {
    std::stack<ListNode *> nodes;
    ListNode *pNode = pHead;
    while (pNode != nullptr) {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }
    while (!nodes.empty()) {
        pNode = nodes.top();
        printf("%d\t", pNode->m_nValue);
        nodes.pop();
    }
}



既然考虑到了栈，而递归本质上也就是一个栈结构，因此也可以使用递归来实现它。我们每访问一个节点，先递归输出它后面的节点，再输出自身，如此一来便反过来了：

1
2
3
4
5
6
7
8
void printListNodeReversinglyRecursively(ListNode *pHead) {
    if (pHead != nullptr) {
        if (pHead->m_pNext != nullptr) {
            printListNodeReversinglyRecursively(pHead->m_pNext);
        }
        printf("%d\t", pHead->m_nValue);
    }
}


当然，需要注意的是，递归代码虽然看着很简洁，但也存在问题：如果链表很长，那么函数递归调用的层级就会很深，有可能导致函数调用的栈溢出。因此还是使用迭代法的栈代码的鲁棒性比较好。

课后习题

题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。结构与函数定义如下：

1
2
3
4
5
6
7
8
9
10
/**
* Definition for singly-linked list.
*/ 
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* reverseList(ListNode* head);

解题思路
和前面的例题一致，可以考虑使用迭代或者递归的方式来解决。
 
示例代码

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
    // 迭代法
    ListNode *cur = head, *pre = nullptr;
    while(cur != nullptr) {
        ListNode* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
// 递归法
ListNode* reverseList(ListNode* head) {
    return recur(head, nullptr);          
}

ListNode* recur(ListNode* cur, ListNode* pre) {
    if (cur == nullptr){
        return pre;
    }
    ListNode* res = recur(cur->next, cur);
    cur->next = pre;
    return res;
}


0%