Re: [問題] Leetcode 744
※ 引述《Kuba4ma ()》之銘言:
這裡的問題在於寫碼方式和語言習慣相左, 導致無法描述空區間,
以及避免儲存重複的資訊.
C/C++ 是用半開區間來描述資料範圍, 因此存取 letters 的合法索
引落在 [0, 3) 內, 在這種設計下基於陣列的 divide-and-conquer
演算法就可以簡單將空區間 (物件不存在) 判斷作為迴圈終止條件:
size_t left = 0;
size_t right = letters.size();
// search in [left, right)
while (left < right) {
// divide [left, right) into 3 sub-intervals:
// 1. [left, m)
// 2. [m, m + 1) (only [m] itself)
// 3. [m + 1, right)
const size_t m = (left + (right - left) / 2);
assert(m < letters.size()); // m should be valid index
if (target < letters[m]) {
right = m; // search in [left, m)
// laters[m] <= target
} else {
left = m + 1; // search in [m + 1, right)
}
}
在迴圈結束後, left 的值只有兩種可能: 小於 3 或者等於 3. 只
要根據這兩種結果來印值, 不需要另外定義變數儲存相同資訊.
assert(left <= letters.size());
if (left == letters.size()) {
cout << letters[0] << endl;
} else {
cout << letters[left] << endl;
}
任何物件都被視為單個元素的陣列, 掌握這個概念就可以和所有的
標準函式庫函式, 尤其是 STL algorithms 來介接. 這份程式碼存
在其他如有號/無號數的轉型問題就不多做說明了.
--
[P1389R1] Standing Document for SG20: Guidelines for Teaching
C++ to Beginners
https://wg21.link/p1389r1
SG20 Education and Recommended Videos for Teaching C++
https://www.cjdb.com.au/sg20-and-videos
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.76.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1626022585.A.C98.html
※ 編輯: poyenc (123.193.76.216 臺灣), 07/12/2021 01:41:27
推
07/12 10:11,
2年前
, 1F
07/12 10:11, 1F
推
07/12 14:31,
2年前
, 2F
07/12 14:31, 2F
推
07/12 17:34,
2年前
, 3F
07/12 17:34, 3F
推
07/13 18:25,
2年前
, 4F
07/13 18:25, 4F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇):