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

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

2017-09-21 CS学渣学酥小混混 北美加群小助手Jogchat 北美加群小助手Jogchat

每天30分钟关注【北美加群小助手Jogchat.com】小编们带你60天刷完硅谷一线二线公司，学渣学酥也能跻身一线公司、升职加薪、当上总经理、出任CEO、迎娶白富美、从此走上人生巅峰！想想还有点小激动😏

第五天来啦！今天小编们给文章加了一点高亮，既可以让大家看着方便也可以体现我们的逼格 谢谢大家的支持，公众号应该很快就能开通评论功能，大家可以正儿八经的吐槽小编啦（当然我们知道更多的是赞美）

635

作者：学酥

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

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

635

作者：学酥

题目：要求design一个日志存储系统 (log storage system)。每一条log是一个timestamp，format为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)，即存和取。retrieve要求从start到end，在granularity上找到落在范围内的timestamp。比如在granularity是 year，则只需要找到落在start和end对应年份区间内的timestamp。start和end是inclusive的，return timestamp对应的id

题解：比较新颖一道题。

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

range query。本题实质是range query，可以用TreeMap这个data structure解决。retrieve的时候把start和end做成range，比如granularity为天，就把时分秒部分对start改为 00:00:00，end改为24:00:00，然后直接进入TreeMap中query。不同语言这里具体的实现不一样，可参照java实现并理解这个 data structure。这样理论上两个function的复杂度都是O(log(n))，不过retrieve完要把返回整理为所需要的type可能还需要 loop一遍。

634

作者：学酥

题目：给出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解法：先看recursion，dp[n]定义为1到n的derangement数量。每进行一次操作（调换数字）可产生新的state（剩下的未被调换数字的derangement数量）。一次操作使一个数字a离开其原本位置，这样有n-1个可能的新位置放这个数字。而对原本在新位置的这个数字b，要么去到a的位置，要么不去到a的位置。第一种情况相当于a和b都被放到了新位置，只需要找剩下的n-2个数对应的derangement数量，即dp[n-2]；第二种情况相当于a放到了新位置，b暂时到了a的位置但是b需要换个位置，和剩下的n-2个数一样，因此需要找n-1个数对应的derangement数量，即dp[n-1]。综上所述，我们有

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

此题还有一种用数学推导的方法解，大家可以自行搜索。

633

作者：学酥

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

题解：2sum变种，在1到sqrt(c)这些个整数上搜索。running time O(n)

632

作者：学渣小混混

题目：Smallest Range

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

思路：先把所有list中的第一个数放在一个set里面，（这里由于C++的set可以快速找到该容器中的最小跟最大的元素，其他语言也有类似的数据结构。）同时记录每个数来自于那个list。然后依次删除该set中最小的元素，并将其换成对应list中的下一个元素，知道不能替换位置（到达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};
   }
};

复杂度：O(n*log k)，这里n是数字总数，k是list的数目

631

作者：学渣小混混

题目：Design Excel Sum Formula

建立一个类似Excel的运算系统(class)。这个class有一个constructor跟三个method：

void set(int r, char c, int v) := 将r行c列的数重置为v。（列由字母标记，所以输入是char）

int get(int r, char c) := 得到r行c列的值

int sum(int r, char c, vector<string> strs) := r行c列的值被重置，并且在这个位置定义一个公式sum，就是strs中所有格子之和。其实就是建立一个依赖关系，而且这个关系式在该点被重置之前一直存在。

（strs是一个字符串组，每个字符串表示一个格子，或一个范围。sum的公式就是这些格子跟范围的总和。这个公式在r行c列被重置之前，一直有效：也就是说，如果那个字符串组中某个格子的值改变了，r行c列这个值也会跟着变。这个跟Excel的公式计算有点类似。）

思路:

表格的规模很小，最多26*26，所以考点不是复杂度。所以只要找一个能够存放依赖关系的数据结构实现就行了，不用太在意时间。难点是里面可能存在多重关系，比如A1 = B1 + C2；B1 = C2 + D3。这时如果：1，如果D3发生了变化，虽然A1的公式里面没有D3，但由于B1会随D3而变，所以A1也会发生变化；2，如果C2增加了x，虽然A1 的公式中只有一个C2，但由于B1的公式里面还有一个C2，所以A1的增量是2x，而不是x。（这里我们只能假设没有环，否则答案不唯一了。）我用map 的table来表示依赖关系，同时用一个recursion专门处理多重关系：也就是下面题解中的 void ad(int r,int j,int v)函数，作用是把r行j列的数字增加v，通过recusion来处理连锁反应。

题解：

typedef vector<int> vi;
typedef map<int,int> mii;
typedef set<int> si;
class Excel {
   const int M = 30;
   vector<vi> val;
   int h,w;
   vector<vector<si>> to;
   vector<vector<mii>> from;
public:
   Excel(int H, char W) {
       h = H;
       w = (int)(W-'A')+1;
       val = vector<vi>(h+1,vi(w+1,0));
       to = vector<vector<si>>(h+1,vector<si>(w+1));
       from = vector<vector<mii>>(h+1,vector<mii>(w+1));
   }

   void ad(int r,int j,int v){ //not reseting the sum relationship
       val[r][j] += v;
       for(int k:to[r][j]) ad(k/M,k%M,v*from[k/M][k%M][r*M+j]);
   }

   void set(int r, char c, int v) {
       int j=(int)(c-'A'), old=get(r,c);
       for(auto p:from[r][j]) to[p.first/M][p.first%M].erase(r*M+j);
       ad(r, j, v-old);
   }

   int get(int r, char c) {
       int j=(int)(c-'A');
       return val[r][j];
   }

   int sum(int r, char c, vector<string> strs) {
       int j=(int)(c-'A'), old=get(r,c), cnt = 0;
       for(auto p:from[r][j]) to[p.first/M][p.first%M].erase(r*M+j);
       from[r][j].clear();
       for(auto s:strs){
           auto i = s.find_first_of(":");
           if(i==string::npos){
               int i1=stoi(s.substr(1)),j1=(int)(s[0]-'A');
               cnt += val[i1][j1];
               from[r][j][i1*M+j1] += 1;
               to[i1][j1].insert(r*M+j);
           }
           else{
               int x1=(int)(s[0]-'A'),x2=(int)(s[i+1]-'A');
               if(x1>x2) swap(x1,x2);
               int y1=stoi(s.substr(1)), y2=stoi(s.substr(i+2));
               if(y1>y2) swap(y1,y2);
               for(int i1=y1;i1<=y2;++i1) for(int j1=x1;j1<=x2;++j1){
                   cnt += val[i1][j1];
                   from[r][j][i1*M+j1] += 1;
                   to[i1][j1].insert(r*M+j);
               }
           }
       }
       for(int k:to[r][j]) val[k/M][k%M] += cnt-old;
       val[r][j] = cnt;
       return cnt;
   }
};

630

作者：学渣小混混

题目：Course Schedule III

有N门不同的课，已知他们的duration：t（必须是连续的t天），跟deadline：d，求你能最多选多少门课。要求：1，不能在同一天选两门课，2，不能重复选。

思路：之前有一道类似的题，不过那道题是给定了每门课开始跟结束的时间，所以只要不停的贪心去选结束早的课，就能得到最优的选法。这道题明显难了很多，因为开始时间不确定了（t<=d）。

首先，从直觉来想，肯定还是优先选deadline早的课，这样可以空出来更多的时间。所以不妨先对所有课就deadline时间进行排序。其次，进行选课：也就是依次把deadline比较早的课加入到课表中。1，如果这个过程没有一点冲突，那最好，答案就是N，因为你能把所有课都选上。2，如果选到第 k门课的时候，出现了冲突：也就是选完1～k-1门课之后，再选第k门课，则上完第k门课的时间超了其deadline。这就意味着，着1～k门课不能共存，需要进行取舍。很显然，为了以后能选到更多的课，我们应该优先选取时长尽可能小的课。具体操作很简答，把第k门课加入，然后删掉最长的那课就行了。很容易可以证明更新后的这k-1门课是可以共存的，而且用时不比之前的选法大。最后，依次比较+替换更新，直到所有课程被扫了一遍。此时得到的课表就是最优课表，也就是课程数最多的选法。

题解：

typedef pair<int,int> ii;
class Solution {
public:
   int scheduleCourse(vector<vector<int>>& courses) {
       vector<ii> I;
       for(auto v:courses) I.push_back(ii(v[1],v[0]));
       sort(I.begin(), I.end());
       priority_queue<int> que;
       int cnt = 0, ending = 0;
       for(auto cs:I){
           if(ending+cs.second<=cs.first){
               que.push(cs.second);
               ending += cs.second;
           }
           else if(cs.second < que.top()){
               ending += cs.second - que.top();
               que.pop();
               que.push(cs.second);
           }
           cnt = max(cnt, (int)que.size());
       }
       return cnt;
   }
};

复杂度：O(n log n)

629

作者：学渣小混混

题目：K Inverse Pairs Array

给定n，k，求{1, 2, …, n}的排列中，有k个Inverse pair的个数。得到的结果对100,000,007取余。一个Inverse pair (i,j)的定义是 i<j but P[i] > P[j], {P} 为{1, 2, ..., n}的一个排列。

思路：

设函数f(n, k)为有k个Inverse 的 {1, 2, …, n}的排列个数。

我们先从“1”的位置开始着手：（1）如果“1”出现在序列开头，则能够与“1”形成Inverse pair的数是没有的，因为圣下的数都会排在“1”的后面，且它们都比“1”大。（2）如果“1”出现在了第k个位置，则能够与“1”形成Inverse pair的数有k-1个，就是最终排在“1”前面的那k-1个数。（3）固定了“1”之后，不论{2, 3, .., n}如何排列，能够与“1”形成Inverse pair 的数的个数是不变的（很显然）。所以我们其实可以列出以下关系式：

f(n, k) = f(n-1, k) + f(n-1, k-1) + ... + f(n-1, k - n + 1)

直接调用这个关系式的话，时间复杂度是O(k*n^2)，因为f(n, k)是二元函数，而且每次递归里面有一个求和关系。这个复杂度显然是不可以被接受的，因为n，k的规模是1000，k*n^2～10^9。通常刷题跟竞赛网站可以接受的最高时间复杂度是10^7 ~ 10^8。这样我们在对上面的式子进行变形：

f(n, k-1) = f(n-1, k-1) + f(n-1, k-2) + ... + f(n-1, k - n)

两式相减得：

f(n, k) = f(n, k-1) + f(n-1, k) - f(n-1, k - n)

变成了一个O(1)的递归关系，总时间复杂度就变成O(k*n^2)。

题解：

typedef vector<int> vi;
class Solution {
   const int MOD = 1E9 + 7;
public:
   int kInversePairs(int n, int k) {
       vector<vi> f(n+1,vi(k+1,0));
       f[1][0] = 1;
       for(int i=2; i<=n; ++i){
           f[i][0] = 1;
           for(int j=1;j<=k;++j){
               f[i][j]=f[i][j-1]+f[i-1][j];
               if(j>=i) f[i][j]-=f[i-1][j-i];
               if(f[i][j]>=MOD) f[i][j]-=MOD;
               if(f[i][j]<0) f[i][j]+=MOD;
           }
       }
       return f[n][k];
   }
};

复杂度：时间空间都是O(k*n^2)

628

作者：学酥

题目：求一个数组中三个数字乘起来的最大值。

题解：这题很无聊。。。。有一个公式：要么是三个最大数的product要么是最大数和两个最小数的product

627

考察SQL语法，请自行参考答案～

附加题
有无数张纸牌，开始的时候有N张头朝上，其他头朝下。对这些牌重复如下操作：选一个大于或等于3的质数p，然后连续地选p张纸牌并翻面。问最少操作多少次可以使所有纸牌头朝下。
要求：2sec / 256MB / 1<=N<=100 / N张头朝上的纸牌的标号不超过10^7
输入：N张头朝上的纸牌标号。
例子：输入4，5输出2。第一次选质数5，翻1,2,3,4,5号牌；第二次选质数3，翻1,2,3号牌。
祝解题愉快！

明日题目 Leetcode: 636-627

查看所有题目：

打开Wechat微信->Contacts[联系人]->Official Accounts[公众号]->北美加群小助手Jogchat->每日播报->Leetcode总入口

【长按关注北美加群小助手Jogchat.com】

阅读

微信扫一扫
关注该公众号