题目一

7.2 41m
image.png

  • 英文数字每三个位是一部分，中文数字每四个位是一部分。举例子一千万 一百万，所以只要写出前面四个函数之后万就可以转化了

  • 尽量减少嵌套if else方向优化代码

    题目二

    8.2 1m
    image.png

    思路

  • 可以初始一个哈希表，然后计数最后获取出现次数为0的数字

  • 好的方法可以用replace算法，确保i位置上出现i+1这个数，遍历i位置的时候如果不是i+1就(设值为value)找value-1下标的元素，看它是不是value如果是就停下来，不是则继续执行上面的步骤

  • 执行完上面的流程以后，每个i位置都应该有i+1这个数，如果不是则说明缺i+1这个数判断即可

    代码

    image.png

    题目三

    7.2 1h 54m
    image.png

  • 最差方法 把数字表示出来然后模3==0

  • 其次方法可以计算每一个数字的数位的和 1+2+3…+9++1+0+1+1..+L 的数值然后模3==0，原理是 123 数位数字之和如果可以整除3那么表示的数就可以整除

  • 最好方法 计算 1+2+…+9+10+..+L 然后模3==0 利用等差数列求和公式 原理是 一个数字每个数位模3 等价于 这个数模3 比如 123 % 3==0 1+2+3 %3==0

    题目四 无限递归问题

    8.2 9m27s
    image.png

    错误写法

  • 尝试很好想，一共三种决策，但是会造成无限递归情况，原因如图所示

image.png
image.png

思路 在业务中找限制

  1. basecase要考虑更多的情况，第一种是如果比平凡解更差就抛弃掉 a到b每次加2一共需要20x
  2. 首先a和b人气值都是偶数，a必须小于2b，如果等于2b肯定不是最优解，因为b是偶数相当于先到了b然后乘2再做减法
  3. 其他类型的题自己找限制

image.png

代码

  • 下面是递归尝试代码 可以改成二维动态规划
  • 参数主要有 已经用的钱，目标钱，还有三种情况，以及当前人气值和限制的目标人气，限制的平凡解

image.png
image.png

题目五 二叉树

7.2 59m
image.png
image.png

思路

  • 完全二叉树的左右子树必定有一个满二叉树
  1. 首先获得根节点为首的二叉树的最大深度 假设为5
  2. 然后看根节点X的右子树最左面的节点的深度，为5，说明X的左子树是一个满二叉树，那么节点个数算上X节点就为 1<<4 解释一下二的子树深度减1次方，算上顶部节点就不减1.
  3. 然后求Y节点的树的节点个数，Y节点右树最大深度没到底说明右树是满二叉树
  4. 重复上面的过程

    代码

    image.png

  • 考虑一下边界的情况 ，节点右子树为空 左子树为高度h的时候，执行else流程 前面的表达式1个节点，后面的递归过程遇到basecase返回1个节点

    时间复杂度

  • 为 h的平方 ，logn的平方 如果40亿 2的32次方个节点的树只需要1000多次就可以查出来

    题目六

    8.2 39m
    image.png
    image.png

  • 对每个节点定义一个有序表，保存当前节点累加后续的key和value

  • 然后对每个map进行删除不符条件的元素，要求key值增加value也增加
  • 最后每个节点的map都整合在一个map里面，再进行上面的删除操作
  • 最后根据题意返回key满足的答案就行

image.png

题目七 最长递增子序列

7.2 1h 25m

解法一 ON2

image.png
7.2 1h 32m

解法二

image.png