Day29

admin2024-05-15  1

回溯算法part03

LC39组合总和(未掌握)

  1. 未掌握分析:被数组中的元素可以被重复选取误导,同时没有想到暴力解法来理解回溯
    • 暴力解法肯定是for循环遍历candidates中的每个元素,下一层子循环不像之前的组合题目那样从i+1开始,该题目元素可以循环使用,因此下一层子循环从i开始
  2. 错误代码:错在没有排除掉重复的情况
    Day29,在这里插入图片描述,第1张
  3. 正确代码
    Day29,在这里插入图片描述,第2张

LC40组合总和II(未掌握

  1. 未掌握分析:跳过同层元素相等的递归理解错误
    • if(i>0&& candidates[i-1]===candidates[i]) continue; 如果是i>0则下一层与本层相等的元素情况将被忽略,范围被扩大了
    • if(i>index&& candidates[i-1]==candidates[i]) continue;才是忽略掉同层相同元素的递归
    • if(indexcandidates.length || sum>target) return;应该放在sumtarget后面,因为看你indexcandidates.length && sumtarget的情况
      Day29,在这里插入图片描述,第3张
  2. 代码
    Day29,在这里插入图片描述,第4张

LC131 分割回文串(未掌握

  1. 未掌握分析:切割方式不知道如何体现在回溯算法中
    • 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
    • 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。
    • 切割位置index和组合选择元素位置index是一样的
    • 然后多了个判断回文的过程,如果是回文mid才加入s
  2. 代码
    Day29,在这里插入图片描述,第5张
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!