譯者序

譯者認為這是一本非常好的入門書籍。因為內(nèi)容通俗易懂、編排用心，沒有太多數(shù)學和編程基礎的人也能看懂。沒有介紹像動態(tài)規(guī)劃這樣的重要思想算是一個遺憾。

前言

本書的配套網(wǎng)站 algs4.cs.princeton.edu 提供了豐富的關于數(shù)據(jù)結(jié)構(gòu)和算法的資料。

TODO 進行探索，看是否能將網(wǎng)站和圖書結(jié)合起來使用。

第1章 基礎

本章介紹學習算法和數(shù)據(jù)結(jié)構(gòu)所需要的基本工具：

• 首先介紹的是基礎編程模型，即Java語言的基本使用
• 接下來是數(shù)據(jù)抽象并定義抽象數(shù)據(jù)類型以進行模塊化編程
• 之后學習三種基礎的抽象數(shù)據(jù)類型：背包、隊列、棧
• 最后描述了分析算法性能的方法，并且給出了一個案例分析

我們關注的大多數(shù)算法都需要適當?shù)亟M織數(shù)據(jù)，由此產(chǎn)生了數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法的關系十分密切，作者的觀點是它是算法的副產(chǎn)品或結(jié)果。理解算法必須學習數(shù)據(jù)結(jié)構(gòu)，因此本書中會討論多數(shù)數(shù)據(jù)結(jié)構(gòu)的性質(zhì)。

學習算法的原因是它們能夠節(jié)約非常多的資源，甚至能讓我們完成一些本不可能完成的任務，精心設計的算法在任何領域都是解決大型問題的最有效的方法。本書的焦點就在那些復雜算法分解后的子問題的算法，他們是被證實為在很多領域內(nèi)是解決困難問題的有效方法。

1.1 基礎編程模型

1.1.1-1.1.10

略，因為自己有過使用Java的經(jīng)驗，并且預備使用JavaScript實現(xiàn)算法因此略過該部分

基礎練習

13. 編寫一段代碼，打印出一個M行N列的二維數(shù)組的轉(zhuǎn)制（交換行和列）。

/* Analyze
    
    先遍歷行，會先把每一行的所有列號的下標暴露
    反過來，先遍歷列，會先把每一列的所有行號暴露
    但是取值仍舊要將行號放在前面，列號放在后面，這是由2維數(shù)組的存儲結(jié)構(gòu)決定的
*/

// JavaScript Impl
function reversePrint(array, M, N) {
  for (let i = 0; i < N; i++) {
    let line = '';
    for (let j = 0; j < M; j++) {
      line += (array[j][i] + ' ');
    }
    console.log(line);
  }
}

// Test 
var array = [
  [11, 12, 13],
  [21, 22, 23]
];
var M = 2,  N = 3;
reversePrint(array, M, N)

// Test Output
// 11 21 
// 12 22 
// 13 23 

14編寫一個靜態(tài)方法lg(), 接受一個整形參數(shù)N，返回不大于log2N的最大整數(shù)。

/* Analyze

數(shù)值初始為2，操作次數(shù)為1
連續(xù)做乘以2的操作，直到大于N（<=N要繼續(xù)做乘法）
返回 `操作次數(shù)-1` 作為返回結(jié)果

*/

function f(){}

// JavaScript Impl
function lg(N) {

  if(N == 1) return 0;
  
  var value = 2, result = 1;

  while(value <= N) {
    result += 1;
    value *= 2;
  }
  return result - 1;
}

// Test
lg(1) // 0
lg(2) // 1
lg(4) // 2
lg(1025) // 10

16. 給出exR1(6)的返回值：

//Java Define
public static String exR1(int n) {
    if(n <= 0) return "";
    return exR1(n-3) + n + exR1(n-2) + n;
}

// JavaScript
function exR1(int n) {
    if(n <= 0) return "";
    return exR1(n-3) + n + exR1(n-2) + n;
}

// Calculate
        e6
    e3 + 6 + e4 + 6
    (e0 + 3 + e1 + 3) + 6 + (e1 + 4 + e2 + 4) + 6
    (e0 + 3 + (e-2 + 1 + e-1 + 1) + 3) + ((e-2 + 1 + e-1 + 1) + 4 + (e-1 + 2 + e0 + 2) + 4 ) + 6  
    3+1+1+3+1+1+4+2+2+4+6
    result: 31131142246

// Execute Result

    311361142246

    Miss a 6 in third step

17. 找出以下函數(shù)的問題

//Java Define
public static String exR1(int n) {
    String s =  exR1(n-3) + n + exR1(n-2) + n;
    if(n <= 0) return "";
    return s;
}

exR2會永遠循環(huán)調(diào)用，退出代碼 n <= 0 永遠不會被執(zhí)行

18. 略

本題執(zhí)行結(jié)果會有6次左右的遞歸運算，但是連續(xù)的乘法使結(jié)果變得非常大。作者嘗試用一道練習題來告訴我們，遞歸可能導致最終的運算結(jié)果非常大，使用時候需要評估運算量。

19. 在計算機上運行以下程序

// JavaScript Define
function fibonacci(n) {
  if(n === 0 || n === 1) return n;
  return fibonacci(n-1) + fibonacci(n - 2);
}
for (let i = 0; i < 100; i++) {
  console.log(i + ' ' + fibonacci(i));
}

計算機上運行這段程序1小時所能得到的N的最大值是多少？開發(fā)一個更好的實現(xiàn)，用數(shù)組保存已經(jīng)計算的值。

// JavaScript Update One
for (let i =0; i < 100; i++) {
  var start = new Date();
  let result = fibonacci(i);
  var end = new Date();
  console.log(i + ' ' + (end.getTime() - start.getTime())/1000 + ' ' + result)
}

答：嘗試記錄每次調(diào)用 fibonacci 的執(zhí)行時間，發(fā)現(xiàn)從45開始，執(zhí)行時間已經(jīng)長達16s，并且N每加1，執(zhí)行時間近乎是成倍的執(zhí)行時間，必須減少重復運算來提高執(zhí)行效率，目測很可能1小時下只能執(zhí)行到54左右。優(yōu)化后的代碼如下（執(zhí)行時間不到1秒）：

// JavaScript Update Two
var caches = new Array(100);
function fibonacci(n) {
  if(chaches[n]) return caches[n];
  if(n === 0 || n === 1) return n;
  return fibonacci(n-1) + fibonacci(n - 2);
}
for (let i = 0; i < 100; i++) {
  var start = new Date();
  let result = caches[i] = fibonacci(i);
  var end = new Date();
  console.log(i + ' ' + (end.getTime() - start.getTime())/1000 + ' ' + result)
}

20. 編寫一個遞歸的靜態(tài)方法計算ln(N!)的值

基礎的數(shù)學知識(百度百科)：

• a的x次方等于N（a>0，且a不等于1），那么數(shù)x叫做以a為底N的對數(shù)，記作x=logaN。其中，a叫做對數(shù)的底數(shù)，N叫做真數(shù)。
• 自然對數(shù) 以無理數(shù)e為底 記為ln。
• 常用對數(shù) 以10為底的對數(shù) 記為lg。

對數(shù)基本公式

//JavaScript 
function ln(N) {
    if(N == 1) return 0;
    return Math.log(N) + ln(N-1);
}

24. 給出使用歐幾里得算法計算102

// JavaScript 
function euclid(p, q) {
    if(q > p) {var t = p; p = q; q = t}
    console.log(p + ','+ q);
    if(q == 0) return p;
    return euclid(q,p-q);
}


euclid(102,24)
// 102,24
// 78,24
// 54,24
// 30,24
// 24,6
// 18,6
// 12,6
// 6,6
// 6,0

euclid(1 111 111， 1 234 567);
//...
//Uncaught RangeError: Maximum call stack size exceeded


對應地將 `p-q` 改為  `p%q`，因為p和q差值巨大的時候，會大量的時間用于遞歸。

25. 數(shù)學歸納法證明歐幾里得算法那能夠?qū)θ我庖环秦撜麛?shù)的 p 和 q 的最大公約數(shù)。

假設：p, q的最大公約是是r，假定p >= q

證明：

p/r = p1(整數(shù))
q/r = q1(整數(shù))

(p-q)/r=p1-q1 同樣為整數(shù)
那么 p 和 p-q 的最大公約數(shù)也是r

如果其中p-q為0，那么r 的值即等于此時的p的值

提高題

27. 二項分布。估計用以下代碼計算 binomial(100, 50, 0.25)將會產(chǎn)生的遞歸調(diào)用次數(shù)，將已經(jīng)計算過的值保存在數(shù)組中并給出一個更好的實現(xiàn)。

// JavaScript Slow
function binomial(N, k, p) {
    if(N == 0 && k == 0) return 1.0;
    if(N < 0 || K < 0) return 0.0;
    return (1.0-p) * binomial(N-1, k, p) + p * binomial(N-1, k-1, p);
}

binomial(5,  2,  .25); // 0.263671875
binomial(5, 3, .25); // 0.087890625
binomial(5, 0, .25); // 0.2373046875
binomial(5, 5, .25); // 9.765625E-4

// JavaScript Quick
function binomial(N, k, p) {
  var mArray = new Array(N + 1);
  for (let i = 0; i <= N; i++) {
    mArray[i] =  new Array(k + 1);
  }
  mArray[0][0] = 1;

  for (let i = 1; i <= N; i++) {
    mArray[i][0] = (1-p)*mArray[i-1][0];
  }
  for (let i = 1; i <= k; i++) {
    mArray[0][i] = 0;
  }

  for (let i = 1; i <= k; i++) {
    for (let j = 1; j <= N; j++) {
      mArray[j][i] = (1-p)*mArray[j-1][i] + p*mArray[j-1][i-1];
    }
  }
  console.log(mArray[N][k]);
}

29. 等值鍵。為BinarySearch類添加一個靜態(tài)方法rank(key, a)，它接受一個鍵和一個整形有序數(shù)組（可能存在重復鍵）作為參數(shù)返回數(shù)組中小于該鍵的元素數(shù)量，以及一個類似的方法count(key, a)返回該數(shù)組中等于該鍵的元素的數(shù)量。

// JavaScript
function rank(key, a) {
  var lo = 0, ro = a.length - 1;
  var mo = -1;
  var li = 0;
  while(lo <= ro) {
    li ++;
    if(li == 1000) break;
    var mid = parseInt((lo + ro) / 2);
    if(a[mid] >= key) {
      ro = mid - 1;
    } else if(a[mid] < key) {
      mo = mid;
      lo = mid + 1;
    }
  }
  return mo;
}

console.log(rank(1, [1,1,2,2,2,3,3,3,3])); // -1
console.log(rank(2, [1,1,2,2,2,3,3,3,3])); // 1
console.log(rank(4, [1,1,2,2,2,3,3,3,3])); // 8
console.log(rank(3, [1,1,2,2,2,3,3,3,3])); // 4
console.log(rank(11, [1,3,5,7,9,11,11,15,19])); // 4 

function count(key, a) {
  var lo = 0, ro = a.length - 1;
  var mo1 = -1, mo2 = -1;
  while(lo <= ro) {
    var mid = parseInt((lo + ro) / 2);
    if(a[mid] >= key) {
      ro = mid - 1;
    } else  {
      mo1 = mid;
      lo = mid + 1;
    }
  }

  lo = 0, ro = a.length - 1;
  while(lo <= ro) {
    var mid = parseInt((lo + ro) / 2);
    if(a[mid] <= key) {
      lo = mid + 1;
    } else  {
      mo2 = mid;
      ro = mid - 1;
    }
  }
  if(mo1 == -1 && mo2 == -1) return 0;
  else if(mo1 == -1) return mo2 + 1;
  else if(mo2 == -1) return a.length - (mo1 + 1);
  else return mo2 - mo1 - 1;
}
console.log(count(5, [1,2,3,4,5,6])) // 1
console.log(count(5, [1,2,5,5,5,6])) // 3
console.log(count(8, [1,2,5,5,5,6])) // 0