快速排序
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
背包算法递归定义最优解的方程式:
大概解释一下:
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]; }
Modern PHP
红包算法
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()方法的区别在于:
- 如果两个对象相等(equal),那么他们一定有相同的哈希值。
- 如果两个对象的哈希值相同,但他们未必相等(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
[ 转载请保留原文出处、译者和译文链接。]
MySQL Query GROUP BY day / month / year
GROUP BY YEAR(record_date), MONTH(record_date)