第一题
题目描述
- 给定一颗二叉树，二叉树每个节点都有唯一的正整数值代表节点，在遍历时，我们使用节点的数值作为标记。给定二叉树的前序和中序遍历结果，求二叉树的叶子节点个数。
输入
- 第一行，输入二叉树节点个数N，其中0 < N < 30000
- 第二行与第三行，分别输入二叉树的前序和中序遍历结果，每个节点对应唯一整数值
输出
- 二叉树叶子节点个数
样例输入
- 3
- 1 3 4
- 3 1 4
样例输出
- 2
分析
- 这是leetcode一个经典的题的拓展：给定一个二叉树的前序和中序遍历，让你重构一个二叉树。如果leetcod这个题会的话只需要简单加个统计就能解出字节这个题了。
- 大概的思路就是用递归的方法。利用这个关键信息：前序遍历的第一个节点一定是根节点root，而在中序遍历中root节点左侧的节点一定是它左子树的所有节点。
- 对于这个题的话，我们其实没必要去重构二叉树。当我们在重构的过程中发现root左侧的节点只有一个的时候，那么它左侧的这个节点一定是叶子节点。右侧的节点同理。
代码欢迎关注“面鲸”
第二题
题目描述
- 小明在学习一种编码协议，二进制数据可以用一串16进制的字符来表示(0-9, A-F)，其中的“0010”是这个协议的特殊字符串，不允许出现。
- 现在给出一串16进制的字符串s，问：
- 最少去掉几个字符，使得剩下的字符串中不存在“0010”
输入
- 第一行t(1<= t <= 1000)，表示有t组测试数据
- 每个样例一行字符串s，s的长度不超过1e5
输出
- 每个样例一行，输出最少去掉字符数
样例输入
- 2
- 0123456789ABCDEF
- 0010123456789ABCDEF00
样例输出
- 0
- 1
分析
- 如果出现了“0010”，那么我们考虑只需要去掉任意一个字符让它不构成“0010”就好了。但是如果由于我们去掉一个字符导致后面出现了新的“0010”，那就不太划算了。比如原来的是"001010"，去掉第一个1之后出现了新的“0010”，这个时候去掉第三个0是最好的。所以可以寻找“0010”出现的位置，如果后面跟着的是1，那么去掉最后这个0；如果后面跟着的是0，那么去掉1是最好的。这么看来只需要寻找出现了几个"0010"就好了，只不过下次寻找的时候需要考虑上已经找到的"0010"中的最后这个0。
解法&代码欢迎关注“面鲸”
第三题
题目描述
- 某视频网站有N个视频，每个视频时长为
秒。产品经理找到你，希望你帮忙在其中插入M个广告。
- 一个视频里的两个广告必须间隔一段时间，当然间隔时间可以为0。
- 为了用户体验，他希望这个间隔时间尽可能长。为了方便实现，间隔时间是一个整数。
- 请你帮忙计算一下，这个间隔时间最大可以设置为多少秒呢？如果不能插入广告，则输出0。
输入
- 第一行有两个整数N, M（1<=N<=100000, N<M<=5000000）
- 第二行有N个整数
输出
- 一个整数，表示最大的间隔时间
样例输入
- 3 9
- 90 100 120
样例输出
- 45
说明
- 最长广告间隔为45秒。第一个视频时长90秒，可以在第0秒，第45秒，第90秒分别插入一个广告，总共3个广告。
分析
- 这个题目是寻找在一定条件限制下的最大值，可以用二分法快速解。
代码&解法欢迎关注“面鲸”
第四题
题目描述
- 在n(1<=n<=35)个正整数中，任意挑选k个(不可重复挑选，0<=k<=n)数字的和记为sum，另有一个正整数m，请问sum%m的最大值是多少？
输入描述
- 第一行两个整数，分别为n, m
- 第二行为n个正整数
输出描述
- 一个数x，x表示sum%m的最大值
样例输入
- 5 5
- 1 2 3 4 5
样例输出
- 4
题目分析
- 如果n比较小的话，我们可以用暴力的方式拿到所有这n个元素能组成的和，然后求最大值即可。复杂度是O(2^n)。但是这个题n最大可以达到35，小本本一算，2^35=34359738368，妥妥的超时。:(
- 所以我们可不可以尝试把问题分解一下。将原数组分解成两个数组
和
，对于每个数组都算出来利用这些元素能组成哪些和，得到两个数组B和C。这个的复杂度是可以接受的，O(
。
- 最大的结果可能是B中某元素，也可能是C中某元素，也可能是B中某元素和C中某元素的和对m求余数。如果只来自B或者C的话，很容易得到答案。复杂的是如何从B中选一个
，再从C中选一个
，让它两加起来的和模m最大。
- 把B和C数组都排序之后，B和C中所有元素加起来的和的范围是0~2m-2。那么他们的和模m的范围是0～m-1，所以中间可能会有一个跳跃点，从(b+c)%m最大，然后b或者c继续增大的话b+c超过了m，所以(b+c)%m就又到了一个低谷值。因此我们可以尝试用two pointer的思路，一个指向B的开始，一个指向C的结尾，然后看这两指针所指位置加和模m与前一个位置的比较。如果加起来要比前一个位置大，说明我们有继续逼近最大值的希望，那么可以尝试增大左指针；否则说明我们尝试过了劲儿，越过了最大点，那么这时候就要减少右指针所指位置的值了。
全部评论
(0) 回帖