快速排序

public static void quickSort(int[] array, int start, int end) {
	if (start < end) {
		int middle = getMiddle(array, start, end);
		quickSort(array, 0, middle - 1);
		quickSort(array, middle + 1, end);
	}
}

private static int getMiddle(int[] array, int start, int end) {
	int baseVal = array[start];
	while (start < end) {
		while (start < end && array[end] >= baseVal) {
			end--;
		}
		array[start] = array[end];
		while (start < end && array[end] <= baseVal) {
			start++;
		}
		array[end] = array[start];
	}
	array[start] = baseVal;
	return start;
}

二分查找

递归方法:

public static int search(int[] array, int start, int end, int val) {
	int mid = (end + start) / 2;
	if (array[mid] == val) {
		return mid;
	}
	if (array[mid] > val) {
		end = mid - 1;
	}
	if (array[mid] < val) {
		start = mid + 1;
	}
	int r = search(array, start, end, val);
	if (r >= 0) {
		return r;
	}
	return -1;
}

非递归:

public static int search2(int[] array, int val) {
	int start = 0;
	int end = array.length - 1;
	while (end >= start) {
		int mid = (end + start) / 2;
		if (array[mid] == val) {
			return mid;
		}
		if (array[mid] > val) {
			end = mid - 1;
		}
		if (array[mid] < val) {
			start = mid + 1;
		}
	}
	return -1;
}

0/1背包算法

装货问题
隔壁老王开着顺丰的标配货车(限载5吨,含5吨,不考虑限高),想要一次性拿走尽可能重的货物,这些货有红木沙发,有钢材等等。

货物编号   货物重量(单位:kg)
1         509
2         838
3         924
4         650
5         604
6         793
7         564
8         651
9         697
10        649
11        747
12        787
13        701
14        605
15        644

背包算法递归定义最优解的方程式:
wechatimg49
大概解释一下:
i 代表第几个货物,j表示当前容量,w(i)表示第i个货物的重量,v(i)表示第i个货物的价值,m(i,j)表示第i个货物,容量为j的最优解
转态转移的时候有两种情况:
1.可以装下一个 j>= w(i),这种情况可以装入这个物品,比较装入后和没有装入的最优解,决定是否装入
2.不可以装下一个 0<=j<=w(i), 这种情况不能装入这个物品,最优解不变

代码实现:


public static int knapsack(int val[], int wt[], int W) {
	int N = wt.length;
	
        //构造一个二维数组
	int[][] V = new int[N + 1][W + 1];
        //初始化数组数据
	for (int col = 0; col <= W; col++) {
		V[0][col] = 0;
	}
         
	for (int row = 0; row <= N; row++) {
		V[row][0] = 0;
	}

	for (int item = 1; item <= N; item++) {
		for (int weight = 1; weight <= W; weight++) {
			if (wt[item - 1] <= weight) {
                //可以装入
				V[item][weight] = Math.max(val[item - 1] + V[item - 1][weight - wt[item - 1]], V[item - 1][weight]);
			} else {
                //不能装入
				V[item][weight] = V[item - 1][weight];
			}
		}

	}

	// 计算选择结果
	int j = W;
	int length = N;
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = length; i > 0; --i) {
		//转态转移的时候记录
		if (V[i][j] > V[i - 1][j]) {
			stringBuilder.append(i).append("-");
			j = j - wt[i-1];
		}
	}
	String result = stringBuilder.toString();
	System.out.println("选择的序号 : " + result.substring(0, result.length()-1));
	
	//打印表
	for (int[] rows : V) {
	      for (int col : rows) {
		System.out.format("%5d", col);
	       }
	      System.out.println();
	}

	return V[N][W];
}

红包算法

JAVA

public class SplitRedPacket {

	public static void main(String[] args) {
		LeftMoneyPackage leftMoneyPackage = new LeftMoneyPackage();
		leftMoneyPackage.remainMoney = 10;
		leftMoneyPackage.remainSize = 8;
		int i = 1;
		while (leftMoneyPackage.remainSize > 0) {
			double money = getRandomMoney(leftMoneyPackage);
			System.out.println(i + " : " + money);
			i++;
		}
	}

	public static double getRandomMoney(LeftMoneyPackage _leftMoneyPackage) {
		// remainSize 剩余的红包数量
		// remainMoney 剩余的钱
		if (_leftMoneyPackage.remainSize == 1) {
			_leftMoneyPackage.remainSize--;
			return (double) Math.round(_leftMoneyPackage.remainMoney * 100) / 100;
		}
		Random r = new Random();
		double min = 0.01; //最小金额
		double max = _leftMoneyPackage.remainMoney / _leftMoneyPackage.remainSize * 2;
		double money = r.nextDouble() * max;
		money = money <= min ? min : money;
		money = Math.floor(money * 100) / 100;
		_leftMoneyPackage.remainSize--;
		_leftMoneyPackage.remainMoney -= money;
		return money;
	}

}

class LeftMoneyPackage {
	public int remainSize;
	public double remainMoney;

	public static class BuildLeftMoneyPackage {
		
	}

}

PHP

$total=10;//红包总额
$num=8;// 分成8个红包,支持8人随机领取
$min=0.01;//每个人最少能收到0.01元

for ($i=1;$i<$num;$i++)
{
    $safe_total=($total-($num-$i)*$min)/($num-$i);//随机安全上限
    $money=mt_rand($min*100,$safe_total*100)/100;
    $total=$total-$money;
    echo '第'.$i.'个红包:'.$money.' 元,余额:'.$total.' 元 
';
}
echo '第'.$num.'个红包:'.$total.' 元,余额:0 元';

8张图理解Java

一图胜千言,下面图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

1、字符串不变性

2、equals()方法、hashCode()方法的区别

HashCode被设计用来提高性能。equals()方法与hashCode()方法的区别在于:

  1. 如果两个对象相等(equal),那么他们一定有相同的哈希值。
  2. 如果两个对象的哈希值相同,但他们未必相等(equal)。

3、Java异常类的层次结构

图中红色部分为受检查异常。它们必须被捕获,或者在函数中声明为抛出该异常。

4、集合类的层次结构

注意Collections和Collection的区别。(Collections包含有各种有关集合操作的静态多态方法)

5、Java同步

Java同步机制可通过类比建筑物来阐明。

6、别名

别名意味着有多个变量指向同一可被更新的内存块,这些别名分别是不同的对象类型。

7、堆和栈

图解表明了方法和对象在运行时内存中的位置。

8、Java虚拟机运行时数据区域

图解展示了整个虚拟机运行时数据区域的情况。

原文链接: programcreek 翻译: ImportNew.com era_misa
译文链接: http://www.importnew.com/11725.html
[ 转载请保留原文出处、译者和译文链接。]