笔试——Day29

第一题

题目

排序子序列

思路

贪心： 上升的、下降的都找到最远

• 当前处于上升，那就找到下一个下降的位置；
• 当前处于下降，那就找到下一个上升的位置；

代码

第二题

题目：

消减整数

思路

贪心：
每次要么减step，要么减2 * step，为了次数最少，优先选择后者，但一定有前提条件，看下面推导

h - ( n1 * step) - (n2 * step) - (n3 * step) ...... - (nn * step)
=> (h - n * step == 0)

因为n是整数，所以有h % step == 0

代码

第三题

题目：

最长上升子序列(二)

思路

贪心 + 二分在考虑最⻓递增⼦序列的⻓度的时候，其实并不关⼼这个序列⻓什么样⼦，我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后，我们就可以判断是否可以拼接到它的后⾯。

• 创建⼀个数组，统计⻓度为x的递增⼦序列中，最后⼀个元素是谁。为了尽可能的让这个序列更⻓，我们仅需统计⻓度为x 的所有递增序列中最后⼀个元素的最⼩值

• 数组中的数呈现递增趋势，因此可以使⽤⼆分来查找插⼊位置

代码