斐波那契高级

略

题目一

5.2 55分
image.png

打表法

  • 通过递归发现斐波那契数列的规律

    尝试发现斐波那契数列

  • 首先长度为i的字符串前面一个位置必须为1，然后F(i) = F(i-1)+F(i-2)

image.png

题目二

image.png

  • 这个题可以传化成，保留最少的木棍可以让任意木棍不能组成三角形，那么i位置的木棍要等于i-2和i-1位置的木棍可以最少 贪心
  • 题目问 N以内 斐波那契数列的个数

image.png

题目三（题库错误）

4.2 1时49分
image.png

  • 这个题关键是找到分类讨论的点，然后进行不同情况讨论
  • 数据类型 有偶数但是不能整除4 （包含2因子） 有能整除4的数 （包含4因子） 还有奇数
  1. 设 奇数数量为a 2因子数数量为 b 4因子数数量为c
  2. 当 b=0 时候 141 奇数这样摆放最少 满足 c>=a-1即可
  3. 当 b！= 0 时候 2224141 确保一个4摆在偶数后面的位置 c>=a即可
  4. 这里有特殊情况 比如 只有一个偶数 b=1 和 一个奇数情况 单独判断数组长度即可

    思考

  • 上面的总结是做完很多 abc之间的情况讨论的 有时候可能一步想不全 可以把情况全列出来再想办法减少

    题目四 业务题

    5.2 1时31分
    image.png

  • 首先考虑一下正常整数的情况如下图所示

  1. 只允许有‘-’这个符号
  2. 如果有那么只在开头并且后面是数字不是0
  3. 如果开头是0后头没数字
  4. 不允许其他符号只允许0到9

image.png
image.png

  • 然后把符合规定的数字转换成int类型

image.png

  1. 首先用负数保存结果，因为负数的范围比正数多1
  2. 如果是负数从1开始遍历，不是负数从10开始遍历，每次用字符0去减去当前的数
  3. 每次将res结果进一位然后再加上cur
  4. 防止溢出的代码 首先判断结果是不是小于最小值除10 其次判断cur小于最小值模10（负数）
  5. 如果这个数不是负数 还达到了最大值 则溢出

    题目六 动态规划

    image.png
  • dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]] (j>=arr[i]) 第i个位置想凑出小于等于j容量的方法数

    题目七

    image.png
  1. 首先把工作按照难度从低到高排序，然后相同难度的按工资从高到低排序
  2. 然后相同难度为一组 把每组除了组长的元素排除出去，然后保证难度和工资是递增的，不满足条件也排除出去

image.png

代码

  • 排序器代码实现如下

image.png

  • 首先对数组进行排序，然后定义一个TreeMap，把第一元素放入map里面，然后找到下一个不同难度并且money递增的满足条件放入map，然后定义一个结果数组，开始遍历每次找到难度满足的元素设置工资

image.png