类别归档:算法

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.

RSS feed of 算法

Java滚动数组计算编辑距离

编辑距离(Edit Distance),也称Levenshtein距离,是指由一个字符串转换为另一个字符串所需的最少编辑次数。

下面的代码摘自org.apache.commons.lang.StringUtils

用法示例:

StringUtils.getLevenshteinDistance(null, *)             = IllegalArgumentException
StringUtils.getLevenshteinDistance(*, null)             = IllegalArgumentException
StringUtils.getLevenshteinDistance("","")               = 0
StringUtils.getLevenshteinDistance("","a")              = 1
StringUtils.getLevenshteinDistance("aaapppp", "")       = 7
StringUtils.getLevenshteinDistance("frog", "fog")       = 1 ...

继续阅读

Java实现数组洗牌算法

数组洗牌是指将一个数组中的元素顺序打乱,随机重新排列。

算法实现思路如下:

按照下标从大到小的顺序遍历数组,记下标为i

遍历时生成范围[0, i]的随机数j,交换下标i与下标j的数组元素

参考:java.util.Collections类中的shuffle方法

Java代码:

public static void shuffle(int[] nums) {
    Random rnd = new Random();
    for (int i = nums.length - 1; i > 0; i--) {
        int j ...

继续阅读

线段树 | 第1讲 (给定区间求和)

让我们通过考虑下面的问题来理解线段树。

给定一个数组arr[0 . . . n-1],我们要对数组执行这样的操作:

1 计算从下标l到r的元素之和,其中 0 <= l <= r <= n-1
​2 修改数组指定元素的值arr[i] = x,其中 0 <= i <= n-1

一个简单的方案是从lr执行循环,计算给定区间的元素之和。更新值的时候,简单地令arr[i] = x。第一个操作花费O(n)的时间,第二个操作花费O ...

继续阅读

无符号整数按位反转[LeetCode译文]

Reverse bits of an unsigned integer.

将无符号整数按位反转

有几种方法可以实现一个无符号整数的按位反转。在此,我们设计一个使用异或交换(XOR swap)技巧的算法,然后使用分治法对其进行优化。

提示:

怎样实现第i位与第j位的对调?想想能否使用异或操作实现。

异或交换技巧:

按位反转可以通过将低n/2位与高位对换实现。技巧就是实现一个名为swapBits(i, j)的函数,将第i位与第j位对换。回忆一下异或运算的原理:0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, and 1 ^ 0 == 1。

我们只需要在第i位与第j位不同时执行对换 ...

继续阅读

不使用乘除和pow计算一个数的平方

Calculate square of a number without using *, / and pow()

不使用乘除和pow计算一个数的平方 

给定一个整数n,在不使用乘除和pow函数的前提下计算其平方的值。

Examples:

Input: n = 5
Output: 25

Input: 7
Output: 49

Input: n = 12
Output: 144

一个直观的解法是重复地向结果加n。下面是该思路的C++实现。

// Simple solution to calculate square without
// using * and pow()
#include<iostream> ...

继续阅读