資訊專(zhuān)欄INFORMATION COLUMN
摘要：題意找出以某些數(shù)為公因數(shù)的遞增排序的第個(gè)數(shù)條件維護(hù)了的元素的相乘因素的。由于是最小值，所以每次保留最小的。問(wèn)題轉(zhuǎn)化，多次迭代，變成，處理對(duì)象變了。不重復(fù)的思想找出重復(fù)計(jì)算的地方，找出不重復(fù)計(jì)算的方法，用極值約束，加以記錄。
題意：找出以某些數(shù)為公因數(shù)的 遞增排序的第n個(gè)數(shù)
條件：indexes 維護(hù)了 primes的元素的相乘因素（uglies）的index。
思路：每次從 primes的遍歷*中，找出最小的一個(gè)ugly，添加到uglies中去，然后將 indexes維護(hù)的primes的相乘對(duì)象的索引表中，找出這個(gè)，+1.
應(yīng)用： 每次只變動(dòng)一個(gè)數(shù)的思想。 相乘時(shí)候，遍歷primes是循環(huán)進(jìn)行的。 相乘的對(duì)象 是 primes的各個(gè)元素，也是uglies中的所有元素。
由于是最小值，所以每次保留最小的。 每次找出 得到最小值的prime的index，+1，方便下次迭代。
問(wèn)題轉(zhuǎn)化， primeprime==》多次迭代，變成 uglyprime， 處理對(duì)象變了。
每個(gè)prime每次*的對(duì)象，有可能反復(fù)是同一個(gè)數(shù)，所以用indexes記錄走到的位置。避免重復(fù)。
不重復(fù)的思想：找出重復(fù)計(jì)算的地方，找出不重復(fù)計(jì)算的方法，用極值約束，index加以記錄。沒(méi)有找到思路原因： 沒(méi)有將問(wèn)題建模，抽象為 prime*ugly 的迭代過(guò)程+每次一個(gè)最小值的比較。 索引記錄prime的迭代位置。
class Solution:
def nthSuperUglyNumber(self, n, primes):
uglies=[1]
indexes=[0]*len(primes)
while len(uglies)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/42296.html
摘要：滾動(dòng)求最大值復(fù)雜度考慮一個(gè)，的值是下一個(gè)可能的替補(bǔ)值。思路數(shù)組中保存的是之前保留到的值，因?yàn)橄乱粋€(gè)可能的值是和之前的值的倍數(shù)關(guān)系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...
摘要：題目解答這個(gè)問(wèn)題最主要的就是如果按順序找出那么我們?nèi)绻芟氲桨岩詾橐蜃拥倪@些分成三個(gè)然后在每次輸出時(shí)取里最小的那個(gè)數(shù)輸出就可以解決了。 264 Ugly NumberII題目：Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only i...
摘要：建兩個(gè)新數(shù)組，一個(gè)存數(shù)，一個(gè)存。數(shù)組中所有元素初值都是。實(shí)現(xiàn)的過(guò)程是，一個(gè)循環(huán)里包含兩個(gè)子循環(huán)。兩個(gè)子循環(huán)的作用分別是，遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積，結(jié)果與相同的，就將加，即跳過(guò)這個(gè)結(jié)果相同結(jié)果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...
摘要：如果有一個(gè)方法能夠順序只生成丑陋數(shù)就好了。仔細(xì)觀察可以發(fā)現(xiàn)，丑陋數(shù)的因子也必定是丑陋數(shù)，它一定是某個(gè)丑陋數(shù)乘得到的。不過(guò)，我們可以確定的是，小的丑陋數(shù)乘，肯定小于大的丑陋數(shù)乘。 Ugly Number I Write a program to check whether a given number is an ugly number. Ugly numbers are positi...
摘要：每次出一個(gè)數(shù)，就把這個(gè)數(shù)的結(jié)果都放進(jìn)去。，指針從個(gè)變成個(gè)。的做法參考還是復(fù)雜度的問(wèn)題，回頭再看看 264. Ugly Number II 題目鏈接：https://leetcode.com/problems... dp的方法參考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...
閱讀 1613·2021-09-23 11:31
閱讀 929·2021-09-23 11:22
閱讀 1353·2021-09-22 15:41
閱讀 4085·2021-09-03 10:28
閱讀 2918·2019-08-30 15:55
閱讀 3549·2019-08-30 15:55
閱讀 1966·2019-08-30 15:44
閱讀 2728·2019-08-30 13:50
