時間復(fù)雜度
二進(jìn)制
二進(jìn)制操作
二分查找
冒泡排序
快速排序
動態(tài)規(guī)劃
例子一：切鋼條
例子二：過河問題
例子三：最長公共子序列
例子四：最長公共連續(xù)子序列
例子五：01背包問題
時間復(fù)雜度
一個算法在給定輸入下執(zhí)行的基本操作數(shù)或步數(shù)，我們假定執(zhí)行每行代碼需要的時間為常量
二進(jìn)制
二進(jìn)制原碼、反碼、補(bǔ)碼：
- 二進(jìn)制的最高位是符號位：0表示正數(shù)，1表示負(fù)數(shù)
- 正數(shù)的原碼、反碼、補(bǔ)碼都一樣
- 負(fù)數(shù)的反碼 = 它的原碼符號位不變，其他位取反
- 負(fù)數(shù)的補(bǔ)碼 = 它的反碼 +1
- 0的反碼、補(bǔ)碼都是0
- 補(bǔ)碼的補(bǔ)碼是原碼
如
- 2的原碼：00000000 00000000 00000000 00000010
- -2的原碼：10000000 00000000 00000000 00000010
- -2的反碼：11111111 11111111 11111111 11111101
- -2的補(bǔ)碼：11111111 11111111 11111111 11111110
查看數(shù)字的二進(jìn)制表示，可以用Integer.toBinaryString(-1)
十六進(jìn)制其實(shí)是補(bǔ)碼表示，0xFFFFFFFF等于十進(jìn)制-1
二進(jìn)制操作
"&"與
"|"或
"^"異或：不相同才為1
">>"右移：正數(shù)左邊補(bǔ)0，負(fù)數(shù)左邊補(bǔ)1
"<<"左移：右邊補(bǔ)0
二分查找
描述：在有序數(shù)組里查找一個值，查找成功返回下標(biāo)，否則返回-1
思路：
- 用數(shù)組中間的值，與給定值比較，相等則查找成功
- 不相等，把數(shù)組分為兩半，在其中一半中繼續(xù)步驟1
- 直到查找成功，或子數(shù)組不存在
時間復(fù)雜度：
第一步耗時O(1)，一個長度為n的數(shù)組，一共要進(jìn)行1 + logn次第一步，因此時間復(fù)雜度是O(logn)
private static int binarySearch(int[] arr, int key) {
if (arr == null || arr.length <= 0) {
return -1;
}
int start = 0;
int end = arr.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2; // 防止溢出
if (arr[mid] == key) {
return mid;
}else if (arr[mid] > key) {
end = mid - 1;
}else {
start = mid + 1;
}
}
return -1;
}
冒泡排序
思路：
- 針對無序序列，兩兩比較，順序不對則交換，一趟排序后序列末尾的值是有序的
- 重復(fù)步驟1，直到無序序列為空
private static void bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int end = arr.length - 1;
int tem;
for (int i = end - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
if (arr[j] > arr[j+1]) {
tem = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tem;
}
}
}
}
時間復(fù)雜度：
上述算法，無論輸入如何，時間復(fù)雜度都是O(N^2)
冒泡排序改進(jìn)：
上述代碼，如果內(nèi)層循環(huán)中沒有進(jìn)行數(shù)據(jù)交換，那么內(nèi)層循環(huán)中的值已經(jīng)是有序的了，此時可以跳出循環(huán)
private static void bubbleSort1(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int end = arr.length - 1;
int tem;
boolean swapped;
for (int i = end - 1; i >= 0; i--) {
swapped = false;
for (int j = 0; j <= i; j++) {
if (arr[j] > arr[j+1]) {
tem = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tem;
swapped = true;
}
}
if (!swapped)
break;
}
}
時間復(fù)雜度：
此時如果輸入已經(jīng)是正序的，那么外層循環(huán)只執(zhí)行一次，此時時間復(fù)雜度O(n)
因此對冒泡排序改進(jìn)來說，最好的時間復(fù)雜度是O(n)
快速排序
思路：
- 選取一個主元，進(jìn)行一次定位，定位后，主元左邊元素都比它小，主元右邊元素都比它大
- 針對左右兩個分區(qū)，分別執(zhí)行步驟1
// 定位
private static int position(int[] arr, int start, int end) {
int i = start;
int j = end;
int key = arr[i];
while (i < j) {
while(i < j && arr[j] > key) { // 由于可能出現(xiàn)i==j，因此每一步都加i<j判斷，防止ij亂加減
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] <= key) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
} // 最后i==j
arr[i] = key; // 由于是覆蓋，而不是交換，因此最后要有一步賦值
return i;
}
// 快速排序
private static void quickSort(int[] arr, int start, int end) {
if (arr == null || arr.length <= 1 || start >= end || start < 0 || end > arr.length) {
return;
}
int pos = position(arr, start, end);
quickSort(arr, pos+1, end);
quickSort(arr, start, pos-1);
}
快速排序還有很多改進(jìn)版本，如隨機(jī)選擇基準(zhǔn)數(shù)，區(qū)間內(nèi)數(shù)據(jù)較少時直接用另的方法排序以減小遞歸深度。也可以選中間的數(shù)作為基準(zhǔn)數(shù)，要實(shí)現(xiàn)這個方便非常方便，直接將中間的數(shù)和第一個數(shù)進(jìn)行交換就可以了（我們用的是覆蓋，因此這里是用第一個數(shù)覆蓋中間的數(shù)）
int key = arr[i];
替換為
int mid = start + (end - start) / 2;
int key = arr[mid];
arr[mid] = arr[i];
時間復(fù)雜度：
最好場景：T(n) = 2T(n / 2) + n，最好時間復(fù)雜度O(nlogn)
最壞場景：T(n) = T(n - 1) + n，最壞時間復(fù)雜度O(n^2)
動態(tài)規(guī)劃
動態(tài)規(guī)劃和分治算法相似，都是通過組合子問題的解來求解原問題。
特殊情況下，分治算法會反復(fù)求解子問題
動態(tài)規(guī)劃每個子問題只求解一次，將其保存起來，避免不必要的計(jì)算
動態(tài)規(guī)劃通常用來求解最優(yōu)化問題。
動態(tài)規(guī)劃有下面兩種方式，我們通常使用第二種
- 帶備忘的自頂向下法：通常用一個數(shù)組保存已經(jīng)計(jì)算過的值，求解時，如果數(shù)組中有值，直接返回，否則才進(jìn)行計(jì)算。（計(jì)算f(n)，在計(jì)算f(n)的過程中去計(jì)算f(n-1)...）
- 自底向上法：求解一個問題時，直至它依賴的所有子問題均已求解完成，才求解它。（先計(jì)算f(0)，在計(jì)算f(1)...直到f(n)）
例子一：切鋼條
問題描述：長度為i的鋼條，價格為p(i)，i是整數(shù)。給定一段長度為n的鋼條，怎么切能讓收益最大？
思路：
- 長度為n的鋼條，最大切割收益用f(n)表示。
- f(n)怎么計(jì)算呢，考慮鋼條n所有可能的切割方案，先想第一步，第一刀切在哪，第一刀可以切長度為1，2，3，...，n（這是所有可能的場景），那么第一刀切長度i的收益是p(i)+f(n-i)
- 最大切割收益f(n)，即所有可能場景的最大值，于是f(n) = max(p(i)+f(n-i)), i=1 to n
直接遞歸法
private static int cut(int[] price, int n) {
if (n == 0) {
return 0;
}
int res = -1;
for (int i = 1; i <= n; i++) {
System.out.println(n + "-" + (n-i));
res = Math.max(res, price[i-1] + cut(price, n-i));
}
return res;
}
動態(tài)規(guī)劃-帶備忘自頂向下法
private static int cut1(int[] price, int n) {
int[] fArr = new int[n+1];
for (int i = 0; i < n+1; i++) {
fArr[i] = -1;
}
return cut1_aug(price, n, fArr);
}
private static int cut1_aug(int[] price, int n, int[] fArr) {
if(fArr[n] >= 0) {
return fArr[n];
}
int res = -1;
if (n == 0) {
res = 0;
}else {
for (int i = 1; i <= n; i++) {
System.out.println(n + "-" + (n-i));
res = Math.max(res, price[i-1] + cut1_aug(price, n-i, fArr));
}
}
fArr[n] = res;
return res;
}
動態(tài)規(guī)劃-自底向上法
private static int cut2(int[] price, int n) {
int[] f = new int[n+1]; // 最優(yōu)解數(shù)組
for (int i = 1; i <= n; i++) {
int res = -1;
for (int j = 1; j <= i; j++) {
System.out.println("*");
res = Math.max(res, price[j-1] + f[i-j]);
}
f[i] = res;
}
return f[n];
}
例子二：過河問題
一座橋，n個人，一個手電筒。橋一次最多通過兩個人，兩個人過橋時間為兩人中時間較長者，過橋必須用手電筒，所以每次過橋之后需要有人把手電筒送回來，問n個人過橋總時間最短是多少？
http://www.360doc.com/content/08/0706/02/37063_1402145.shtml
A ---> B
最佳場景：
1.每次B->A送手電筒的人，一定是B當(dāng)中最快的
2.手電筒在A時，速度最快的人一定在A
3.每次A->B的兩人，要么這兩人其中一個是所有人中最快的，要么這兩個人到B之后再也不回來
4.每次B->A送手電筒的人，一定是所有人中最快的，或者次快的
n個人中：
-最快的人，單人過橋時間設(shè)為a
-次快的人，單人過橋時間設(shè)為b
-次慢的人，單人過橋時間設(shè)為y
-最慢的人，單人過橋時間設(shè)為z
那么，最慢和次慢的人過橋有兩種模式
模式一：（耗時y+a+z+a）
- ay過橋
- a回來
- az過橋
- a回來
模式二：（耗時b+a+z+b）
- ab過橋
- a回來
- yz過橋
- b回來
另一種思路，同樣按過河時間從小到大排序
- 1個人：a直接過
- 2個人：ab直接過
- 3個人：ab-a-ac
- 4個人：和上面的模式相同
場景一：ab-a-ac-a-ad，耗時b+a+c+a+d
場景二：ab-a-cd-b-ab，耗時b+a+d+b+b - n個人
因?yàn)橐淮巫疃噙^兩個人，所以考慮最后升兩個人（耗時最長），這兩個人的過河方式有2種，對應(yīng)上面兩種模式
模式一：f(n) = f(n-2) + a + c + a + d
模式二：f(n) = f(n-2) + a + d + b + b
第i個人過河時間為a[i]，遞增
于是 f(n) = min{f(n-2)+arr[1]+arr[n-1]+arr[1]+arr[n], f(n-2)+arr[1]+arr[n]+arr[2]+arr[2]}
/**
* 過河時間
* 輸入：每個人單獨(dú)過河時間，從小到大排列
* 輸出：所有人過河最短時間
*/
private static int leastTime(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
int i = arr.length - 1;
int sum = 0;
for (; i > 2; i -= 2) {
int t1 = 2 * arr[0] + arr[i-1] + arr[i];
int t2 = 2 * arr[1] + arr[0] + arr[i];
sum += Math.min(t1, t2);
}
if (i == 2) { // 剩下3人
sum = sum + arr[0] + arr[1] + arr[2];
}
if (i == 1) { // 剩下2人
sum = sum + arr[1];
}
return sum;
}
例子三：最長公共子序列LCS
描述：給定兩個序列X、Y，如果Z即是X的子序列，又是Y的子序列，那么稱Z是X和Y的公共子序列
比如：X=abcbdab，Y=bdcaba，那么bcba是X和Y的一個最長公共子序列
思路：
我們設(shè)X={x1,x2...xm}，Y={y1,y2...yn}兩個序列，Z={z1,z2...zk}是X和Y的任意一個LCS，那么
1.如果xm = yn，那么zk=xm=yn且Zk-1是Xm-1和Yn-1的一個LCS
2.如果xm != yn，那么zk != xm表示Z是Xm-1和Y的一個LCS
3.如果xm != yn，那么zk != yn表示Z是X和Yn-1的一個LCS
于是
用c[i,j]表示Xi和Yj的LCS長度，可以得到下面的公式
// 最長公共子序列
private static int lcsLenth(char[] x, char[] y) {
if (x.length == 0 || y.length == 0) {
return 0;
}
int m = x.length;
int n = y.length;
int[][] res = new int[m+1][n+1]; // 動態(tài)規(guī)劃典型用法，字典
for (int i = 1; i <= m; i++) {
for (int j = 1; j<= n; j++) {
if (x[i-1] == y[j-1]) {
res[i][j] = res[i-1][j-1] + 1;
}else if (res[i-1][j] > res[i][j-1]) {
res[i][j] = res[i-1][j];
}else {
res[i][j] = res[i][j-1];
}
}
}
return res[m][n];
}
例子四：最長公共子串
https://blog.csdn.net/u010397369/article/details/38979077
描述：給定兩個字符串X和Y，求最長公共子串，注意子串是連續(xù)了（上面說的子序列可以不連續(xù)）
思路：和求最長公共子序列相同的思路
我們定義S(i,j)表示“以xi和yj結(jié)尾的最長公共子串”，用c[i,j]表示其長度
那么
// 最長公共子串
private static int lcsLenth2(char[] x, char[] y) {
if (x.length == 0 || y.length == 0) {
return 0;
}
int m = x.length;
int n = y.length;
int[][] res = new int[m+1][n+1];
int max = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[i-1] == y[j-1]) {
res[i][j] = res[i-1][j-1] + 1;
if (res[i][j] > max) {
max = res[i][j];
}
}
}
}
return max;
}
上述方法需要一個mn的數(shù)組，空間復(fù)雜度可以優(yōu)化到O(1)
上述方法實(shí)際是計(jì)算了下面這個數(shù)組
我們可以遍歷每一條對角線，求出最大值，這樣只需要O(1)的空間
// 最長公共子串
private static int lcsLenth3(char[] x, char[] y) {
if (x.length == 0 || y.length == 0) {
return 0;
}
int i = x.length + y.length - 1;
int tem = 0; // 代替上面二維數(shù)組的臨時變量
int max = 0;
while (i > 0) { // 從矩形右上角，沿上邊和左邊，遍歷到左下角
int col = i > y.length ? (i-y.length) : 0; // 對角線起點(diǎn) 列
int row = i > y.length ? 0 : (y.length - i); // 對角線起點(diǎn) 行
while (col < x.length && row < y.length) {
if (x[col] == y[row]) {
tem++;
max = tem > max ? tem : max;
}else {
tem = 0;
}
col++;
row++;
}
i--;
}
return max;
}
例子五：01背包問題
描述：有N件物品和一個容量為V的背包。第i件物品的容量是c(i)，價值是v(i)。每種物品僅有一件，可以選擇放或不放。求解將哪些物品裝入背包可使價值總和最大。
思路：
f[i][j] = max{f[i-1][j], f[i-1][j-c(i)] + v(i)}
f[i][j]表示：“將前i件物品放入容量為j的背包中”的最大價值
考慮第i件物品，
1.背包單獨(dú)放不下，即j<c(i)
-- 此時f[i][j]=f(i-1,j)
2.背包單獨(dú)放的下，即j>=c(i)
-- 放，此時最大價值是，把前i-1個物品放入容量為j-c(i)的背包的最大價值，加上物品i的價值
-- 不放，此時最大價值是，把前i-1個物品放入容量為v的背包，f[i-1][j]
f[i][j] = max{f[i-1][j], f[i-1][j-c(i)] + v(i)}
// 01背包
private static int maxV(int[] c, int[] v, int pac) {
if (c.length == 0 || v.length == 0 || c.length != v.length) {
return -0;
}
int num = c.length; // 物品個數(shù)
int[][] maxV = new int[num+1][pac+1]; // 行號：物品號 列號：容量大小
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= pac; j++) {
if (j < c[i-1]) {
maxV[i][j] = maxV[i-1][j];
}else if (maxV[i-1][j] > maxV[i-1][j-c[i-1]] + v[i-1]) {
maxV[i][j] = maxV[i-1][j];
}else {
maxV[i][j] = maxV[i-1][j-c[i-1]] + v[i-1];
}
}
}
return maxV[num][pac];
}
public static void main(String[] args) {
int[] c = {4,5,6,2,2}; // 物品占用
int[] v = {6,4,5,3,6}; // 物品價值
maxV(c, v, 10);
}
