雨夜带刀's Blog

Boyer Moore 字符串搜索算法之 JavaScript 实现

最近碰到的一个需求需要借助字符串的快速搜索算法,于是看了一些有关字符串搜索的一些算法,最先看的是 KMP 算法,看完之后发现还有更优的算法,那就是 Boyer Moore 算法。编辑器的文本搜索、GNU 的 grep 都有使用 Boyer Moore 算法,那么效率应该是经过权威验证的。

虽然网上有不少介绍资料,但我还是从一个算法小白所理解的算法原理来尝试解析该算法,算法大神可绕道了。

从头至尾搜索一个字符串,看这个被搜索的字符串是否包含指定的子串,有则返回其位置,没有则返回 -1,相当于使用自己的算法来实现 JavaScript 中的 String.prototype.indexOf 的功能。

JavaScript算法题之–查找不同顺序排列的字符串

需求描述:从一组数组中找出一组按不同顺序排列的字符串的数组元素。假如有这样一个数组:

[ 'abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc' ]

需要找出的结果是:

[ 'abcd', 'bdca', 'cadb' ]

那么这里的关键点其实是判断一组字符串是否是否只是字符的顺序不同,只要解决整个关键点其他都好办了。

方法1:

var stringClassify = function( arr ){
	var arrLength = arr.length,
		obj = {},
		i = 0,
		num, item, name, strLength;

	for( ; i < arrLength; i++ ){
		item = arr[i];
		strLength = item.length;
		num = 0;

		// 将单个的字符转换成 Unicode 编码
		// 对编码进行取和计算
		for( j = 0; j < strLength; j++ ){
			num += item.charCodeAt( j );
		}		

		if( !obj[num] ){
			obj[ num ] = [];
		}	

		obj[ num ].push( item );
	}

	for( name in obj ){
		console.log( obj[name] );
	}
};	

JavaScript算法题之–随机数的生成

需求描述:从一组有序的数据中生成一组随机并且不重复的数,类似于简单的抽奖程序的实现。

先来生成一个有序的数组:

var arr = [],
	length = 100,
	i = 0;

for( ; i < length; i++ ){
	arr.push( i );
}

从一个长度为 100 的有序数组中随机拿出 10 个随机的数,并且不能有重复。

再谈等高瀑布流布局的算法

之前有写过一篇非等宽图片列表的布局的博文,那只是这种布局之前的叫法,为了和常规的等宽瀑布流布局做区分,根据这种布局的特性(整行是等高的),那么就叫等高瀑布流布局吧。

怎么又拿这种布局出来说事?最近几天在对以前开发的360图片搜索结果列表页的图片尺寸和交互效果做一些细节上的调整。同时也对布局的算法做了优化,之前采用的是以宽度裁切为主和夹杂着一些等比缩放的算法,当时是为了让每一行看起来高度都一致。由于宽度裁切的效果会让图片左右边缘部分有损失,而且当时也有图片 hover 时的放大效果在一定程度上弥补了这种损失。这次放弃了宽度裁切,也去掉了 hover 时放大图片的效果,全部采用了等比缩放的算法。

在上一篇博文中谈到的等比缩放的算法其实并不是最优的,还是会有一定的上下或者左右的裁切。研究了一下 Google+ 的相册使用的等高瀑布流布局的缩放,发觉还有一种更优的缩放计算的算法,于是花了两个小时将这种算法推演了出来。这里先检讨下,由于智商上的缺陷,数学绝对是我的弱项,这种算法比之前的要简单得多,之前是走了弯路了。

头像

雨夜带刀

前端开发工程师,技术宅,现居北京。

雨夜带刀的开源项目

easy.js
一个简洁的 JavaScript 类库,集成了模块加载器,同时也有包含了常见的的组件库,可访问项目网站
seed
符合 AMD 规范的 JavaScript 模块加载器。
ecope
从 easy.js 组件库中移值过来的基于 jQuery 的组件库,简单实用,API 风格统一。