js版数据结构与算法—3.6种花问题-原理讲解

小咪咪 2022-02-04 20:43 182阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 4][]

export default (arr, n) => {
      // 计数器
      let max = 0
      // 右边界补充[0,0,0],最后一块地能不能种只取决于前面的是不是1，所以默认最后一块地的右侧是0（无须考虑右侧边界有阻碍）（LeetCode测试用例）
      arr.push(0)
      for (let i = 0, len = arr.length - 1; i < len; i++) {
        if (arr[i] === 0) {
          if (i === 0 && arr[1] === 0) {
            max++
            i++
          } else if (arr[i - 1] === 0 && arr[i + 1] === 0) {
            max++
            i++
          }
        }
      }
      return max >= n
    }

import flower from '../../code/array/lesson3'
    
    test('flower:[1,0,0,0,1],1', () => {
      expect(flower([1, 0, 0, 0, 1], 1)).toBe(true)
    })
    test('flower:[1,0,0,0,1],2', () => {
      expect(flower([1, 0, 0, 0, 1], 2)).toBe(false)
    })
    test('flower:[1, 0, 0, 0, 1, 0, 0], 2', () => {
      expect(flower([1, 0, 0, 0, 1, 0, 0], 2)).toBe(true)
    })

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190504220751258.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 1]: /images/20220205/847f76904a2047f19de17b9e8b89f344.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 2]: /images/20220205/b3a0cf94893d4a32bc99e272ada3555a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 3]: /images/20220205/f187a50a24c8434c9216f1eeeb678486.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 4]: /images/20220205/76e0a9d5bf394239b03431387b9548bd.png