数据结构与算法之美（已面试部分）

作者: zhouluyao | 来源:发表于2018-12-18 23:13 被阅读18次

数据结构与算法
数据结构与算法之美（已面试部分）
数据结构之栈
数据结构之队列
数据结构之二分查找的概念
数据结构之二叉树
数据结构之二叉搜索树
二叉树的遍历(前序中序后序层序)
数据结构之数组
数据结构之链表

1.题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

//链表结点定义如下：
struct ListNode
{
    int m_nKey;
    ListNode *m_pNext;
};

算法实现:

ListNode * reverseList(ListNode *pHead)
{
    //防止链表断开，要保存当前节点，上一个节点，下一个节点
    //保存顺序:先保存上一个节点，再让当前节点指向上一个节点完成反转，遇到pNext==nullptr时到达链表尾部
    ListNode *pNode = pHead;
    ListNode *pPrev = nullptr;
    ListNode *pReverseHeadNode=nullptr;
    while (pNode!=nullptr)
    {
        //保存当前节点的下一个节点
        ListNode *pNext = pNode->m_pNext;

        //如果下一个节点为nullptr，找到了pReverseHeadNode
        if (pNode->m_pNext == nullptr)
            pReverseHeadNode = pNode;

        //反转
        pNode->m_pNext = pPrev;

        //把当前节点赋值为上一个节点
        pPrev = pNode;
        //把下一个节点赋值为当前节点
        pNode = pNext;

    }

    return pReverseHeadNode;

}

2.题目：输入两个链表，找出它们的第一个公共结点。

应用场景:

1.遍历两个view的第一个父控件

//链表结点定义如下：
struct ListNode
{
    int m_nKey;
    ListNode *m_pNext;
};

算法实现:

//找到两个链表的公共节点
ListNode *findCommonNode(ListNode *pFirstHead,ListNode *pLastHead)
{
//计算出两个链表的长度差值
    ListNode *pFirstNode = pFirstHead;
    ListNode *pLastNode = pLastHead;

    unsigned int firstListLength = getLinkedListLength(pFirstNode);
    unsigned int lastListLength = getLinkedListLength(pLastNode);
    unsigned int diff;
    if (firstListLength>lastListLength)
    {
        diff = firstListLength - lastListLength;
        //先让pFirstHead走diff个节点
        for (int i = 0; i < diff; i++)
        {
            pFirstNode = pFirstNode->m_pNext;
        }
    }
    else
    {
        diff = lastListLength - firstListLength;
        //先让pLastHead走diff个节点
        for (int i = 0; i < diff; i++)
        {
            pLastNode = pLastNode->m_pNext;
        }
    }
    while ((pFirstNode!=pLastNode)&&(pFirstNode!=nullptr) &&(pLastNode!=nullptr))
    {
        pFirstNode = pFirstNode->m_pNext;
        pLastNode = pLastNode->m_pNext;
                    
    }

    return pFirstNode;


}

unsigned int getLinkedListLength(ListNode *pHead)
{
    unsigned int length = 0;
    ListNode *pNode = pHead;

    while (pNode!=nullptr)
    {
        length++;
        pNode = pNode->m_pNext;
    }

    return length;
}

3.一个n阶的楼梯,每一步只能走1阶或者2阶，问n阶楼梯有多少种走法？

算法实现:

int f(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n - 1) + f(n - 2);
}

4.题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：

f(0)=0;

f(1)=1;

f(n)=f(n-1)+f(n-2); //n>1

//降低时间复杂度,带数组缓存的实现
int fib(int n, int memo[] )
{

    if (n <= 1) return n;
    else if (!memo[n])
    {
        memo[n] = f(n - 1) + f(n - 2);
    }
    return memo[n];
}

5.链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

链表定义如下:

struct ListNode
{
    int m_nKey;
    ListNode *m_pNext;
};

ListNode *findKthToTail(ListNode *pHead,unsigned int k)
{
    //pHead==null,k=0,k超出链表的长度直接返回
    if(pHead==nullptr ||k==0) return nullptr;
    
    //先让前一个节点从链表头走k-1步,然后再让后一个节点同步走，前一个节点到达尾部，后一个节点就是倒数第k个节点
    
    ListNode *pAhead =pHead;
    ListNode *pBehind =nullptr;
    for (int i=0; i<k-1; i++) {
        if (pAhead->m_pNext!=nullptr) {
            pAhead =pAhead->m_pNext;
        }
        else
        {
            return nullptr; //保证k不超过链表的长度
        }
    }
    
    pBehind =pHead;
    while (pAhead->m_pNext!=nullptr) {
        pAhead =pAhead->m_pNext;
        pBehind=pBehind->m_pNext;
    }
    return pBehind;
    
}

6.合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入下图中的链表1和链表2，则合并之后的升序链表如链表3所示。

合并有序链表.jpg

链表结点定义如下：

struct ListNode
{
    int m_nKey;
    ListNode *m_pNext;
};


ListNode *Merge(ListNode *pHead1,ListNode *pHead2)
{
    if (pHead1==nullptr) return pHead2;
    if (pHead2==nullptr) return pHead1;
    //比较两个节点,哪个节点的值小，取出哪个节点，放到合并后链表的尾部
    ListNode *pMergeHead=nullptr;

    if(pHead1->m_nKey<pHead2->m_nKey)
    {
        pMergeHead =pHead1;
        pMergeHead->m_pNext=Merge(pHead1->m_pNext, pHead2);
    }
    else
    {
       pMergeHead =pHead2;
       pMergeHead->m_pNext=Merge(pHead1, pHead2->m_pNext);
    }

    return pMergeHead;
};

7.题目：判断一个链表是否包含环，如果包含环找出环的入口节点？

思路：

1.两个指针,快指针走2步,慢指针走一步,如果走到链表尾部还没相遇,说明链表中没有环，否则返回在链表中相遇的节点

2.找到相遇的节点,再次回到该节点时，计算环的大小loopLen

3.从链表的头部开始,一个指针先走LoopLen个节点,两个指针同时走，两个指针相遇的点即为环的入口点

truct ListNode
{
    int m_nKey;
    ListNode *m_pNext;
};

ListNode * MeetingNode(ListNode *pHead)
{
    if(pHead ==nullptr) return nullptr;
    
    ListNode *pSlow =pHead->m_pNext;
    if (pSlow==nullptr) return nullptr;
    
    ListNode *pFast =pSlow->m_pNext;
    
    while (pSlow!=nullptr &&pFast!=nullptr)
    {
        if (pSlow ==pFast) {
            return pSlow;
        }
        
        pSlow =pSlow->m_pNext;
        pFast=pFast->m_pNext;
        if (pFast!=nullptr) {
            pFast=pFast->m_pNext;
        }
    }
    
    return nullptr;
}


ListNode *EntryNodeOfLoop(ListNode *pHead)
{
    ListNode *meetingNode =MeetingNode(pHead); //第一次相遇的节点
    if(meetingNode==nullptr) return nullptr;
    
    //计算链表中环的大小
    int loopLen =1;
    ListNode *tempNode =meetingNode->m_pNext;
    while (meetingNode!=tempNode) {
        tempNode =tempNode->m_pNext;
        loopLen++;
    }
    
    //从头节点开始一个指针先走loopLen,两个指针一起走,第一次相遇的节点,即为环的入口
    ListNode *pNode1 =pHead;
    ListNode *pNode2 =pHead;
    for (int i=0; i<loopLen; i++) {
        pNode1 = pNode1->m_pNext;
    }
    
    while (pNode1!=nullptr &&pNode2!=nullptr)
    {
        if (pNode1==pNode2) {
            break;
        }
        pNode1=pNode1->m_pNext;
        pNode2=pNode2->m_pNext;
    }
    return pNode1;
}

给定二叉树，写出前序、中序、后序遍历的结果
算法待实现:

waiting

9.不用递归，实现二叉树的前序、中序、后序遍历
算法待实现:

waiting

10.找到一个字符串最长无重复字符的子序列，你的算法复杂度是多少，什么是最大子序列问题，并求解，说出算法复杂度
算法待实现:

#include <string>
#include <map>

#define MAX( a , b) (a>b)?a:b;
int lengthOfLongestSubstring(std::string s)
{
    if (s.size() == 0) return 0;
    //利用map保存遍历的字符和下标
    std::map<char, int> c_map;
    int max = 0;
    for (int i = 0,j = 0; i < s.size(); i++)
    {
        //找到同样的字符时，更新下标
        if (c_map.find(s[i]) != c_map.end())
        {
            j = MAX(j, c_map[s[i]]+1);
        }
        c_map[s[i]] = i;
        max = MAX(max, i - j + 1);
    }
    //找到同样的字符时，计算这段子串的长度,下标i遍历，j标识子串起始位置
    return max;

    //把每个子串的长度记录下来，返回最大值
}

动态规划算法有哪些特性
算法待实现:

waiting

12.一篇文章，如何准确的计算单词个数
算法待实现:

waiting

13.当我们想要查询 202.102.133.13 这个 IP 地址的归属地时，我们就在地址库中搜索，
发现这个 IP 地址落在 [202.102.133.0, 202.102.133.255] 这个地址范围内，
那我们就可以将这个 IP 地址范围对应的归属地“山东东营市”显示给用户了。
假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个 IP 地址的归属地呢？

解题思路：ip可看做是32bit整数对应的一个整数
查找指定iP的归属地本质上就是查找最后一个小于等于给定值的元素的问题，查找对应iP取出对应归属地即可，如果没查到则提示没找到

//查找最后一个小于等于给定值的元素 :eg:2,4,5,7,8,9 找出最后一个小等于6的值
int binarySearch(int a[],int n,int value)
{
    int low =0;
    int high =n-1;

            while (low<=high)
            {
                 int mid =low+ ((high-low)>>1);
                 if(a[mid]>value)
                 {
                     high=mid-1;
                 }
                 else
                 {
                     if(mid==0 ||a[mid+1]>value) return a[mid];
                     low =mid+1;
                 }
            }
    return -1;

}
    int array[] ={2,4,5,7,8,9};
    int key = binarySearch(array,6,6);

题目14：快手算法面试,两个单向链表相加

比如:通过链表把两个数相加
//1->2->8->9
//3->8->1->6
//4->0->0->6->1

//实现思路:涉及到链表长度不相等处理，相加>9进位问题
1.在while循环里遍历2个链表对应节点值,取出值相加，到达尾部后值为0
2.只要链表没到尾部或者存在进位数,继续添加新节点，新节点值为(两个链表节点值+进位)%10,进位值为(两个链表节点值+进位)/10
3.初始化一个节点，指向新链表的头结点，然后遍历添加新值
ListNode *addSingleLinked(ListNode *phead1, ListNode *phead2)
{
    ListNode preHead(0);
    ListNode *p = &preHead;

    int extra = 0;
    while (phead1 || phead2 ||extra)
    {
        int newValue = (phead1?phead1->m_nKey:0 + phead2?phead2->m_nKey:0 + extra)%10;
        extra = (phead1 ? phead1->m_nKey : 0 + phead2 ? phead2->m_nKey : 0 + extra) / 10;
        ListNode *node=new ListNode(newValue);
        p->m_pNext = node;
        p = p->m_pNext;

        phead1 = (phead1 ? phead1->m_pNext : phead1);
        phead2 = (phead2 ? phead2->m_pNext : phead2);
    }
    return preHead.m_pNext;
}