首页 > 其他分享 >刷题总结

刷题总结

时间:2023-04-30 09:22:06浏览次数:28  
标签:总结 个数 回溯 集合 刷题 dp 指针

结束本轮的刷题任务 感受颇多 基本体现在双指针 回溯以及动规上

使用双指针法,定义两个指针(也可以说是索引下标),一个从字符串前面,一个从字符串后面,两个指针同时向中间移动,并交换元素。,时间复杂度是O(n)

回溯算法能解决如下问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 棋盘问题:N皇后,解数独等等
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}



动规五部曲分别为:

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

希望日后大量训练反复多次 早日上岸

标签:总结,个数,回溯,集合,刷题,dp,指针
From: https://www.cnblogs.com/libertylhy/p/17364915.html

相关文章

  • 总结,从 766 开始(Div2 30)
    3.10A分块B 分数规划,以前没学过C推式子 3.11A推结论,先划分连续段,然后从一个长度>=k的连续段开始操作B推式子C平衡树套线段树(为了节省空间需要把内层线段树改成平衡树)或定期重构+树上差分+动态开点线段树,每个结点上有一棵线段树,每B次操作后向上合并 3.12......
  • 师大 2023.04 总结
    题目1:P10011A第1次提交提交通过。每次减去\(\max(n-n/2,x)\),边减边计数。题目2:P10021A第1次提交提交通过。\(cnt\)表示字符串有\(cnt\)对对应的字符不同。对于每组询问,因为只改变一个字符,看改变字符改变前和改变后和对应字符的关系(相同或不同),以改......
  • 每日总结2023-04-29
    今天初步学习了kotlin语言在学习中认为比较重要的点:在学习字符串模板时,我们了解到,可以在单个变量名称前加上$符号。但是,如果您使用更复杂的表达式,就必须用大括号将该表达式括起来,并在大括号前添加$符号:${unreadCount+readCount}。用大括号括起来的表达式(即unreadCount+......
  • OOP4-6题目集总结
    4-6次题目集,从集合框架,正则表达式,类的继承与多态三个方面展开,在帮助我们了解java常用的工具(集合框架,正则表达式)的同时让我们学着利用类与类之间的关系来减少耦合,第六次题目集侧重于类的继承与多态,同时让我们自己根据题目设计类来解题,在了解面向对象的编程思想后,加强我们对类与......
  • Java学习2——第四-六次题目集的分析与总结
     一.前言 本次Blog是对java学习中第二阶段练习的一个总结,作为刚学习JAVA的小白,以下依旧只是本人作为普通学生,以当前能力和状态所做出的总结和分析,不足之处也欢迎各位大佬的指正! 这次的三个题目集,题量除了题目集六很少外,其它都是正常数量,当然题目集六的题也是最难的。总体难......
  • 题目集4-6总结
    一、前言本阶段的题目集最开始还是和前面的题目集有些相似的内容,但相较于前阶段的题目集主要是改进了代码所用到的知识点使代码更加简洁与所用内存更加小。这次题目集的难度还可以,并且是逐渐加大难度的,特别是题目集六一道题一百分。这次的题目集主要考察了正则表达式的应用,类与类......
  • OOP 4-6题目集总结
    目录前言设计与分析踩坑心得改进建议总结一、前言      (1)第四次题目集           本次题目集一共有7道题目,题量适中,但第一题难度较大,其余题目难度适中。考察的知识点有类与类之间的关系调用、对象数组的使用、排序、String类方法的使......
  • 4-6次题目集总结
    前言:4-6次pta实验相较于之前三次难度有所提升,主要是为了训练我们对于java类的设计以及类内方法的设计,以及很多语法知识,是正式进入java的过程。题目集四:主要知识点是一些语法的使用,类的设计,以及类的方法体,需要考虑输出格式和算法设计,如正则表达式,LinkedHashSet去重等,题目难度不低......
  • PTA题目集4~6的总结
    1.前言题目集4题目集4题目量适中,整体难度中偏易题目7-1要求厘清类与类间的关系,能对题目所给的要求作出准确的设计,难度中偏上题目7-2~7-7考察基本的算法,对Java中集合框架的使用以及对LocalDate类的使用,总体上难度偏易题目集5......
  • Java题目集4~6的总结
    1.前言第四次作业主要涉及的知识点有通过查询JavaAPI文档,了解Scanner类中nextLine()等方法、String类中split()等方法、Integer类中parseInt()等方法的用法,了解LocalDate类中of()、isAfter()、isBefore()、until()等方法的使用规则,了解ChronoUnit类中DAYS、WEEKS、MONTHS等单位......