第一题

image.png
image.png

第二题（业务类）（贪心）

2.2 29分
image.png

  1. 这是属于业务类的题，要在分类当中找思路，首先假设两个集合的平均值是一样的 都是100 100，那么从A中拿数字 都不能保证A和B的平均值提高
  2. 假设A集合平均值 50 B 100，那么从A中不能拿 也就是不能从小集合中拿元素到大集合去
  3. 如果从B中拿50到100的数，就可以提高A的平均值大小，也可以提高B的。
  4. 关键是50到100的数可能有 60 70 80 90 这样的，先拿哪个 这里可以采用贪心优先拿最小的数，这样A的提升幅度大 B的提升幅度小，A会拿更多的数 如下图所示

image.png

实现（code技巧点）

  1. 首先用double类型来保存平均值 损失精度结果可能不正确
  2. 然后平均值大的集合数组和小的数组 以及他们的sum 可以做个重定向 重新用引用来指向他们 这样避免了程序分类逻辑 只用一套主逻辑就行
  3. 然后对数组进行排序 这样在遍历平均值大的集合 如果遇到满足条件的元素直接加入到小集合 而不用再去找满足条件最小的
  4. 定义set 保存小集合，这样查找起来快速
  5. 最后就是满足三个条件把 元素从大set 移动到小set里面

image.png
image.png

第四题

image.png

  • 定义count 左括号count++ 右括号count— count最大值就是最大深度

    延伸（动态规划！）

  • 连续子串子数组题 求每个位置为结尾的前提下答案是多少

image.png

  • 求合法的最长括号子串 定义dp数组 dp[i] 表示以i为结尾的最长有效长度
  • 所有左括号的dp 应该填充为0
  • 那么右括号的dpi 的填充应该分情况讨论 把i-1往前推dp[i-1]个位置 也就是p 如果值为左括号 则加上dp[p-1]，如果值为右括号则为0。
  • 右括号为0的原因是 i-1表示了最大子串 前面不可能合法

image.png

实现

image.png

题目五

image.png

  • 准备两个栈 辅助栈必须要求栈顶从小到大的顺序，如果元素加入不满足 则把辅助栈的数据依次弹出加入到主栈里。

    题目六

    image.png
    这种从左到右的递归模型可以转换为动态规划

  • 每个位置的决策都可以是自己或者包括自己的两个字符小于等于26的 basecase为index = 字符串长度时返回1，代表成功做出的决策1个

image.png
image.png

题目七

image.png
image.png