Home Tags Posts tagged with "算法"

算法

0 59

说到数组,我一向自认为熟知其概念,操作,特性,但是最近看到的一个问题却把我难住了,那就是,为什么数组下标从0开始而不是从1开始?

带着这个疑问,结合王争老师的《数据结构与算法》来重新剖析数组这种数据结构

 

如何实现随机访问?

一、为什么数组可以实现随机访问(1.线性表 2.连续空间春初相同类型的数据)

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据

这个定义里有几个关键词,理解了这几个关键词,我想你就能彻底掌握数组的概念了。

第一是线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。

其实除了数组,链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

第二个是连续的内存空间和相同类型的数据。

正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

数组的两个限制分别为:

  1. 线性表
  2. 连续的内存空间和相同类型的数据

 

二、数组是如何实现根据下标随机访问数组元素的?(原理  内存偏移公式)

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例。

在我画的这个图中,计算机给数组 a[10],分配了一块连续内存空间 1000~1039,其中,内存块的首地址为 base_address = 1000。我们知道,计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:a[i]_address = base_address + i * data_type_size其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里,数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。这个公式非常简单,我就不多做解释了。

三、数组的查找时间复杂度为O(1)吗?

我在面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)

 

数组的低效插入和删除(低效均是因为数据偏移)

插入操作

假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢?你可以自己先试着分析一下。如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。

插入操作的时间复杂度应该区分数组中的数据是否有序(二者可以采取的策略不同)

如果数组中的数据是有序的,我们在某个位置插入一个新的元素时,就必须按照刚才的方法搬移 k 之后的数据。

但是,如果数组中存储的数据并没有任何规律,数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个数据插入到第 k 个位置,为了避免大规模的数据搬移,我们还有一个简单的办法就是,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 个位置。为了更好地理解,我们举一个例子。假设数组 a[10]中存储了如下 5 个元素:a,b,c,d,e。我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5],将 a[2]赋值为 x 即可。最后,数组中的元素如下: a,b,x,d,e,c。

在这种特定情况下,即数据无序,插入第K位的元素,时间复杂度可以降低到O(1),此思想在快速排序中也会用到!!!

 

删除操作

删除操作为什么要数据迁移?(避免出现空洞)

删除操作搬移数据是为了避免出现空洞!

跟插入数据类似,如果我们要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。

如何提高删除效率?(先标记,再删除,减少数据迁移的次数,与JVM垃圾回收机制相似)

实际上,在某些特殊场景下,我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行,删除的效率是不是会提高很多呢?我们继续来看例子。数组 a[10]中存储了 8 个元素:a,b,c,d,e,f,g,h。现在,我们要依次删除 a,b,c 三个元素。

为了避免 d,e,f,g,h 这几个数据会被搬移三次,我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

如果你了解 JVM,你会发现,这不就是 JVM 标记清除垃圾回收算法的核心思想吗?没错,数据结构和算法的魅力就在于此,很多时候我们并不是要去死记硬背某个数据结构或者算法,而是要学习它背后的思想和处理技巧,这些东西才是最有价值的。如果你细心留意,不管是在软件开发还是架构设计中,总能找到某些算法和数据结构的影子。

警惕数组的访问越界问题

在Java语言中,当数组出现越界时,会出现异常 在c语言中,数组出现越界时,一样可以访问;ArrayIndexOutOfBoundsException 属于 运行期错误,而不属于编译期错误.

 

容器能否完全替代数组?

针对数组类型,很多语言都提供了容器类,比如 Java 中的 ArrayList、C++ STL 中的 vector。

在项目开发中,什么时候适合用数组,什么时候适合用容器呢?

这里我拿 Java 语言来举例。如果你是 Java 工程师,几乎天天都在用 ArrayList,对它应该非常熟悉。那它与数组相比,到底有哪些优势呢?我个人觉得,ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外,它还有一个优势,就是支持动态扩容

数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组,当第 11 个数据需要存储到数组中时,我们就需要重新分配一块更大的空间,将原来的数据复制过去,然后再将新的数据插入。

如果使用 ArrayList,我们就完全不需要关心底层的扩容逻辑,ArrayList 已经帮我们实现好了。每次存储空间不够的时候,它都会将空间自动扩容为 1.5 倍大小。(JDK1.8,初始大小为10个)

不过,这里需要注意一点,因为扩容操作涉及内存申请和数据搬移,是比较耗时的。

使用ArrayList如果能事先确定数据大小能省掉很多次的内存申请和数据迁移操作

所以,如果事先能确定需要存储的数据大小,最好在创建 ArrayList 的时候事先指定数据大小。比如我们要从数据库中取出 10000 条数据放入 ArrayList。我们看下面这几行代码,你会发现,相比之下,事先指定数据大小可以省掉很多次内存申请和数据搬移操作。

 

容器和数组对比总结(极致性能则使用数组,否则使用容器)

1.Java ArrayList 无法存储基本类型,比如 int、long,需要封装为 Integer、Long 类,而 Autoboxing、Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。自动拆箱,装箱需要读写内存,而基本数据类型只需要使用寄存器,寄存器比内存快一个级别)

2. 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。3. 还有一个是我个人的喜好,当要表示多维数组时,用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList<arraylist

我总结一下,对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发,比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选。

 

解答开篇(1.根据内存偏移计算公式,从1开始要多做一次减法 2.历史原因)

现在我们来思考开篇的问题:为什么大多数编程语言中,数组要从 0 开始编号,而不是从 1 开始呢?

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也讲到,如果用 a 来表示数组的首地址,a[0]就是偏移为 0 的位置,也就是首地址,a[k]就表示偏移 k 个 type_size 的位置,所以计算 a[k]的内存地址只需要用这个公式:a[k]_address = base_address + k * type_size但是,如果数组从 1 开始计数,那我们计算数组元素 a[k]的内存地址就会变为:a[k]_address = base_address + (k-1)*type_size对比两个公式,我们不难发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。不过我认为,上面解释得再多其实都算不上压倒性的证明,说数组起始编号非 0 开始不可。

所以我觉得最主要的原因可能是历史原因。C 语言设计者用 0 开始计数数组下标,之后的 Java、JavaScript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习成本,因此继续沿用了从 0 开始计数的习惯。实际上,很多语言中数组也并不是从 0 开始计数的,比如 Matlab。甚至还有一些语言支持负数下标,比如 Python。

之前接触过加密算法,粗略了解到对称算法,非对称算法,不可逆算法等等

正好本次项目中用到了 MD5加密,特此详解MD5加密算法

 

MD5加密算法

基本介绍

MD5是一个安全的散列算法,输入两个不同的明文不会得到相同的输出值根据输出值,不能得到原始的明文,即其过程不可逆;所以要解密MD5没有现成的算法,只能用穷举法,把可能出现的明文,用MD5算法散列之后,把得到的散列值和原始的数据形成一个一对一的映射表,通过比在表中比破解密码的MD5算法散列值,通过匹配从映射表中找出破解密码所对应的原始明文

 

破解方法

对信息系统或者网站系统来说,MD5算法主要用在用户注册口令的加密,对于普通强度的口令加密,可以通过以下三种方式进行破解:

(1)在线查询密码。一些在线的MD5值查询网站提供MD5密码值的查询,输入MD5密码值后,如果在数据库中存在,那么可以很快获取其密码值。

(2)使用MD5破解工具。网络上有许多针对MD5破解的专用软件,通过设置字典来进行破解。

(3)通过社会工程学来获取或者重新设置用户的口令。

因此简单的MD5加密是没有办法达到绝对的安全,因为普通的MD5加密有多种暴力破解方式,因此如果想要保证信息系统或者网站的安全,需要对MD5进行改造,增强其安全性,本文就是在MD5加密算法的基础上进行改进!

 

加密原理

MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位分组级联后将生成一个128位散列值。

在MD5算法中,首先需要对信息进行填充,使其字节长度对512求余数的结果等于448。因此,信息的字节长度(Bits Length)将被扩展至N*512+448,即N*64+56个字节(Bytes),N为一个正整数。填充的方法如下,在信息的后面填充一个1和无数个0,直到满足上面的条件时才停止用0对信息的填充。然后再在这个结果后面附加一个以64位二进制表示的填充前的信息长度。经过这两步的处理,现在的信息字节长度=N*512+448+64=(N+1)*512,即长度恰好是512的整数倍数。这样做的原因是为满足后面处理中对信息长度的要求。MD5中有四个32位被称作链接变量(Chaining Variable)的整数参数,他们分别为:A=0x01234567,B=0x89abcdef,C=0xfedcba98,D=0x76543210。当设置好这四个链接变量后,就开始进入算法的四轮循环运算,循环的次数是信息中512位信息分组的数目。

将上面四个链接变量复制到另外四个变量中:A到a,B到b,C到c,D到d。主循环有四轮(MD4只有三轮),每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算,然后将所得结果加上第四个变量(文本中的一个子分组和一个常数)。

再将所得结果向右环移一个不定的数,并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。以一下是每次操作中用到的四个非线性函数(每轮一个)。

其中,?是异或,∧是与,∨是或,是反符号。

如果X、Y和Z的对应位是独立和均匀的,那么结果的每一位也应是独立和均匀的。F是一个逐位运算的函数。即,如果X,那么Y,否则Z。函数H是逐位奇偶操作符。所有这些完成之后,将A,B,C,D分别加上a,b,c,d。然后用下一分组数据继续运行算法,最后的输出是A,B,C和D的级联。最后得到的A,B,C,D就是输出结果,A是低位,D为高位,DCBA组成128位输出结果。

安全性

从安全的角度讲,MD5的输出为128位,若采用纯强力攻击寻找一个消息具有给定Hash值的计算困难性为2128,用每秒可试验1000000000个消息的计算机需时1.07×1022年。若采用生日攻击法,寻找有相同Hash值的两个消息需要试验264个消息,用每秒可试验1000000000个消息的计算机需时585年。

 

算法应用

MD5加密算法由于其具有较好的安全性,加之商业也可以免费使用该算法,因此该加密算法被广泛使用,md5算法主要运用在数字签名、文件完整性验证以及口令加密等方面。

 

算法缺陷

在目前的信息系统中,对md5加密方法的利用主要通过在脚本页面中引用包含md5加密函数代码的文件,以asp脚本为例,在需要调用的页面中加入,md5.asp为md5加密函数代码文件,然后直接调用函数MD5(sMessage)即可,md5加密后的值有16位和32位之分,如果在md5加密函数中使用的是MD5 = LCase(WordToHex(a) &WordToHex(b) & WordToHex(c) & WordToHex(d)),则表示是32位,如果使用的是MD5=LCase(WordToHex(b) & WordToHex(c)),则表示是16位。例如对明文为“123456”的值进行加密,其md5值有两个,如下所示:

 

A=123456password=md5(A)= 49ba59abbe56e057 password=md5(A)=10adc3949ba59abbe56e057f20f883e如果将加密的md5值直接保存在数据库,当网站存在注入或者其它漏洞时,入侵者极有可能获取用户的密码值,通过md5在如果将加密的md5值直接保存在数据库,当网站存在注入或者其它漏洞时,入侵者极有可能获取用户的密码值,通过md5在线查询或者暴力破解可以得到密码。

 

算法改进

本文提到的方法是在使用md5加密算法对明文(口令)加密的基础上,对密文进行了改变,在密文中截取一段数据并丢弃,然后使用随机函数填充被丢弃的数据,且整个过程不改变md5加密后的位数。其加密过程用算法描述如下:

(1)对明文password进行md5加密,获得密文md5(password)。

(2)使用截取函数截取加密后的密文,从第beginnumber位置开始截取number位数值,得到密码A,其中A=left(md5(password),beginnumber-1)。

(3)使用截取函数截取加密后的明文的number位数后的值B,其中 B=right(md5(password),md5-digit -(beginnumber+number-1))。

(4)使用随机函数gen_key(number)填充被截取的number的值。

(5)变换后的密码值为encrypt_password =A&get_key(number)&B

变量说明:

解密过程跟加密过程有些类似,先对输入的明文进行加密,接着从beginnumber处截取前半部分得到A′,后半部分得到B′,然后从数据库中读出密码中的A和B部分,最后如果A=A′并且B=B′,则认为用户输入的密码跟数据库中的密码是匹配的。

当然,这只是改进 MD5 算法的一种方法,实际可行的思路有很多

 

结束

有人也曾经提出对md5加密算法中的函数或者变量进行修改,从而加强在使用原md5算法的安全,但是这种方法修改了md5原函数或者变量后,无法验证修改后md5算法在强度上是否跟原算法一致。本文提出的方法是在原有md5加密的基础上,通过对密文截取一定位数的字符串,并使用随机数进行填充,最后得到的密文虽然是经过md5加密,但是其值已经大不一样,因此通过md5常规破解方法是永远也不能破解其原始密码值,从而保证了数据的安全。虽然目前有很多攻击方法,诸如SQL注入、跨站攻击等,可以较容易的获取数据库中的值,通过本方法进行加密,在网站或者系统代码泄露前,其数据是相对安全的,因此具有一定参考加值。

 

/输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

解题思路:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

动态规划是本题的最优解法,以下按照标准流程解题。
动态规划解析:
状态定义: 设动态规划列表 dpdpdp ,dp[i]dp[i]dp[i] 代表以元素 nums[i]nums[i]nums[i] 为结尾的连续子数组最大和。
为何定义最大和 dp[i]dp[i]dp[i] 中必须包含元素 nums[i]nums[i]nums[i] :保证 dp[i]dp[i]dp[i] 递推到 dp[i+1]dp[i+1]dp[i+1] 的正确性;如果不包含 nums[i]nums[i]nums[i] ,递推时则不满足题目的 连续子数组 要求。
转移方程: 若 dp[i−1]≤0dp[i-1] \leq 0dp[i−1]≤0 ,说明 dp[i−1]dp[i – 1]dp[i−1] 对 dp[i]dp[i]dp[i] 产生负贡献,即 dp[i−1]+nums[i]dp[i-1] + nums[i]dp[i−1]+nums[i] 还不如 nums[i]nums[i]nums[i] 本身大。
当 dp[i−1]>0dp[i – 1] > 0dp[i−1]>0 时:执行 dp[i]=dp[i−1]+nums[i]dp[i] = dp[i-1] + nums[i]dp[i]=dp[i−1]+nums[i] ;
当 dp[i−1]≤0dp[i – 1] \leq 0dp[i−1]≤0 时:执行 dp[i]=nums[i]dp[i] = nums[i]dp[i]=nums[i] ;
初始状态: dp[0]=nums[0]dp[0] = nums[0]dp[0]=nums[0],即以 nums[0]nums[0]nums[0] 结尾的连续子数组最大和为 nums[0]nums[0]nums[0] 。
返回值: 返回 dpdpdp 列表中的最大值,代表全局最大值。
 空间复杂度降低:
由于 dp[i]dp[i]dp[i] 只与 dp[i−1]dp[i-1]dp[i−1] 和 nums[i]nums[i]nums[i] 有关系,因此可以将原数组 numsnumsnums 用作 dpdpdp 列表,即直接在 numsnumsnums 上修改即可。
由于省去 dpdpdp 列表使用的额外空间,因此空间复杂度从 O(N)O(N)O(N) 降至 O(1)O(1)O(1) 。
复杂度分析:
时间复杂度 O(N)O(N)O(N) : 线性遍历数组 numsnumsnums 即可获得结果,使用 O(N)O(N)O(N) 时间。
空间复杂度 O(1)O(1)O(1) : 使用常数大小的额外空间。

动态规划,小试牛刀,感谢楼主。
1.状态,即子问题。
dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。

2.转移策略,自带剪枝。
若 dp[i−1]≤0 ,说明 dp[i−1] 对 dp[i] 产生负贡献,即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。

3.状态转移方程,根据前两步抽象而来。

  • 当 dp[i−1]>0 时:执行 dp[i] = dp[i-1] + nums[i];
  • 当 dp[i−1]≤0 时:执行 dp[i] = nums[i] ;

4.设计dp数组,保存子问题的解,避免重复计算

5.实现代码

整个动态规划,最难的就是定义状态。一旦状态定义出来,表明你已经抽象出了子问题,可以肢解原来的大问题了。

贪心算法+分治算法https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/tan-xin-fen-zhi-dong-tai-gui-hua-fa-by-luo-jing-yu/