738. Monotone Increasing Digits
此题大意：求比一个自然数小且单调递增的数中最大的那个。例如对于1002来说，答案是999.对于14436来说答案是13399。
解题思路：寻找要求解答案的规律，发现，答案是原来的正数，从右向左看，第一个违反递减的数字可以减1，然后后面全部用9补齐。注意边界条件：(1)例如1455中后面两个5算不算违反递减规律，其实不用考虑。因为1455的答案是1399，真正违反规律的是4。(2)例如17756，那么违反规律的是第一个7，而前7变为6后，前面的第一个7也会违反规律。这里要做的就是只要出现违反，那么就立即就地减1，继续往前扫描。
452. Minimum Number of Arrows to Burst Balloons
此题大意：给出元素是区间的数组。把区间当作是气球，然后，区间点上射箭会让气球爆炸，现在求让全部气球爆炸的最小射箭次数。
解：先按照区间的右端点的由小到大排序。然后，从第一个右端点开始射箭，看一次能射爆几个气球（只要后面区间的左端点小于射箭点就可以被射爆）。对排序好的区间一遍扫描，每次更新最近射箭点，更新的方法就是跳过可以被射爆的区间，然后每次更新射箭点，需要的箭的数量就加1。
605. Can Place Flowers
此题大意：给出0和1的数组，1代表花，现在要向数组里面加入花，要求是花和花之间必须要有间隔。
解：贪心法。从头到尾扫描一遍数组，如果能放入花，那么就放。
621. Task Scheduler
题意：给出字母数组，字母代表一种任务，每种任务单位时间为1就能解决，在给出一个CPU间隔n，表示不同任务执行之间必须要有n个单位时间的间隔。例如：A任务执行后，必须要执行n-1个其他任务，然后才能重新执行A，如果没有那么多种类的任务，那只有空闲着单位时间了。要求解的是执行完所有任务花费的最少时间，任务执行顺序不受数组顺序限制。
解：此题是贪心的，通用解法就是，把任务装进优先级队列，然后每次往每一轮里面装。
由于每个任务都是间隔时间为n，那么假设n足够大（比任务种类多），那么会发现执行完所有任务其实取决于数量最多的任务，只要每一轮间隔优先执行数量最多的任务，期间安插一些其他任务，就是最优解的形式。当n比任务种类小的时候，贪心的放入，由于每一轮都将被放满，所以最后的长度就是等于任务的数量。
有了最优形式解，那么如果编写程序模拟这样往里面填，其实还是有操作难度的，所以最好还是进一步找答案的规律。当n很大的时候，最优解的形式，假设数量最多的任务数量是maxN，那么前maxN-1轮是不会一定有的，也就是前maxN-1轮的结果一定是(maxN-1)*(n+1)。再来考虑最后一轮，由于前面已经间隔插入了其他任务，所以留到最后一层的任务必然是等于数量最多的任务的（任务数量最多的可能不止一个）。只要加上即可，当然有一种例外，那就是发现最后一轮的任务超过了间隔数，或者算出来的任务比任务的个数（下限）还要少，那就就选任务的个数做结果返回。
PS.计算数量最多任务种类时候，要从map遍历，不能从原数组进行遍历。另外，在max中使用size()时候，要显式转化为int。
253. Meeting Rooms II
题意：给出开会开始结束时间区间为元素的数组，开会房间不能重叠，求开会所需要的最少房间数量。
解：此题使用贪心法+sweepline。原理是这样的：先按会议开始时间将所有区间进行排序，然后扫描每个区间，模拟分配房间的过程：首先，第一个区间占一个房间；对于第二个区间，如果第二个区间的开始时间大于第一个区间的结束时间，意味着第二个区间可以使用第一个区间分配的房间，反之，则要新开一个房间给第二个会议使用。对于第三个房间，如果前面分配的是一个房间，那么要看第二个会议结束时间和自己的开始时间；如果前面分配的是两个房间，那么，看自己起始时间是否比其中的一个结束时间要小，要是比两个都小，那么就只能新开第三个房间，否则就占用其中一个最早结束（所以是贪心法）的房间。
Read full article from leetcode按题目总结（十五）—— 贪心法
No comments:
Post a Comment