Re: [問題] Leetcode 744

[poyenc (髮箍)]

※ 引述《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
推 chuegou: 這篇讓我醍醐灌頂 推個
推 F04E: M
推 BlazarArc: 推
推 sivle: 感謝
推 howareuuu: 推