剑指offer数据结构

2018-11-20 本文已影响0人锅锅Iris

剑指offer线性数据结构

剑指offer是找工作开始后刷的第一本书，刷题用牛客网。这本书可以说是已经总结归纳的很好了，按照基础知识，高质量代码，解决问题的思路以及优化时间和空间的效率分成了好几章。对于初次刷题的人很有启发的作用，为了加深印象，决定按照数据结构的类型/算法类型重新整理一遍，同时加入Leetcode相同tag的题。第一遍刷题用的是C++，很多时候有些题想不到思路，得回去看书，回去翻牛客网的答案。总结完之后打算二刷，~~用Python再刷一遍。~~（还是Java吧，Python就是简化版伪代码，刷了几题之后python的确简单）

线性数据结构

字符串类

下标的移动很关键. 如何移动下标使得效率高？（怎么利用冗余的信息？）

如果是插入删除，如何使移动的次数最少？

查找如何用空间换时间？

带特殊条件的查找类，如何控制边界条件？

如何把问题分解为递归？回溯？分治？动态规划？

string类和char *str的区别以及string类含有什么标准函数？ char* 和string的的互相变换？

回文问题

字符串的查找都见过的题以及去思科面试被两个面试官都问过的题：判断是不是判断是不是回文, 双指针即可。

变种题： 给定一个字符串，问是否能通过添加一个字母将其变为回文串？

思路：分析题意，本身是回文，添加一个字母一定是回文。本身不是回文，则可以允许其中一个字符不匹配，这时处理好指针的移动。结束条件，两指针相遇。

查找子串：模式匹配算法

字符串为T，模式为P，求P是不是T的子串。

朴素/KMP/BM算法

朴素的方法为回溯的方法，如果不同，回溯，复杂度o(mn)，又称Brute Force（暴力搜索方法）。
KMP（Knuth-Morris-Pratt）算法，通过增加额外的表，利用子串自己本身的信息，移动两个指针

本身的信息：每次不匹配时，如何移动指向pattern的指针。空间换时间的一种做法。先存下当前位置，后缀和前缀相同的长度。
BM算法（Boyer-Moore）

从后往前比较，如果相同，则双指针向前移，如果不同，则移动的位数为该字符在子字符中出现的位置。采用两个规则，好后缀规则和坏字符规则。

坏字符规则：如果不匹配，不存在这个字符，则整体后移，存在，则移动，使其对齐。

好后缀规则：和KMP类似，直接移动直到对齐部分和前缀相同。

实现的时候，生成两张表，一个为坏字符移动的表，一个为好后缀移动表。

子串问题

例题1：计算两个字符串的最大公共字串的长度，字符不区分大小写

int getCommonStrLength(char * pFirstStr, char * pSecondStr);

看到此题联想起生物信息课上蛋白质序列local alignment，其实为动态规划Dynamic Programming问题。建立数值矩阵。

例题2：对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

测试样例：

"abc1234321ab",12
返回：7

思路：将该字符串翻转，则变成例题1.

基于哈希表的查找

题目描述：题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

分析：这题有点和桶排序类似，直接记录字符出现的次数。字符串的数值范围[0-256]。

哈希表的知识补充：1. 根据key值，可以直接访问value,加快存取速度。哈希表重要的几个因素，如果键值不同，值相同，称为冲突。散列函数，处理冲突，载荷因子。
$collision : k1 \neq k2, f(k1) = f(k2)$

字符串含特殊字符的匹配

此类题目看似简单，但字符串的指针的移动需要特别小心。

正则表达式的匹配

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"aba"均不匹配

分析:此题的难点再于理清思路，比较难处理的是*，因为* 是变长的，而且影响的是前面的字符。程序中最难处理的是 .*,而且前一个字符匹配成功与否与后面的*是相关的，而且也很难确定*到底有几个。

这时用到了递归。（将复杂的循环转换为递归是很方便的）

当pattern+1 == * 时， return match(str,pattern+2)|| match(str+1,pattern);返回匹配0个或者匹配1个以上的时候。

表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e", "1a3.14", "1.2.3", "+-5"和 "12e+4.3"都不是。

分析：自动机的实现。自动机可以回顾研一上学的课Fundamental of CS.书籍《Logic and Language Models for Computer Science,Hamburger and Richards》 Finite Automatic Machine.

其中比较有意思的知识点事DFA和NFA， Determinstic和Non-determinstic自动机。其中NFA一个条件可以到达多种状态。不过状态机虽然看起来一目了然，实现的时候处理要很好的处理转移给自己的状态。

字符串中正则表达式的函数以及库

解题的时候可以快速解答。

字符串的翻转

例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

分析：先旋转一遍，再找到单词再转一遍。

字符串转换为整数

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。

分析：按部就班 - ‘0’即可

左旋字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

分析

利用额外空间储存的话，简单
要是不用额外空间储存，则翻转即可。前K个翻转一次，后K个翻转一次，再整体翻转。
$BA = (A^TB^T)^T$

大数类题目

动态规划类

这一类题目归结到动态规划当中

数组类

排序

	时间复杂度最坏	时间复杂度最好	时间复杂度平均	稳定性
冒泡排序	n^2	n^2	n^2	稳定
选择排序	n^2	n^2	n^2	不稳定
插入排序	n^2	n^2	n^2	稳定
归并排序	nlogn	nlogn	nlogn	稳定
堆排序	nlogn	nlogn	nlogn	不稳定
快速排序	nlogn	nlogn	n^2	不稳定
希尔排序	n^1.5	n^1.3	n^2	不稳定
桶排序	n+m	n	n	不稳定
基数排序	p(n+b)	p(n+b)	p(n+b)	稳定

冒泡排序，选择排序，插入排序

这三种时间复杂大相同。

冒泡排序：二重循环，和相邻的元素比较，有点类似于水泡上升，第二重循环值为[arr.size()-1:i;-1]

选择排序：二重循环，第二重循环值为[i:arr.size()-1:1],每次选择最小的值和i交换。

插入排序：假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。第二重的循环值为[i+1:0,-1], 看需不需要交换

归并排序，mergeSort

先split
再merge， merge的时候~~需要每次找到左边和右边的边界值~~,需要创建额外的空间，然后先保存中间结果，再copy过去。
需要注意的地方，由于middle =(l+r)/2,此时分治法的递归函数里的左中右需要很清晰的处理,左开右闭，左闭右开，元素为1的时候返回。
外部排序？

快速排序，分治，quicksort

重要的函数为Partition函数，其中还有与其类似的利用partition思想的题目。随机选择一个数，比它大的放左边，比它小的放右边。

进阶random quicksort

不稳定.

class BubbleSort {
public:
    void bubbleSort(vector<int> &data) {
        for (int i = 0; i < data.size(); ++i) {
            for (int j = data.size() - 1; j > i; --j) {
                if (data[j - 1] > data[j]) {
                    swap(data[j - 1], data[j]);
                }
            }
        }
    }
};

class SelectionSort {
public:
    void selecSort(vector<int> &data) {
        for (int i = 0; i < data.size(); ++i) {
            int small = i;
            for (int j = i + 1; j < data.size(); ++j) {
                if (data[j] < data[small]) {
                    small = j;
                }
                swap(data[small], data[i]);
            }
        }
    }
};

class InsertSort {
public:
    void insertSort(vector<int> &data) {
        for (int i = 1; i < data.size(); ++i) {
            for (int j = i; j > 0; j--) {
                if (data[j - 1] > data[j]) {
                    swap(data[j - 1], data[j]);
                }
            }
        }
    }
};

class MergeSort {
public:

    void merge(vector<int> &data, int l, int m, int r) {
        int temp[r - l];
        int index = 0;
        int leftIndex = l;
        int rightIndex = m;

        while (leftIndex < m && rightIndex < r) {
            if (data[leftIndex] > data[rightIndex]) {
                temp[index++] = data[rightIndex++];

            } else {
                temp[index++] = data[leftIndex++];
            }
        }

        // copy the rest to the temp
        if (leftIndex < m) {
            while (leftIndex < m) {
                temp[index++] = data[leftIndex++];
            }
        } else {
            while (rightIndex < r) {
                temp[index++] = data[rightIndex++];
            }
        }

        // copy back
        for (int i = l; i < r; ++i) {
            data[i] = temp[i - l];
        }

    }

    void mergeSort(vector<int> &data, int l, int r) {
        // [l,r)，数组大小为1的时候，即l<r-1的时候返回， 或者也可以为[l,r],则上面不等式要加等号
        if (l < r - 1) {
            int m = (l + r) / 2;
            mergeSort(data, l, m);
            mergeSort(data, m, r);
            merge(data, l, m, r);
        }
    }

};

class QuickSort {
public:
    void quickSort(vector<int> &data, int left, int right) {
        if (left < right) {
            int pi = partition(data, left, right);
            quickSort(data, left, pi - 1);
            quickSort(data, pi + 1, right);
        }
    }

    int partition(vector<int> &data, int left, int right) {
        int pivot = data[right];
        if (left < right) {
            int rightIndex = right;
            int index = right - 1;
            while (index >= left) {
                if (data[index] >= pivot) {
                  //这段代码是有错误的 比如[3,1,2]，1和1交换后，rightIndex却移了.网上找到一段更通用的代码12.29
                    swap(data[index], data[rightIndex - 1]);
                    rightIndex--;
                }
                index--;
            }
            swap(data[rightIndex], data[right]);
            return rightIndex;
        }
    }
};

希尔排序 Shell sort

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。时间复杂度减少

不稳定

~~什么脑回路，先搁置。~~

增量序列+插入排序
增量序列为size/2这样计算出来
最坏情况 O(N^2),各种间隔序列的排序没有交换，增量序列不互质，这样每次都不起作用（youtube上）
Hibbard增量序列。D=2^{k-1,相邻元素互质，T=（N}3/2）,avg(N^5/4)
Sedgewick增量序列
依赖于增量序列的选择，跳着排，不稳定。

计数排序

有点类似与哈希表的感觉，适用于海量数据并且数据值在一定范围内的时候。

基数排序Radix Sort创建10个桶，再从个位开始直到最高位。

此种排序方法没有接触过，实现一遍。基数=10，建立桶，此为优先，LSD least significant digit，次位优先。时间复杂度,时间复杂度，T=O(P(n+b)) 桶的个数和n。别的用途，多关键字的排序。时间复杂度取决于放入桶中以及收集。

堆排序

什么是堆？

不稳定，堆排序是不稳定的。理论上看很好，实际效果虽然是O（logn），但常数大。快速排序总是可以找到最坏的情况，平均时间复杂度为nlogn，实际中运用条件。

查找和排序

基本思路是 O(n) -> O(logn),以及要灵活利用数组本身的规律。

题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何，如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

分析：总共五张牌，其实是一道很简单的题，选择排序的方式加大小王的处理即可。

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

链表类的题目

链表类的题目，要很好的处理好指针，不要存在内存泄露的情况。以及还有一类快慢指针的问题。总之目前来看是很单一的题目类型。

快慢指针题

题目描述：输入一个链表，输出该链表中倒数第k个结点。

分析：一个快指针先走K步，走到尾部即可。

题目进阶：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

分析：

是否有环，一个指针每次走两步，一个指针每次走一步。
入口节点：当快指针追上慢指针，有环，此时快指针不动，计算环的大小K。
让快指针从头先走K步，然后当两指针相遇，为环的入口节点。

处理好指针类

题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

分析：删除重复指针的话，得一直记录前驱节点，所以这个时候是两个指针一起工作。注意判断条件不要乱。

类似题： 合并两个排序的链表，反转链表，注意指针的处理

双向队列类

题目描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

分析： 该题看了论坛上的答案，为双向队列处理，方法巧妙。应该记一下。

位图

树形数据结构

二叉树，很多时候都要用到递归和动态规划。另外树形题目范围很大很广，还有很多没有听过的树形结构，各有特点，先介绍一下常见的一些树。

树的种类和基础知识

基础的树形结构：二叉搜索树，线索二叉树，哈夫曼树，二叉堆
平衡树： AVL,红黑树，2-3树，2-3-4，B树，B+树，B-树，treap SBT
优先队列：左高树，双端堆，斐波那契堆
集合类：并查集
区间树：线段树，划分树，归并树
字母树：字典树，后缀树，AC自动向量机
动态树：伸展树
其他

要求：时间富余时都实现一遍这些树

树的遍历

先序和后序中序的相互变换类题目。

题目描述：重建二叉树

分析：根据二叉树的前序和中序/二叉树的后序和中序重建二叉树，关键点在于找准根节点。

问题：前序和后序，能重建二叉树么？不能，前序和后序只反应出了父子关系，没有反应出左右关系。

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

分析：二叉树后序遍历的题目。左子树，右子树，根。此树为二叉搜索树，则比根节点小的为左子树，比根节点大为右子树，递归即可。

题目描述：序列化二叉树

分析：看似这题简单，但是却要考虑很多种形态的树，如果不用递归而用循环处理和栈队列处理的话，会出现很多错。错误代码可以看提交历史，最简洁的方法还是用递归。序列化选用先序遍历，这样可以迅速的定位根节点。用循环来处理的时候，想到了栈，但是栈在处理空叶子的时候向上回退的时候回有问题，比如是左孩子还是右孩子，谁为父亲节点，总之在提交的历史代码里出现了很多错。故解题经验为尽量转换为递归来做。递归的技巧，将专门放到另一章。

题目描述：给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

分析：递归？动态规划？ root_K>k,搜寻左边，root_K = K返回， root_K<K搜寻右边。

遍历二叉树/递归类型遍历

题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

分析： 队列，采用双队列来实现。

题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

分析： 采用双栈来实现，后打印的节点的孩子在下一轮先打印。

题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

分析：左子树走一步，右子树也要走一步。如果转化为递归的话，左右子树对称，左右子树的孩子也对称。

题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

分析: 左根右。右子树存在，下一个，右子树不存在，向上返回。直至返回至为父亲的左孩子。

题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

分析： 遍历类型题目的变种题，A得遍历整棵树，直至B为A的子结构。首先找到根节点相同，然后左右子树。还是递归。

题目描述：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

分析：所有路径，则该题为BFS，要遍历所有可能的路径。采用Queue.

题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

分析： 平衡二叉树，深度差不超过1。抓准重点，左右遍历。

题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。

分析：同样也是指针的变换，将左右子树分别交换，即为镜像，同样也可以为递归

指针变换类

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

分析： 根节点的前驱节点为左孩子的最右孩子，根节点的右边节点为右孩子的最左孩子。可以先序递归，先变换自己的指针，再改变左子树，改变右子树。

第二次刷题的时候尝试采用三种遍历方式来做

递归和循环

能用递归的方法，如何用循环来实现？？

借助stack和queue.