[849] Maximize Distance to Closest Person

[tsungtingdu]

two pointers

var maxDistToClosest = function(seats) {
    let max = 0
    let runner = 0
    let base = 0

    while (runner < seats.length) {

        // find the next base
        while (seats[base] === 1) {
            base++
            runner = base
        }

        if (seats[runner + 1] === 1 || runner + 1 === seats.length) {
            // edge case
            if (runner + 1 === seats.length || base === 0) {
                max = Math.max(runner - base + 1, max)
            } else {
                max = Math.max((runner - base + 2) >> 1, max)
            }
            runner++
            base = runner
        } else {
            runner++
        }
    }
    return max
};

JS 原生方法解

• 先用 join('') 將陣列組合成字串
• 再用 split(1) 把所有包含 0 的字串給拆出來成為陣列
• 最後用 reduce 遍歷該陣列。頭尾的 items 回傳原本的長度，其他則回傳 (item.length + 1) >> 1
• 跟先前的 acc 比較過後，將較大的值回傳到 acc 當中
• 回傳 reduce 之後的結果

var maxDistToClosest = function(seats) {
    return seats.join('').split(1).reduce((acc, item, index, arr) => {
        let tempAcc = (index === 0 || index === arr.length - 1) ? item.length : (item.length + 1) >> 1
        return Math.max(acc, tempAcc)
    }, 0)
};

[henry22]

• 紀錄1也就是有人坐的位置，更新每個1之間的距離
• 每個1之間的距離可為：
• 1的前面皆為0，則最大距離為1的index減去第一個0的index
• 1的後面皆為0，則最大距離為陣列長度減去第一個0的index

• 夾在兩個1正中間的0，則最大距離為第二個1的index減去第一個0的index加1再除以二

  /**
  * @param {number[]} seats
  * @return {number}
  */
  var maxDistToClosest = function(seats) {
  let res = 0
  let pos = 0
  const size = seats.length
  
  for(let i = 0; i < size; i++) {
      if(seats[i] === 1) {
          if(pos === 0) {
              res = Math.max(res, i)
          } else {
              res = Math.max(res, Math.floor((i - pos + 1) / 2))
          }
          pos = i + 1
      }
  }
  res = Math.max(res, size - pos)
  return res
  };

[harrytothemoon]

把早上說的寫法完成

var maxDistToClosest = function(seats) {
    if (seats.length === 2) return 1
    return Math.max(...distance (seats), ...distance(seats.reverse()))

    function distance (nums) {
        let res = []
        let start = 0
        let end = 0
        let run = 0
        while (run < nums.length) {
           if (nums[run] === 1 && run !== nums.length - 1) {
               start = run
               end = run
               while (nums[run + 1] !== 1 && run + 1 !== nums.length - 1) {
                   run++
               }
               end = run + 1
               if (end === nums.length - 1 && nums[end] !== 1) res.push(end - start)
               else res.push((end - start) >> 1)
           }
            run++
        }
        return res       
    }
};