编程之法读书笔记第一章——数据结构——字符串

一本在铁哥博客发现的不要钱的书
内容有点多啊，这篇只记录数据结构的字符串部分，其他待更

《编程之法：面试和算法心得》

第一部分 数据结构

第一章 字符串

1.1 旋转字符串

核心：分两半
例如，字符串 abcdef ，若要让 def 翻转到 abc 的前头，只要按照下述 3 个步骤操作即可：
首先将原字符串分为两个部分，即 X:abc，Y:def；
将 X 反转，X->X^T，即得：abc->cba；将 Y 反转，Y->Y^T，即得：def->fed。
反转上述步骤得到的结果字符串 X^TY^T，即反转字符串 cbafed 的两部分（cba 和 fed）给予反转，cbafed 得到 defabc，形式化表示为 (X^TY^T)^T=YX，这就实现了整个反转。

1. 链表翻转。给出一个链表和一个数 k，比如，链表为 1→2→3→4→5→6，k=2，则翻转后 2→1→6→5→4→3，若 k=3，翻转后 3→2→1→6→5→4，若 k=4，翻转后 4→3→2→1→6→5，用程序实现。

首先我们来看一下单链表反转

单链表反转有递归和非递归两种算法。
先定义一下节点

1
2
3
4
typedef struct ListNode{  
    int value;  
    ListNode* next;  
}ListNode;

在递归算法中的做法是：

  1. 找到最后一个节点和倒数第二个节点，把最后一个节点设为头节点的后继
  2. 反转这两个节点
  3. 倒数第三个和第四个节点重复执行步骤 2

其中注意，链表是以节点后继为 NULL 结束的，在更改指针的过程中要把改后的节点后继改为 NULL
代码如下：

1
2
3
4
5
6
7
8
9
10
11
void Inversion_Recursion(ListNode* p,ListNode* Head)  
{  
    if(p->next==NULL)  
    {  
        Head->next=p;  
        return;// 找到最后一个节点  
    }  
    Inversion_Recursion(p->next,Head);  
    p->next->next=p;// 反转节点  
    p->next=NULL;// 第一个节点反转后其后继应该为 NULL  
}

非递归实现很简单，只需要遍历一遍链表，在遍历过程中，把遍历的节点一次插入到头部。在这个过程之后，第一个节点成了最后节点，因此要特殊处理，改其后继为 NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Inversion(ListNode* Head)  
{  
    ListNode *current,*tmp;  
    current=Head->next;  
    if(current!=NULL)// 反转后第一个节点的后继要为 NULL  
    {  
        tmp=current;  
        current=current->next;  
        tmp->next=NULL;  
    }  
      
    while(current!=NULL)  
    {  
        tmp=current;  
        current=current->next;  
        tmp->next=Head->next;  
        Head->next=tmp;  
    }  
}

回到习题

链表翻转。给出一个链表和一个数 k，比如，链表为 1→2→3→4→5→6，k=2，则翻转后 2→1→6→5→4→3，若 k=3，翻转后 3→2→1→6→5→4，若 k=4，翻转后 4→3→2→1→6→5，用程序实现。

思路：
1、先 求出链表总的元素个数 temp

2、创建一个头结点 result，用来指向 result->next=head，并保存头节点 reverhead=result；

3、 用 temp 和 k 的值比较 while(k<=temp) 当 k 小于等于 temp 时就进行逆置操作

4、设置部分逆置长度 ，令 t=k ， while（t>0） 进行部分逆置

5、temp=temp-k 最后返回 reverhead->next

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    var len = 0,//用来记录链表长度
        t,//记录当前翻转了多少个
        p = head,
        result = new ListNode(0),
        reverhead,
        remark;
    //遍历，得到链表长度
    while(p){
        len++;
        p = p.next;
    }
    //如果长度为0 或者k等于1 或者 k比长度大就不操作
    if(len === 0 || k === 1 || k > len){
        return head;
    }
    
    //用reverhead保存头结点
    result.next = head;
    reverhead = result;
    //用p来指向下一个节点，进行操作的第一个有效节点
    p = result.next;
    
    //外层循环用k和temp
    while(k <= len){
        //里层循环每次操作t个
        t = k;
        //用remark保存每次进行部分逆置的第一个节点，该节点将指向部分逆置的下一个节点，如上k=2时，1指向3
        remark = p;
        //将p开始的t个节点进行逆置(这里就是单链表的非递归翻转嘛)
        while(t > 0){
            q = p;
            p = p.next;
            q.next = result.next;
            result.next = q;
            t--;
        }
        //将每部分连接起来
        remark.next = p;
        //改变result，指向部分逆置的最后一个节点
        result = remark;
        //做了部分逆置后，改变temp
        len = len -k;
    }
    return reverhead.next;
    
};

2 单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入 “I am a student.”，则输出 “student. a am I”。

第一步：先把整个字符串翻转.

第二步：再把翻转后的字符串中从头到尾进行遍历，遍历的过程中遇到空字符就把空字符之前的单词进行翻转，反复这样直到结束.

如：

I am a boy.

第一步：

.yob a ma I

第二步：

(1) boy. a ma I

(2) boy. a ma I

(3) boy. a am I

(4) boy. a am I

经过第二步的 (4) 就可以达到要求了。

不过有一点我们要注意就是当这个句子只有一个单词的时候就不需要进行翻转了，所以我们要在进行前面两个步骤之前要先判断一下是否需要翻转，如果不需要就不做任何动作。

1.2 字符串包含

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，比如 bad 和 adb 即为兄弟字符串，现提供一个字符串，如何在字典中迅速找到它的兄弟字符串，请描述数据结构和查询过程。

方法一：看成 26 进制的数，每个字符串对应一个具体的数

方法二：用 hashmap 可以 以字母为 key 出现的次数为 value ，次数一样即为相同的

1.4 回文判断

1. 判断一条单向链表是不是 “回文”

分析：对于单链表结构，可以用两个指针从两端或者中间遍历并判断对应字符是否相等。但这里的关键就是如何朝两个方向遍历。由于单链表是单向的，所以要向两个方向遍历的话，可以采取经典的快慢指针的方法，即先位到链表的中间位置，再将链表的后半逆置，最后用两个指针同时从链表头部和中间开始同时遍历并比较即可。

2、判断一个栈是不是 “回文”

分析：对于栈的话，只需要将字符串全部压入栈，然后依次将各字符出栈，这样得到的就是原字符串的逆置串，分别和原字符串各个字符比较，就可以判断了。

习题

1.第一个只出现一次的字符

方法一：从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较，如果在后面没有发现重复的字符，则该字符就是只出现一次的字符。如果字符串有 n 个字符，每个字符可能与后面的 O(n) 个字符相比较，因此这种思路时间复杂度是 O(n2)。

我们试着去找一个更快的方法。由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次数？要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。

由于字符（char）是一个长度为 8 的数据类型，因此总共有可能 256 种可能。于是我们创建一个长度为 256 的数组，每个字母根据其 ASCII 码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为 256，以字符 ASCII 码为键值的哈希表。（256 个字符我们建立一个 256 个数组，数组用来存放字符的次数，使用字符的 ASCII 值作为数组的下标）

我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。

2、对称子字符串的最大长度

算法