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^210^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】


阅读 5669

微信扫一扫
关注该公众号