深度优先算法解两个题 最近读了<啊哈算法>看到里面使用深度优先算法解出了下面两个题,自己用Scala实现下,记录下来. 深度优先搜索 解决全排列问题 从 1~9共9个数字中选择正确数字填入_,使得等式 _ _ _ + _ _ _ = _ _ _ 成立 对于第二个题竟然由3百多个解,而自己想一个解想了半天… 先看dfs执行流程图 pac ...
排序算法总结拾遗 说到算法,脑子里最先想到的就是排序. 工作之后陆陆续续听说过,接触过的排序算法很多,真正掌握的的很少,有必要总结一下,便于查阅. 若无特别说明,本文提到的排序都是从小到大排序. 1. 桶排序/计数排序 考虑这样一个问题: 已知有一群人的身高数据都是整数,单位是cm. 现在需要将这组身高数据按照从小到大 ...
package com.alg.test /** * **************************** 二叉树与堆排序 ******************************** * 最近工作中,需要用到树的相关数据结构和算法,正好前段时间收了一本数据结构和算法相关的书,就看了下树相关的章节. * 记录作为读书笔记,加深理解,也便于以后复习 * * 1 - 概念: * 1.1 二 ...
import scala.util.Sorting /** * ***** Scala 快速排序 quick sort ***** * * 快速排序的思想是,假如有一个List存放整数,首先选取第一个数作为基准(pivot),将这个LIst分为如下三部分, * less pivot greater, 其中less和greater也是List, less是小于pivot的List,greater是大于pivot的List * 接下来对less和greate ...
项目中用到了蒙特卡洛算法,之前没有接触过,还比较陌生.于是学习了一番,用Scala实现了一个经典的例子:计算π的近似值. 网上搜索了下,蒙特卡洛(Monte Carlo)算法起源于二战时研制原子弹的”曼哈顿计划”,创始人之一就有大名鼎鼎的冯诺依曼大牛.蒙特卡洛是以一个赌城的名字命名的(还有一个相关的算法叫拉斯维加斯 ...