Re: [閒聊] 每日LeetCode
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
推
02/13 08:36,
1年前
, 1F
02/13 08:36, 1F
推
02/13 08:36,
1年前
, 2F
02/13 08:36, 2F
推
02/13 08:37,
1年前
, 3F
02/13 08:37, 3F
補充一下另一個做法
當遇到邊界是偶數的時候 可以把他往中間縮減 不會改變答案
這樣就保證求解的區間固定是 [odd, odd]
但要特別考慮 low == high 的 case
※ 編輯: idiont (140.113.229.216 臺灣), 02/13/2023 08:40:32
→
02/13 08:46,
1年前
, 4F
02/13 08:46, 4F
→
02/13 09:10,
1年前
, 5F
02/13 09:10, 5F
推
02/13 09:22,
1年前
, 6F
02/13 09:22, 6F
→
02/13 12:08,
1年前
, 7F
02/13 12:08, 7F
推
02/13 15:31,
1年前
, 8F
02/13 15:31, 8F
討論串 (同標題文章)
完整討論串 (本文為第 231 之 719 篇):
閒聊
1
3