算法-数据结构

描述/** * 翻转指定字符串中的内容,每个单词以空格字符分开 * * input： "the sky is blue" * * output: "blue is sky the" */既有APIfun reversStringByCollection(s: String): String { // 分割 val str: MutableList<String> = s.split("\\s+".toRegex()) as MutableList<String> // 翻转 str.reverse() // 插入 return str.joinToString(separator = " ")}双指针fun reversStringByPointer(s: String): String { // 定义左右指针，右指针不动，左指针向左移动取单词 var right = s.length - 1 var left = right // 存放翻转后的字符 val sb = StringBuilder() while (left >= 0) { // 查找第一次出现的空格 while (left >= 0 && s[left] != ' ') left-- sb.append(s.substring(left + 1, right + 1) + " ") while (left >= 0 && s[left] == ' ') left-- // 右指针移动 right = left } return sb.toString().trimEnd()}双端队列fun reversStringByQueue(s: String):String { var left = 0 // 构建双端队列 val deque: Deque<String> = ArrayDeque() val sb = StringBuilder() while (left <= s.length - 1) { if (s.isNotEmpty() && s[left] == ' ') { // 将单词push到队列头部 deque.offerFirst(sb.toString()) // sb.setLength(0) } else if (s[left] != ' ') { sb.append(s[left]) } // 移动指针 ++left } // 插入最后一个单词 deque.offerFirst(sb.toString()) return (deque.toTypedArray() as Array<String> ).joinToString(separator = " ")}

应用访问地域排名题目内容：给定陌陌一段时间的Nginx AccessLog（多个文件，估计66G左右），以最快的方式找到访问次数最多的5个IP。提交脚本或是可执行程序，约定以命令行参数的形式传入文件所在路径。按照次数降序输出5个IP，每个IP一行。 已知说明： 1. Linux Centos7服务器，配置限制在内存2G，4核CPU 2. Nginx access log 放置在指定目录下, 文件内容格式   '$remote\_addr\\t-\\t$remote_user\t$time_local\t'                '$http\_x\_forwarded\_for\\t$tcpinfo_rtt\t$tcpinfo\_rttvar\\t$tcpinfo_snd_cwnd\t$tcpinfo_rcv_space\t'                    '$request\_method\\t$host\t$request\_uri\\t$server_protocol\t$request\_length\\t$request_time\t'                    '$status\\t$body_bytes_sent\t$bytes_sent\t'                    '$http\_referer\\t$http_user_agent\t'                    '$connection\\t$connection_requests\t'                    '$upstream\_addr\\t$upstream_status\t$upstream\_response\_length\\t$upstream_response_time\t'                    '$scheme\\t$ssl_session_reused';    10.0.0.1 - - 22/Oct/2019:00:00:05 +0800 - 45250 5000 20 14600 POST api.immomo.com /v1/welcome/logs?fr=123456789 HTTP/1.1 567 0.029 200 96 651 - MomoChat/8.20.2 ios/1878 (iPhone 7 Plus; iOS 11.0.3; zh_CN; iPhone9,2; S1) 93983365152 15 10.0.0.1:9000 200 101 0.029 https . 3. 不限制实现语言，但是不能依赖任何开源的第三方依赖或者服务 3. 题目输入参数只有一个就是: Accesslog的文件夹路径 4. 题目输出需要在程序运行路径下创建result的文件，文件内容的格式是：按照访问量倒排的5个IP和对应的访问次数。比如：10.12.12.1    10000102.12.12.2   9999...评判规则：统计准确且耗时最短者胜出2核4G  机械硬盘 ...

作者 | George Dvorsky编译 | 深度学习这件小事1 排序算法 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。 稳定的 冒泡排序（bubble sort） — O(n^2）鸡尾酒排序(Cocktail sort，双向的冒泡排序) — O(n^2）插入排序（insertion sort）— O(n^2)桶排序（bucket sort）— O(n); 需要 O(k) 额外空间计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间合并排序（merge sort）— O(nlog n);需要 O(n) 额外空间原地合并排序— O(n^2)二叉排序树排序 （Binary tree sort） — O(nlog n)期望时间； O(n^2)最坏时间；需要 O(n) 额外空间鸽巢排序(Pigeonhole sort)— O(n+k); 需要 O(k) 额外空间基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间Gnome 排序— O(n^2)图书馆排序— O(nlog n) withhigh probability，需要（1+)n额外空间不稳定的 选择排序（selection sort）— O(n^2)希尔排序（shell sort）— O(nlog n) 如果使用最佳的现在版本组合排序— O(nlog n)堆排序（heapsort）— O(nlog n)平滑排序— O(nlog n)快速排序（quicksort）— O(nlog n) 期望时间，O(n^2) 最坏情况；对于大的、乱数列表一般相信是最快的已知排序Introsort—O(nlog n)Patience sorting— O(nlog n+k) 最坏情况时间，需要额外的 O(n+ k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）不实用的 ...

kmp算法（字符串匹配算法）对于刚刚接触这个算法的人，可能百分之八十的人，都对这个算法感到头疼。网上好的文章很多，但也同样会让新手很难去理解看懂。下面是一个博主放的视频，可以说讲的很清楚了，看完加理解，估计一个小时，自己再琢磨琢磨，外加看看其他博客两小时，进行代码的优化就可以了。kmp算法第一讲kmp算法第二讲

/** * 线性查找 */@Testpublic void OrderSearch() { int[] array = new int[]{-10,-5,0,5,10,15,20}; boolean flag = false; int target = 20; for (int i = 0; i < array.length; i++) { if (array[i] == target) { flag = true; System.out.println("存在要查找的数字，下标为：" + i); break; } } if (!flag) { System.out.println("要查找的数字不存在"); }}/** * 二分查找 */@Testpublic void TwoPointSearch() { int[] array = new int[]{-10, -5, 0, 5, 10, 15, 20}; int target = 20; boolean flag = false; int start = 0; int end = array.length - 1; while (start <= end) { int middle = (start + end) / 2; if (array[middle] == target) { flag = true; System.out.println("存在要查找的数字，下标为：" + middle); break; } else if (target < array[middle]) { end = middle - 1; } else { start = middle + 1; } } if (!flag) { System.out.println("要查找的数字不存在"); }}

提出问题：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807 解题思路：设置两个指针指向两条链表，构造新节点存储两个当前指针节点的值，当前节点被遍历过后，指针后移。对于满10进1的情况，设置一个变量判断即可。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: if l1==None: return l2 elif l2==None: return l1 else: h1 = l1 h2 = l2 flag = 0 new = ListNode(0) res = new while h1 or h2: temp = 0 if h1: temp += h1.val h1 = h1.next if h2: temp += h2.val h2 = h2.next if flag == 1: temp += 1 flag = 0 if temp >= 10: temp -= 10 flag = 1 res.next = ListNode(temp) res = res.next if flag == 1: res.next = ListNode(1) return new.next时间与空间复杂度： ...

提出问题：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4 解决思路：合并链表很简单，设置两个指针遍历两个链表，同时遍历并比较大小，如果1链表的当前节点值较小，将该节点添加到新链表中，1链表遍历指针后移一位，直到两个链表内所有节点都添加到新链表中。注意：题目要求新链表是通过拼接给定的两个链表的所有节点组成的，所以初始新建一个头节点，将头节点下一个节点指针指向两个链表中的最小节点，最后返回头节点的下一个节点。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1==None: return l2 elif l2==None: return l1 else: h1 = l1 h2 = l2 head = ListNode(0) result = head while h1!=None and h2!=None: if h1.val <= h2.val: head.next = h1 h1 = h1.next else: head.next = h2 h2 = h2.next head = head.next if h1!=None: head.next = h1 if h2!=None: head.next = h2 return result.next时间与空间复杂度： ...

提出问题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 解题思路：使用异或运算解决。异或运算规则：1.相同数字进行异或运算结果为0。2. 0与任何数进行异或运算结果为该数字。比如[4,1,1] 4与1异或为5，5与1异或为4，最终输出4为正确答案。所以算法先设定最终输出值为0，让输出值与数组中所有元素进行一次异或操作，即可得出最终答案。 代码如下(￣▽￣)： class Solution: def singleNumber(self, nums: List[int]) -> int: num = 0 for i in range(len(nums)): num = num^nums[i] return num时间与空间复杂度： 题目链接：https://leetcode-cn.com/probl...

问题提出：反转一个单链表 解决思路：最先想到的是使用栈来存储链表的第一遍遍历的值。再重新遍历链表，遍历的同时弹出栈的元素（弹出的顺序刚好是链表节点值的倒序），为当前节点赋值当前弹出的值。python可以直接使用list结构存储遍历值，读取的时候倒序读取list元素，就相当于栈的原理。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def reverseList(self, head: ListNode) -> ListNode: l = [] temp = head while temp!=None: l.append(temp.val) temp = temp.next i = len(l)-1 temp2 = head while i>=0: temp2.val = l[i] i-=1 temp2 = temp2.next return head时间与空间消耗： 题目来源：https://leetcode-cn.com/probl...

面试官: 既然已经有数组了,为什么还要链表本文发布于微信平台: 程序员面试官超过20w字的「前端面试与进阶指南」可以移步github 对于不少开发者而言,链表(linked list)这种数据结构既熟悉又陌生,熟悉是因为它确实是非常基础的数据结构,陌生的原因是我们在业务开发中用到它的几率的确不大. 在很多情况下,我们用数组就能很好的完成工作,而且不会产生太多的差异,那么链表存在的意义是什么?链表相比于数组有什么优势或者不足吗? 什么是链表链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer). 从本质上来讲,链表与数组的确有相似之处,他们的相同点是都是线性数据结构,这与树和图不同,而它们的不同之处在于数组是一块连续的内存,而链表可以不是连续内存,链表的节点与节点之间通过指针来联系. 当然,链表也有不同的形态,主要分为三种:单向链表、双向链表、循环链表. 单向链表单向链表的节点通常由两个部分构成,一个是节点储存的值val,另一个就是节点的指针next. 链表与数组类似,也可以进行查找、插入、删除、读取等操作,但是由于链表与数组的特性不同,导致不同操作的复杂度也不同. 查找性能单向链表的查找操作通常是这样的: 从头节点进入,开始比对节点的值,如果不同则通过指针进入下一个节点重复上面的动作,直到找到相同的值,或者节点的指针指向null链表的查找性能与数组一样,都是时间复杂度为O(n). 插入删除性能链表与数组最大的不同就在于删除、插入的性能优势,由于链表是非连续的内存,所以不用像数组一样在插入、删除操作的时候需要进行大面积的成员位移,比如在a、b节点之间插入一个新节点c,链表只需要: a断开指向b的指针，将指针指向cc节点将指针指向b，完毕这个插入操作仅仅需要移动一下指针即可，插入、删除的时间复杂度只有O(1). 链表的插入操作如下: 链表的删除操作如下: 读取性能链表相比之下也有劣势，那就是读取操作远不如数组，数组的读取操作之所以高效，是因为它是一块连续内存，数组的读取可以通过寻址公式快速定位，而链表由于非连续内存，所以必须通过指针一个一个节点遍历. 比如,对于一个数组,我们要读取第三个成员,我们仅需要arr[2]就能快速获取成员,而链表则需要从头部节点进入,在通过指针进入后续节点才能读取. 应用场景由于双向链表的存在,单向链表的应用场景比较少,因为很多场景双向链表可以更出色地完成. 但是单向链表并非无用武之地,在以下场景中依然会有单向链表的身影: 撤销功能,这种操作最多见于各种文本、图形编辑器中,撤销重做在编辑器场景下属于家常便饭,单向链表由于良好的删除特性在这个场景很适用实现图、hashMap等一些高级数据结构双向链表我们上文已经提到,单向链表的应用场景并不多,而真正在生产环境中被广泛运用的正是双向链表. 双向链表与单向链表相比有何特殊之处? 我们看到双向链表多了一个新的指针prev指向节点的前一个节点,当然由于多了一个指针,所以双向链表要更占内存. 别小看双向链表多了一个前置指针,在很多场景里由于多了这个指针,它的效率更高,也更加实用. 比如编辑器的「undo/redo」操作,双向链表就更加适用,由于拥有前后指针,用户可以自由得进行前后操作,如果这个是一个单向链表,那么用户需要遍历链表这时的时间复杂度是O(n). 真正生产级应用中的编辑器采用的数据结构和设计模式更加复杂,比如Word就是采用Piece Table数据结构加上Command queue模式实现「undo/redo」的,不过这是后话了.循环链表循环链表,顾名思义,他就是将单向链表的尾部指针指向了链表头节点: 循环链表一个应用场景就是操作系统的分时问题,比如有一台计算机,但是有多个用户使用,CPU要处理多个用户的请求很可能会出现抢占资源的情况,这个时候计算机会采取分时策略来保证每个用户的使用体验. 每个用户都可以看成循环链表上的节点,CPU会给每个节点分配一定的处理时间,在一定的处理时间后进入下一个节点,然后无限循环,这样可以保证每个用户的体验,不会出现一个用户抢占CPU而导致其他用户无法响应的情况. 当然,约瑟夫环的问题是单向循环链表的代表性应用,感兴趣的可以深入了解下. 当然如果是双向链表首尾相接呢?这就是双向循环链表. 在Node中有一类场景，没有查询，但是却有大量的插入和删除，这就是Timer模块。几乎所有的网络I/O请求，都会提供timeout操作控制socket的超时状况，这里就会大量使用到setTimeout，并且这些timeout定时器，绝大部分都是用不到的（数据按时正常响应），那么又会有响应的大量clearTimeout操作，因此node采用了双向循环链表来提高Timer模块的性能,至于其中的细节就不再赘述了. 插入！TimersList <-----> timer1 <-----> timer2 <-----> timer4 <-----> timer3 <-----> ...... 1000ms后执行 1050ms后执行 1100ms后执行 1200ms后执行小结至此,我们对链表这个数据结构有了一定的认知,由于其非连续内存的特性导致链表非常适用于频繁插入、删除的场景，而不见长于读取场景，这跟数组的特性恰好形成互补，所以现在也可以回到题目中的问题了，链表的特性与数组互补，各有所长，而且链表由于指针的存在可以形成环形链表，在特定场景也非常有用，因此链表的存在是很有必要的。 那么，现在有一个非常常见的一个面试向的思考题: 我们平时在用的微信小程序会有最近使用的功能,时间最近的在最上面,按照时间顺序往后排,当用过的小程序大于一定数量后,最不常用的小程序就不会出现了,你会如何设计这个算法?

又是来自我的好朋友 EvilSay 的投稿，以下是原文： 1、基本定义二分搜索树的每个子节点最多有两个叶子节点二分搜索树的每个节点最多有一个根节点存储的元素必须具有可比较性二分搜索树每个子节点的值 大于其左子节的所有节点的值小于其右子节点的所有节点的值二分搜索树不一定是满的2、二分搜索树 Java 实现/** * @Author: EvilSay * @Date: 2019/8/6 19:00 */public class BSTMain <E extends Comparable<E>> { private class Node { public E e; private Node left, right; public Node(E e) { this.e = e; left = null; right = null; } } //根节点 private Node root; private int size; public BSTMain() { root = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void add(E e){ root = add(this.root, e); } // 向node为根的二分搜索树中插入元素E,递归算法 // 返回插入新节点后二分搜索树的根 private Node add(Node node, E e){ if (node == null){ size ++; return new Node(e); } if (e.compareTo(node.e) < 0) node.left = add(node.left, e); else if (e.compareTo(node.e) > 0) node.right = add(node.right,e); return node; } // 看二分搜索树中是否包含元素e public boolean contains(E e){ return contains(root,e); } // 看以node为根的二分搜索树中是否包含元素e,递归算法 private boolean contains(Node node, E e){ if (node == null) return false; if (e.compareTo(node.e) == 0) return true; else if (e.compareTo(node.e) < 0) return contains(node.left, e); else return contains(node.right,e); } @Override public String toString() { StringBuilder res = new StringBuilder(); generateBSTSString(root,0,res); return res.toString(); } // 生成以node为根节点，深度为depth的描述二叉树的字符串 private void generateBSTSString(Node root, int depth, StringBuilder res) { if (root == null){ res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + root.e + "\n"); generateBSTSString(root.left, depth + 1 ,res); generateBSTSString(root.right, depth + 1, res); } private String generateDepthString(int depth) { StringBuilder res = new StringBuilder(); for (int i = 0; i < depth; i++) res.append("--"); return res.toString(); }}3、图解二分搜索树 ...

JavaScript中的算法（附10道面试常见算法题解决方法和思路）关注github每日一道面试题详解 Introduction面试过程通常从最初的电话面试开始，然后是现场面试，检查编程技能和文化契合度。几乎毫无例外，最终的决定因素是还是编码能力。通常上，不仅仅要求能得到正确的答案，更重要的是要有清晰的思维过程。写代码中就像在生活中一样，正确的答案并不总是清晰的，但是好的推理通常就足够了。有效推理的能力预示着学习、适应和进化的潜力。好的工程师一直是在成长的，好的公司总是在创新的。 算法挑战是有用的，因为解决它们的方法不止一种。这为决策的制定和决策的计算提供了可能性。在解决算法问题时，我们应该挑战自己从多个角度来看待问题的定义，然后权衡各种方法的优缺点。通过足够的尝试后，我们甚至可能看到一个普遍的真理:不存在“完美”的解决方案。 要真正掌握算法，就必须了解它们与数据结构的关系。数据结构和算法就像阴阳、水杯和水一样密不可分。没有杯子，水就不能被容纳。没有数据结构，我们就没有对象来应用逻辑。没有水，杯子是空的，没有营养。没有算法，对象就不能被转换或“消费”。 要了解和分析JavaScript中的数据结构，请看JavaScript中的数据结构 Primer在JavaScript中，算法只是一个函数，它将某个确定的数据结构输入转换为某个确定的数据结构输出。函数内部的逻辑决定了怎么转换。首先，输入和输出应该清楚地提前定义。这需要我们充分理解手上的问题，因为对问题的全面分析可以很自然地提出解决方案，而不需要编写任何代码。 一旦完全理解了问题，就可以开始对解决方案进行思考，需要那些变量？ 有几种循环？ 有那些JavaScript内置方法可以提供帮助？需要考虑那些边缘情况？复杂或者重复的逻辑会导致代码十分的难以阅读和理解，可以考虑能否提出抽象成多个函数？一个算法通常上需要可扩展的。随着输入size的增加，函数将如何执行? 是否应该有某种缓存机制吗? 通常上，需要牺牲内存优化(空间)来换取性能提升(时间)。 为了使问题更加具体，画图表！当解决方案的具体结构开始出现时，伪代码就可以开始了。为了给面试官留下深刻印象，请提前寻找重构和重用代码的机会。有时，行为相似的函数可以组合成一个更通用的函数，该函数接受一个额外的参数。其他时候，函数柯里的效果更好。保证函数功能的纯粹方便测试和维护也是非常重要的。换句话说，在做出解决问题的决策时需要考虑到架构和设计模式。 Big O（复杂度）为了计算出算法运行时的复杂性，我们需要将算法的输入大小外推到无穷大，从而近似得出算法的复杂度。最优算法有一个恒定的时间复杂度和空间复杂度。这意味着它不关心输入的数量增长多少，其次是对数时间复杂度或空间复杂度，然后是线性、二次和指数。最糟糕的是阶乘时间复杂度或空间复杂度。算法复杂度可用以下符号表示: Constabt: O(1)Logarithmic: O(log n)Linear: O(n)Linearithmic: O(n log n)Quadratic: O(n^2)Expontential: O(2^n)Factorial: O(n!) 在设计算法的结构和逻辑时，时间复杂度和空间复杂度的优化和权衡是一个重要的步骤。 Arrays一个最优的算法通常上会利用语言里固有的标准对象实现。可以说，在计算机科学中最重要的是数组。在JavaScript中，没有其他对象比数组拥有更多的实用方法。值得记住的数组方法有:sort、reverse、slice和splice。数组元素从第0个索引开始插入，所以最后一个元素的索引是 array.length-1。数组在push元素有很好的性能，但是在数组中间插入，删除和查找元素上性能却不是很优，JavaScript中的数组的大小是可以动态增长的。 数组的各种操作复杂度Push: O(1)Insert: O(n)Delet: O(n)Searching: O(n)Optimized Searching: O(log n)Map 和 Set是和数组相似的数据结构。set中的元素都是不重复的，在map中，每个Item由键和值组成。当然，对象也可以用来存储键值对，但是键必须是字符串。 Iterations与数组密切相关的是使用循环遍历它们。在JavaScript中,有5种最常用的遍历方法，使用最多的是for循环，for循环可以用任何顺序遍历数组的索引。如果无法确定迭代的次数，我们可以使用while和do while循环，直到满足某个条件。对于任何Object, 我们可以使用 for in 和 for of循环遍历它的keys 和values。为了同时获取key和value我们可以使用 entries()。我们也可以在任何时候使用break语句终止循环，或者使用continue语句跳出本次循环进入下一次循环。 原生数组提供了如下迭代方法：indexOf,lastIndexOf,includes,fill,join。 另外我们可以提供一个回调函数在如下方法中：findIndex,find,filter,forEach,map,some,every,reduce。 Recursions在一篇开创性的论文中，Church-Turing论文证明了任何迭代函数都可以用递归函数来复制，反之亦然。有时候，递归方法更简洁、更清晰、更优雅。以这个迭代阶乘函数为例: const factorial = number => { let product = 1 for (let i = 2; i <= number; i++) { product *= i } return product}如果使用递归，仅仅需要一行代码 ...

一、简介迪克斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，就像剥洋葱一样，所以它也属于广度优先搜索。 二、算法正确性证明老哥们自己找吧，网上没找到一篇能让我完全满意的证明 三、JAVA代码实现 public class Dijkstra { public static final int INF = 65535; public static final String RIGHT_ARROW = "-->"; public static final String LEFT_ARROW = "<--"; public static void main(String[] args) { getShortestDistance(new int[][]{ {0, INF, 10, INF, 30, 100}, {INF, 0, 5, INF, INF, INF}, {INF, INF, 0, 50, INF, INF}, {INF, INF, INF, 0, INF, 10}, {INF, INF, INF, 20, 0, 60}, {INF, INF, INF, INF, INF, 0} }, 0); } private static void getShortestDistance(int[][] matrix, int start) { boolean[] visited = new boolean[matrix.length]; // 节点是否已被访问 int[] distance = new int[matrix.length]; // 距离数组 int[] pre = new int[matrix.length]; // 前驱数组，用于记录路径信息 // 初始化距离数组、前驱数组，访问数组 for (int j = 0; j < matrix[start].length; j++) { distance[j] = matrix[start][j]; if (distance[j] == INF) { pre[j] = -1; } else { pre[j] = start; } visited[j] = false; } // 初始节点设置为已访问 visited[start] = true; int k = start; while (k != -1) { visited[k] = true; for (int j = 0; j < matrix[k].length; j++) { if (matrix[k][j] + distance[k] < distance[j]) { distance[j] = matrix[k][j] + distance[k]; pre[j] = k; } } // 获取下一个距离起始节点最近的未被访问的节点 k = getNextNodeIndex(visited, distance); } // 打印最短距离和路径 printShortestPath(distance, pre, start); } private static void printShortestPath(int[] distance, int[] pre, int start) { for (int i = 0; i < distance.length; i++) { StringBuilder sb = new StringBuilder(); sb.append(getNodeName(start)); sb.append(RIGHT_ARROW); sb.append(getNodeName(i)); if (distance[i] < INF) { sb.append("最短距离:"); sb.append(distance[i]); sb.append("\t"); } else { sb.append("不通"); continue; } sb.append("最短路径"); sb.append(getNodeName(i)); sb.append(LEFT_ARROW); int j = i; do { j = pre[j]; sb.append(getNodeName(j)); sb.append(LEFT_ARROW); } while (pre[j] != -1 && j != start); System.out.println(sb.substring(0, sb.lastIndexOf(LEFT_ARROW))); } } private static int getNextNodeIndex(boolean[] visited, int[] distance) { int min = INF; int k = -1; for (int i = 0; i < distance.length; i++) { if (distance[i] < min && !visited[i]) { min = distance[i]; k = i; } } return k; } private static String getNodeName(int nodeIdx) { return "v" + (nodeIdx + 1); }结果打印：v1-->v1最短距离:0 最短路径v1<--v1v1-->v3最短距离:10 最短路径v3<--v1v1-->v4最短距离:50 最短路径v4<--v5<--v1v1-->v5最短距离:30 最短路径v5<--v1v1-->v6最短距离:60 最短路径v6<--v4<--v5<--v1四、扩展我另外想了一种方法来实现寻找最短路径，类似迪克斯特拉算法，只不过将广度优先搜索变为深度优先搜索 ...

本文的源码在我的github，可以参考一下数组是数据结构中最简单，也是使用最广泛的一种。在原生的js中，数组给我们提供了很多方便的操作方法，比如push(), pop(), shift(), unshift()。但出于对数据结构的学习，我将不依赖这些方法，只是使用数组简单的存储元素功能，另外我会假定数组是定长数组。这样也方便我们计算相关的时间复杂度。另外我会使用TypeScript实现，主要是因为TypeScript的强类型控制，以及泛型这些高级特性。 先来看我们自己实现数组的实例属性以及构造函数，我们用capacity来表示数组的容量，在用户没有传入容量的情况下，会给数组一个默认的capacity。我会用size来表示当前数组中元素的个数。 class MyArray<T> { private data: Array<T>; private size: number = 0; constructor(capacity = 10) { this.data = new Array(capacity); }}1.在数组中插入元素在数组index位置插入元素是我们经常使用的一个操作，那我们就需要从之前数组中index位置开始，每个元素向后移动一个位置。以便给新插入的元素挪出index这个位置。在操作的末尾，我们需要维护一下数组的size。 public add(index: number, e: T) { if (index < 0 || index > this.size) { throw new Error('Add failed. Required index >= 0 and index <= size.'); } if (this.size === this.data.length) { this.resize(2 * this.data.length); } for (let i = this.size - 1; i >= index; i--) { this.data[i + 1] = this.data[i]; } this.data[index] = e; this.size++;} ...

[TOC] 题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 思路一：利用map统计每个数字出现的次数代码 import java.util.HashMap;import java.util.Map;public class Solution { public int MoreThanHalfNum_Solution(int [] array) { int num = 0; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); int len = array.length ; if(len == 0) return 0; for(int i = 0; i < len ;i++){ if(map.containsKey(array[i])){ int count = map.get(array[i]); ++count; map.put(array[i],count); }else{ map.put(array[i],1); } } for(Map.Entry<Integer,Integer> entry: map.entrySet()){ if(entry.getValue() > (len/2)){ num = entry.getKey(); } } return num; }}总结 ...

public class QuickSortTest { public static void main(String[] args) { int[] arr = {2,1,6,1,4}; quickSort(arr, 0, arr.length - 1); print(arr); } private static void print(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } private static void quickSort(int[] arr, int p, int r) { if (p < r) { int q = partition(arr, p, r); quickSort(arr, p, q - 1); quickSort(arr, q + 1, r); } } private static int partition(int[] arr, int pivot, int r) { int p = pivot + 1; int bigger = r; while (p <= bigger) { if (arr[p] <= arr[pivot]) { p++; } else { swap(arr, p, bigger); bigger--; } } //最后还要一次交换 swap(arr, pivot, bigger); return bigger; } private static void swap(int[] arr, int p, int bigger) { //交换元素 int t = arr[p]; arr[p] = arr[bigger]; arr[bigger] = t; }}

状态转移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i<k<j思路对于每一个k(i<k<j)，全部遍历下来之后，肯定会发生一次有效的比较 public class FloydTest { private static int[][] matrix; private static int[][] path; public static void main(String[] args) { initMatrixAndPath( new int[][]{ {0, 1, 8, 5}, {1, 0, 7, 6}, {8, 7, 0, 2}, {5, 6, 2, 0}} ); floyd(matrix, path); printShortDistance(); printShortDistanceDetail(); } private static void initMatrixAndPath(int[][] matrix) { FloydTest.matrix = matrix; FloydTest.path = new int[matrix.length][matrix.length]; for (int i = 0; i < FloydTest.matrix.length; i++) { for (int j = 0; j < FloydTest.matrix[i].length; j++) { path[i][j] = j; } } } private static void floyd(int[][] matrix, int[][] path) { for (int k = 0; k < matrix.length; k++) { for (int i = 0; i < matrix.length; i++) for (int j = 0; j < matrix.length; j++) { if (matrix[i][j] > matrix[i][k] + matrix[k][j]) { matrix[i][j] = matrix[i][k] + matrix[k][j]; path[i][j] = path[i][k]; } } } } private static String getNodeName(int nodeIndex) { return "v" + nodeIndex; } private static void printShortDistanceDetail() { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { int x = j; StringBuilder sb = new StringBuilder("最短路径[v" + i + ",v" + j + "]为:"); sb.append(getNodeName(x)); sb.append("<--"); while (path[i][j] != x) { x = path[i][x]; sb.append(getNodeName(path[i][x])); sb.append("<--"); } sb.append(getNodeName(i)); System.out.println(sb); } } } private static void printShortDistance() { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { System.out.println("v" + i + "到" + "v" + j + "最短路径为:" + matrix[i][j]); } } }}输出结果 ...

排序讲一组有顺序的元素按大小(只要定义可以返回true或false的比较关系，非一定数值比较)重新调整顺序。 归并排序归并排序是分而治之策略，每次把两个已经排序的数组按大小关系。算法实现采用了递归实现，依次将数组长度(1,2...n/4,n/2,n)内的元素排序合并。 算法实现void merge(long long int* arr, long long int* tmp, int left, int right, int rightEnd) { int i, leftEnd, num, tmpPos; leftEnd = right - 1; tmpPos = left; num = rightEnd - left + 1; while(left <= leftEnd && right <= rightEnd) { if (arr[left] <= arr[right]) { tmp[tmpPos++] = arr[left++]; } else { tmp[tmpPos++] = arr[right++]; } } while(left <= leftEnd) { tmp[tmpPos++] = arr[left++]; } while(right <= rightEnd) { tmp[tmpPos++] = arr[right++]; } for (i = 0; i < num; i++, rightEnd--) { arr[rightEnd] = tmp[rightEnd]; }}void mSort(long long int* arr, long long int* tmp, int left, int right, int len) { int center; int i; if (left < right) { center = (left + right) / 2; mSort(arr, tmp, left, center, len); mSort(arr, tmp, center + 1, right, len); merge(arr, tmp, left, center + 1, right); printf("合并参数：%d %d 结果：", left, right); for (i = 0; i < len; i++) { printf("%lld ", arr[i]); } printf("\n"); }}long long int* elrSortMerge(long long int* arr, int len) { long long int* tmp; tmp = malloc(len * sizeof(long long int)); if (tmp) { mSort(arr, tmp, 0, len - 1, len); free(tmp); } else { printf("no space for sort merge\n"); } return arr;}调试调用#include <stdio.h>#include <stdlib.h>#include "elr_sort_merge.h"int main(int argc, char **argv){ int i; long long int arr[] = {6, 2, 4, 1, 3, 5, 0, 8, 9, -1, 7}; elrSortMerge(arr, 11); printf("%d\n", (int)(sizeof(arr) / sizeof(long long int))); for (i = 0; i < 11; i++) { printf("%lld ", arr[i]); } printf("\n"); return 0;}输出合并参数：0 1 结果：2 6 4 1 3 5 0 8 9 -1 7 合并参数：0 2 结果：2 4 6 1 3 5 0 8 9 -1 7 合并参数：3 4 结果：2 4 6 1 3 5 0 8 9 -1 7 合并参数：3 5 结果：2 4 6 1 3 5 0 8 9 -1 7 合并参数：0 5 结果：1 2 3 4 5 6 0 8 9 -1 7 合并参数：6 7 结果：1 2 3 4 5 6 0 8 9 -1 7 合并参数：6 8 结果：1 2 3 4 5 6 0 8 9 -1 7 合并参数：9 10 结果：1 2 3 4 5 6 0 8 9 -1 7 合并参数：6 10 结果：1 2 3 4 5 6 -1 0 7 8 9 合并参数：0 10 结果：-1 0 1 2 3 4 5 6 7 8 9

时间复杂度冒泡排序public static void bubbleSort(int[] arr){ if(arr == null || arr.length < 2) return; for(int end = arr.length-1; end > 0; end--){ for(int i = 0; i < end; i++) if(arr[i] > arr[i+1]) swap(arr,i,i+1); } }选择排序public static void selectionSort(int[] arr){ if(arr == null || arr.length < 2) return; for(int i = 0; i < arr.length-1; i++){ int minIndex = i; for(int j = i+1; j < arr.length; j++) minIndex = arr[j] < arr[minIndex] ? j : minIndex; swap(arr, i, minIndex); } }插入排序public static void insertionSort(int[] arr){ if(arr == null || arr.length < 2) return; for(int i = 1; i < arr.length; i++) for(int j = i - 1;j >= 0 && arr[j] > arr[j + 1]; j--)//一次次往前交换 swap(arr, j, j + 1); }对数器随机产生器：产生随机数组准备一个绝对正确的方法：不需考虑时间复杂度，保证绝对正确即可实现比对的方法把方法a和方法b比对很多次来验证方法a是否正确如果有一个样本是的比对出错，打印样本分析是哪个方法出错当样本数量很多时比对测试依然正确，可以确定方法a已经正确以冒泡排序为例 ...

前言基础知识就像是一座大楼的地基，它决定了我们的技术高度。我们应该多掌握一些可移值的技术或者再过十几年应该都不会过时的技术，数据结构与算法就是其中之一。栈、队列、链表、堆 是数据结构与算法中的基础知识，是程序员的地基。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。 1. 线性表与非线性表线性表（Linear List）：就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组、链表、队列、栈 等就是线性表结构。 非线性表：数据之间并不是简单的前后关系。二叉树、堆、图 就是非线性表。 本文主要讲线性表，非线性表会在后面章节讲。 2. 数组 定义数组 (Array) 是一个有序的数据集合，我们可以通过数组名称 (name) 和索引 (index) 进行访问。数组的索引是从 0 开始的。特点数组是用一组连续的内存空间来存储的。所以数组支持 随机访问，根据下标随机访问的时间复杂度为 O(1)。 低效的插入和删除。数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效，因为底层通常是要进行大量的数据搬移来保持数据的连续性。插入与删除的时间复杂度如下：插入：从最好 O(1) ，最坏 O(n) ，平均 O(n)删除：从最好 O(1) ，最坏 O(n) ，平均 O(n) 注意但是因为 JavaScript 是弱类型的语言，弱类型则允许隐式类型转换。 隐式：是指源码中没有明显的类型转换代码。也就是说，一个变量，可以赋值字符串，也可以赋值数值。 let str = "string"str = 123 console.log(str) // 123你还可以直接让字符串类型的变量和数值类型的变量相加，虽然得出的最终结果未必是你想象的那样，但一定不会报错。 let a = 123let b = "456"let c = a + b// 数值加字符串，结果是字符串console.log(c) // "123456"数组的每一项可以是不同的类型，比如： ...

在互联网行业的算法面试中经常会被考到数据结构的知识，它与算法相辅相成，没有扎实的数据结构基础，学好算法几乎不太可能。 这里精心整理了 Google 资深工程师的学习笔记和解题技巧，总结出６大数据结构必考知识点，同时以力扣 LeetCode 经典题辅助讲解，帮助你更好的理解数据结构要点。 ** 一、数据结构、字符串** 数组和字符串是最基本的数据结构，在很多编程语言中都有着十分相似的性质，这部分的算法面试题也是最多的。 很多时候，在分析字符串相关面试题的过程中，要针对字符串当中的每一个字符进行分析和处理，甚至有时候需要先把给定的字符串转换成字符数组之后再进行分析和处理。举个最简单的例子：翻转一个字符串。 一种比较快速和直观的方法是用两个指针，一个指向字符串的第一个字符a，一个指向它的最后一个字符m，然后互相交换。交换之后，两个指针向中央一步步地靠拢并相互交换字符，直到两个指针相遇。由于无法直接修改字符串里的字符，所以必须先把字符串变换为数组，然后再运用这个算法。 采用数据的优缺点 ａ．优点： 构建一个数组非常简单； 能让我们在 O（1）的时间里根据数组的下标（index）查询某个元素。 ｂ．缺点： 构建时必须分配一段连续的空间； 查询某个元素是否存在时需要遍历整个数组，耗费Ｏ（ｎ）的时间（其中，ｎ是元素的个数）； 删除和添加某个元素时，同样需要耗费Ｏ（ｎ）的时间。 所以，在考虑是否应当采用数组去辅助所用算法时，务必需要考虑它的优缺点，看看它的缺点是否会阻碍所用算法的复杂度以及空间复杂度。 真题：力扣（LeetCode）第２４２题．Valid Anagram 判断两个字符串是否互为字谜 解题思路： 所谓字谜，也就是两个字符串中的相同字符的数量要对应相等。例如：ｓ　等于　“anagram”，ｔ等于　“nagaram”，ｓ和ｔ就互为字谜，因为它们都包含有三个字符ａ，一个字符ｇ，一个字符ｍ，一个字符ｎ以及一个字符ｒ。而当ｓ为“rat”，ｔ为　“car”的时候，ｓ和ｔ不互为字谜。 题目里有一个重要的前提：假设两个字符串只包含小写字母。小写字母一共26个，这意味着，可以利用两个个长度都为26的字符数组来统计每个字符串中小写字母出现的次数，然后再对比看看是否相等即可。 或者，也可以只利用一个长度为26的字符数组，将出现在字符串s里的字符个数加一，而出现在字符串t里的字符个数减一，最后判断每个小写字母的个数是否都为零就可以了。 二、链表链表的出现在某种程度上是为了避免数组的一大缺陷，即分配数组的时候需要开辟一段连续的内存空间，但鱼和熊掌不可兼得，链表也牺牲了数组的一些优点，链表不能通过下标进行快速查询。所以在考虑是否需要运用链表的时候，务必搞懂所用算法是否需要经常进行查询和遍历。 １．链表的优点和缺点 ａ．优点： 链表能灵活地分配内存空间 能在Ｏ（１）时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在Ｏ（１）时间内删除或者添加该元素。 ｂ．缺点： 查询第ｋ个元素需要Ｏ（ｋ）时间 很显然，如果要解决的问题里面需要很多快速的查询，链表可能并不适合。一般而言，如果数据的元素个数不确定，而且需要经常进行数据的添加和删除，那么链表会比较合适，而如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合。 ２．链表的经典解题方法 ａ．利用快慢指针（有时候需要用到三个指针）： 例如，链表的翻转，寻找倒数第ｋ个元素，或者寻找链表中间位置的元素，判断链表是否有环等等。 ｂ．构建一个虚假的链表头： 这个方法一般用在要返回新的链表的题目中，例如： 给定两个排好序的链表，要求将它们整合在一起并排好序 将一个链表中的奇数和偶数按照原定的顺序分开后重新组合成一个新的链表，链表的头一半是奇数，后一半是偶数。 在这类问题里，如果不用一个虚假的链表头，那么在创建新链表的第一个元素时，都虚要判断一下链表的头指针是否为空，也就是要多写一条if else语句，比较简洁的写法是创建一个空的链表头，直接往其后面添加元素即可，最后返回这个空的链表头的下一个节点即可。 另外，链表有单链表和双链表，它们是实现很多复杂数据结构的基础，在解决链表的题目时，建议在纸上或者白板上画出节点之间的相互关系，然后画出修改的方法，这样可以有效地分析问题，因为凭空想象是比较困难的，而且在面试的时候，如果能把方法画在白板上，还能帮助面试官清楚地看到你的思路。 真题：力扣（LeetCode）第２５题．Reverse Nodes in k-Group在链表中对每ｋ个节点所组成的部分进行翻转 这道题是力扣（LeetCode）第24题．Swap Node in Paris（在链表中每两个节点进行翻转）的扩展，在这道题里，当ｋ等于２时，第25题就变成了第24题。 ...

队列栈与一般线性表区别线性表抽象是存储具有先后顺序元素数据的结构，支持任意位置的插入，删除操作。队列和栈限制插入删除操作，队列只能从尾部插入，首部取出(删除)，既先入先出;栈限制插入和取出操作只能在尾部进行，既先入后出。 实现方式队列和栈同一般线性表相同，可用数组和链式结构体实现。由于限制了插入和取出的位置，没有频繁的中间元素操作，数组实现比链式实现效率更高。对应缺点为初始化时要定义数组大小，无法动态分配大小。 代码实现栈struct stack;typedef struct stack sStack;typedef sStack *pStack;#define EmptyTOS -1;struct stack { int capacity; int topOfStack; long long int *data;};pStack elrInitStackInt(int capaticy) { pStack s; s = malloc(sizeof(sStack)); if (s == NULL) { printf("out of space!"); } s->data = malloc(sizeof(long long int) * capaticy); if (s->data == NULL) { printf("out of space!"); } s->capacity = capaticy; elrMakeStackEmpty(s); return s;}void elrFreeStackInt(pStack stack) { if (stack != NULL) { free(stack->data); free(stack); }}int elrIsStackEmpty(pStack stack) { return stack->topOfStack == EmptyTOS;}int elrIsStackFull(pStack stack) { return stack->topOfStack == (stack->capacity - 1);}void elrMakeStackEmpty(pStack stack) { stack->topOfStack = EmptyTOS;}void elrPushStackInt(pStack stack, long long int data) { if (elrIsStackFull(stack)) { printf("full stack"); } else { stack->data[++stack->topOfStack] = data; }}long long int elrPopStackInt(pStack stack) { if (elrIsStackEmpty(stack)) { printf("empty stack"); } else { return stack->data[--stack->topOfStack]; }}队列struct queue;typedef struct queue sQueue;typedef sQueue *pQueue;struct queue { int capacity; int front; int rear; int size; long long int *data;};pQueue elrInitQueueInt(int capaticy) { pQueue s; s = malloc(sizeof(sQueue)); if (s == NULL) { printf("out of space!"); } s->data = malloc(sizeof(long long int) * capaticy); if (s->data == NULL) { printf("out of space!"); } s->capacity = capaticy; elrMakeQueueEmpty(s); return s;}void elrFreeQueueInt(pQueue queue) { if (queue != NULL) { free(queue->data); free(queue); }}int elrIsQueueEmpty(pQueue queue) { return queue->size == 0;}int elrIsQueueFull(pQueue queue) { return queue->size == queue->capacity;}void elrMakeQueueEmpty(pQueue queue) { queue->size = 0; queue->front = 1; queue->rear = 0;}int succ(pQueue queue, int value) { if (++value == queue->capacity) { value = 0; } return value;}void elrEnqueuekInt(pQueue queue, long long int data) { if (elrIsQueueFull(queue)) { printf("full queue"); } else { queue->size++; queue->rear = succ(queue, queue->rear); queue->data[queue->rear] = data; }}long long int elrDequeueInt(pQueue queue) { if (elrIsQueueEmpty(queue)) { printf("empty queue"); } else { queue->size--; int data = queue->data[queue->front]; queue->front = succ(queue, queue->front); }}

算法的学习是枯燥无味的，如何快速理解和提高学习的乐趣？理解复杂数据结构的最佳方法是看到它们的实际运行。 今天给大家推荐一个网址、它已经为各种数据结构和算法开发了交互式动画，这样有助于我们更直观的去理解和学习各种数据结构。 废话不多说了，直接上网址了 主页：https://www.cs.usfca.edu/ 算法： https://www.cs.usfca.edu/~galles/visualization/about.html 算法列表：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 希望对爱好算法的你有帮助谢谢。

哈希表定义及实现哈希表也叫散列表，是快速执行查找，删除，插入的技术，不支持元素排序信息。原理是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。关键码值到存储位置的映射被称为哈希函数也叫散列函数，当不同关键key被映射到同一value时，称为冲突。解决冲突主要有：分离链接法：对Hash表中每个Hash值建立一个冲突表，即将冲突的几个记录以表的形式存储在其中。开发定址法：根据冲突算法找到空的单元为止（线性探测法，平方探测法...）。 编程实例算法实现采用平方探测法的实现放在git@code.aliyun.com:c-program/projecteuler.git上projecteulerccommonstruct目录下elr_hash_int.h elr_hash_int.c两个单元内。 解决问题https://www.hackerrank.com/ch...要求用一个map结构存放名字name和电话phone。 定义结构#define MaxStr 20typedef unsigned long int Index;typedef Index Position;typedef char *KeyType;typedef long int *ValueType;struct HashTbl;typedef struct HashTbl *HashTable;enum KindOfEntry { Legitimate, Empty, Deleted };struct HashEntry { KeyType Key; ValueType Value; enum KindOfEntry Info;};typedef struct HashEntry Cell;struct HashTbl { long int TableSize; Cell *TheCells;};初始化及释放HashTable InitializeTable(long int TableSize) { HashTable H; long int i; H = malloc(sizeof(struct HashTbl)); if (H == NULL) { printf("Out of space!\n"); } H->TableSize = TableSize; H->TheCells = malloc(sizeof(Cell) * H->TableSize); if (H->TheCells == NULL) { printf("Out of space!\n"); } for (i = 0; i < H->TableSize; i++) { H->TheCells[i].Info = Empty; H->TheCells[i].Key = NULL; H->TheCells[i].Value = 0; } return H;}void DestroyTable(HashTable H) { int i; if (H == NULL) { return; } for (i = 0; i < H->TableSize; i++) { H->TheCells[i].Info = Empty; if (H->TheCells[i].Key != NULL) { free(H->TheCells[i].Key); } } free(H);}哈希及冲突插入操作Position Hash(KeyType Key, long int TableSize) { long int keyValue = 0; register unsigned char *p; for (p = (unsigned char *)Key; *p; p++) { keyValue = 31 * keyValue + *p; } return keyValue % TableSize;}int KeyEqual(KeyType a, KeyType b) { if ((a == NULL) || (b == NULL)) { return 1; } return strcmp(a, b) == 0 ? 0 : 1;}int Find(KeyType Key, HashTable H, Position *Pos) { Position CurrentPos; long int CollisionNum; int rst = 0; CollisionNum = 0; CurrentPos = Hash(Key, H->TableSize); while (1) { if (H->TheCells[CurrentPos].Info == Empty) break; if (KeyEqual(H->TheCells[CurrentPos].Key, Key) == 0) { rst = 1; break; } CurrentPos += (++CollisionNum << 1) - 1; if (CurrentPos >= H->TableSize) { CurrentPos -= H->TableSize; } } *Pos = CurrentPos; return rst;}void Insert(KeyType Key, ValueType Value, HashTable H) { Position Pos; int exist; exist = Find(Key, H, &Pos); H->TheCells[Pos].Info = Legitimate; if (!exist) { H->TheCells[Pos].Key = malloc(sizeof(char) * MaxStr); } strcpy(H->TheCells[Pos].Key, Key); H->TheCells[Pos].Value = Value;}调用解决问题#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>int main() { long int n = 0; scanf("%ld", &n); HashTable H = InitializeTable(n * 2); for (int i = 0; i < n; i++) { char name[20]; long int phone; scanf("%s %ld", name, &phone); Insert(name, phone, H); } for (int i = 0; i < n; i++) { char name[20]; Position Pos; int exist; scanf("%s", name); // while (() != '\n'); exist = Find(name, H, &Pos); if (exist == 1) { ValueType Value = H->TheCells[Pos].Value; printf("%s=%ld\n", name, Value); } else { printf("Not found\n"); } if (getchar() == EOF) break; } DestroyTable(H); return 0;}

线性表定义及实现线性表是最常用的数据结构，抽象上讲表是存储具有先后顺序元素数据的结构，实现上分为顺序表和链式表。顺序表一般采用C语言中数组实现，数组中存储数据，依靠数据索引确定先后顺序信息，物理上存储连续。根据C中数组的定义，移动，动态申请空间，复制等操作，可以想象顺序表在处理动态变化线性表上的缺点。链式表一般采用C语言中结构体struct实现，每个结构体节点除了存储数据，还存储元素先后顺序信息，物理上存储不连续；根据是否存储前置元素可分为单链表双链表等。插入，删除，移动等动态操作较为方便。 编程实例问题及解决思路projecteuler的Problem10求2000000以内所有素数的和，首先要找到2000000所有素数。判断一个是是否素数，如果采用比之小的数去除，则除法运行次数太多。所以建立一个素数链表，用该链表里的素数去除，判断是否素数；一旦是素数，插入或追加到该链表中，为判断后续数字做嫁衣。详细介绍：https://segmentfault.com/a/11... 代码实现结构定义struct intNode;typedef struct intNode sIntNode;typedef sIntNode *pIntNode;struct intNode{ long long int data; pIntNode next; pIntNode prv;};操作方法//初始化pIntNode elrInitListInt(long long int data){ pIntNode tmp = NULL; tmp = (pIntNode)malloc(sizeof(sIntNode)); tmp->data = data; tmp->prv = tmp->next = tmp; return tmp;}//释放void elrPushListInt(pIntNode pList, long long int data){ pIntNode tmp = NULL; tmp = (pIntNode)malloc(sizeof(sIntNode)); tmp->data = data; tmp->next = pList; tmp->prv = pList->prv; pList->prv->next = tmp; pList->prv = tmp;}//追加元素void elrFreeListInt(pIntNode pList){ pIntNode tmp; while (pList->prv != pList){ tmp = pList->prv; pList->prv = tmp->prv; tmp->prv->next = pList; free(tmp); } free(pList); pList = NULL;}素数全局变量初始化方法pIntNode globalPrime;int globalPrimeCount;long long int globalPrimeNum;void initGlobalPrime(){ globalPrime = elrInitListInt(2); elrPushListInt(globalPrime, 3); elrPushListInt(globalPrime, 5); globalPrimeNum = 0; globalPrimeCount = 3;}void freeGlobalPrime(){ elrFreeListInt(globalPrime); globalPrimeNum = 0; globalPrimeCount = 0; }判断是否素数//优化：//1.用链表的素数去除，减少除法运行次数,本质上应该就是Eratosthenes埃拉托斯特尼筛选法//2.采用6n+1,6n+5才可能是素数，减少运行次数 ...

一、写在前面算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？ 每个人都知道那就是学习、特别是算法没有任何捷径可走。 在这记录平时自己工作和生活中遇到的一些算法，以便来自己来温故。 今天去面试笔试题 斐波那契数列 实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。 二、简介*斐波那契数列（Fibonacci sequence）的定义： 斐波拉契数列是指这样的一组数据 0、1、1、2、3、5、8、13、21……这个数列其实很容易找到规律的从第三项开始每一项值都等于前两项之和（fn = f(n-1) + f(n-2)） 斐波那契数列又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。 算法基本概念很好理解，下面我们来看看用代码来实现下。 实现其实数学公式已经有了，F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2) 那我们就用递归来实现下 public class PrintFib { //建立一个函数，用于计算数列中的每一项 public static int fib(int num) { if(num <= 0 ){ return 0; } if(num == 1 || num == 2) { return 1; } //循环调用本函数 return fib(num - 2) + fib(num - 1); } //主函数（程序入口） public static void main(String[] args) { //建立一个for循环，用于打印第一个至第十个数字 for(int i = 1;i <= 10;i++) { //调用函数进行打印 System.out.print(fib(i) + "\t"); } } }实现很简单，结果我就不答应了， 感兴趣的同学可以自己试一下。 ...

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1:输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4输出: 2解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 说明:所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉搜索树中。 思路：二叉搜索树的定义为：对于树中的每个节点X，它的左子树的所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。这意味着二叉搜索树所有的元素可以用某种统一的方式排序。在这里只需要比较两个节点和根的值的大小，确定两个节点所在位置，如果两个节点分别在根的两边，那么可以肯定它们的最近公共祖先就是根节点，如果在同一侧就可以递归查找了。递归写法： # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if p.val > root.val < q.val: return self.lowestCommonAncestor(root.right, p, q) elif p.val < root.val > q.val: return self.lowestCommonAncestor(root.left, p, q) else: return root非递归写法： ...

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。 树被用来存储具有层级关系的数据，比如文件系统中的文件。 树还可以用来存储有序列表。 树的定义树是由一组以边连接的节点组成。公司的组织结构图就是一个树的例子。 组织结构图就是一种树一棵树最上面的节点成为根节点。如果一个节点下面连接着多个节点，那么该节点称为父节点，它下面的节点称为子节点。一个节点可以有0个，1个或者多个子节点。没有任何子节点的节点称为叶子节点。下图展示了一些树的术语。 沿着一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径。以特定的顺序访问树中所有的节点称为树的遍历。树可以分为几个层次，根节点是第0层，它的子节点是第1层，子节点的子节点是第2层，以此类推。树中任何一层的节点都可以看成是子树的根，该子树包含根节点的子节点，子节点的子节点等。我们定义树的层数就是树的深度。节点的高度：节点到叶子节点的最长路径（边树）。节点的深度：根节点到这个节点所经历的边的个数。节点的层数：节点的深度+1。节点的高度：根节点的高度。下面举个例子来看：每一个节点都有一个与之关联的值，该值有时被称为键。二叉树是一种特殊的树。它的子节点不超过2个。二叉树具有一些特殊的计算性质，使得在它之上的一些操作异常高效。 二叉树和二叉查找树一个父节点的两个子节点分别称为左节点和右节点。左节点包含一组特定的值，右节点包含一组特定的值。 下图展示了一颗二叉树：当考虑某种特殊的二叉树，比如二叉查找树时，确定子节点非常重要。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。这一特性使得查找的效率很高，对于数值和非数值的数据，比如单词和字符串，也是如此。我们来看下图中的树：编号2的二叉树中，叶子节点全在最底层，除了叶子节点以外的每个节点都有左右两个子节点，这种二叉树叫做满二叉树。编号3的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其它层的节点个数都达到最大，这种二叉树叫做完全二叉树。 实现二叉查找树（BST）定义 Node 对象。 function node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; function show() { return this.data; }}现在可以创建一个 BST 类来表示二叉查找树。我们让类只包含一个数据成员：一个表示二叉查找树根节点的 Node 对象。该类的构造函数将根节点初始化为 null ，以此创建一个空节点。 BST 首先要有一个 insert() 方法，用来向树中插入新节点。首先要创建一个 Node 对象，将数据传入该对象保存。其次，检查 BST 是否有根节点，如果没有，则这是棵新树，该节点就是根节点，这个方法到此也就结束了；否则，进入下一步。 如果待插入节点不是根节点，那么就准备遍历 BST ，找到插入的适当位置。该过程类似遍历链表。用一个节点保存当前节点，一层层地遍历 BST 。 进入 BST 以后，下一步就需要确定将该节点放在什么位置。找到正确的插入点时，会跳出循环。 查找正确的插入点的算法如下： 设根节点为当前节点；如果待插入的节点小于当前节点，则设新的当前节点为原节点的左节点；反之，执行第四步；如果当前节点的左节点为 null ，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环；设新的当前节点为原节点的右节点；如果当前节点的右节点为 null ，就将新的节点插入该位置，退出循环；反之，继续执行下一次循环。 function BST() { this.root = null; this.insert = insert; function insert(data) { var n = new Node(data, null, null); if(this.root == null) { this.root = n; }else { var currentNode = this.root; var parent; while(true) { parent = currentNode; if(data < currentNode.data) { currentNode = currentNode.left; if(currentNode == null) { parent.left = n; break; } }else { currentNode = currentNode.right; if(currentNode.data == null) { parent.right = n; break; } } } } } }另外一个写法，其实思路是一样的，但是上面的稍微简洁一些。（代码思路来自王争老师的《数据结构与算法之美 》） ...

leetCode第一题普通解决思路将数组变量两次，相加判断是否等于传过来的值，如果等于，返回下标自己写的代码，如果有错误请指出，谢谢 package com.leetcode.firstquestion.one;import java.util.Arrays;/** * @program: test * @description: 两数之和 给定一个整数数组 nums 和一个目标值 target， * 请你在该数组中找出和为目标值的那 * 两个 整数，并返回他们的数组下标。 * @author: Mr.Yang * @create: 2019-05-08 09:20 **/public class Solution { public int[] twoSum(int[] nums, int target) { int[] ints = new int[2]; int indexOne=0; int indexTwo=0; boolean flag=false; for(int x=0;x<nums.length;x++){ for(int y=x+1;y<nums.length;y++){ if((nums[x]+nums[y])==target){ indexOne=x; indexTwo=y; flag=true; break; } } if(flag){ break; } } ints[0]=indexOne; ints[1]=indexTwo; return ints; } public static void main(String[] args) { int[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9}; Solution solution = new Solution(); int[] ints1 = solution.twoSum(ints, 9); System.out.println(Arrays.toString(ints1)); }}网上流传思路，使用HashMap来处理将数组的遍历值当作key（为了存取好处理，所以将数组的遍历值当作key），索引当作value来存储。 ...

题目描述请输入字符串，最多输入4 个字符串，要求后输入的字符串排在前面，例如 输入：EricZ 输出：1=EricZ 输入：David 输出：1=David 2=EricZ 输入：Peter 输出：1=Peter 2=David 3=EricZ 输入：Alan 输出：1=Alan 2=Peter 3=David 4=EricZ 输入：Jane 输出：1=Jane 2=Alan 3=Peter 4=David 输入第一行为字符串个数m，接下来m行每行一个字符床，m不超过100，每个字符床长度不超过20。 输出输出m行，每行按照样例格式输出，注意用一个空格隔开。 样例输入5EricZDavidPeterAlanJane样例输出1=EricZ1=David 2=EricZ1=Peter 2=David 3=EricZ1=Alan 2=Peter 3=David 4=EricZ1=Jane 2=Alan 3=Peter 4=David思路：字符串数组逆序输出的问题，用二维字符数组表示一个字符串数组。注意点是只需要输出四个，输入第i（假设i大于4）个字符串后，一次输出的分别是s[i - 0],s[i-1],s[i-2],s[i-3]。按照题目要求的1=s[i - j]的格式输出。用变量first表示是否是第一个，若不是第一个，输出字符串之前要先输出一个空格。 下面是C语言代码。 #include<stdio.h>#include<string.h>int main(){ int n,first,index; char str[100][100]; while(scanf("%d",&n) != EOF){ for(int i = 0;i < n;i++){ scanf("%s",str[i]); first = 0; if(i < 3) index = i + 1; else index = 4; for(int j = 0;j < index;j++){ if(first) printf(" "); first = 1; printf("%d=%s",j+1,str[i-j]); } printf("\n"); } } return 0;}

1. HashMap中Node类:static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }重写hashCode，key和value的hashcode取异或。重写equals，当为同一个对象或是同一个key和同一个value都认为这两个对象相等。2.散列值的计算static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }与无符号右移的自己异或同时兼顾了hash高16位和低16位，让散列值更散。3. 关注 get(Object key)public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }可以看出，get()是拿着key的hash和key去找的值。在getNode()中先是一系列判断和赋值，然后通过下标找定位到key在table中的位置定位的方式：(n - 1) & hash，这样取出的值总是小于table长度n的。然后对比key是否相等，相等就返回，不相等则判断是否是红黑树存储结构，若是则在红黑树上查找。若不是则在链表结构上查找。4.核心put(K key, V value)public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //判断是否扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }首先调用了putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)，第一步做初始化工作。然后，定位到table没有冲突，则直接存到table上。若是冲突了，则判断key是否相等，若相等则，直接将旧德的Node覆盖。否则，继续判断头节点是否是TreeNode的实例，TreeNode是一个红黑树，若是，则直接在树中插入。如果不是红黑树，插到链表的尾部。在hashmap中有一个属性为TREEIFY_THRESHOLD，这是一个阈值，若数量超过它，链表会转化为红黑树，小于它则会换回链表。所以hashMap同时用到了数组，链表，红黑树这三种数据结构。每次新添一个节点都会判断是否需要扩容。5. 扩容机制resize()首先涉及三个成员变量: ...

莱文斯坦(Levenshtein)距离莱文斯坦距离可以解决字符串相似度的问题。在莱文斯坦距离中，对每一个字符都有三种操作:删除、添加、替换例如有s1和s2两个字符串，a和b是与之对应的保存s1和s2全部字符的数组，i/j是数组下标。莱文斯坦距离的含义，是求将a变成b(或者将b变成a)，所需要做的最小次数的变换。举个例子，字符串"kitten" 与“sitting” 的莱文斯坦距离是3，因为将kitten变为sitting，最少需要三次变换：第一步kitten -> sitten （字符k变成s）sitten -> sittin （字符e变成i）sittin -> sitting （ 在末尾插入字符g）python实现莱文斯坦距离的python模块在https://github.com/ztane/pyth…，py2和py3都支持。安装Levenshtein模块windows安装 1，pip 安装Levenshtein模块 pip install python-Levenshtein 具体安装过程中，需要C++ 14.0 以上版本支持。C++ 下载路径:https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads 2，源码安装 首先下载python_Levenshtein的源码:https://www.lfd.uci.edu/~gohlke/pythonlibs/#python-levenshtein 下载的时候，注意源码包的python版本与本机安装python版本一致；同时需要注意的是，系统的位数。 拿python_Levenshtein‑0.12.0‑cp36‑cp36m‑win_amd64.whl为例，cp36表示python版本是python3.6，amd64表示支持64位windows系统。 pip install python_Levenshtein‑0.12.0‑cp36‑cp36m‑win_amd64.whllinux安装 pip 安装Levenshtein模块 pip install python-Levenshtein计算两个字符串的相似度import Levenshteins3=‘kitten’s4=‘sitting’result=Levenshtein.ratio(s3,s4)print(‘s3:%s,s4:%s:similar:%s’ % (s3,s4,str(result)))#s3:kitten,s4:sitting:similar:0.6153846153846154案例计算两个字符串list的相似度import Levenshteinimport jiebaautohome=‘2009款 1.6L 自动G特别版’#current=‘花冠 2009款 1.6L 自动G特别版’current=‘2009款 自动G特别版 1.6L’autohome_jieba_gene=jieba.cut(autohome)current_jieba_gene=jieba.cut(current)l1 = list(autohome_jieba_gene)l2 = list(current_jieba_gene)listSimilar=Levenshtein.seqratio(l1,l2)print(’l1:%s,l2:%s,similar:%s’ %(repr(l1),repr(l2),str(listSimilar)))#l1:[‘2009’, ‘款’, ’ ‘, ‘1.6’, ‘L’, ’ ‘, ‘自动’, ‘G’, ‘特别版’],l2:[‘2009’, ‘款’, ’ ‘, ‘自动’, ‘G’, ‘特别版’, ’ ‘, ‘1.6’, ‘L’],similar:0.6666666666666666 ...

网址：https://algorithm-visualizer….进去之后的页面是程序员熟悉的码农风格：假设我想学习冒泡排序算法，在搜索栏里输入sort，在结果列表里选择bubble sort：点击之后，排序操作处于就绪状态，点击play开始：此时右边的JavaScript代码像我们平时单步调试一样逐行执行，同时每一步执行后排序的效果在屏幕正中实时显示：比单步调试更强大之处是，我们能随时回退到前面的执行结果，通过下图高亮的84/144这个柱状开关控制。144意思是这个排序全过程总共要进行144次单步执行，当前已经执行了84步。自动播放的速度也可以在下图所示的Speed开关控制。这是非波拉契数列的生成动画：二叉树的遍历动画：Dijkstra迪杰斯特拉算法最短路径算法：有了这个网站，算法学习从此不再枯燥。这个网站的源代码是完全开源的，如果你有新的算法想给全世界的编程爱好者展示，可以按照Readme.md里定义的规范，提交您的动画。https://github.com/algorithm-…截至2019年3月16日，已经有14000多个赞了，顺手去点一个吧。要获取更多Jerry的原创文章，请关注公众号"汪子熙":

前言本周讲解两个50多年前发明，但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 – 归并排序，几乎每个软件系统中都可以找到其中一个或两个的实现，并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法适应现代系统的实际应用的细节。Mergesort。我们研究 mergesort 算法，并证明它保证对 n 项的任何数组进行排序，最多只能进行 nlgn 次的比较。我们还考虑一个非递归的自下而上版本。我们证明，在最坏的情况下，任何基于比较的排序算法必须至少进行 ~nlgn 的比较。我们讨论对我们正在排序的对象使用不同的排序以及相关的稳定性概念。上一篇：基本数据类型下一篇：快速排序这章我们讨论归并排序，这是计算基础中的两个重要排序算法之一我们已经对一些算法有了科学全面的认知，这些算法被大量运用在系统排序和应用内排序超过50多年，我们之后所要看到的快速排序更是被在科学和工程中被誉为20世纪10大算法之一归并排序概貌所以归并排序到底是什么样的?基本计划流程：将阵列分成两半递归排序每一半合并两半它的思想其实很简单, 只要把数组一分为二, 然后再不断将小数组递归地一分为二下去, 经过一些排序再将它们合并起来, 这就是归并排序的大致思想, 这是人们在计算机上实现的最早的算法之一.(EDVAC 计算机是最早的通用型计算机之一, 冯诺依曼认为在他的 EDVAC 中需要一种排序算法, 于是他提出了归并排序, 因此他被公认为是归并排序之父)归并排序的核心就是“并”。所以要理解如何归并，先考虑一种抽象的“原位归并”。抽象合并演示目标 给定一个数组，它的前一半(a[lo]-[mid]) 和 后一半([mid + 1]-[hi]) 已是排好序的，我们所要做的就是将这两个子数组合并成一个大的排好序的数组看一个演示1.在排序之前我们需要一个辅助数组，用于记录数据，这是实现归并的最简单的方式2.首先将原数组中所有东西拷贝进辅助数组，之后我们就要以排好的顺序将它们拷贝回原数组这时我们需要三个下标：i 用于指向左边子数组；j 指向右边子数组；k指向原数组即排好序的数组。3.首先取 i 和 j 所指数字中取其中小的放入原数组k的位置，当一个被拿走之后，拿走位置的指针 (这次是 j) 和 k 递增4.同样取 i 和 j 中小的那个移向 k 的位置，再同时增加移动位置的指针(这次还是 j 和 k)以此类推。完整演示地址：在此这就是一种归并方式： 用了一个辅助数组，将它们移出来又排好序放回去。这就是归并部分的代码，完全依着之前的演示Java 实现public class Merge { private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {/** * assertion功能: 方便我们找出漏洞并且确定算法的正确 * 想确定a[lo] 到 a[mid] 和 a[mid+1] 到 a[hi] 是否已是排好序的 / assert isSorted(a, lo, mid); assert isSorted(a, mid + 1, hi); //拷贝所有东西进辅助数组 for (int k = lo; k <= hi; k++) aux[k] = a[k]; /* * 完成归并 * 初始化 i 在左半边的最左端 * j 在右半边最左端 * 指针 k 从 lo 开始 * 比较辅助数组中 i 和 j 谁更小，并将小的那个的值移向 k **/ int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { //如果 i 走到边界了，就只将 j 的值都移上去 if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } //最后再检查最终合并后的时候排好序 assert isSorted(a, lo, hi); } // 递归的 sort 方法 private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); merge(a, aux, lo, mid, hi); } // 对外提供接口中 sort 函数 public static void sort(Comparable[] a) { //创建辅助数组 Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length - 1); }}在这个简单的实现中传入了 Comparable 类型的原数组 a[] 和 辅助数组 aux[], 还有三个参数 lo, mid, and hi. lo指向的是两个将要合并的子数组的头部 mid指向前一个子数组的末端 所以我们的前提是lo到mid时排好的 从mid+1到hi也是排好的有了归并，排序中递归的就简单多了。sort() 在递归调用前先检查下标，然后像二分查找那样计算中点值。sort前半部分，再sort后半部分，然后merge对外提供接口中 sort 函数只接收一个参数，创建辅助数组的任务就交给这个 sort()这里关键在于不要将辅助数组在递归的 sort() 中创建, 因为那会多出许多额外的小数组的花费, 如果一个归并排序效率很低通常都是由这引起 这是一个很直接的实现方式。也是依据了我们看到多次的一个思想–分治法：即解决问题时将其一分为二，分别解决两个小问题，再将它们合并起来Assertion一般来说Java程序员，认为加入这些 assert 是有益的：1.帮助我们发现漏洞2.同时也提示了之间的代码的功能这个归并代码就是很好的例子，如此以代码的形式加入 assert 语句表明了接下来你想做什么，在代码最后加上 assert 语句表明了你做了什么。你不仅确定了代码的正确，也告诉阅读代码的人你所干的事情。Java 中 asset 语句接受一个 boolean 值。isSorted 函数前面已经写过了(请回复 – 基本排序)，如果排好序返回 true，反之返回 false. assert 在验证到没正确排序时会抛出异常.assert 可以在运行时禁用.这很有用因为你可以把 asset 语句一直放在代码中, 编程时供自己所需, 禁用后在最终上线程序中不会有额外代码。因此 assertion 默认是禁用的。出错的时候人们还可以启用assertion然后找到错误所在。java -ea MyProgram //启用 assertionsjava -da MyProgram //禁用 assertions(默认)所以平时最好像之前的例子那样加入assert语句，并且不让他们出现在产品代码中，而且不要用额外的参数来做检查。算法分析附录 ...

???? 内容速览 ????普通函数和箭头函数的this原始数据类型及其判断和转化方法深浅拷贝及实现JS事件模型常见的高阶函数????查看全部教程 / 阅读原文????普通函数和箭头函数的this还是一道经典题目，下面的这段代码的输出是什么？（为了方便解释，输出放在了注释中）function fn() { console.log(this); // 1. {a: 100} var arr = [1, 2, 3]; (function() { console.log(this); // 2. Window })(); // 普通 JS arr.map(function(item) { console.log(this); // 3. Window return item + 1; }); // 箭头函数 let brr = arr.map(item => { console.log(“es6”, this); // 4. {a: 100} return item + 1; });}fn.call({ a: 100 });其实诀窍很简单，常见的基本是3种情况：es5普通函数、es6的箭头函数以及通过bind改变过上下文返回的新函数。① es5普通函数：函数被直接调用，上下文一定是window函数作为对象属性被调用，例如：obj.foo()，上下文就是对象本身obj通过new调用，this绑定在返回的实例上② es6箭头函数： 它本身没有this，会沿着作用域向上寻找，直到global / window。请看下面的这段代码：function run() { const inner = () => { return () => { console.log(this.a) } } inner()()}run.bind({a: 1})() // Output: 1③ bind绑定上下文返回的新函数：就是被第一个bind绑定的上下文，而且bind对“箭头函数”无效。请看下面的这段代码：function run() { console.log(this.a)}run.bind({a: 1})() // output: 1// 多次bind，上下文由第一个bind的上下文决定run .bind({a: 2}) .bind({a: 1}) () // output: 2最后，再说说这几种方法的优先级：new > bind > 对象调用 > 直接调用至此，这道题目的输出就说可以解释明白了。原始数据类型和判断方法题目：JS中的原始数据类型？ECMAScript 中定义了 7 种原始类型：BooleanStringNumberNullUndefinedSymbol（新定义）BigInt（新定义）注意：原始类型不包含Object和Function题目：常用的判断方法？在进行判断的时候有typeof、instanceof。对于数组的判断，使用Array.isArray()：typeof：typeof基本都可以正确判断数据类型typeof null和typeof [1, 2, 3]均返回"object"ES6新增：typeof Symbol()返回"symbol"instanceof：专门用于实例和构造函数对应function Obj(value){ this.value = value; }let obj = new Obj(“test”);console.log(obj instanceof Obj); // output: true判断是否是数组：[1, 2, 3] instanceof Array Array.isArray()：ES6新增，用来判断是否是’Array’。Array.isArray({})返回false。原始类型转化当我们对一个“对象”进行数学运算操作时候，会涉及到对象 => 基础数据类型的转化问题。事实上，当一个对象执行例如加法操作的时候，如果它是原始类型，那么就不需要转换。否则，将遵循以下规则：调用实例的valueOf()方法，如果有返回的是基础类型，停止下面的过程；否则继续调用实例的toString()方法，如果有返回的是基础类型，停止下面的过程；否则继续都没返回原始类型，就会报错请看下面的测试代码：let a = { toString: function() { return ‘a’ }}let b = { valueOf: function() { return 100 }, toString: function() { return ‘b’ }}let c = Object.create(null) // 创建一个空对象console.log(a + ‘123’) // output: a123console.log(b + 1) // output: 101console.log(c + ‘123’) // 报错除了valueOf和toString，es6还提供了Symbol.toPrimitive供对象向原始类型转化，并且它的优先级最高！！稍微改造下上面的代码：let b = { valueOf: function() { return 100 }, toString: function() { return ‘b’ }, [Symbol.toPrimitive]: function() { return 10000 }}console.log(b + 1) // output: 10001最后，其实关于instanceof判断是否是某个对象的实例，es6也提供了Symbol.hasInstance接口，代码如下：class Even { static Symbol.hasInstance { return Number(num) % 2 === 0; }}const Odd = { Symbol.hasInstance { return Number(num) % 2 !== 0; }};console.log(1 instanceof Even); // output: falseconsole.log(1 instanceof Odd); // output: true深拷贝和浅拷贝题目：实现对象的深拷贝。在JS中，函数和对象都是浅拷贝（地址引用）；其他的，例如布尔值、数字等基础数据类型都是深拷贝（值引用）。值得提醒的是，ES6的Object.assign()和ES7的…解构运算符都是“浅拷贝”。实现深拷贝还是需要自己手动撸“轮子”或者借助第三方库（例如lodash）：手动做一个“完美”的深拷贝函数：https://godbmw.com/passages/2019-03-18-interview-js-code/借助第三方库：jq的extend(true, result, src1, src2[ ,src3])、lodash的cloneDeep(src)JSON.parse(JSON.stringify(src))：这种方法有局限性，如果属性值是函数或者一个类的实例的时候，无法正确拷贝借助HTML5的MessageChannel：这种方法有局限性，当属性值是函数的时候，会报错<script> function deepClone(obj) { return new Promise(resolve => { const {port1, port2} = new MessageChannel(); port2.onmessage = ev => resolve(ev.data); port1.postMessage(obj); }); } const obj = { a: 1, b: { c: [1, 2], d: ‘() => {}’ } }; deepClone(obj) .then(obj2 => { obj2.b.c[0] = 100; console.log(obj.b.c); // output: [1, 2] console.log(obj2.b.c); // output: [100, 2] })</script>JS事件流事件冒泡和事件捕获事件流分为：冒泡和捕获，顺序是先捕获再冒泡。事件冒泡：子元素的触发事件会一直向父节点传递，一直到根结点停止。此过程中，可以在每个节点捕捉到相关事件。可以通过stopPropagation方法终止冒泡。事件捕获：和“事件冒泡”相反，从根节点开始执行，一直向子节点传递，直到目标节点。addEventListener给出了第三个参数同时支持冒泡与捕获：默认是false，事件冒泡；设置为true时，是事件捕获。<div id=“app” style=“width: 100vw; background: red;"> <span id=“btn”>点我</span></div><script> // 事件捕获：先输出 “外层click事件触发”; 再输出 “内层click事件触发” var useCapture = true; var btn = document.getElementById(“btn”); btn.addEventListener( “click”, function() { console.log(“内层click事件触发”); }, useCapture ); var app = document.getElementById(“app”); app.onclick = function() { console.log(“外层click事件触发”); };</script>DOM0级 和 DOM2级DOM2级：前面说的addEventListener，它定义了DOM事件流，捕获 + 冒泡。DOM0级：直接在html标签内绑定on事件在JS中绑定on系列事件注意：现在通用DOM2级事件，优点如下：可以绑定 / 卸载事件支持事件流冒泡 + 捕获：相当于每个节点同一个事件，至少2次处理机会同一类事件，可以绑定多个函数常见的高阶函数没什么好说的，跑一下下面的代码就可以理解了：// map: 生成一个新数组，遍历原数组，// 将每个元素拿出来做一些变换然后放入到新的数组中let newArr = [1, 2, 3].map(item => item * 2);console.log(New array is ${newArr});// filter: 数组过滤, 根据返回的boolean// 决定是否添加到数组中let newArr2 = [1, 2, 4, 6].filter(item => item !== 6);console.log(New array2 is ${newArr2});// reduce: 结果汇总为单个返回值// acc: 累计值; current: 当前itemlet arr = [1, 2, 3];const sum = arr.reduce((acc, current) => acc + current);const sum2 = arr.reduce((acc, current) => acc + current, 100);console.log(sum); // 6console.log(sum2); // 106更多系列文章⭐在GitHub上收藏/订阅⭐《前端知识体系》JavaScript基础知识梳理(上)JavaScript基础知识梳理(下)谈谈promise/async/await的执行顺序与V8引擎的BUG前端面试中常考的源码实现Flex上手与实战……《设计模式手册》单例模式策略模式代理模式迭代器模式订阅-发布模式桥接模式备忘录模式模板模式……《Webpack4渐进式教程》webpack4 系列教程(二): 编译 ES6webpack4 系列教程(三): 多页面解决方案–提取公共代码webpack4 系列教程(四): 单页面解决方案–代码分割和懒加载webpack4 系列教程(五): 处理 CSSwebpack4 系列教程(八): JS Tree Shakingwebpack4 系列教程(十二)：处理第三方 JavaScript 库webpack4 系列教程(十五)：开发模式与 webpack-dev-server……⭐在GitHub上收藏/订阅⭐ ...

前言增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。1. 跳表的样儿2. 跳表具有如下性质：1.由很多层结构组成2.每一层都是一个有序的链表3.最底层(第一层)的链表包含所有元素4.如果一个元素出现在 第 i 层 的链表中，则它在第 i 层 之下的链表也都会出现。5.每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。3. 来一个栗子,你将豁然开朗栗子：查找元素 61.头指针最开始在第一层最小值INT_MIN处2.于是和旁边的1比较,当然了1大嘛,于是指针移向13.再和当前层4比较， 比 4 大，跳到44.与7比较,比7小,于是向下跳到第二层45..与5比较,比5大,跳到56.与7比较,比7小,跳到最低层57.只能依次向后比较了,于是找到了64. 笔者的Java实现,慢慢看,很清晰1.节点定义,共三个成员变量:value,right,downpackage crabapple;/* * Copyright (c) This is zhaoxubin’s Java program. * Copyright belongs to the crabapple organization. * The crabapple organization has all rights to this program. * No individual or organization can refer to or reproduce this program without permission. * If you need to reprint or quote, please post it to zhaoxubin2016@live.com. * You will get a reply within a week, * /import java.util.Random;/* * 节点类定义 /class Node { //值 public int value = 0; //当前层下一个节点 public Node right; //下一层,直连的节点 public Node down; //构造函数 public Node() { } public Node(int value) { this.value = value; }}2.跳表类 定义,大家可以清晰的看请代码逻辑结构,该类只暴露insert()和search()两个方法,其它变量及方法均设为私有./* * 跳表定义 /public class SkipTable { //表层数 private int levelCount; //表的头指针 private Node firstNode; //初始化:层数为1,共前后两个节点,一个最小值,一个最大值 private void init() { levelCount = 1; firstNode=new Node(); firstNode.value = Integer.MIN_VALUE; firstNode.right = new Node(Integer.MAX_VALUE); } public SkipTable() { init(); } /* * 查找值 * @param value * @return / public boolean search(int value) { Node current = firstNode; return toSearch(current, value); } private boolean toSearch(Node node, int value) { if (node.value == value) return true; else if (node.right!=null&&value >= node.right.value) return toSearch(node.right, value); else if (node.down != null) return toSearch(node.down, value); return false; } /* * 插入值 * @param value * @return / public boolean insert(int value) { //判断是否有这个元素 if (search(value)) return false; //随机获取一个层数 int willLevel = updateLevelCount(); //判断是否添加新层 if (willLevel > levelCount) { Node newFirstNode = new Node(); addLevel(firstNode, newFirstNode); firstNode=newFirstNode; levelCount = willLevel; } //插入新元素 Node port = firstNode; int skipLevel = levelCount - willLevel; //迭代到指定层 while ((skipLevel–) > 0) port = port.down; //上下层新节点的桥梁 Node insertNode = null; while (port != null) { //获取当前层第一个节点指针 Node curPort = port; //迭代到右边的节点值比自己大为止 while (port.right.value < value) port = port.right; //准备插入的新节点 Node curInNode = new Node(value); //更新当前节点和前节点指针指向 curInNode.right = port.right; port.right = curInNode; //将当前节点引用给上层节点 if (insertNode != null) insertNode.down = curInNode; //将新插入的节点指针更新到insertNode,以备在下一层建立指向 insertNode = curInNode; //行头指针向下迭代 port = port.down; } return true; } /* * 添加新层 * * @param oldFirst * @param newFirst / private void addLevel(Node oldFirst, Node newFirst) { newFirst.value = oldFirst.value; newFirst.down = oldFirst; if (oldFirst.right != null) { Node newRightNode = new Node(); newFirst.right = newRightNode; addLevel(oldFirst.right, newRightNode); } } /* * 以一定概率使得获取一个和老层数差值不超过1的新层数 * @return / private int updateLevelCount() { Random random=new Random(); int v = random.nextInt(10); return v ==0 ? random.nextInt(levelCount) + 2 : random.nextInt(levelCount)+1 ; }}3.测试类package crabapple;public class Main { public static void main(String[] args) { //测试 SkipTable skipTable=new SkipTable(); skipTable.insert(1); skipTable.insert(2); skipTable.insert(3); skipTable.insert(4); skipTable.insert(5); skipTable.insert(6); skipTable.insert(7); skipTable.insert(8); skipTable.insert(9); skipTable.insert(10); //边界值测试 System.out.println(skipTable.search(0)); System.out.println(skipTable.search(1)); System.out.println(skipTable.search(2)); System.out.println(skipTable.search(5)); System.out.println(skipTable.search(9)); System.out.println(skipTable.search(10)); System.out.println(skipTable.search(11)); }}//output:/* * false * true * true * true * true * true * false * * Process finished with exit code 0 */结语上面的代码,大家是可以直接运行,笔者能力有限,代码也许还有不足,望大家多多指教. ...

删除重复节点，只保留一个示例：Input: 1->1->2Output: 1->2代码：ListNode* deleteDuplicates(ListNode* head) { ListNode pre = head, cur = head; while (cur) { if (pre->val != cur->val) { pre->next = cur; pre = pre->next; } cur = cur->next; } if (pre) pre->next = nullptr; return head;}2. 删除全部重复节点示例：Input: 1->2->3->3->4->4->5Output: 1->2->5代码：ListNode deleteDuplicates(ListNode head) { ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *pre = dummy, *cur = head; while (cur) { while (cur->next && cur->next->val == cur->val) cur = cur->next; if (pre->next == cur) pre = cur; else pre->next = cur->next; cur = cur->next; } return dummy->next; //不能直接返回 head，因为 head 有可能被删除}

前言如果能够科学上网，英文水平良好，建议登入cousera进行学习。平台上有完整的作业提交平台，对提交的作业有详细的性能诊断和反馈；有课程各种资源；有课程讨论。在课程提问区提问还会收到导师的回答。链接：Algorithms, Part IAlgorithms, Part II《算法》第四版：testbook链接(英文)：https://algs4.cs.princeton.ed…主要内容并查集是一种树形的数据结构，通过这种数据结构能够有效处理不相交集合间的合并(union)及查询(find)问题。比如动态连通性问题。这种数据结构主要涉及两个操作：Find：查询元素属于哪一个子集。此操作还可以用来确定两个元素是否属于同一子集。Union：将两个子集合并成到一个集合中。1. 动态连通性问题(dynamic connectivity)动态连通性的应用很广泛：比如网络诊断：网络中的两台计算机是否连通，社交网络中的两个人是否存在交集，芯片中的电路元件连通性等等。场景：对象数码照片：像素网络：计算机社交网络：人…在编程中我们会对所有这些不同类型的对象进行简单的编号（0 – N-1），这样方便利用整数作为数组的索引号，快速地访问每个对象的相关信息，还可以忽略与并查集问题不相关的很多细节。1.1 建立问题模型给定一个有N个性质相同的对象的集合问题大体上所需要的基本操作：连通（Union）：两个对象间可以连通连通性的查询（Find/connected）：查询两个对象之间是否有连通路径如下图，通过Union(x,y)命令给若干对象之间建立连通路径；通过connected(x,y)命令查看两个对象是否连通。我们的任务就是对于给定的对象集合高效地实现这两个命令。因为合并命令和连通命令交叉混合，所以我们还有一个任务是我们的解决方案能支持大量对象和大量混合操作的高效处理。1.2 提取连通性质的抽象性1.2.1 假设“连接到（is connected to）”是一个具有下边关系性质的等价关系：那么它会有如下一些性质：反身：每个对象都能连接到自己 （p is connected to p）对称：如果p与q连通，那么q也与p连通传递：如果p与q连通，q与r连通，那么p与r连通这些性质都是直观自然的。明确了这些等价关系后，下面给出“连通分量”的定义。1.2.2 连通分量（connected components）有了等价关系后，一个对象和链接的集合就分裂为子集，这些子集就为连通分量。连通分量是互相连接对象的最大集合，并且连通分量之间并不连通。如下图左边，有3个连通分量。我们的算法通过维护连通分量来获得效率，并使用连通分量来高效地应答接收的请求。有了连通分量的概念后，并查集（即动态联通问题）要实现的操作有:Find 查找: 查找检查两个对象是否在相同的连通分量中Union 合并命令：将包含两个对象的连通分量合并为一个子集（一个连通分量）。如下图。1.3 Union-find 数据类型（API)从之前的讨论我们得到了一个数据类型，在编程的概念中，它是为了解决问题我们想要实现的方法和规范。在Java的模型中，创建一个类来表示这些方法和规范。其中包含：构造函数：参数是对象的数量，根据对象的数量建立数据结构两个操作：a) 实现合并； b) 连接超找，返回一个布尔值（逻辑变量：真/假）在实现算法的过程中，应该明确算法在以下的情况下也必须高效：对象和操作的数量都可能是巨大的合并和连接的混合操作也会非常频繁在处理更深层的问题之前，通过设计一个测试客户端用于检查API，确保任何一种实现都执行了我们希望他执行的操作。如下图，客户端从标准输入（tinyUF）中读取信息。首先读取“10”这个整数，表示要处理的对象的数量，并创建一个UF对象。然后只要标准输入中还有输入，客户端将从输入读取两个整数，如果他们没有连通，将他们连通并输出。否则忽略这条输入。2. 实现动态连通性问题的算法也可以说就是实现并查集的算法。这些算法的目的并不是给出两个对象的连通路径是什么，而是回答是否存在这么一条路径。虽然给出两个对象相连的路径也回答了是否连通的问题，但是于我们的目的而言不是直接契合，效率也不高。使用并查集数据结构是一个不错的策略。实现动态连通性问题的算法有：quick-find 快速查找 （QF）quick-union 快速合并 （QU）Weighted quick-union 加权优化 （WQU）Quick union with path compression 路径压缩优化（QUPC）两种优化可以结合一起使用，以下简称"WQUPC",即 weighted QU + path compression2.1 quick-find快速查找算法也称为“贪心算法”。（简单来说贪心算法就是在对问题求解时总是作出当前看来是最好的选择，只得出在某种意义上的局部最优解，不一定能得到整体最优解）2.1.1 Qinck-find 简介Qinck-find数据结构：简单的对象索引整数数组 id[](size = n)(具体来说就是当且仅当两个对象 p 与 q 是在数组中的id一样，那么他们即为连通)如图：0,5,6在一个连通分量；1,2,7在一个连通分量；3,4,8,9连通由此：Find：检查 p 和 q 是否 id 值相等Union：合并两个给定对象的的两个连通分量，即需要将与给定对象之一（p）有相同 id 的所有对象的 id 值都变为另一个给定对象（q）的 id 值如图经过 union(6,1), 通过合并6和1,6所在的连通分量中的所有对象（0,5,6）的id值都变为1的 id 值（1）这个算法的主要问题是当进行合并操作是，遇往后，需要改变id值的操作就越多。2.1.2 Java实现：a) 构造器：建立一个私有化整数数组，并将对应索引的数组项设为索引值b) 连通判断：两个数组项的 id 值是否相等c) 合并操作：取出两个参数的 id 值，遍历整个数组，找到同第一个参数id值相同的所以id项，并将他们都赋值成第二个参数的id值。具体代码实现：QuickFindUF.java2.1.3 性能分析衡量因子：代码需要访问数组的次数增长量级构造函数初始化和合并操作时都需要遍历整个数组，所以他们必须以常数正比于N次访问数组（增长量级为N）查找的操作很快，只需要进行常数次比较（增长量级为1）算法的特点是查找很快，但是合并的代价太大，如果需要在N个对象上进行N次合并操作，访问数组就需要N的平方次增长量级的操作，这是不合理的。平方量级的时间太慢。对于大型问题不能接受平方时间的算法。随着计算机变得更快，平方时间算法实际会变得更慢，简单来说，假如计算机每秒能进行几十亿次的操作，这些计算机的主内存中有几十亿项，大约一秒钟的时间我们就可以访问主内存所有的项，现在希望算法对几十亿的对象进行几十亿的操作，快速查找算法需要访问数组大约10的18次方次，大概是30多年的计算时间。2.2 quick-union快速查找对于处理巨大问题太慢，所以第一个尝试是使用快速合并算法进行替换。快速合并的算法设计采用了所谓的“懒策略”，即尽量避免计算直到不得不进行计算。2.2.1 Quick-union简介Quick-union数据结构大小为N的整数数组 id[]（size = N）这里的数组看做是一片森林（即一组树的集合），数组中的每一项包含它在树中的父节点。下图可以看出3的父节点是4, 4的父结点是9，9的父节点是它自身，也就是9是这颗树的父节点。从某个对象出发，一路从父节点向上就能找到根节点。由此：Find：查找两个对象（p & q）的根节点是否相等Union：合并两个对象的连通分量，即把 p 的根节点的值设为 q 的根节点的值。如图， union(3,5) 即把3的根节点(9)的id值设为5的根节点(6)的id值。由此，3所在的连通分量与5所在的连通分量进行了合并。可以看出合并两个连通分量只需要改数组中的一个值，但查找根节点会需要多一些操作。2.2.2 Java实现：a) 构造器与Quick-find相同b) 私有方法root()通过回溯实现寻找根节点c) 通过私有方法实现查找操作（是否连通操作）。通过判断两个对象的根节点是否相同即得出返回d) 合并操作就是找到两个对象的根节点，并将第一个根节点的id值设为第二个对象根节点的id值详细实现：QuickUnionUF.java2.2.3 性能分析：衡量因子：代码需要访问数组的次数增长量级快速合并的算法依旧很慢。快速查找的缺点在于树可能太高，这样对于查找操作的代价太大，最坏的情况需要N次数组访问才能找到某个对象的根节点。（合并操作的统计也包含了查找跟的操作）3 quick-union算法改进3.1 加权QF 和 QU 都不能支持巨大的动态连通性问题，一种有效的改进办法：加权 Weighted quick-union之前说到了 QU 的缺点就是因为树太高会引起查找操作代价巨大，那么在实现QU算法的时候执行一些操作避免得到很高的树就是改进的一个思路。QU算法在合并两颗树的时候可能会把大树放在小树的下边，如此树会变高。为了避免合并后导致更高的树，让小树的根节点指向大树的根节点。由此保证所有的对象不会离根节点太远。可以通过加权的方式可以实现。WQU:跟踪每棵树中对象的个数将小树（对象所在的连通分量里的元素个数较少一方）的根节点设为大树的根节点的子节点Java 实现数据结构在QU的基础上添加一个额外的数组 size[i] 记录以该对象为根节点的树中的对象个数Find: 同QU一样，只需要检查根节点是否相同Union：通过 size[i] 先检查两颗树的大小，然后将小树的根节点设为大树的根节点，同时更新合并后连通分量中根节点项的size数组项的值完整实现：WeightedQuickUnionUF.java性能分析运行时间Find：与结点在树中的运行时间成正比Union：给出根节点后花费常量时间命题树中任意结点的深度上限为lgN(此lg以2为底数)证明理解这个命题的关键在于观察节点（此为X节点）的深度到底是在何时会增加a) 只有当T2的尺寸>=T1的尺寸的时候，T1和T2才会合并为一个连通分量，此时T1的深度（depth）才会增加b) 合并后T1的大小至少是原来的2倍，由此粗略估计，x的深度每增加1，则x所在的集合的大小变为原来的2倍c) 如果整个集合的大小为N，那么x所在的集合大小最大尺寸只能为N，那么从x=1开始，有12^depth=N –> depth = lgN 即树中任意节点的深度最多为lgN三种算法的性能对比如果N是100万，则lgN=20；如果N是10亿，lgN=30。加权的处理在代码上并不需要多少的修改，可是性能上却取得了很大的提升。3.2 路径压缩在经过加权处理后，还可以更进一步优化这个算法。此为添加路径压缩 Quick union with path compression 的操作。在试图寻找包含给定节点的树的根节点时，我们需要访问从该节点到根节点路径上的每个节点。那么，于此同时我们可以将访问到的所有节点的根节点顺便移动设置为他所在的树的根节点。 这需要付出常数的额外代价。如图：当我们找到P的根节点后，把9,6,3的根节点都设为0（1的根节点已经是树的根节点）：变为 这里做的改变是：将路径上的每个节点指向它在路径上的祖父节点，这种实现并没有把树完全展平，但在实际应用中两种方式都超不多一样好。将树完全展平：find(int p) 方法回溯一次路径找到根节点，然后再回溯一次将树展平，参考：QuickUnionPathCompressionUF.java性能分析以证明：有N个对象，M个合并与查找操作的任意序列，需要访问数组最多为 c( N + M lg N )次。lgN 是使N变为1所需要的对数的次数，叫迭代对数函数。在真实世界中可以认为lgN是一个小于5的数。这个证明可以不用深究，两种优化的代码实现参考：WeightedQuickUnionPathCompressionUF.java通过WQUPC的优化，之前的例子，假如要对10亿个对象进行10亿个操作，QF需要30年，现在只需要大概6秒。课后巩固（折日更新）Interview Questions 面试问题Programming Assignment: Percolation 编程练习IDE本人使用IntelliJ IDEA, jdk8需要使用的jar包：git地址： ...

识别手写的阿拉伯数字，对于人类来说十分简单，但是对于程序来说还是有些复杂的。不过随着机器学习技术的普及，使用10几行代码，实现一个能够识别手写数字的程序，并不是一件难事。这是因为有太多的机器学习模型可以拿来直接用，比如tensorflow、caffe，在python下都有现成的安装包，写一个识别数字的程序，10几行代码足够了。然而我想做的，是不借助任何第三方的库，从零开始，完全自己实现一个这样的程序。之所以这么做，是因为自己动手实现，才能深入了解机器学习的原理。1 模型实现1.1 原理熟悉神经网络回归算法的，可以略过这一节了。学习了一些基本概念，决定使用回归算法。首先下载了著名的MNIST数据集，这个数据集有60000个训练样本，和10000个测试样本。每个数字图片都是2828的灰度图片，所以输入可以认为是一个2828的矩阵，也可以认为是一个2828=784个像素值。这里定义一个模型用于判断一个图片数字，每个模型包括每个输入的权重，加一个截距，最后再做个归一。模型的表达式：Out5= sigmoid(X0W0+ X1W1+……X783W783+bias)X0到X783是784个输入，W0到W783是784个权重，bias是一个常量。sigmoid函数可以将较大范围的数挤压到(0,1)区间内，也就是归一。例如我们用这一组权重和bias来判断数字5，期望当图片是5时输出是1，当不是5时输出是0。然后训练的过程就是根据每个样本的输入，计算Out5的值和正确值（0或1）的差距，然后根据这个差距，调整权重和bias。转换一下公式，就是在努力使得（Out5-正确值）接近于0，即所谓损失最小。同理，10个数字就要有10套模型，每个判断不同的数字。训练好以后，一个图片来了，用这10套模型进行计算，哪个模型计算的结果更接近于1，就认为这个图片是哪个数字。1.2 训练按照上面的思路，使用集算器的SPL（结构化处理语言）来编码实现：不用再找了，训练模型的所有代码都在这里了，没有用到任何第三方库，下面解析一下：A1，用游标导入MNIST训练样本，这个是我转换过的格式，可以被集算器直接访问；A2，定义变量：输入x，权重wei，训练速度v，等；A3，B3，初始化10组模型（每组是784个权重+1个bias）；A4，循环取5万个样本进行训练，10模型同时训练；B4，取出来label，即这个图片是几；B5，计算正确的10个输出，保存到变量y；B6，取出来这个图片的2828个像素点作为输入，C6把每个输入除以255，这是为了归一化；B7，计算X0W0+ X1W1+……X783W783+biasB8，计算sigmoid(B7)B9，计算B8的偏导，或者叫梯度；B10，C10，根据B9的值，循环调整10个模型的参数；A11，训练完毕，把模型保存到文件。1.3 测试测试一下这个模型的成功率吧，用 SPL 写了一个测试程序：运行测试，正确率达到了91.1%，我对这个结果是很满意的，毕竟这只是一个单层模型，我用TensorFlow的单层模型得到的正确率也是91%多一点。下面解析一下代码：A1，导入模型文件；A2，把模型提取到变量里；A3，计数器初始化（用于计算成功率）；A4，导入MNIST测试样本，这个文件格式是我转换过的；A5，循环取1万个样本进行测试；B5，取出来label；B6，清空输入；B7，取出来这个图片的2828个像素点作为输入，每个输入除以255，这是为了归一化；B8，计算X0W0+ X1W1+……X783W783+biasB9，计算sigmoid(B7)B10，得到最大值，即最可能的那个数字；B11，判断正确测计数器加一；A12，A13，测试结束，关闭文件，输出正确率。1.4 优化这里要说的优化并不是继续提高正确率，而是提升训练的速度。想提高正确率的同学可以尝试一下这几个手段：1. 加一个卷积层；2. 学习速度不要用固定值，而是随着训练次数递减；3. 权重的初始值不要使用全零，使用正态分布；我认为单纯追求正确率的意义不大，因为MNIST数据集有些图片本身就有问题，即使人工也不一定能知道写的是数字几。我用集算器显示了几张出错的图片，都是书写十分不规范的，下面这个图片很难看出来是2。下面说重点，要提高训练速度，可以使用并行或集群。使用SPL语言实现并行很简单，只要使用fork关键字，把上面的代码稍加处理就可以了。使用了并行之后，训练的时间减少差不多一半，而代码并没有做太多修改。2 为什么是 SPL 语言？使用SPL语言在初期可能会有点不适应，用得多了会觉得越来越方便：1. 支持集合运算，比如例子里用到的784个输入和784个权重的乘法，直接写一个**就可以了，如果使用Java或者C，还要自己实现。2. 数据的输入输出很方便，可以方便地对文件读写。3. 调试太方便了，所有变量都直观可见，这一点比python要好用。4. 可以单步计算，有了改动不用从头重来，Java和C做不到这一点，python虽然可以但也不方便，集算器只要点中相应格执行就可以了。5. 实现并行和集群很方便，不需要太多的开发工作量。6. 支持调用和被调用。集算器可以调用第三方java库，Java也可以调用集算器的代码，例如上面的代码就可以被Java调用，实现一个自动填验证码的功能。这样的编程语言，用在数学计算上，实在是最合适不过了。相关文件下载：154037421300096d9.rar