2020-11-26 經(jīng)典算法問題

判斷鏈表是否有環(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ù)字一定為降序排列,所以我們想要使其順序排列室梅,只需要將其倒置即可戏仓。

手寫一個(gè)reverse,我尋思對(duì)于各位大佬來說亡鼠,這不是有手就行赏殃?
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ù)的判斷擅威,這沒必要壕探。

自底向上求解

來源:漫畫算法

遞歸的過程我們是從n到1,現(xiàn)在我們從1開始郊丛,如圖李请,第一行。從只有一個(gè)工人和一座金礦開始統(tǒng)計(jì)厉熟,最后延伸到我們題目的條件导盅,五座金礦,十個(gè)工人揍瑟。每個(gè)單元格代表了其所處行數(shù)有n座金礦白翻,其所處列數(shù)有w個(gè)礦工時(shí)的最大收益。因此绢片,table[5][10]代表了我們的最大收益嘁字,也就是900。

規(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í)先寫到這吧烟阐,算法無窮無盡。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末紊扬,一起剝皮案震驚了整個(gè)濱河市蜒茄,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌餐屎,老刑警劉巖檀葛,帶你破解...
    沈念sama閱讀 222,464評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異啤挎,居然都是意外死亡驻谆,警方通過查閱死者的電腦和手機(jī)卵凑,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,033評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門庆聘,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人勺卢,你說我怎么就攤上這事伙判。” “怎么了黑忱?”我有些...
    開封第一講書人閱讀 169,078評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵宴抚,是天一觀的道長勒魔。 經(jīng)常有香客問我,道長菇曲,這世上最難降的妖魔是什么冠绢? 我笑而不...
    開封第一講書人閱讀 59,979評(píng)論 1 299
  • 正文 為了忘掉前任,我火速辦了婚禮常潮,結(jié)果婚禮上弟胀,老公的妹妹穿的比我還像新娘。我一直安慰自己喊式,他們只是感情好孵户,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,001評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著岔留,像睡著了一般夏哭。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上献联,一...
    開封第一講書人閱讀 52,584評(píng)論 1 312
  • 那天竖配,我揣著相機(jī)與錄音,去河邊找鬼酱固。 笑死械念,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的运悲。 我是一名探鬼主播龄减,決...
    沈念sama閱讀 41,085評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼班眯!你這毒婦竟也來了希停?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,023評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤署隘,失蹤者是張志新(化名)和其女友劉穎宠能,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體磁餐,經(jīng)...
    沈念sama閱讀 46,555評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡违崇,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,626評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了诊霹。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片羞延。...
    茶點(diǎn)故事閱讀 40,769評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖脾还,靈堂內(nèi)的尸體忽然破棺而出伴箩,到底是詐尸還是另有隱情,我是刑警寧澤鄙漏,帶...
    沈念sama閱讀 36,439評(píng)論 5 351
  • 正文 年R本政府宣布嗤谚,位于F島的核電站棺蛛,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏巩步。R本人自食惡果不足惜旁赊,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,115評(píng)論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望椅野。 院中可真熱鬧彤恶,春花似錦、人聲如沸鳄橘。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽瘫怜。三九已至术徊,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間鲸湃,已是汗流浹背赠涮。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評(píng)論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留暗挑,地道東北人笋除。 一個(gè)月前我還...
    沈念sama閱讀 49,191評(píng)論 3 378
  • 正文 我出身青樓,卻偏偏與公主長得像炸裆,于是被迫代替她去往敵國和親垃它。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,781評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容