设为首页 加入收藏

TOP

剑指offer中数据结构与算法部分笔记(一)
2019-06-05 02:08:08 】 浏览:31
Tags:剑指 offer 数据结构 算法 部分 笔记

2.3.4 树


遍历:前中后序,宽度优先。


二叉树的特例:二叉搜索树、堆(最大堆和最小堆,用于找最值)、红黑树(c++ STL中的很多数据结果就是基于这实现的);


题7-重建二叉树:递归,设置四个位点;


class Linuxidc {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()!=vin.size()||vin.size()==0) return nullptr;
        return Construct(0,pre.size()-1,0,vin.size()-1,pre,vin);
    }
   
    TreeNode* Construct(int prestart,int preend,int vinstart,int vinend,const vector<int> &pre,const vector<int> &vin){
        if(prestart>preend) return nullptr;
        TreeNode* root=new TreeNode(pre[prestart]);
        for(int i=vinstart;i<=vinend;i++)
            if(pre[prestart]==vin[i]){
                root->left=Construct(prestart+1,prestart+i-vinstart,vinstart,i-1,pre,vin);
                root->right=Construct(prestart+i-vinstart+1,preend,i+1,vinend,pre,vin);
                break;
            }
        return root;
    }
};


题8-二叉树的下一个节点


class Linuxidc {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode==nullptr) return nullptr;
        if(pNode->right!=nullptr){
            pNode=pNode->right;
            while(pNode->left!=nullptr){
                pNod

e=pNode->left;
            }
            return pNode;
        }
        else{
            if(pNode->next==nullptr)
                return nullptr;
            else{
                if(pNode==pNode->next->left)
                    return pNode->next;
                else{
                    while(pNode->next!=nullptr){
                        if(pNode==pNode->next->left)
                            return pNode->next;
                        pNode=pNode->next;
                    }
                    return nullptr;
                }
            }
        }
    }
};


2.3.5 栈和队列


题9-两个栈实现队列:一个用于插入,一个用于删除,增加判空操作,每次插入/删除操作后只有一个栈是有数据的;


2.4 算法和数据结构


递归/循环,排序/查找,搜索路径(回溯法),最优解(动态规划),贪心,位运算(与、或、异或、左右移)


2.4.1 递归和循环


如果面试官没有要求,多采用递归;递归存在时间效率和调用栈溢出的问题;


题10-斐波那契数列:递归效率低,采用循环O(n),也可以用到数学公式用递归O(logn),青蛙跳和格子都是这个问题;


2.4.2 查找和排序


顺序查找、二分、哈希表查找、二叉排序树


交换使用swap函数
编程开发网

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++中STL容器的比较 下一篇Pytest-selenium简单使用示例

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }