判斷鏈表是否有環(huán)

先搞清楚有環(huán)是什么意思尿招？鏈表的結(jié)構(gòu)是一環(huán)扣一環(huán)诀豁，每一環(huán)都有一個(gè)next指針窄刘，指向下一個(gè)節(jié)點(diǎn)，從頭開始往下遍歷舷胜，在遍歷過程中如果一個(gè)節(jié)點(diǎn)出現(xiàn)兩次娩践，則說明有環(huán)。

漫畫算法

一般來說，思路都是從頭開始遍歷翻伺，用一個(gè)哈希表hash來存儲(chǔ)遍歷過的節(jié)點(diǎn)的值材泄，遍歷的過程判斷hash中是否存在，如果存在穆趴，則說明有環(huán)脸爱。
看起來是不是很棒？只需要遍歷一次未妹，而且哈希表查找數(shù)據(jù)也是非常高效的簿废，如果最優(yōu)解是這樣，那該題就沒有存在的必要了络它。

小學(xué)數(shù)學(xué)題
在一個(gè)環(huán)形運(yùn)動(dòng)場族檬，兩個(gè)運(yùn)動(dòng)員，A速度1m/s化戳，B速度2m/s单料，環(huán)形運(yùn)動(dòng)場周長為400m，兩人同時(shí)起跑点楼，多久之后扫尖，B能夠再次與A相遇？

重點(diǎn)是掠廓，再次相遇换怖。說明了什么？在一個(gè)有限的環(huán)形閉合空間蟀瞧，起點(diǎn)相同沉颂，速度不一，是一定會(huì)相遇的悦污。

所以铸屉，我們可以以不同的遍歷單位（遍歷步長）來遍歷鏈表，然后判斷他們是否會(huì)相遇切端。如果相遇彻坛，則說明鏈表有環(huán)。

function isCircle(linkList: { data: number, next: any }): boolean {
  let first = linkList;
  let second = linkList;
  while (second && second.next) {
    first = first.next;
    second = second.next.next;
    if (first === second) {
      return true;
    }
  }
  return false;
}

計(jì)算環(huán)的長度

這個(gè)比較簡單踏枣，第一次相遇以后小压，開始統(tǒng)計(jì)長度，可以記錄下相遇的節(jié)點(diǎn)meet椰于，當(dāng)first節(jié)點(diǎn)再次等于meet時(shí)，說明環(huán)的長度計(jì)算完畢仪搔。也可以判斷兩個(gè)指針再次相遇瘾婿。

求鏈表中的入環(huán)節(jié)點(diǎn)

• 通過觀察有環(huán)鏈表的結(jié)構(gòu)，我們很容易發(fā)現(xiàn)，鏈表中只有一個(gè)節(jié)點(diǎn)是屬于其他兩個(gè)節(jié)點(diǎn)的next指針指向的對(duì)象偏陪，而這個(gè)節(jié)點(diǎn)就是入環(huán)節(jié)點(diǎn)抢呆。我們只需要遍歷鏈表，在這個(gè)過程中記錄每一個(gè)節(jié)點(diǎn)被上一個(gè)節(jié)點(diǎn)指向的次數(shù)（hash表中進(jìn)入存儲(chǔ)）笛谦，只要在寫入hash表之前發(fā)現(xiàn)已經(jīng)有相同的key抱虐，則說明該節(jié)點(diǎn)就是入環(huán)節(jié)點(diǎn)。

function isCircle(linkList: { data: number, next: any }) {
  let node = linkList;
  const hash = {};
  while (node && node.next) {
    node = node.next;
    if (hash[node.data]) {
      // 此時(shí)饥脑，該節(jié)點(diǎn)為第一個(gè)第二次作為next節(jié)點(diǎn)
      return node;
    }
    hash[node.data] = node;
  }
  return "無環(huán)";
}

• 還有一種數(shù)學(xué)思想的解法恳邀，需要配合圖來解答，稍微有點(diǎn)復(fù)雜
  

  image.png
  
  如圖可以得出等式：2 * (D + S1) = D + n * (S2 + S1)
  怎么來的呢灶轰？首先谣沸，在兩個(gè)指針首次相遇時(shí)，node1移動(dòng)的距離為：D + S1笋颤，這很明顯乳附。然后node2的速度是node1的兩倍，因此node2的移動(dòng)距離為2 * (D + S1)伴澄，這也沒有問題赋除。node2實(shí)際移動(dòng)距離是什么概念呢？既然它和node1相遇了非凌，那么它肯定已經(jīng)繞環(huán)超過一周了（參考運(yùn)動(dòng)場跑步問題）举农，具體是繞了幾周呢？我們也不能確定清焕，所以把它定成n周（n >= 1）并蝗。所以node2跑過的距離為D + n * (S2 + S1)

  最終得出D = (n - 1)(S1 + S2) + S2;再轉(zhuǎn)換一下，相當(dāng)于兩個(gè)速度相同的節(jié)點(diǎn)秸妥，一個(gè)從起點(diǎn)開始滚停，一個(gè)從首次相遇點(diǎn)出發(fā)，當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)粥惧，他們一定處于入環(huán)點(diǎn)键畴。

• 最優(yōu)解：入環(huán)點(diǎn)是鏈表在遍歷時(shí)第二次出現(xiàn)的首個(gè)節(jié)點(diǎn)。那么我們可以在遍歷的過程中突雪，每遍歷一個(gè)節(jié)點(diǎn)起惕，就修改其next指針指向頭節(jié)點(diǎn)，當(dāng)發(fā)現(xiàn)一個(gè)節(jié)點(diǎn)的next節(jié)點(diǎn)為頭節(jié)點(diǎn)時(shí)就說明該節(jié)點(diǎn)為入環(huán)節(jié)點(diǎn)咏删。這種方法將空間復(fù)雜度優(yōu)化到了O(1)惹想。

最大公約數(shù)

求兩個(gè)數(shù)的最大公約數(shù)：

• 獲取兩個(gè)數(shù)中最小數(shù)min，從min/2開始遍歷督函，遞減嘀粱，條件大于1激挪，直到能被兩個(gè)數(shù)同時(shí)整除。
  該方法比較容易理解锋叨，但是時(shí)間復(fù)雜度是O(min(a, b))垄分，在某些條件下（如10001、10000）需要遍歷很多次娃磺，效率較低
• 歐幾里得（輾轉(zhuǎn)相除法）
  最古老的算法薄湿，原理是兩個(gè)正整數(shù)a,b（a>b），他們的最大公約數(shù)為(a%b)與b的最大公約數(shù)偷卧，我們可以通過遞歸豺瘤，從而獲取結(jié)果。但是a%b的模運(yùn)算效率較低涯冠。
• 更相減損法
  《九章算術(shù)》中寫過炉奴，兩個(gè)數(shù)a,b（a>b），他們的最大公約數(shù)為(a-b)與b的最大公約數(shù)蛇更，也是遞歸瞻赶，可以獲取結(jié)果。但是派任，當(dāng)兩個(gè)數(shù)比較懸殊砸逊，運(yùn)算次數(shù)也無法進(jìn)行優(yōu)化。
• 最優(yōu)解
  輾轉(zhuǎn)相除法與更相減損法結(jié)合掌逛，再利用移位運(yùn)算的高性能师逸，（gcb(a, b)為求兩個(gè)數(shù)的最大公約數(shù)函數(shù)）
  • 1、兩個(gè)數(shù)都為偶數(shù)時(shí)豆混，得其最大公約數(shù)為2倍兩個(gè)數(shù)都做一次移位運(yùn)算之后求得的最大公約數(shù)篓像，gcb(a, b) = 2 x gcb(a>>1, b>>1)
  • 2、a為偶數(shù)皿伺，gcb(a, b) = gcb(a>>1, b)
  • 3员辩、b為偶數(shù)，gcb(a, b) = gcb(a, b>>1)
  • 4鸵鸥、都為奇數(shù)奠滑，兩個(gè)奇數(shù)相減，必得偶數(shù)妒穴，所以利用更相減損法宋税，可得gcb(a, b) = gcb(a-b, b)

function gcb(a, b) {
  if (a == b) {
    return a;
  }
  // 均為偶數(shù)
  if ((a & 1) == 0 && (b & 1) == 0) {
    // 相當(dāng)于gcb(a, b) = 2 * gcb(a/2, b/2)
    return gcb(a>>1, b>>1)<<1;
  }
  // a為偶數(shù)，b為奇數(shù)
  if ((a & 1) == 0) {
    return gcb(a>>1, b);
  }
  // a為奇數(shù)讼油，b為偶數(shù)
  if ((b & 1) == 0) {
    return gcb(a, b>>1);
  }
  // a杰赛、b都為奇數(shù)
  const big = a > b ? a : b;
  const small = a < b ? a : b;
  return gcb(big - small, small);
}
console.log(gcb(25, 5));

2的整數(shù)次冪

如何判斷一個(gè)正整數(shù)是否為2的整數(shù)次冪呢？我們可以將其循環(huán)除以2（可用移位運(yùn)算）矮台，看到最后結(jié)果是否為1乏屯，如果為1就說明是整數(shù)次冪阔墩。該解法的時(shí)間復(fù)雜度為O(logn)，看似已經(jīng)非常不錯(cuò)了瓶珊，但是，我們可以觀察耸彪，二進(jìn)制數(shù)伞芹，從2開始，不斷乘以2蝉娜，得到的結(jié)果是怎么樣唱较，
10
100
1000
......
可以得出，一個(gè)數(shù)若為2的整數(shù)次冪召川，那么它的二進(jìn)制表示南缓，只有首位是1，其他全為0

再觀察荧呐，如果上述數(shù)字都減一呢汉形？（為了更直觀，數(shù)前補(bǔ)0）
01
011
0111
......
除了補(bǔ)的0倍阐，每一位都為1概疆，所以我們發(fā)現(xiàn)一個(gè)為2的整數(shù)次冪的數(shù)n，與n-1峰搪，在二進(jìn)制表示中是對(duì)著干的岔冀，你為0，我就為1概耻，你為1使套，我就為0。
可以發(fā)現(xiàn)：n與n-1相與鞠柄，結(jié)果必然為0侦高，即

function isPowerOf2(num) {
  return （n & n-1) == 0;
}

是不是非常簡單呢？

無序數(shù)列排序后的最大相鄰差

• 1春锋、排序后矫膨，再遍歷找到最大相鄰差，這種方法簡單易懂期奔，但是時(shí)間復(fù)雜度最少為O(nlogn)侧馅，而且這個(gè)題目就不應(yīng)該這樣出了，直接出一個(gè)排序題不是更好呐萌？有些時(shí)候馁痴，我們?cè)谶x擇解法的時(shí)候，一定要結(jié)合題目描述來看肺孤，如果你的解法 雖然能夠得到正確結(jié)果罗晕，但是跟題目描述沒有緊密的聯(lián)系济欢，而且顯得有點(diǎn)“直接”，這時(shí)候應(yīng)該思考是不是還有更好的解法小渊。

• 2法褥、計(jì)數(shù)排序，可以很直觀的表示出數(shù)組在哪個(gè)區(qū)段有值酬屉，從而快速得到最大相鄰差半等。但是計(jì)數(shù)排序的缺陷是什么？數(shù)字相差太大的時(shí)候呐萨，會(huì)建立非常多無用的空數(shù)組元素杀饵，浪費(fèi)空間。

• 3谬擦、桶排序切距，還記得桶排序嗎？針對(duì)無序數(shù)組的個(gè)數(shù)和極值差來確定桶的個(gè)數(shù)和取值范圍惨远，從而盡可能均勻的對(duì)數(shù)組進(jìn)行排列谜悟。很大概率彌補(bǔ)了計(jì)數(shù)排序的短板。傳統(tǒng)的桶排序锨络，是需要對(duì)每一個(gè)桶內(nèi)部進(jìn)行排序的赌躺，但是在這里我們不需要，我們只需要判斷相鄰非空桶的極值差即可羡儿，為什么呢礼患？

  有的同學(xué)可能會(huì)覺得，萬一最大的相鄰差在同一個(gè)桶內(nèi)呢掠归？

  這其實(shí)是不可能出現(xiàn)的缅叠，因?yàn)橥暗膫€(gè)數(shù)已經(jīng)限制了，n個(gè)數(shù)對(duì)應(yīng)n個(gè)桶虏冻，上述情況必定有多于一個(gè)數(shù)在桶內(nèi)肤粱，那么必定存在空桶，而桶內(nèi)的極值差最大也就是單個(gè)桶的取值區(qū)間厨相，而相差一個(gè)空桶的兩個(gè)值领曼，它們的差一定更大。

function getMaxSortedDistance(list: number[]) {
  let max = list[0];
  let min = list[0];
  for (let i = 1; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i];
    }
    if (list[i] < min) {
      min = max;
    }
  }
  if (max == min) {
    return 0;
  }
  let d = max - min;
  // 生成桶
  const buckets = list.map(num => {
    return {
      max: null,
      min: null
    }
  });
  const itemDistance = d / (list.length - 1);
  // 插入桶蛮穿，并獲取每個(gè)桶的最大最小值
  for (let i = 0; i < list.length; i++) {
    const index = Math.floor((list[i] - min) / itemDistance);
    if (!buckets[index].max || buckets[index].max < list[i]) {
      buckets[index].max = list[i];
    }
    if (!buckets[index].min || buckets[index].min > list[i]) {
      buckets[index].min = list[i];
    }
  }
  // 遍歷桶庶骄，獲取桶的最大值與后續(xù)相鄰非空桶的最小值的差
  let maxDistance = 0;
  let leftMax = buckets[0].max;
  for (let i = 1; i < buckets.length; i++) {
    if (buckets[i].min == null) {
      continue;
    }
    if (buckets[i].min - leftMax > maxDistance) {
      maxDistance = buckets[i].min - leftMax;
    }
    leftMax = buckets[i].max;
  }
  return maxDistance;
}

棧實(shí)現(xiàn)隊(duì)列

棧的特點(diǎn)是？先進(jìn)后出践磅，隊(duì)列的特點(diǎn)是先進(jìn)先出单刁，如何用棧來實(shí)現(xiàn)隊(duì)列呢？
提示：兩個(gè)隊(duì)列

思想：解決出隊(duì)順序問題府适，雙重否定表肯定羔飞，棧的出棧順序和隊(duì)列的出隊(duì)順序是相反的肺樟，那么我們利用兩個(gè)棧，棧A用來模擬隊(duì)列的入隊(duì)操作逻淌，在出隊(duì)時(shí)么伯，將棧A中的元素依次出棧再進(jìn)入棧B（出一個(gè)進(jìn)一個(gè)），這時(shí)棧B中的元素順序是怎么樣的呢卡儒？是和棧A中相反的蹦狂。棧B出棧的時(shí)候，元素順序就和隊(duì)列的出隊(duì)順序一致了朋贬。

class ImitateQueueByStack {
  stackA = [];
  stackB = [];

  public enQueue(item) {
    this.stackA.push(item);
  }

  public deQueue() {
    if (this.stackB.length == 0) {
      if (this.stackA.length == 0) {
        return null;
      }
      while (this.stackA.length > 0) {
        this.stackB.push(this.stackA.pop());
      }
    }
    return this.stackB.pop();
  }
}

字典序算法（數(shù)字全排列中的后一位數(shù)）

如輸入123，全排列有123, 132, 213, 231, 312, 321窜骄。123的后一個(gè)數(shù)為132锦募，所以輸出132
數(shù)字從大到小有什么規(guī)律？huaji

• 從高位到低位邻遏，降序排列為全排列的最大值（321）
• 尋找全排列的后一位數(shù)糠亩，應(yīng)該保證高位盡量不變，調(diào)整低位的數(shù)字順序使得結(jié)果僅大于原數(shù)准验。

所以字典序算法步驟為：
1赎线、從右向左尋找第一個(gè)左數(shù)小于右數(shù)的數(shù)為target
2、從右向左尋找第一個(gè)大于target的數(shù)為exchangeItem
3糊饱、交換target和exchangeItem的位置
4垂寥、將交換后exchangeItem之后的數(shù)按從小到大順序排列（使得結(jié)果僅大于原數(shù)）

第四個(gè)步驟看似需要進(jìn)行排序坏匪，使得我們的時(shí)間復(fù)雜度提升浪秘，但是仔細(xì)一想，在1睛蛛、2步驟尋找的過程中夭坪，就已經(jīng)決定了target和exchangeItem交換后文判，exchangeItem之后的數(shù)字一定為降序排列，所以我們想要使其順序排列室梅，只需要將其倒置即可戏仓。

image.png

function dictionarySort2(num: number) {
  const list = num.toString().split("");
  // 找到第一個(gè)小于右鄰數(shù)的值
  let targetIndex: any = null;
  for (let i = list.length - 1; i > 0; i--) {
    const left = list[i - 1];
    const right = list[i];
    if (left < right) {
      targetIndex = i - 1;
      break;
    }
  }
  // 如果沒找到呢，說明整個(gè)數(shù)字都是降序排列的拆宛，說明是最大值
  if (targetIndex == null) {
    return "沒有比它更大的值了";
  }
  // 找到第一個(gè)比target大的數(shù)
  let exchangeItemIndex: any = null;
  for (let i = list.length - 1; i > 0; i--) {
    if (list[i] > targetIndex) {
      exchangeItemIndex = i;
      break;
    }
  }
  // 交換兩個(gè)值
  const temp = list[targetIndex];
  list[targetIndex] = list[exchangeItemIndex];
  list[exchangeItemIndex] = temp;
  // 手寫reverse
  for (let i = targetIndex + 1, j = list.length - 1; i < j; i++, j--) {
    const temp = list[i];
    list[i] = list[j];
    list[j] = temp;
  }
  // 大功告成
  return parseInt(list.join(""));
}

刪除n個(gè)數(shù)后的最小值（貪心算法）

一個(gè)數(shù)嗓奢，我想要?jiǎng)h除其中幾個(gè)數(shù)字，使得其值變得盡可能小浑厚，應(yīng)該怎么做呢股耽？

數(shù)字高位是決定數(shù)字大小的關(guān)鍵因素根盒，所以我們應(yīng)該盡可能地將高位數(shù)字降低，使得在相同位數(shù)的情況下物蝙，數(shù)字更小炎滞。
如346852，刪除一位數(shù)使其最小诬乞，應(yīng)該刪除哪個(gè)數(shù)呢册赛？沒錯(cuò)，應(yīng)該是從左往右的第一個(gè)比左鄰值大的數(shù)8震嫉，數(shù)就變成了34652森瘪。這時(shí)如果再刪一個(gè)呢？應(yīng)該刪除6票堵，變?yōu)?code>3452扼睬。

上述是兩次刪除一個(gè)數(shù)的結(jié)果，其實(shí)一次刪除兩個(gè)數(shù)的結(jié)果也就是上述的過程悴势，這樣依次求得局部最優(yōu)解從而求得全局最優(yōu)解的方法叫做貪心算法

按照上述的過程窗宇，我們一般會(huì)想到遍歷n次，每個(gè)過程中去刪除目標(biāo)數(shù)特纤，最終輸出結(jié)果
這樣的話军俊，假設(shè)數(shù)字長度為m，復(fù)雜度就為O(mn)捧存，代碼如下：

function greedSort(num: number, n: number) {
  if (n == 0) {
    return num;
  }
  const list = num.toString().split("");
  if (list.length <= n) {
    return 0;
  }
  while (n > 0) {
    let cut = false;
    for (let i = 1; i < list.length; i++) {
      if (list[i] < list[i - 1]) {
        list.splice(i - 1, 1);
        n--;
        cut = true;
        break;
      }
    }
    // 沒找到目標(biāo)數(shù)粪躬，則刪除最后一位
    if (!cut) {
      list.splice(-1, 1);
      n--;
    }
    console.log(n, list);
  }
  return parseInt(list.join(""));
}

其實(shí)，完全沒有必要像上述這樣來寫昔穴，在遍歷數(shù)字的過程中短蜕，即使刪除了一個(gè)數(shù)字，我們也并沒有污染已經(jīng)遍歷的數(shù)字傻咖，所以不需要再次從頭開始遍歷朋魔。因此我們只需要：

• 遍歷一次數(shù)字
• 每個(gè)遍歷過程中，將每個(gè)數(shù)字壓入一個(gè)棧內(nèi)卿操，如果遍歷的數(shù)字比棧頂元素小警检，說明棧頂元素需要被刪除，直接出棧害淤，n--扇雕，再將新元素壓入即可
• 遍歷完成后，如果n值還大于0窥摄，說明此時(shí)數(shù)字已經(jīng)是從左到右順序排列了镶奉，那直接從棧頂出棧剩余的n個(gè)元素即可。
• 將棧內(nèi)元素遍歷輸出即可

function greed(num: number, n: number) {
  if (n == 0) {
    return num;
  }
  const list = num.toString().split("");
  // 全部刪除肯定為0
  if (list.length == n) {
    return 0;
  }
  const stack = [];
  for (let i = 0; i < list.length; i++) {
    if (n > 0 && stack.length > 0 && list[i] < stack[stack.length - 1]) {
      stack.pop();
      n--;
    }
    stack.push(list[i]);
  }
  // 上述過程完成后，若刪除的數(shù)字個(gè)數(shù)不夠哨苛，直接從棧頂刪除即可（棧內(nèi)必定為順序排列）
  for (let i = n; i > 0; i--) {
    stack.pop();
  }
  return parseInt(stack.join(""));
}

金礦問題（動(dòng)態(tài)規(guī)劃）

問題描述：五座金礦鸽凶，10名工人，只能分配工人挖掘完整的金礦建峭，怎樣分配可以獲得最多的金子呢玻侥？如圖：

來源：漫畫算法

乍一看，無從下手亿蒸，總不能把所有可能性給列出來凑兰，然后再比較吧。

簡化一：5進(jìn)4

A這樣想：五座金礦边锁，就10個(gè)人姑食，反正也挖不完，要不我直接放棄第五座了茅坛，去前4座金礦中挖掘矢门；
B這樣想：我有10個(gè)人，直接分配5個(gè)人去挖第五座灰蛙，剩下的人再去前4座中挖。

此時(shí)A還有10個(gè)人隔躲，需要在4座金礦中選擇摩梧，B還有5個(gè)人，也要在4座金礦中選擇宣旱。

簡化二：4進(jìn)3

A-1：我還是放棄第四座仅父，選擇10個(gè)人去挖前三座；
A-2：我選擇分配5個(gè)人去挖第四座浑吟，剩下的人再去前三座挖笙纤；

B-1：我還是選擇分配5個(gè)人去挖第四座，剩下的人再去前三座挖组力；
B-2：我選擇放棄第四座省容，選擇5個(gè)人去挖前三座；

此時(shí)：金礦數(shù)量n燎字、剩余礦工w和到手金礦F存在這樣的關(guān)系：

        金礦(n)       剩余礦工(w)       收益(F)
A-1:      3             10            F(3, 10)
A-2:      2             5             F(2, 5) + 400kg(第四座的礦產(chǎn))
B-1:      2             0             F(2, 0) + 500kg(第五座的礦產(chǎn)) + 400kg(第四座的礦產(chǎn))
B-2:      3             5             F(3, 5) + 500kg(第五座的礦產(chǎn))

其中F(n, w)就代表了礦產(chǎn)收益和剩余金礦數(shù)量(n)和剩余礦工(w)之間的關(guān)系腥椒，相當(dāng)于是w個(gè)礦工最多可以從n座金礦中挖多少金子。

看一下B-1候衍，此時(shí)他已經(jīng)用完了所有的礦工（w為0）笼蛛，說明他從剩余的金礦中不可能再獲取多的金子了，那么他選擇的路走到頭了蛉鹿，即到達(dá)問題的邊界滨砍。

假設(shè)金礦總量存在一個(gè)數(shù)組里：

gold = [
  { f: 200, w: 3 },
  { f: 300, w: 4 },
  { f: 350, w: 3 },
  { f: 400, w: 5 },
  { f: 500, w: 5 }
]
// f代表該座金礦的收益，w為需要分配的礦工

狀態(tài)轉(zhuǎn)移方程：

1、邊界

再往下惋戏，還會(huì)有3進(jìn)2领追，2進(jìn)1，當(dāng)金礦數(shù)量或者礦工數(shù)量為0時(shí)日川，我們無法再往下進(jìn)行了蔓腐，此時(shí)

• 收益為：F(n, w) = 0
• 條件為：n = 0 或者 w = 0

2、一種子結(jié)構(gòu)

當(dāng)我們可以選擇是否放棄的金礦挖掘需要的人數(shù)超過我們剩余的礦工時(shí)龄句，那我們只能放棄回论，此時(shí)

• 收益為：F(n, w) = F(n - 1, w)
• 條件為：n >= 1，w < gold[n-1]

3分歇、兩種子結(jié)構(gòu)

像一開始一樣傀蓉，我們有足夠的實(shí)力去選擇，最終肯定要選擇收益最大的一種選擇职抡，所以

• 收益為：F(n, w) = max( F(n, w), F(n-1, w-gold[n-1].w) + gold[n-1].f )
• 條件為：n > 0, w > gold[n-1]

此時(shí)我們可以通過遞歸來完成整個(gè)過程：

// 遞歸
function recursiveDig(n: number, w: number, g: { f: number, w: number }[]) {
  if (n == 0 || w == 0) {
    return 0;
  }
  if (w < g[n-1].w) {
    return recursiveDig(n-1, w, g);
  }
  return Math.max(recursiveDig(n-1, w, g), recursiveDig(n-1, w-g[n-1].w, g) + g[n-1].f);
}

這個(gè)方法雖然簡潔明了葬燎，但是仔細(xì)觀察，我們可以發(fā)現(xiàn)它的時(shí)間復(fù)雜度達(dá)到了O(2^n)缚甩。
如果把全過程列出來谱净，可以發(fā)現(xiàn)很多次遞歸調(diào)用的參數(shù)是一樣的，說明做了一些重復(fù)的判斷擅威，這沒必要壕探。

自底向上求解

來源：漫畫算法

規(guī)律

觀察黃色的單元格杉畜，代表了9個(gè)礦工和4座金礦的最大收益纪蜒，那這個(gè)條件下有兩個(gè)子結(jié)構(gòu)：

• 3座金礦5個(gè)工人 + 第4座金礦的收益300；
• 4座金礦5個(gè)工人此叠。

那這兩個(gè)子結(jié)構(gòu)的結(jié)果怎么得出呢纯续？查看兩個(gè)綠色的單元格随珠，他們就分別代表了兩種子結(jié)構(gòu)。

所以除了第一行猬错，其他行的結(jié)果都依賴于其上一行窗看。我們?cè)谟?jì)算的過程中，只需要利用臨時(shí)變量存放上一行的數(shù)據(jù)倦炒，計(jì)算完當(dāng)前行結(jié)果后显沈，再將臨時(shí)變量更新

注意，這里在更新臨時(shí)變量時(shí)逢唤，我們需要從后往前拉讯，為什么呢？因?yàn)槿藬?shù)多的情況我們是拆分為多個(gè)人數(shù)少的結(jié)構(gòu)鳖藕，所以相當(dāng)于單行數(shù)據(jù)中魔慷，后面的結(jié)果是依賴于上一行前面的數(shù)據(jù)，要使用過后著恩，再將其更新院尔。

// 自底而上，為了理解方便喉誊，按數(shù)組索引 + 1來對(duì)應(yīng)人數(shù)和礦產(chǎn)數(shù)
function fromBottomDig(n: number, w: number, g: { f: number, w: number }[]) {
  // 上一行的收益
  const lastRow: number[] = [];
  for (let i = 1; i <= n; i++) {
    for (let j = w; j >= 1; j--) {
      const currentMineral = g[i];
      // 如果人數(shù)大于等于當(dāng)前金礦所需人數(shù)邀摆，獲取max(人數(shù)減去當(dāng)前金礦所需人數(shù)的最大收益 + 當(dāng)前金礦收益, 減少一座金礦人數(shù)不變的最大收益)
      if (j >= currentMineral.w) {
        // 人數(shù)減去當(dāng)前金礦所需人數(shù)的最大收益
        const minusWorkerF = lastRow[j - currentMineral.w] || 0;
        // 減少一座金礦人數(shù)不變的最大收益
        const sameWorkerF = lastRow[j] || 0;
        lastRow[j] = Math.max(minusWorkerF + currentMineral.f, sameWorkerF);
      }
    }
  }
  return lastRow[w] || 0;
}

尋找缺失整數(shù)

1、有99個(gè)不重復(fù)的整數(shù)伍茄，范圍從1-100栋盹，求出1-100中缺失的整數(shù)。

• 時(shí)間復(fù)雜度O(n)幻林，空間復(fù)雜度O(n)：
  大部分人應(yīng)該會(huì)想到，創(chuàng)建一個(gè)哈希表音念，遍歷1-100沪饺，添加對(duì)應(yīng)的key，再遍歷99個(gè)整數(shù)闷愤，遇到對(duì)應(yīng)的key整葡，就將其刪除，最終哈希表中只剩余一個(gè)key讥脐，那就是缺失的整數(shù)遭居。
• 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)：
  利用等差數(shù)列的求和公式旬渠，求出1-100的和俱萍，再依次減去99個(gè)整數(shù)，剩余的數(shù)就是缺失的告丢。是不是很簡單枪蘑。

2、若干個(gè)數(shù)，范圍1-100岳颇，其中有99個(gè)數(shù)都出現(xiàn)了偶數(shù)次照捡，只有一個(gè)數(shù)出現(xiàn)了奇數(shù)次，求該數(shù)
這里要用到異或運(yùn)算话侧，我在這篇文章講過栗精，異或的具體運(yùn)算，不懂的同學(xué)可以去看看瞻鹏。

• 大家注意這個(gè)偶數(shù)次悲立，兩個(gè)相同的數(shù)異或運(yùn)算是0，那么他們異或兩次呢乙漓？還是0级历，異或偶數(shù)次的結(jié)果一定是0。

• 0和任何數(shù)異或就是任何數(shù)叭披。

因?yàn)楫惢蜻\(yùn)算是符合交換律和結(jié)合律的寥殖，可以得出：所有數(shù)異或過后轉(zhuǎn)換成為了0和出現(xiàn)奇數(shù)次那個(gè)數(shù)的異或，那么就可以直接得到這個(gè)數(shù)涩蜘。

3嚼贡、若干個(gè)數(shù)，范圍1-100同诫，其中有98個(gè)數(shù)都出現(xiàn)了偶數(shù)次粤策，只有2個(gè)數(shù)（A、B）出現(xiàn)了奇數(shù)次误窖，求該數(shù)
此時(shí)我們將所有數(shù)異或后的結(jié)果變成了什么叮盘？沒錯(cuò)，變成了A和B的異或結(jié)果霹俺。這有什么用呢柔吼？異或是找不同，說明了通過這個(gè)結(jié)果丙唧，我們可以得出A與B不同的地方愈魏，比如說數(shù)組[3, 4, 3, 4, 5, 7, 8, 8, 7, 9]，異或后的結(jié)果是5和9的異或結(jié)果5 ^ 9 = 0101B ^ 1001B = 1100B那說明5和9在二進(jìn)制表示中想际，倒數(shù)第三位是不同的培漏，那么必定存在一個(gè)數(shù)的倒數(shù)第三位是1，另一個(gè)是0胡本。

分治法牌柄，我們可以將這個(gè)題的計(jì)算轉(zhuǎn)換成兩個(gè)第2題的計(jì)算。
遍歷所有數(shù)字侧甫，將倒數(shù)第三位是1的分為一批友鼻，是0的分為一批傻昙，其中AB肯定是處在不同的批次內(nèi)，那么將其分別依次異或彩扔，即可得到AB的值妆档。

• 從低位到高位，如何找到第一個(gè)不同位
  將一個(gè)數(shù)字和1相與（&）虫碉，若結(jié)果為0贾惦，則該數(shù)最低位不為1，和2（10B）相與結(jié)果為0敦捧，則說明倒數(shù)第二位也是0须板，和4（100B）相與，若結(jié)果為1兢卵，則說明倒數(shù)第三位為1习瑰。說明從1開始，相與秽荤，不等于1再向左移位甜奄，最終可以確定從右向左第幾位為1
• 遍歷數(shù)組，分為兩批窃款，一批包含A课兄，一批包含B，這個(gè)過程中可以進(jìn)行異或運(yùn)算晨继，最終得到結(jié)果

function findLostNum(list: number[]) {
  let diff = 0;
  for (let i = 0; i < list.length; i++) {
    diff = (diff ^ list[i]);
  }
  console.log("AB差異值：", diff);
  let separator = 1;
  while ((separator & diff) == 0) {
    separator<<=1;
  }
  console.log("分批標(biāo)志：", separator);
  const res = [0, 0];
  for (let i = 0; i < list.length; i++) {
    if ((separator & list[i]) == 0) {
      res[0] = (list[i] ^ res[0]);
    } else {
      res[1] = (list[i] ^ res[1]);
    }
  }
  return res;
}

暫時(shí)先寫到這吧烟阐，算法無窮無盡。