資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：計算n個人翻動開關後，最終亮著的開關數量
假設我們有一個數字n，房間裡有n個開關，所有開關都處於關閉狀態。現在有n個人依次翻動開關，如下所示：
- 第1個人翻動所有是1的倍數的開關（即所有開關）。
- 第2個人翻動所有是2的倍數的開關（2、4、6……）。
- 第i個人翻動所有是i的倍數的開關。
我們需要找到最後亮著的開關數量。
例如，如果輸入是n = 5，則輸出將是2，因為最初所有開關都關閉[0, 0, 0, 0, 0]，第1個人翻動所有開關[1, 1, 1, 1, 1]，第2個人翻動[1, 0, 1, 0, 1]，然後第3個人翻動[1, 0, 0, 0, 1]，第4個人翻動[1, 0, 0, 1, 1]
為了解決這個問題，我們將遵循以下步驟：
- l := 0, r := n
- 當 l <= r 時，執行以下操作：
- mid := l +(r - l) / 2
- 如果 mid^2 <= n < (mid + 1)^2，則
- 返回 mid
- 否則，如果 n < mid^2，則
- r := mid
- 否則，
- l := mid + 1
讓我們看看下面的實現以更好地理解：
示例
class Solution: def solve(self, n): l, r = 0, n while l <= r: mid = l + (r - l) // 2 if mid * mid <= n < (mid + 1) * (mid + 1): return mid elif n < mid * mid: r = mid else: l = mid + 1 ob = Solution() n = 5 print(ob.solve(n))
輸入
5
輸出
2
更新於：2020年12月2日
343 次瀏覽
廣告