KMP算法求解的问题

给定两个字符串str和match,长度分别为N和M。实现一个算法,如果字符串str中含有子串match,则返回match在str中的开始位置。不含有则返回-1.

例如:

str=”acbc”,match=”bc”,返回2;

str=”acbc”,match=”bcc”,返回-1;

要求:如果match的长度大于str的长度(M>N),str必然不会含有match,可直接返回-1.但如果N≥M,要求算法复杂度为O(N).

对数器

什么叫对数器呢?

我们可以通过一个事例来了解它,我们在学算法时,一般来说,会学到常见的排序算法(后面也会涉及到),我们在写完排序代码后需要对代码进行验证其正确性,比较常用的做法就是我们自己定义一个数组,然后运行我们的代码,然后我们逐一看结果是否按序排好,这种方式缺点就是不能将所有可能的情况全都覆盖,可能看起来我们的输出的结果没问题,其实在特殊情况下,可能会存在问题。对数器就是生成一个随机数组(数组大小,数组元素范围完全随机),然后将随机数组进行复制,一个数组用我们来进行排序,另一个数组我们一个绝对正确的排序算法来进行排序,将两组数据进行比较,一般来说我们会生成多个数组来进行排序,最终所有的数组排序正确才返回正确,由于数组是随机且大小、元素值都不唯一,而且数组是多组,因此如果再这种情况下返回正确的结果,那么我们就认为我们的算法是正确的。

引言
最近实习,闲着无聊,买了本《剑指offer》,看到里面的算法面试题不错,正好每天晚上闲着也没事,然后就打算拿来刷一刷,活跃一下思维,工作期间保证一天一题,双休日的话看心情刷题,所有题目的代码均保证通过oj的测试,同时代码放在github上,欢迎download和star。

数据结构可分为线性结构和非线性结构两大类。。一般的,线性结构只能用来描述数据元素之间的线性顺序关系,而很难反映元素之间的层次(分支)关系。本文将要讨论一种非线性数据结构,所谓非线性结构是指在结构中至少存在一个数据元素,它具有两个或两个以上的直接后继或直接前驱。

树形结构,是一类非常重要的非线性数据结构,它用于描述数据元素之间的层次关系。树形结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种结构是树和二叉树。

二叉树是一种非常重要的数据结构,它同时具有数组和链表各自的特点:它可以像数组一样快速查找,也可以像链表一样快速添加。但是它也有自己的缺点:删除操作复杂。

概述

排序算法无论是在日常的编码中亦或者是面试中都经常出现,比较常见的像冒泡排序法,这应该是大家入门是必须要会的排序算法,下面使用java语言实现几种常用的排序。

这里先贴出两张思维导图:

第一张图是我们在编码中所能遇到的所有的排序方法,可能不太全,后期遇到了再慢慢补充

数据结构与算法之排序

本文主要讲内部排序,内部排序和外部排序不同之处在于,内部排序只使用内存进行排序,外部排序使用内存和外存结合起来进行排序。