修改3SUM算法不與浮點

-1

所以我一直試圖解決的問題3SUM很好工作，下面是我的算法修改3SUM算法不與浮點

def findThree(seq, goal): 
    for x in range(len(seq)-1): 

     left = x+1 
     right = len(seq)-1 

     while (left < right): 
      tmp = seq[left] + seq[right] + seq[x] 
      if tmp > goal: 
       right -= 1 
      elif tmp < goal: 
       left += 1 
      else: 
       return [seq[left],seq[right],seq[x]]

正如你可以看到它是一個非常通用的算法，解決它在O（n ）。

我一直在經歷的問題是，這個算法似乎不喜歡使用浮點數。

爲了測試我的理論是正確的，我給它下面的兩個陣列

FloatingArr = [89.95, 120.0, 140.0, 179.95, 199.95, 259.95, 259.95, 259.95, 320.0, 320.0] 
IntArr = [89, 120, 140, 179, 199, 259, 259, 259, 320, 320] 


findThree(FloatingArr, 779.85) // I want it to return [259.95, 259.95, 259,95] 
>> None // Fail 
findThree(FloatingArr, 777) // I want it to return [259,259,259] 
>> [259, 259, 259] // Success

該算法的工作，但它似乎並不浮點數很好地工作。我能做些什麼來解決這個問題？

有關其他信息，我的第一個數組原本是價格字符串的列表，但爲了與他們做數學計算，我不得不去掉「$」符號。我的做法是這樣的

for x in range(len(prices)): 
    prices[x] = float(prices[x][1:]) // return all the prices without the "$" sign. Casting them to float.

如果有更好的方法，請讓我知道。我感覺好像這個問題不是真的findThree（）而是我如何修改原始價格數組。

編輯：看到這確實是一個浮點問題，我想我的下一個問題是什麼是脫離「$」後將字符串轉換爲int的最佳方法？

來源

2014-09-21 user3277633

'0。1 + 0.2！= 0.3'。閱讀[浮點舍入問題]（http://floating-point-gui.de/basic/）。 – user2357112 2014-09-21 18:00:28

價格最初是如何儲存的（使用何種格式）？ – kraskevich 2014-09-21 18:09:01

@ user2040251原來是這樣的['$ 120.00'，'$ 140.00'，'$ 179.95'，'$ 199.95'，'$ 259.95'，'$ 259.95'，'$ 259.95'，'$ 320.00'，'$ 320.00'，'$ 89.95'] – user3277633 2014-09-21 18:15:35

它不起作用，因爲89.95等數字通常無法準確存儲（因爲0.95的基數二表示是重複的十進制數）。

通常，在處理浮點數時，不要通過==比較完全相等，而要檢查數字是否「足夠接近」以使其相等;通常使用abs(a - b) < SOME_THRESHOLD完成。 SOME_THRESHOLD的確切值取決於您想要的準確程度，並且通常需要反覆試驗以獲得良好的價值。

在您的具體情況，因爲你用美元和美分的工作，你可以簡單地轉換爲美分乘以100，並四捨五入到整數（通過round，因爲int會即7.999999四捨五入至7）。那麼，你的一組數字將只是整數，解決舍入問題。

來源

2014-09-21 18:00:48

由於諸如「0.07 * 100！= 7.0」的問題，乘以100可能不夠。 – user2357112 2014-09-21 18:03:15

@ user2357112已修復 – 2014-09-21 18:07:15

您可以將您的價格從字符串轉換爲整數，而不是將它們轉換爲浮點數。假設所有價格在小數點後最多有k位（初始字符串表示形式）。然後10^k * price總是一個整數。所以你完全可以擺脫浮點運算。

示例：如果小數點後最多有兩位數，則$2.10變爲210，並且$2.2變爲220。即使在中間計算中也不需要使用float，因爲可以將小數點右移兩位（如果需要，可以附加零），然後直接將字符串轉換爲整數。

這裏是轉換函數的示例：

def convert(price, max_digits): 
    """ price - a string representation of the price 
     max_digits - maximum number of digits after a decimal point 
        among all prices 
    """ 
    parts = price[1:].split('.') 
    if len(parts) == 2 and len(parts[1]) > 0: 
     return int(parts[0]) * 10 ** max_digits + \ 
       int(parts[1]) * 10 ** (max_digits - len(parts[1])) 
    else: 
     return int(parts[0]) * 10 ** max_digits

來源

2014-09-21 18:16:47 kraskevich

修改3SUM算法不與浮點

回答

相關問題