摘要：
1.荷兰三色国旗问题 问题描述：一个数组只含有三种元素：0，1，2，不使用计数排序，将0放在1的左边，2放在1的右边。 分析： 1.可借鉴快排中划分的思想。将数组分为{0区},arr[],{2区} 2.遍历arr,当发现0时，0区向右扩，发现2时，2区向左扩， 3.当前元素进入2区时，结束。 2.行 阅读全文
摘要：
1.对几乎有序的数组排序 问题：给定数组arr，元素个数为N，将其排序后元素移动的顺序不超过K，其中K<<N。 分析： 1.冒泡排序，选择排序，快速排序，归并排序等排序时间复杂度与数组状态无关。 2.插入排序复杂度为O(N*K) 3.改进后的堆排序可以做到O(N*logK) 改进后的堆排序： 1.考 阅读全文
摘要：
1.堆的数组实现 1.由于堆是一个完全二叉树，故可用数组a56爆大奖在线娱乐。 2.当根节点下标为0时，左节点为2i+1，右节点为2i+2，父节点为(i-1)/2。 3.利用数组实现的堆，当对其删除元素时，应该从数组尾部删除，堆的根节点位置不应改变，否则堆的内部会发生变化，如图。 数组的初始状态和堆结构 初始状态 阅读全文
摘要：
1.计数排序 T(n)=O(n)，S(n)与桶的数量有关，算法稳定。 2.基数排序 T(n)=O(n*m),m是所排序的最大位数。 S(n)=O(n)，算法稳定。 阅读全文
摘要：
1.O(n^2)排序算法 1.冒泡排序：稳定 2.选择排序：不稳定 3.插入排序 2.O(N*logN)排序算法 1.归并排序 2.快速排序 3.shell排序 4.堆排序 3.空间复杂度分析 O(1)：冒泡排序，选择排序，插入排序，希尔排序，堆排序 O(n)：归并排序 不确定：快速排序，与基准的选 阅读全文
摘要：
1.需要掌握的相关概念 1.回文 2.字串（连续） 3.子序列（不连续） 4.前缀树（Trie树） 5.后缀树和后缀数组 6.匹配 7.字典序 1.判断一个二叉树是否另一个二叉树的子树 方法：将二叉树序列化，再使用KMP算法进行匹配即可，时间复杂度O(M+N). 要点：1.将二叉树进行序列化的时需标 阅读全文
摘要：
1.二叉树的序列化 序列化：如图，按前序进行序列化可得到字符串1!2!3!4!-1!-1!5!-1!-1!3!-1!-1!，其中!a56爆大奖在线娱乐一个值的结束，-1a56爆大奖在线娱乐该节点为空。 反序列化：序列化的逆操作。 附代码 2.二叉树的分层遍历 1.维护last和nlast指针。 2.开始时last=root 3.队 阅读全文
摘要：
1.完全二叉树结点的个数 1.问题：给一个完全二叉树的根节点，返回该二叉树的结点数。 2.步骤： 1.计算左子树和右子树的高度，记为h1,h2 2.如果h1=h2,则左子树必满，n+=2^h1-1.计算右子树 3.如果h1>h2,则右子树比满，n+=2^h2-1,计算左子树 4.如果h1=0,则结束 阅读全文
摘要：
先附个经典二分搜索代码 1.考察要点 1.二分搜索不仅在有序序列中可以运用，无序序列也同样适用，只要满足每次查找都会缩小一半查找范围。 2.注意循环初始条件，边界值，划分点的处理，确保循环不会无法终止。 3.划分点的经典写法：(p+r)/2 ，安全写法：r-(r-p)/2或p+(r-p)/2 2.局 阅读全文
摘要：
1.参与者和用例由对功能性需求的分析来确定，用例图是参与者和用例的可视化a56爆大奖在线娱乐。 2.参与者（Actor） 1.参与者是主题外部的人或事物针对用例所扮演的角色。参与者不一定代表人，可以是一个组织或一个机器。 2.木头人a56爆大奖在线娱乐法。 3.用例（Use Case） 1.用例a56爆大奖在线娱乐对参与者有价值的功能单元，不是所 阅读全文