每日一题 | 每天都要进步一点点！

贴一下这周的每日一题和解题思路。

20200316

给定一个整数 num，你可以将一个数位从0变为1，找出你能够获得的最长连续一串1的长度。

请编写一个程序，找出你能够获得的最长连续一串1的长度。

示例 ：

输入: num = 1775
输出: 8
解释：1775二进制为11011101111，改变倒数第五位的0为1，则最长连续1为8

简单说一下思路：

普通版：暴力双重循环，定义标志位flag。将最近的0改为1设置0为flag，并计算长度，下一次循环从flag开始，一直到循环结束

进阶版①：将数字转换为二进制数，以0为分割点进行切分，统计相邻两个的长度和sum，取sum最大的结果，最后+1即可

进阶版②：将数字转换为二进制数，利用动态规划思想，设置两个标志位，一个用来表示改变0之后的长度，一个用来表示未改变0时连续1长度

---

20200317

给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

如果找不到前一个或者后一个满足条件的正数，那么输出 -1。

示例:

输入：2（0b10）
输出：[4, 1] （[0b100, 0b1]）
---
输入：num = 1
输出：[2, -1]

解题思路：

位运算

---

20200318

配对交换。

编写程序，交换某个整数的奇数位和偶数位（也就是说，位0与位1交换，位2与位3交换，以此类推）。

示例:

输入：num = 2（或者0b10）
输出 1 (或者 0b01)
示例2:
---
输入：num = 3
输出：3

解题思路：

奇数位清零后左移，偶数位清零后右移，将结果相加即可

---

20200319

三步问题。

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例:

输入：n = 3
输出：4
说明: 有四种走法
----
输入：n = 5
输出：13

解题思路：

动态规划问题

举个简单的例子：比如现在有5阶台阶，那么就会有

• 在第4阶的时候，上1阶

• 在第3阶的时候，上2阶

• 在第2阶的时候，上3阶

一共就这三种情况。

我们需要算出在第4阶、第3阶、第2阶的时候已经走了几步，然后加起来就是最终的结果。

因为结果太大，这道题结果还需要对1000000007 取余。

---

20200320

跳水板问题。

有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。

编写一个方法，生成跳水板所有可能的长度，返回的长度需要从小到大排列。

示例：

输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}

解题思路：

构造一个数据结构，依次存储每一步的结果。

例如：当为1的时候，有两种情况：shorter和longer

当为2的时候为：f(1)+shorter，f(1)+longer

当为3的时候…

（和昨天同样的解题思路）

进阶：最终的结果会在【k * shorter~k * longer】的范围内，以每次 longer-shorter 的步长增加。

提示：range 函数

---

写在后面的话

题目一般是中午之前发，题解会在下午或晚上会发到群里

大家的解题代码都可以发群里，可以互相探讨学习

最近没时间写文章，不过每日一题还是每天会在群里发出来，感兴趣的同学扫码进群