LintCode刷起來（一）

1. A + B 問題

• 方法一：

class Solution:"""@param a: An integer@param b: An integer@return: The sum of a and b """def aplusb(self, a, b):# write your code herereturn a + b

• 方法二：

class Solution:"""@param a: An integer@param b: An integer@return: The sum of a and b """def aplusb(self, a, b):# write your code herereturn sum([a, b])

• 方法三：

from operator import addclass Solution:"""@param a: An integer@param b: An integer@return: The sum of a and b """def aplusb(self, a, b):# write your code herereturn add(a, b)

2 · 尾部的零

大佬救命，大佬饒命
大佬還是大佬，太強了。想要知道有多少個0也就是里面有這n個數可以拆分出來多少個2和5。很顯然5的個數遠遠小于2的個數，所以這n個數可以拆分出來多少個5也就是多少個0.
不得不說大佬思路太強了。下面也就是找1234···n-1n里面可以拆分出多少個5了很顯然5的倍數必定可以拆分出至少一個5，同時25的倍數可以拆分出至少兩個5，依次類推，5^i次方至少可以拆分出來i個5，我們可以第一次只統計5的倍數，然后5 ^ 2的倍數依次類推到5 ^ i的倍數，所有個數加起來即可。

class Solution:"""@param n: A long integer@return: An integer, denote the number of trailing zeros in n!"""def trailingZeros(self, n):# write your code herenum = 0i = 5while n>=i:num += n//ii = i * 5return num

3 · 統計數字

• 方法一：偷個懶直接用python的內置函數 cout來做，可以用來查找一個字符串中指定字符的個數

class Solution:"""@param k: An integer@param n: An integer@return: An integer denote the count of digit k in 1..n"""def digitCounts(self, k, n):# write your code hereresult = 0for item in range(0, n+1):number = str(item).count(str(k))result += numberreturn result

• 方法二：
  笨笨的方法對每個數都進行統計，能力所限，懶得優化了，據大佬說可以優化到O(logN)

class Solution:"""@param k: An integer@param n: An integer@return: An integer denote the count of digit k in 1..n"""def digitCounts(self, k, n):# write your code hereresult = 0if k == 0 :result += 1for i in range(n+1):temp = iwhile temp:if temp % 10 == k:result +=1temp//=10return result

• 方法三：大佬的方法，感興趣的看看就好

class Solution:"""@param: : An integer@param: : An integer@return: An integer denote the count of digit k in 1..n"""def digitCounts(self, k, n):def ten(power):return 10**powerdigits = self.getNumOfDigits(n)ans = 0if k == 0:for i in range(digits-1):ans += (n // ten(i+1) -1) * ten(i)ans += min(n % ten(i+1), ten(i) - 1) + 1ans += 1else:for i in range(digits):ans += n // ten(i+1) * ten(i)ans += max(0, min( (k+1)*ten(i)-1, n%ten(i+1) ) - k*ten(i) + 1)return ans@staticmethoddef getNumOfDigits(n):if n == 0:return 1count = 0while n:count += 1n //= 10return count

4 · 丑數 II

其實思路很明確也很簡單，枚舉肯定最麻煩而且也不可取。由于整數均可以劃分為素數不同冪次的乘積且只有一種情況。只有質因子2、3、5所以它必定是這三個數的不同冪次的乘積，所以我們只需要有效到大依次找到并且第N個就好了。

class Solution:"""@param n: An integer@return: the nth prime number as description."""def nthUglyNumber(self, n):# write your code hereheap = [1]p2,p3,p5 = 0,0,0for i in range(n - 1):last = heap[-1]while heap[p2] * 2 <= last:p2 += 1while heap[p3] * 3 <= last:p3 += 1while heap[p5] * 5 <= last:p5 += 1heap.append(min(heap[p2] * 2, heap[p3] * 3, heap[p5] * 5))return heap[-1]

我看網上還有一種堆排序的算法也是可以的
seen采用元組的因為查找方便，運用了空間換時間的方法
求第n小的丑數，可以采用最小堆來解決。每次彈出堆中最小的丑數，然后檢查它分別乘以2、3和 5后的數是否生成過，如果是第一次生成，那么就放入堆中。第n個彈出的數即為第n小的丑數。
至于為什么要判斷是否生成過，因為如果最小為2的時候4，6，10會放入，但是當最小為3時6，9，10也會放入，同理5最小時10，15，25也會放入。這樣可以將重復的6和10排除，方便堆排序

import heapqclass Solution:"""@param n: An integer@return: return a integer as description."""def nthUglyNumber(self, n):heap = []heapq.heappush(heap, 1)seen = set()seen.add(1)factors = [2, 3, 5]curr_ugly = 1for _ in range(n):# 每次彈出當前最小丑數curr_ugly = heapq.heappop(heap)# 生成新的丑數for f in factors:new_ugly = curr_ugly * fif new_ugly not in seen:seen.add(new_ugly)heapq.heappush(heap, new_ugly)return curr_ugly

總結

以上是生活随笔為你收集整理的LintCode刷起来（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。