Re: [閒聊] 每日LeetCode

[idiont (supertroller)]

1523. Count Odd Numbers in an Interval Range

給定 low 跟 high 這個範圍，
求 [low, high] 這個區間中有多少個奇數。

Example 1:
Input: low = 3, high = 7
Output: 3
Explanation: [3, 7] 這個區間的奇數有 [3, 5, 7] 這三個


Example 2:
Input: low = 8, high = 10
Output: 1
Explanation: [8, 10] 這個區間的奇數有 [9] 這一個


解題思路：
基本上可以分成奇數偶數的 case 來探討:

case 1: (odd, odd)
ex: [3, 7], 答案為 (7 - 3) / 2 + 1 = 3

case 2: (odd, even)
ex: [3, 8], 答案為 (8 - 3) / 2 + 1 = 3 <-除法向下取整

case 3: (even, odd)
ex: [4, 7], 答案為 (7 - 4) / 2 + 1 = 2 <-除法向下取整

case 4: (even, even)
ex: [4, 8], 答案為 (8 - 4) / 2 = 2

可以歸納出當任一個邊界為奇數時答案就需要加一。


C++ code:
class Solution {
public:
    int countOdds(int low, int high) {
        if((low & 1) || (high & 1)) return (high - low) / 2 + 1;
        return (high - low) / 2;
    }
};

---

今天的題目好水

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676248540.A.C47.html
推 Rushia: 你贏了
推 a9486l: 大師
推 DreaMaker167: 大師
補充一下另一個做法
當遇到邊界是偶數的時候 可以把他往中間縮減 不會改變答案
這樣就保證求解的區間固定是 [odd, odd]
但要特別考慮 low == high 的 case
※ 編輯: idiont (140.113.229.216 臺灣), 02/13/2023 08:40:32
→ SecondRun: 大師
→ dustsstar79: 大師
推 dannyko: 大師
→ KusanagiYuma: 大師
推 pandix: 大師