又到了需要准备面试的季节，决定来小刷一下Leetcode，在每个Tag里适当地挑几道，锻炼一下手感啥的。

455

题意

有一堆曲奇和一堆小孩，曲奇和小孩都有一个属性值，给小孩一个属性值>=自己的属性值的曲奇就会使小孩满意，一个小孩只能有一块曲奇。求满意的小孩的最大数目。

分析

似乎是很常见的贪心模型，但有一些变化，比如可以给多块曲奇。我觉得可以把最优化的目标从小孩的数目细化一下，比如“浪费”的曲奇属性值，取为每个小孩身上浪费的属性值之和。不过这么搞显然违背了原有的最优化要求，所以需要改一下。

妈的，看错题了，是最多一块曲奇。那就没啥好说的了，分别从最大的属性值开始遍历然后分配好了。

这是一个Java的解法。总之从最不贪婪的孩子开始分配，效果是一样的。

Arrays.sort(g);
Arrays.sort(s);
int i = 0;
for(int j=0;i<g.length && j<s.length;j++) {
    if(g[i]<=s[j]) i++;
}
return i;

代码

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int j = g.size() - 1;
        int res = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            while (s[i] < g[j] && j >= 0) j--;
            if (j < 0) break;
            // allocate s[i] cookie for g[j] kid
            res++;
            j--;
        }
        return res;
    }
};

时间是40ms。

659

题意

有一个排序了的整数序列，需要把它分割成几个子序列，要求每个子序列为单调递增的的整数，且长度至少为3。问能否进行这样的分割。

分析

最简单的想法就是从头开始找最长的序列，找到一个就全部删掉，然后再找下一个。这样做的问题就是可能会出现如下情况：

[1, 2, 3, 3, 4, 5]

如果直接用以上解法，就会得到[1, 2, 3, 4, 5]和剩下的3。但是其实是可以分成[1, 2, 3]和[3, 4, 5]的。中间有2个重复的时候同理。3个重复的时候就可以得到一个新的子序列。

所以新想法是从重复最多的数字开始找。先满足它们的需求。但是似乎只能向一侧延伸，不然效果和刚才是一样的。

另一个想法是直接只找长度为3的序列。但是这样剩下的1和2长度的序列完全无法处理。

查看了一下题目的相关topic，发现除了greedy之外还有heap，所以可能从重复最多的数字开始找是可行的。可以尝试消耗左侧或者右侧最多的数字，仍然是找最长序列。然后用堆来进行维护。

敲了半天，感觉不靠谱，还是去看题解了。

---

这道题果然很有趣，有好多种解题思路。

模拟

http://www.cnblogs.com/pk28/p/7384602.html
这篇文章的思路很有代表性。作者开始的思路是这样的：

开始的想法是，第一遍扫一下，依次枚举3个连续的数作为一个分割，并记录每个分割最后的一个数（为后期拓展所用）。
第二次扫描，看剩下的数能不能放到任何一个分割的后面。如果能，那么更新分割的最后一个值。
第三次扫描，看还有没有剩下的数字，如果没有那么返回true,否则false

但这样的思路是存在问题的，作者给出了反例。于是需要调整一下思考的顺序：

其实我们思考的顺序有错误，对于当前的数字x，我们应该先判断x-1是否存在，如果存在就直接放上就好了，不存在的时候再构建一个长度为3个分割，如果长度为3的分割都构建不了，那么直接返回false就ok了。说道这里，这题目还是有贪心的味道的....

至于模拟的具体实现，这种实现是比较简洁的：http://www.cnblogs.com/grandyang/p/7525821.html。

线段

这个做法参考了https://leetcode.com/problems/split-array-into-consecutive-subsequences/solution/#approach-1-opening-and-closing-events-accepted。可以将本题看做是一系列长度大于等于3的线段叠在一起，数字的数量增加即一条线段的开始，减少即一条线段的结束。只需将开始事件和结束事件配对，要求其间隔>=3即可。

代码

模拟

注意没有给出数字的范围！所以需要用map！！

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        map<int, int> cnt;
        map<int, int> need;
        
        if (nums.size() < 3) return false;
        
        // count
        for (int i = 0; i < nums.size(); i++) {
            cnt[nums[i]]++;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (cnt[nums[i]] <= 0)
                continue;
            
            // find extend
            if (need[nums[i]] > 0) {
                need[nums[i]]--;
                need[nums[i] + 1]++;
                cnt[nums[i]]--;
            }
            // find consecutive
            else if (cnt[nums[i]] > 0 && cnt[nums[i]+1] > 0 && cnt[nums[i]+2] > 0) {
                cnt[nums[i]]--;
                cnt[nums[i]+1]--;
                cnt[nums[i]+2]--;
                need[nums[i]+3]++;
            }
            else {
                return false;
            }
        }
        
        return true;
    }
};

时间为29.39%，可以说是相当慢了，因为使用了两个map的缘故吧。

线段

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        if (nums.size() < 3)
            return false;
        map<int, int> cnt;
        queue<int> q;
        for (int i = 0; i < nums.size(); i++) {
            cnt[nums[i]]++;
        }
        for (int i = nums[0]; i <= nums[nums.size()-1] + 1; i++) {
            int event = cnt[i] - cnt[i-1];
            // segment start
            if (event > 0) {
                for (int j = 0; j < event; j++)
                    q.push(i);  // starts at i
            }
            else if (event < 0) {
                for (int j = 0; j < -event; j++) {
                    if (q.empty())
                        return false;
                    int start = q.front();
                    q.pop();
                    if (i - start < 3)
                        return false;
                }
            }
        }
        
        if (!q.empty()) return false;
        
        return true;
    }
};

注意边界情况的处理。
时长为56.42%，没有什么优势。

45

题意

给你一个正整数数组，每个数代表了你从该位置起跳能够跳到的最大距离。假定你一定能够跳到终点，求最小跳数。

分析

第一种思路类似于DP。从第一点开始跳，同时更新能跳的范围内“跳到此处所需的最小跳数”。然后逐步更新。由于每次更新的范围最多为n，因此复杂度为O(n^2)。这是很容易想到的。也是很容易超时的。（果然超时了）

那么如何优化呢？

看了看题解发现这还真是道贪心题，囧。思路很简单，干脆就把它当成是一个BFS问题。第一跳能跳到的结点显然有一个范围，剩下的结点都是必须要跳两次及以上的。然而，跳两次能跳到的结点的范围显然也是连续的。也就是说可以把这个线性的数组按顺序分成若干层，每层都是一层BFS的结果。然后直接做就行了。

代码

暴力

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() <= 1)
            return 0;
        vector<int> f(nums.size(), 2147483647);
        f[0] = 0;
        for (int i = 0; i < nums.size() -1; i++) {
            for (int j = 0; j <= nums[i] && i+j < nums.size(); j++) {
                if (f[i] + 1 < f[i+j])
                    f[i+j] = f[i] + 1;
            }
        }
        return f[nums.size() - 1];
    }
};

超时了。

BFS

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() <= 1)
            return 0;
        
        int start = 0, end = 0;
        int end2 = 0;
        int layer = 0;
        while (end < nums.size() - 1) {
            end2 = end + 1;
            for (int i = start; i <= end; i++)
                end2 = max(end2, i + nums[i]);
            start = end + 1;
            end = end2;
            layer++;
        }
        return layer;
    }
};

时间大概是13.97%，没有什么优势，不过我觉得已经写得比较简略了。