亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

谷歌Foobar:次優解中的邏輯錯誤

谷歌Foobar:次優解中的邏輯錯誤

白衣非少年 2022-08-16 15:28:25
問題編寫一個函數 answer(l),該函數采用正整數列表 l 并計算 (lst[i], lst[j], lst[k]) 的“幸運三元組”的數量,其中 i < j < k。l 的長度介于 2 和 2000 之間(含)。l 的元素介于 1 和 999999之間。答案適合有符號的 32 位整數。一些列表是故意生成的,沒有任何訪問代碼來甩掉間諜,因此如果沒有找到三元組,則返回0。幸運三元組基本上是元組(x,y,z),其中x除以y,y除以z,例如(1,2,4)。例如,[1, 2, 3, 4, 5, 6]具有三元組:[1, 2, 4],[1, 2, 6],[1, 3, 6],使答案總計3。我的代碼def isLuckyTriple(a,b,c):    if b%a==0 and c%b==0:        return True    return Falsedef solution(l):    count=0    l=sorted(l)    for i in range(len(l)-2):        for j in range(i+1,len(l)-1):            for k in range(j+1,len(l)):                if isLuckyTriple(l[i],l[j],l[k]):                    count+=1    return count我的問題我已經查看了一些關于這個問題的堆棧溢出答案。我知道如何以不同和更優化的方式做到這一點。唯一的問題是,我的上述代碼只通過了5個給定測試用例中的2個測試用例。我想了解我在上面的代碼中做錯了什么。我更感興趣的是找出我的錯誤,而不是以更好的方式去做。如果您不認為代碼不正確,那么它是否因為解決方案非常慢而使測試用例失???任何幫助將不勝感激。
查看完整描述

3 回答

?
蠱毒傳說

TA貢獻1895條經驗 獲得超3個贊

每個問題都有時間限制,我認為大約是15秒。據我所知,所有測試用例在驗證時并行運行,如果超過15秒,測試用例將失敗。具有O(n^3)時間復雜度肯定會使測試用例失敗。


查看完整回答
反對 回復 2022-08-16
?
函數式編程

TA貢獻1807條經驗 獲得超9個贊

def answer(l):

    triples_count=0


    p=len(l)

    print l

    for i in xrange(p-2):

        for j in xrange(i+1, p-1):

            if l[j] % l[i] == 0:

                for k in xrange(j+1, p):

                    if l[k] % l[j] == 0:

                        #print l[i], l[j], l[k]

                        triples_count=triples_count+1

    return(triples_count)


查看完整回答
反對 回復 2022-08-16
?
素胚勾勒不出你

TA貢獻1827條經驗 獲得超9個贊

刪除步驟,因為它會更改數字索引的順序,因為其中一個約束說 。l=sorted(l)i < j < k


考慮以下情況:


4 2 1


答案應該是,但您的代碼將返回。01


關于效率,您可以計算每個數字從右側除以多少個數字。對于每個計數,如下所示:1,2,3,4,5,6


1 2 3 4 5 6

5 2 1 0 0 0 

對于 ,當你來到 時,已經在緩存的數組中,所以現在你有2個三元組添加到最終答案中。當你來到時,你會得到三胞胎,所以=。1222132+13


時間復雜度:O(n^2)


空間復雜度:O(n)


因為,問題說,我認為你可以走階乘的方式。The elements of l are between 1 and 999999 inclusive


首先收集映射中的所有值計數。


現在,對每個數字進行每個倍數,并將三元組從最后一個添加到第一個。如下圖所示:


triplet_map = {}

map = {}

for every number in array: # from last to first

   if number in triplet_map:

       triplets += triplet_map(number)

       continue

   cnt = 0

   for(i = number; i < 1000000; i *= number) 

     if i in map:

         if map(i) > 0: 

           cnt += map(i)

     map(number,map(number) + 1)

   triplets += cnt

   triplet_map(number,cnt)

這樣,它就像每個數字的對數時間。沒有測試這么多,但似乎有效。


查看完整回答
反對 回復 2022-08-16
  • 3 回答
  • 0 關注
  • 132 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號