Android面试基础系列三——数据结构

2017-10-28 本文已影响173人 thinkChao

此系列文章是我在毕业求职期间，对Android面试相关的基础知识做的一个整理，内容还比较全面，现在将其发布出来，希望对即将求职的同学能有帮助。
这一系列的文章都是使用MarkDown编辑的，源文件也一并公布出来，大家可以在我文章的基础上，根据自己的情况修改或增加内容，定制自己的面试笔记。

链接：http://pan.baidu.com/s/1mhM4RSO 密码：hgzt

数据结构相关的知识重点参考我以下几篇博客：

https://thinkchao.github.io/categories/%E7%AE%97%E6%B3%95%E7%BC%96%E7%A8%8B/

这篇文章主要是做个简单的梳理，列出了大纲，内容还需自己细化。

一、查找

1、顺序查找（n）

最直白直接简单的方法。

2、二分查找（折半查找 log2n）

也很好理解的方法，但必须满足两个条件：

必须有序
必须顺序存储，不能链式存储

3、二叉排序树（log2n）

中序遍历二叉排序树可以得到一个有序序列。

插入操作

删除操作（比插入复杂）

4、平衡二叉树（log2n）

平衡二叉树和二叉排序树是平行的概念，它们定义的维度不同，一个是关键字大小，一个是左右子树的深度。但是，平衡二叉树的引入是为了提高二叉排序树的效率，降低树的高度，减少平均查找长度。因此，我们有时默认平衡二叉树，是平衡二叉排序树。

平衡二叉树的调整

左左——右
右右——左
左右——左右
右左——右左

5、B-树

B树的出现是为了解决访问磁盘的问题。在之前，我们在进行查找时，都是把相应的数据结构（各种树）存储在内存中，但是当数据量特别大而内存装不下，我们只有存储到磁盘中。因为磁盘的访问时间要比访问内存大的多，所以我们想把磁盘访问次数控制在一个非常小的常数内，而且我们愿意写一个复杂的程序来完成这个目标，因为只要程序不冗长，机器执行基本不占用时间的。所以思路就是：对于相同的待查数据组成的树形结构，如果我们有更多的分支，那么我们就有更少的深度。

定义

一棵m阶的B-树，或为空树，或满足下列条件。首先，判断它是几阶的，就看它的节点中，最多可有多少个子树（包括叶子节点），也就是倒数第二层的每个节点最多可以有多少个子节点，其它要求如下，其实就是从以下几个维度来定义的：

1、根节点：如果不是叶子节点，至少有两棵子树

2、普通节点（非根非叶）：至少有"m/2上取整数"个子树

3、叶子节点：所有的叶子节点都出现在同一层次上，且不带信息

4、节点中包含的数据信息：应包信息如下：（n , A0 , k1 , A1 , k2 , A2 ……），比较容易理解，不明白参考课本吧

两种基本操作

查找节点：在磁盘中进行
查找关键字：在内存中进行

插入和删除

6、B+树

B+树是应文件系统而生的一种B-树的变形，与B-树的差异在于：

1、节点中有几个关键字，就有几棵子树（教材的说法太别扭，根部不利于记忆）

2、非终端节点可以看成索引，包含了各个子树中的最大值（或最小）

3、所有的叶子节点中包含了全部关键字信息

B+树的查找过程

B+树有两种查找运算方法，因为B+树上有两个指针，一个指向根节点，一个指向最小关键字节点。所以一个是从最小关键字开始顺序查找，一个是从根节点开始进行随机查找

7、哈希表及其冲突处理

哈希函数的选择

处理冲突的方法

线性探测再散列
二次探测再散列
伪随机探测再散列
再哈希法
链地址法

二、排序

关于时间复杂度、稳定性和代码，参考我的博客。

1、插入

这个很简单，自己能写出来。

2、冒泡（沉底）

重点是两个for循环里面的条件判断。

for(int i=ArraySize-1;i>0;i--)  //一共需要“ArraySize-1”次循环才能完成
        for(int j=0;j<i;j++)    //每一次循环需要比较的次数是递减的

3、选择

同样是需要两次for循环。

for(int i=0;i<ArraySize-1;i++)      //需要“ArraySize-1”次循环
        for(int j=i+1;j<ArraySize;j++)

4、快速

使用递归。

void quick(int data[],int lf,int rg)
{
    int tmp;
    //int mid=data[lf_idx];
    int lf_idx=lf+1;
    int rg_idx=rg;
    if(lf<rg)
    {
        while(1)
        {
            for(int i=lf_idx;i<=rg;i++)          //一开始用的i<=rg_idx,这是不可以的
            {
                if(data[i]>=data[lf])
                {
                    lf_idx=i;
                    break;
                }
                lf_idx=i;
            }
            for(int j=rg_idx;j>=lf;j--)
            {
                if(data[j]<=data[lf])
                {
                    rg_idx=j;
                    break;
                }
                rg_idx=j;
            }
            if(lf_idx<rg_idx)
            {
                tmp=data[lf_idx];
                data[lf_idx]=data[rg_idx];
                data[rg_idx]=tmp;
            }
            else
                break;
        }
        tmp=data[lf];
        data[lf]=data[rg_idx];
        data[rg_idx]=tmp;
        quick(data,lf,rg_idx-1);
        quick(data,rg_idx+1,rg);
    }
}

5、归并

1、没有使用递归。

2、进行合并的操作，是先合并到一个新的数组中，然后再复制到原数组中。

6、堆排序

搞清楚每一次建堆的过程，从最后一个非叶子节点，直到根节点。

7、基数排序

三、二叉树

1、几大性质

看课本。

2、建树

#include <iostream>
#include <vector>
using namespace std;

struct BNode
{
    int id;
    int value;
    struct BNode *left;
    struct BNode *right;
};

int main()
{
    BNode *BTree=NULL;   //指向根节点的指针，这个指针始终指向根节点，也就是编号为1的节点
    BNode *node=NULL;   //每一个节点都是指针类型的，这样才能找到它们的地址，把它们给链起来

    char ch;
    int value;
    int fu,zi;
    int id = 1;
    vector<BNode *> vec;
    while(cin>>value)   //这里我们假设输入的顺序是从1——n按编号输入的
    {
        ch=getchar();   
        node = (BNode *)malloc(sizeof(BNode));  //一定不要忘了分配空间
        node->id=id++;
        node->value=value;
        node->left=NULL;
        node->right=NULL;
        vec.push_back(node);
        if(ch=='\n')
            break;
    }

    BTree = vec[0]; //输入的第一个节点就是根节点

    while(cin>>fu>>zi)         //我们这里的边的输入都在一行，遇回车停止
    {
        ch=getchar();
        BNode *temp_fu = vec[fu-1];
        BNode *temp_zi = vec[zi-1];
        //cout<<"temp_fu="<<temp_fu<<endl;
        //cout<<"temp_zi="<<temp_zi<<endl;
        if(temp_fu->left == NULL)
        {
            temp_fu->left = temp_zi;
            //cout<<"执行了1"<<endl;
        }
        else 
        {
            temp_fu->right = temp_zi;
            //cout<<"执行了2"<<endl;
        }
        if(ch=='\n')
            break;
    }

        cout<<BTree->value<<endl;
        cout<<BTree->left->value<<endl;
        cout<<BTree->right->value<<endl;
        cout<<BTree->left->left->value<<endl;
        cout<<BTree->left->right->value<<endl;

    return 0;
}

3、前序遍历

仔细想一想，在前序遍历中，只要访问的节点是空，就执行：出栈，然后访问出栈元素的右孩子。

    BNode* stack[1000];
    int top = 0;    //因为STL没有栈和队列的数据结构，所以使用一个数组+top的形式来模仿栈
    BNode *p=BTree;
    while(p || top!=0)  //这一个判断是整个算法的关键点
    {
        if(p)
        {
            cout<<p->value<<"  ";
            stack[top++]=p;
            p=p->left;
        }
        else
        {
            p=stack[--top];
            p=p->right;
        }
    }

4、中序遍历

与前序遍历只有一行代码的区别，就是cout的位置不同了。

BNode* stack[1000];
    int top = 0;    //因为STL没有栈和队列的数据结构，所以使用一个数组+top的形式来模仿栈
    BNode *p=BTree;
    while(p || top!=0)  //这一个判断是整个算法的关键点
    {
        if(p)
        {
            stack[top++]=p;
            p=p->left;
        }
        else
        {
            p=stack[--top];
            cout<<p->value<<"  ";
            p=p->right;
        }
    }

4、后序遍历

    BNode* stack1[1000];
    int stack2[1000];
    BNode *p=BTree;
    int top1=0,top2=0;
    int flag;
    while(p || top1!=0)
    {
        if(p)
        {
            stack1[top1++]=p;
            stack2[top2++]=0;
            p=p->left;
        }
        else
        {
            p=stack1[top1-1];
            flag=stack2[top2-1];
            if(flag==0)
            {
                stack2[top2-1]=1;
                p=p->right;
            }
            else
            {
                p=stack1[--top1];
                top2--;
                cout<<p->value<<"  ";
                p=NULL;         //这句不要忘了
            }
        }
    }

5、层次遍历

    BNode* queue[1000];
    int front=0,rear=0;
    BNode *p=BTree;
    queue[rear++]=p;
    while(front != rear)
    {
        p=queue[front++];
        cout<<p->value<<"  ";
        if(p->left)
            queue[rear++]=p->left;
        if(p->right)
            queue[rear++]=p->right;
    }

6、哈夫曼树

没有度为1的节点

7、打印出所有的从根节点到叶子节点的路径

void findPath(BNode* node,vector<int> path)
{
    int result=0;
    path.push_back(node->value);
    if(node->left==NULL && node->right==NULL)
    {
        cout<<"node->value="<<node->value<<endl;
        for(int i=0;i<path.size();i++)
        {
            cout<<path[i]<<"  ";
            result = result+path[i];
        }
        cout<<endl;
        path.pop_back();//这一行代码放在这里，或者放在最后都可以
    }

    if(node->left!=NULL)
        findPath(node->left,path);
    if(node->right!=NULL)
        findPath(node->right,path);
    //path.pop_back();
}

8、求二叉树的深度

9、判断是不是平衡二叉树

四、链表

五、字符串

四、题目思路整理

这里是我对算法题思路做的一个简单的思考和整理，想起来就写上了，有的也没写，其中的“T”指的是《剑指offer》上对应的题目，建议将这本书过上几遍。

1、二叉树

1、二叉树的算法，基本都是要配合栈或者队列来操作的

2、有些问题，举一个最简单的，有三个节点的二叉树来考虑就可以，但是要使用递归的思路，类似于上面二叉树部分的第七题，这一题就是“有递无归”的情况。像二叉树的三种遍历方式的递归解法，也可以这样考虑。

2、链表

1、设两个指针，并且两个指针之间有一定间隔。T15

2、节点与节点的值，删除节点并不是指删除某个节点在内存中的位置，而是删除节点的值。T13

3、数组

1、前后并进。可以在开头、结尾都设置指针，两端进行比较。T14

或者，也是需要两个指针，不过指针的位置都是在结尾，或者其它位置。T5

4、递归

一定不要去试图理解用递归写的程序，很难很难，而是要试着去整理归纳题目，正向的写出递归程序。

分类

1、有递有归，在回来的路上解决问题

典型的就是求阶乘。

2、有递无归，在去的路上解决问题 T6、T18、T19、T25、T39。
基本都是二叉树的题目。

1）既然是在去的路上解决问题，

3、有递无归，在尽头解决问题 T28

1）既然是在尽头解决问题，那肯定需要有个判断，是否达到了尽头，然后在进行操作。

5、字符串、二进制问题

T10、T12

五、《剑指offer》题目思路整理

1、赋值运算符函数

此题不需要。

2、实现单例模式

看Java设计模式。

3、二维数组中的查找

由于这个数组按照从上到下，从左至右的递增，很明显要么是从左上角开始比较，要么是从右上角开始，左下同右上，右下同左下。

但是尝试之后发现，从左上开始，一次比较后，只能排除两列的某部分，而从右上开始可以直接排除一整列，所以选择从右上开始。

4、替换空格

这道题的解题思路很明显有两个大方向：

1、从后往前挨个遍历，遇到空格之后，将空格后面的字符串往后移，然后插入%20，直到遍历到第一个节点。

2、先整体遍历一遍，看有多少个空格，这样就可以计算出字符串最终的长度，然后再从后往前挨个移动，这样每个字符只移动一次就可以了。

很明显第二个效率要比第一个高，所以直接考虑第二算法，第二个算法的核心就是如何将字符直接移动到指定位置，这里也有两种思路：

1、这个思路是很明显的一种方法，瞬间就想到的。就是直接计算每个字符应该移动到哪个区域，然后直接赋值过去。这里就要注意计算，每个空格后的字符移动所跨越的位数是不一样的，需要细心的考虑一下。

2、第二个就是设两个指针，第一个就是指字符串的末尾，第二个指移动后字符串的末尾，这样就可以直接一一赋值，不需要我们计算了，当两个指针相遇时结束，比较省心。

由此可见，第二种方法要更简单一些，但第一种方法是瞬间就能想到的，第二种方法不太好直接想到结束条件——两个指针相遇时停止，需要耐心的举个例子试一试。

5、从尾到头打印链表

我还以为这道题能有比较新奇的解法，不需要借助额外的存储空间，看答案还是用到了栈。

6、重建二叉树（递归，较难）

7、用两个栈实现队列

这个就比较简单了，之前也看过答案了。

8、旋转数组的最小数字

能够想到这道题要使用折半查找，就是有一点需要注意的地方，就是两个指针在什么时候停止，主要就是两种情况，是相遇时终止，还是相邻时终止。当然，只要愿意，他们总会相遇的，但可以不必，只要在相遇之前，也就是相邻时，就可以找出我们需要的元素了。

这道题还有一点，就是健壮性问题，考虑问题要全面。

9、斐波那契数列（递归，较难）

10、求二进制的个数

傻逼了，看到这个题我的想法是：先将十进制转换成二进制，然后一个个看二进制数是1还是0。

上面那个思路真的很傻逼，任何数据在计算机中都是二进制存储的，“将十进制转换成二进制”这个怎么做我都不知道，这个思路是我瞬间想出来的，但不知道怎么做，也不必这么做。既然任何数据在计算机中都是二进制，我们就可以直接进行位运算，比如移位、相与和相或。

while(x)
{
    if(x & 1)
        count++;
    n = n>>1;   
}

上面这个解法的不足就是没有考虑负数。所以，换个思路，不右移要求的这个二进制数了，而是左移与它相与的数：

unsigned int flag=1;
while(flag)
{
    if(n & flag)
        count++;
    flag = flag << 1;
}

上面这个解法需要循环32次，也就是整数二进制数的位数。

求十进制各个位上的数的和：

while(x!=0)
{
    g=x%10;  /从个位开始求
    fx=fx+g; //各个位上的数字之和
    x=x/10;  相当于右移
}

11、实现Power()函数

直白的实现思路很简单，就是要考虑健壮性：底数是0、正数、负数的情况，次方是0、正数、负数的情况。

还有更高想的解法，就是总结规律，32次方就是16的平方，以此类推吧。

12、打印从1到最大的n位数（字符串和数字的转换）

#include <iostream>
#include <string>
using namespace std;

void printer(char* number)
{
    for(int i=0;i<strlen(number);i++)
        cout<<number[i];
    cout<<endl;
}

bool increment(char* number)
{
    bool overflow=0;
    int takeOver=0;
    for(int i=strlen(number)-1;i>=0;i--)
    {
        int sum=number[i]-'0'+takeOver;
        if(i==strlen(number)-1)
        {
            sum++;
        }

        if(sum >= 10)
        {
            if(i==0)
                overflow=true;
            else
            {
                sum=sum-10;
                takeOver=1;
                number[i]='0'+sum;
            }
        }
        else
        {
            number[i]='0'+sum;
            cout<<"sum="<<sum<<"  "<<"'0'+sum="<<number[i]<<endl;
            break;
        }
    }
    return overflow;
}

void printNumber(char* number)
{
    bool isBegin0=true;
    for(int i=0;i<strlen(number);++i)
    {
        if(isBegin0 && number[i] != '0')
            isBegin0=false;
        if(!isBegin0)
            cout<<number[i];
    }
    cout<<endl;
}

int main()
{
    int j;
    int n=2;
    char *number = new char[n+1];
    memset(number,'0',n);
    number[n]='\0';
    increment(number);
    while(!increment(number))
        printNumber(number);
    return 0;
}

http://blog.csdn.net/zhaojinjia/article/details/8776639

上面这段代码不好理解，这篇博客写的还算好理解。思路就是每一次都遍历所有位的值，根据情况来做不同的操作。

13、在O(1)时间删除节点

一开始没有想到，后来明白了：删除节点并不是单纯的指删除节点，而是删除节点的值，这一下思路就打开了。

14、调整数组，使奇数位于偶数前面

设置两个指针，挨个移动，然后进行比较。

15、输出链表倒数第K个节点

也是需要两个指针，比较巧妙。

16、反转链表（经典，回头好好写写算法）

需要三个指针，考点就是需要大量的指针操作，容易乱。

17、合并两个排序的链表（经典，回头好好写写算法）

18、树的子结构

19、二叉树的镜像

20、顺时针打印矩阵

个人认为这也是一道非常经典的题目，要求我们必须要思路清晰，因为里面包含了很多条件判断和循环，非常容易混乱，主要思路如下：

1、首先是要搭建一个大的框架，就是什么时候终止结束，这一步需要我们寻找规律。

2、每一个循环里面又分为四步，但除了第一步，并不是每一步都需要完整的执行这四步，所以需要三个判断，判断需不需要执行，这里要好好考虑。

我想：我在做这个题的时候，上来就想for()循环，i++，j++之类的，这已经成了惯性思维了，所以不能这样。很明显这道题如果用for循环搭建框架会很麻烦，所以我们一定要想到使用while()，当然，使用while()就要求我们之前有一个总结的过程，总结出while()结束的条件是什么。然后在while里面使用不那么复杂的for循环。

21、包含min()函数的栈

这个之前看过一遍，第二遍还是能马上想起来，要使用辅助栈。

22、栈的压入弹出序列

也是能马上想起来做法，和人的思路是一样的，就是程序写起来可能要麻烦点。

23、树的层次遍历

这个参考数据结构就好了。

24、判断序列是不是二叉搜索树的后序遍历

25、二叉树中和为某一值的路径

之前做过这道题，也是不太好做，参考上面写的代码吧。

26、复杂链表的复制

算了，这道题看都不想看，放弃吧。

27、将二叉搜索树转换成有序的双向链表

又是链表的操作。

28、字符串的所有排序可能

1、递归要么在去的路上解决问题
2、要么在归的路上解决问题
3、在路的尽头解决问题，即在满足停止条件时解决问题。

#include <iostream>
#include <string>
using namespace std;


void permute(string prefix,  string str)
{
    if(str.length() == 0)
        cout << prefix << endl;
    else
    {   
        for(int i = 0; i < str.length(); i++)
        {
            //cout<<"1 = "<<prefix+str[i]<<endl;
            //cout<<"2 = "<<str.substr(0,i)+str.substr(i+1,str.length())<<endl;
            permute(prefix+str[i], str.substr(0,i)+str.substr(i+1,str.length()));
        }
    }   
}



int main()
{
    string str="abc";
    permute("",str);
    return 0;
}

29、数组中出现次数超过一半的数字

这道题的O(n)解法很巧妙，我是没想出来。

30、最小的K个数

http://blog.csdn.net/songshimvp1/article/details/51605262

这道题的重点是Partion()函数，这个函数的作用是以一个数为基准点，比它小的放左边，比它大的放右边，也就是一次快排，它有一个返回值，返回值是基准点一次快排后的索引。

而这道题的思路就是每一次都以第K个数为基准点进行快排，如果某次中，partion的返回值是k，也就是一次快排后，基准点的索引没有改变，那么就找到了。

31、最大子数组的和

除非使用动态规划，其它解法就是一一枚举，只不过中间有些小过程可以优化，其它的差不多，比如：
1、如果遍历的第一个数是负数，直接可以跳过

2、如果之前的累加之和比当前数还小，直接break，从下一个开始遍历。

32、从1到n的整数中，1出现的次数

除了直白的解法，第二种方法根本想不起来啊。

33、把数组排成最小的数

就是自定义sort()函数，重新定义比较规则。

还是挺简单的思路。

34、找出第1500个丑数

根据前面的数据，生成后面的数据，不用每个数字都进行计算和比较。

这是一种很好的思路。

35、第一个只出现一次的字符

思路和我想的一样，不过我首先想到的是用邻接表来实现，作者使用的是哈希表，思路应该都是一样的。

这道题目的思路是进行两次遍历，每一次遍历的时间复杂度都不高，所以总体的时间复杂度也不高。