-
DFS 深度优先遍历与 BFS 广度优先遍历详解
DFS 什么是深度优先搜索?
深度优先搜索是用来遍历或搜索树和图数据结构的算法,它是可以从任意跟节点开始,选择一条路径走到底,并通过回溯来访问所有节点的算法。
简单来说就是通过选择一条道路走到无路可走的时候回退到上一个岔路口,并标记这条路已走过,选择另外一条道路继续走,直到走遍每一条路。
DFS 深度优先搜索的思想
DFS 思修基于递归思想,通过递归的形式来缩小问题规模,把一件事分割...
2020-01-23 02:09:32 |
Data-Struct
-
五大基本算法概览
什么是算法?
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。
也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。
如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来...
2020-01-23 02:09:32 |
Data-Struct
-
五大基本算法之贪心算法 Greedy
贪心算法
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。
也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
基本要素
贪心选择
贪心选择是指所求问题的整体最优解可以通过一...
2020-01-23 02:09:32 |
Data-Struct
-
五大基本算法之穷举算法
穷举
定义
穷举法又称穷举搜索法,是一种在问题域的解空间中对所有可能的解穷举搜索,并根据条件选择最优解的方法的总称。
数学上也把穷举法称为枚举法,就是在一个由有限个元素构成的集合中,把所有元素一一枚举研究的方法。
使用穷举法解决问题,基本上就是以下两个步骤:
确定问题的解(或状态)的定义、解空间的范围以及正确解的判定条件;
根据解空间的特点来选择...
2020-01-23 02:09:32 |
Data-Struct
-
五大基本算法之动态规划算法 DP dynamic programming
dynamic programming
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimali...
2020-01-23 02:09:32 |
Data-Struct
-
面试算法:斐波那契数列时间复杂度为 O(1) 的解法,你会吗?
题目
今天,我们就重新学习一下,这个每一位学习过递归的同学都见过的题目—斐波那契数列。
但是,你真的理解这个数列了吗?
509. 斐波那契数
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。
该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。
也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2)...
2020-01-23 02:09:32 |
Data-Struct
-
五大基本算法之分治算法 Divided
分治算法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。
求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。
基本思想
当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。
对于这类问题,我们往往先把它分解成几个子...
2020-01-23 02:09:32 |
Data-Struct
-
五大基本算法之回溯算法 backtracking
面试算法:回溯算法与分割回文串实战
回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。
回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。
但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯...
2020-01-23 02:09:32 |
Data-Struct