算法-数据结构 关于算法-数据结构:不基于比较的排序 不基于比拟的排序,核心思想就是桶排序,工夫复杂度都是O(N),常见的不基于比拟的排序有计数排序、基数排序。一、计数排序实用于排序元素的值范畴比拟小的,且是整数。(例如:年龄)1、外围思路:(1)先筹备一个无限个数(比方200)的整型辅助数组,挨个遍历原始数组,失去的值是 i,则将辅助数组 i 地位的值加一(2)…
算法-数据结构 关于算法-数据结构:前缀树 一、前缀树定义1)单个字符串中,字符从前到后的加到一棵多叉树上2)字符放在边上,节点上有专属的数据项(常见的是pass和end值)3)样本增加形式,每个字符串都从根节点开始加,如果没有路就新建,如果有路就复用4)增加时,沿途节点的pass值加1,每个字符串完结时来到的节点end值加1作用:能够更加不便的实现前缀相干…
算法-数据结构 关于算法-数据结构:与堆有关的题目 上次咱们聊了堆和堆排序,这次咱们就顺着说说和堆无关的题目。一、简直有序的数组排序1、题目形容已知一个简直有序的数组,简直有序是指,如果把数组排好序的话,每个元素挪动的间隔肯定不超过K,并且K绝对于数组长度来说是比拟小的。请抉择一个适合的排序策略,对这个数组进行排序。2、解决思路:从第一个数开始,将前K…
算法-数据结构 关于算法-数据结构:堆和堆排序 大家好,我是周一。 明天咱们聊聊堆,以及堆排序。一、堆谈到堆,首先咱们要从二叉树说起,从二叉树到齐全二叉树,再才到堆。1、二叉树每个结点最多只能有两棵子树,且有左右之分2、齐全二叉树一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的程序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中…
算法-数据结构 关于算法-数据结构:荷兰国旗问题以及快速排序 大家好,我是周一。最近几篇算法,咱们都是聊的归并排序,归并排序也说的差不多了,明天聊聊疾速排序。一、荷兰国旗问题1、啥是荷兰国旗问题荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:假如这样的条纹有多条,且各种色彩的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但不仅仅只有这一…
算法-数据结构 关于算法-数据结构:归并排序干掉的LeetCode第一个Hard题LeetCode327-区间和的个数帅 大家好,我是周一。最近几篇算法,咱们都是聊的归并排序,明天再开一篇。再聊两题。一、大于右侧数的两倍怕大家忘了归并排序,所以先拿一题练练手。1、题目形容求给定数组中,以后数 大于 右侧数两倍 的个数2、例子数组:[6, 7, 3, 2, 1]以后数大于右侧数的两倍的数有(6,2),(6,1),(7,3),(7,2),(7,1),(3,1)所有总共…
算法-数据结构 关于算法-数据结构:归并排序解决小和逆序对问题 大家好,我是周一。在上一篇归并排序中,咱们讲了归并排序的基本概念、merge(合并)过程等,明天趁热打铁,咱们来说说应用归并排序的一些常见面试题。一、小和问题1、题目形容:在一个数组中,每一个数右边比以后数小的数累加起来,叫做这个数组的小和。求一个给定数组的小和。2、例子:数组为:[1,3,4,2,5]1右边比1小…
算法-数据结构 关于算法-数据结构:归并排序以及Master公式 一、概念归并排序(Merge Sort)是建设在归并操作上的一种无效,稳固的排序算法,该算法是采纳分治法的一个十分典型的利用。将已有序的子序列合并,失去齐全有序的序列;即先使每个子序列有序,再使子序列段间有序。二、排序过程1、归并操作,指的是将两个程序序列合并成一个程序序列的办法。如:数组 {6,202,100,301…
算法-数据结构 关于算法-数据结构:基础数据结构栈和队列的练习 1、如何用栈构造实现队列构造首先,用一个栈必定是实现不了的。所以,思考两个栈来实现。一个是push栈、一个是pop栈。放数据的时候往push栈放,当取数据的时候,将数据全副倒到pop栈,再从pop栈取数据。留神:(1)倒数据的时候要一次性倒完(2)如果pop栈没有拿完,不能倒数据具体代码: {代码…} 2、如何用队列构造实…
算法-数据结构 关于算法-数据结构:优先队列 优先队列有什么用?能够求一些数据里的最大几个值,能够设定事件程序。为什么不间接排序后再从头拿?假如数据量很大时,比方1亿个选10个最大的,你排好序内存可能装不下。优先队列只有10个空间,间接往队列尾巴插入就行。根底优先队列的根底是把数据结构齐全二叉树构造,用数组实现。树的个性父节点比任何一个子节点大。…