60天带你刷完Leetcode【第5天】636 - 627

作者：学酥

题目1：

有一组function运行的记录，格式如下：id:start/end:timestamp，比如1:start:0表示function1在time0开始，1:end:3表示在time3结束。按照题意这表示function1运行了4个时间点。在一个function运行之后它可能会call别的function也可能call自己。但cpu是单核单程的，所以任何一个时间点只有一个function在运行。求每个function运行的时间。

题解：

注意到任何一个时间点只有一个function在运行，可以loop所有的function，如果记录的是start就放到stack里，(stack顶代表当前运行的function)；如果记录的是end那一定是当前function结束了，pop stack。具体的运行时间由timestamp的差值计算得来。Running time: O(n)

题目2：

要求design一个日志存储系统 (log storage system)。每一条log是一个timestamp，格式为Year:Month:Day:Hour:Minute:Second，比如2017:01:01:23:59:59，除了年是4位数以外都是2位数。要求这个系统有两个功能：void Put(int id, string timestamp) 和 int[] Retrieve(String start, String end, String granularity)。

题解：

比较新颖一道题。 brunt force。Put的时候把id和timestamp pair连接到list尾，retrieve可以遍历这个list，对每个timestamp和start，end取到granularity为止的substring，比较是否落在区间之内。这样put复杂度O(1)，retrieve复杂度O(n)。

题目3：

给出1到n的数，找到derangement的个数。derangement的定义是所有数字不能出现在原先位置，比如[1,2,3]的derangement有[2,3,1]和[3,1,2]。

题解：

brute force找出所有的permutation要O(n!)，每一个permutation要用O(n)时间check是否符合derangement定义。

DP解决方案： dp[n]定义为1到n的derangement数量。每次操作产生新的state（剩下的未被调换数字的derangement数量）

dp[n] := (n-1) * (dp[n-1] + dp[n-2])

题目4：

问一个非负数c和两个整数a和b是否存在平方和的关系：a^2+b^2 = c

题解：

2sum变种，在1到sqrt(c)上的整数上搜索。running time O(n)

题目5：

给定k个sorted list of integers，求一个区间[left, right]覆盖每个list中至少一个数字，且区间长度最小；相同长度情况下，区间的开始值left最小。

思路：

把所有list中的第一个数放在一个set里面，记录每个数来自哪个list。依次删除set中最小的元素并替换为对应list中的下一个元素，记录最小区间[min of set, max of set]。

题解：

#include<cassert>
typedef vector<int> vi;
typedef pair<int,int> ii;
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int n = (int)nums.size();
        assert(n);
        set<ii> col;
        vi index(n,1);
        for(int i=0;i<n;++i) {
            assert(!nums[i].empty());
            col.insert(ii(nums[i][0],i));
        }
        int left=col.begin()->first, right=(--col.end())->first; 
        while(true){
            int j = col.begin()->second;
            col.erase(col.begin());
            if(index[j]>=(int)nums[j].size()) break;
            col.insert(ii(nums[j][index[j]],j));
            index[j]++;
            if((--col.end())->first-col.begin()->first<right-left){
                left = col.begin()->first;
                right = (--col.end())->first;
            }
        }
        return vi{left,right};
    }
};