60天带你刷完Leetcode【第4天】637-646

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

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


第4天来啦!今天的题目有两道特别难,需要应用一些数学的知识,可以说刷新了小编的认知 欢迎评论指正哦!


646

作者:学酥小编

题目:给出一列区间,比如[[1,2], [2,3], [3,4]],如果两个区间头尾差1或以上,则认为两个区间可以连起来形成一个“链”。比如[1,2]和[3,4]。求最长的链。

题解:根据区间的头排序之后,根据能不能形成链作为subsequence是否increasing的判据,run  Longest Increasing Subsequence。这是一个经典的DP问题。

Running time: O(n^2)


645

作者:学渣小编

题目:一个array里本来有n个数1到n,unordered。现在缺了一个数,重复了一个数。问这两个数分别是什么。

假 设这个array 为arr[], loop一遍,目的是想每次traverse到一个新的数把它swap到自己正确位置(ascending order)上。如果1)nums[i] == i + 1,说明数字已归位,不动作。2) arr[i] != arr[arr[i]-1], 把arr[i] 和arr[arr[i]-1] swap 一下,这样arr[i]的数就到了正确的位置上,3) 如果arr[i]==arr[arr[1]-1]说明这是一个duplicate,记录下来。而arr[i]原本位置上的数就空了,所以记录一个 missing为i+1.

Running time:O(n), Space O(1)


644

作者:学酥小编

题目:这道是643的拓展,给一串数和一个整数k,求这一串数中连续k个或k个以上数的平均值的最大值。

题解:sliding window为k直至数组长度,其他与643一致,因此可以对每种长度的window跑用于解643的算法。但这样running time为O(n^2)。Instead有一种快速的办法可以得到足够精确的近似解:在可能的平均值范围(min, max) 内做binary search,每次判断中位数mid有没有可能是符合题意的连续k个或k个以上数的平均值,如果有可能则将范围缩小一半至[mid, max),否则可缩小一半至(min, mid]。重复直至两次iteration的中位数差值足够小(在连续区间上搜索判断convergence的办法),可认为中位数足够近 似,return。要搜索的范围minmax即数组的min,max值(证明在题解最后)。具体判断中位数mid是否满足题意基于不等式变换可以这样:假设window平均值大于mid,那么window里每一个数与mid的差加起来应大于0(证明在题解最后)。这样就有就有基于不等式变换的linear的判断方法(讨论在题解最后),具体见code,可以记下来。Running time: binary search需要O(log(max-min)), 每次判断需要O(n),一共O(n*log(max-min))

public class Solution {
   public double findMaxAverage(int[] nums, int k) {
               double precision = 0.00001;
               double max_val = Integer.MIN_VALUE;
       double min_val = Integer.MAX_VALUE;
       for (int n: nums) {
           max_val = Math.max(max_val, n);
           min_val = Math.min(min_val, n);
       }
       double prev_mid = max_val, error = Integer.MAX_VALUE;
       while (error > precision) {
           double mid = (max_val + min_val) * 0.5;
           if (check(nums, mid, k))
               min_val = mid;
           else
               max_val = mid;
           error = Math.abs(prev_mid - mid);
           prev_mid = mid;
       }
       return min_val;
   }
   public boolean check(int[] nums, double mid, int k) {
       double sum = 0, prev = 0, min_sum = 0;
       for (int i = 0; i < k; i++)
           sum += nums[i] - mid;
       if (sum >= 0)
           return true;
       for (int i = k; i < nums.length; i++) {
           sum += nums[i] - mid;
           prev += nums[i - k] - mid;
           min_sum = Math.min(prev, min_sum);
           if (sum >= min_sum)
               return true;
       }
       return false;
   }
}

证明和讨论:

设数组中的数为a_1, a_2 , …, a_n. 其中最大数为max, 最小数为min, 其平均值为avg

1. avg < max 并且 avg > min

因为a_1 + a_2 + … + a_n < max*n,所以(a_1 + a_2 + … + a_n)/n < max, 即avg < max。同理可证avg > min

2. 考虑window a_i, a_{i+1}, …, a_j, window average大于某一个数mid可以有如下转换:

(a_i + a_{i+1} + … + a_j) / j >= mid 等价于 a_i + a_{i+1} + … + a_j >= mid * j

左边有j项,右边也有j项,可两两相减:(a_i-mid) + (a_{i+1}-mid) + … + (a_j-mid) >= 0

3. 用linear时间check是否存在i, j使得 (a_i-mid) + (a_{i+1}-mid) + … + (a_j-mid) >= 0 的方法

记上面式子为a’_i + a’_{i+1} + … + a’_j >=0, 其等效于sum’_j - sum’_i(sum_i, sum_j为从头开始到i, j处的sum,’表示每个数都减去了mid)。这样问题转化为对于所有的j和i,判断上式是否成立。这可以进一步转化为对于所有的j和sum’_i最小值,判断上式是否成立(放缩,sum’_i最小时上式最小)。因此可以从i=0, j=k开始,在一个循环中,每一步累加a’_j找到sum’_j,累加a’_i找到sum’_i并判断这个sum’_i是不是最小值, 求sum’_j - min{sum’_i}并判断是否大于0。

*idea and code credit: Leetcode Article.


643

作者:学酥小编

题目:给一串数和一个整数k,求这一串数中连续k个数平均值的最大值。

题解:sliding window为k,loop一遍数组并比较所有的window sum即可。window每往前一个只有头尾两个数有变化,这样可以减少重复计算。running time: O(n)


642

作者:学渣小混混

题目:Desing Search Autocomlete system

设 计一个系统(class),用来查找句子,里面要有一个constructor,跟一个method:vector<string> input(char c)。开始的时候,这个系统里面存有一些句子,每个句子由若干小写字母跟空格组成。函数input主要是帮助用户来输入,因为句子是由字母(char)组 成,所以函数的argument也是char,也就是要用户一个字母一个字母输入句子,而不是直接输入一整句话。另外当用户输入下一个字母时,input 返回该系统所存有的top 3 frequent sentences。(这个跟google search索引类似)当用户输入‘#’表示这个句子输入完成,然后把刚才输入的句子存入系统,或跟新它在系统中出现的次数。

思 路:出题人目的很明确,Tier无疑。而且规模限制在:句长不超过100,句字数目不超过100,这样正好限制了Tier 的深度跟广度。更何况在用户依次输入字母的时候,该句话的prefix在更新。如果要用map,或set的lower_bound找,很麻烦,而且需要没 加一个字母,输出Top 3 frequent sentences,复杂度肯定炸了。用Tier的话,只需要在每个结点,存放目前的以该Tier为prefix 的Top 3 frequent sentences即可。而且正如上面所说,Tier的规模已经被限制了,所以Memory也不会炸。当用户输入完一个sentence之后,在对路过的 结点上的Top3 挨个更新即可。 复杂度:1,建树 O(n*l),n是句子个数,l是句子平均长度。2,查找:平均O(1),直接输出该节点存放的top3即可。3,空间 O(n*l)

题解:

#include<cassert>
typedef pair<int,string> is;
struct T{
   int val;
   set<is> top;
   map<char, T*> chl;
   T(){val = 0;}
};

T* buildT(vector<is> &his){
   T* root = new T();
   for(auto p:his){
       T *cur = root;
       for(auto c:p.second){
           if(!cur->chl.count(c)) cur->chl[c] = new T();
           cur = cur->chl[c];
           if((int)cur->top.size() < 3) cur->top.insert(p);
       }
       cur->val = -p.first;
   }
   return root;
}


class AutocompleteSystem {
   T *root,*cur;
   string sentn;
public:
   AutocompleteSystem(vector<string> sentences, vector<int> times) {
       vector<is> his;
       assert((int)sentences.size() == (int)times.size());
       for(int i=0;i<(int)sentences.size();++i) his.push_back(is(-times[i],sentences[i]));
       sort(his.begin(), his.end());
       root = buildT(his);
       cur = root;
   }
   
   vector<string> input(char c) {
       if(c=='#'){
           assert(!sentn.empty());
           cur->val += 1;
           int cnt = cur->val;
           cur = root;
           for(auto c:sentn){
               cur = cur->chl[c];
               if(cur->top.count(is(1-cnt,sentn))) cur->top.erase(is(1-cnt,sentn));
               cur->top.insert(is(-cnt,sentn));
               if((int)cur->top.size()>3) cur->top.erase(--cur->top.end());
           }
           cur = root;
           sentn.clear();
           return vector<string>();
       }
       if(!cur->chl.count(c)) cur->chl[c] = new T();
       cur = cur->chl[c];
       sentn += c;
       vector<string> ans;
       for(auto p:cur->top) ans.push_back(p.second);
       return ans;
   }
};


640

作者:学酥小编

题目:给一个等式,比如"x+5-3+x=6+x-2",求x的值。等式只包含一个变量x,两种运算+和-,x可以有系数。和通常等式一样,x可以有无限个解,也可以没有解。

题解:straighforward分别求出等号左右边常数项和系数的值,再根据情况判断x有没有解、有没有唯一解。


639

作者:学渣小混混

题目:Decode Way II

有这样一种从字符串到数字的编码方式:

‘A’ -> 1, ‘B’ -> 2, ….’Z’ -> 26. 然后把这些序列串联起来。这是给定一个数字(由string的形式给出,每个character 都是’1’ -> ‘9’ 的digit 跟 ’*’ ),求能decode出的不同字符串的个数。其中’*‘ 可以被替换成’1’ 到’9’ (注意:不包括’0’.)得到的结果对100,000,007取余。

思路:dp

(记得原来做过一道decode way 的题,但input里面没有星号。这道题有了星号这种不确定因素,所以稍微难一点,但思路完全相同。)定义 (设input string 为 s)

dp[i] := s.substr(i) 能被decode 的个数

i 从 n-1 向 0 推。每一步主要讨论下 s[i] 是否是 ‘*’; s[i] 是否是’1’ 或 ‘2’;s[i+1] 是否是星号; s[i]与s[i+1]是否能组成能够被decode的两位数 “11” ~ “26”.仔细一点就可以了。 对于同余操作,我的方法是在开头分别定义好乘法跟加法的函数,每一步update的时候,用这些函数代替原有的operator。复杂度: O(n)

题解:

const long MOD = 1E9 + 7;
long Add(long x,long y){
   x += y;
   if(x>=MOD) x%=MOD;
   return x;
}
void Ad(long &x, long y){
   x += y;
   if(x >= y) x%=MOD;
}
long Mul(long x,long y){
   x *= y;
   if(x>=MOD) x%=MOD;
   return x;
}
void Mu(long &x, long y){
   x *= y;
   if(x>=MOD) x%=MOD;
}

class Solution {
public:
   int numDecodings(string s) {
       if(s.empty()) return 0;
       int n = s.size();
       vector<int> dp(n+1,0);
       dp[n] = 1;
       if(s[n-1] == '*') dp[n-1] = 9;
       else if(s[n-1] != '0') dp[n-1] = 1;
       for(int i=n-2;i>=0;--i){
           if(s[i]=='*') {
               dp[i] = Mul(9,dp[i+1]);
               if(s[i+1]=='*') Ad(dp[i], Mul(15,dp[i+2]));
               else if(s[i+1]<='6') Ad(dp[i], Mul(2,dp[i+2]));
               else Ad(dp[i],dp[i+2]);
           }
           else if(s[i]!='0'){
               dp[i] = dp[i+1];
               if(s[i]=='1'){
                   if(s[i+1]=='*') Ad(dp[i],Mul(9,dp[i+2]));
                   else Ad(dp[i],dp[i+2]);
               }
               else if(s[i]=='2'){
                   if(s[i+1]=='*') Ad(dp[i],Mul(6,dp[i+2]));
                   else if(s[i+1]<='6') Ad(dp[i], dp[i+2]);
               }
           }
       }
       return dp[0];
       return 1;        
   }
};


638

作者:学酥小编

题 目:给定商品的单价、折扣价和需要买的数量,问最划算买齐商品的价格。商品的单价是一个array,比如[2,5]对应商品A单价为2,商品B单价为5; 折扣价有多种,由一个array表示,每一种折扣价也是一个array,其最后一个数为价格,前面的数字代表对应商品可以买多少件,比如 [[3,0,5],[1,2,10]]表示两种折扣价,其中[3,0,5]表示商品A买3件,商品B买0件的折扣价为5;最后需要买的数量也是一个 array,比如[3,2]代表需要买3件商品A,2件商品B。

题 解:这道题说了这么多其实就是要给具体写码造成一定困难,但算法就是对需要买的数量试遍所有可能的购买方案,以找到最便宜的价格。因此可以以需要买的数量 为state进行recursion,每次recursion可以用某个折扣价或者完全不用来购买,这样得到一个新的需要买的数量,完成了state transition。每个state对应的购买价格为所有购买方案的最小值。可以加上memorization存储某个state对应的cost来避免 重复计算。 running time: number of states * number of 购买方案。


637

作者:学酥小编

题目:求binary tree每个level上node value的平均值。

题解:level order traversal相应修改一下。


+附加思考题

F  - 收集球
时间限制:2秒/内存限制:256MB

得分:1200分

问题陈述
在xy平面中有2N个球。它们的坐标是(xi,yi)。这里,对于所有i,xi和yi为1和N(含)之间的整数,并且没有两个球占据相同的坐标。

为了收集这些球,Snuke准备了2N机器人,N型为A型和N型,然后将A型机器人放置在坐标(1,0),(2,0),...,(N, 0),坐标(0,1),(0,2),...,(0,N)的B型机器人,每个位置一个。

激活时,每种类型的机器人将如下操作。

当A型机器人在坐标(a,0)处被激活时,它将移动到x = a线上的球之间具有最低Y坐标的球的位置,收集球并使其自身停用。如果没有这样的球,它将会自动停用,而不做任何事情。

当B型机器人在坐标(0,b)处被激活时,它将移动到线y = b上的球中最低x坐标的球的位置,收集球并使其自身停用。如果没有这样的球,它将会自动停用,而不做任何事情。

一旦停用,机器人不能再次被激活。而且,当机器人运行时,在操作机器人停用之前,不能激活新的机器人。

当Snuke即将激活机器人时,他注意到,根据启动机器人的顺序,他可能无法收集所有的球。

在(2N)!激活机器人的可能命令,找到可以收集所有球的数量,模数为1 000 000 007。



Constraints

  • 2≤N≤105

  • 1≤xi≤N

  • 1≤yi≤N

  • If i≠j, either xi≠xj or yi≠yj.


Inputs

Input is given from Standard Input in the following format:

N
x1 y1

x2N y2N

Outputs

Print the number of the orders of activating the robots such that all the balls can be collected, modulo 1 000 000 007.


Sample Input 1

2
1 1
1 2
2 1
2 2

Sample Output 1

8

We will refer to the robots placed at (1,0) and (2,0) as A1 and A2, respectively, and the robots placed at (0,1) and (0,2) as B1 and B2, respectively. There are eight orders of activation that satisfy the condition, as follows:

  • A1, B1, A2, B2

  • A1, B1, B2, A2

  • A1, B2, B1, A2

  • A2, B1, A1, B2

  • B1, A1, B2, A2

  • B1, A1, A2, B2

  • B1, A2, A1, B2

  • B2, A1, B1, A2

Thus, the output should be 8.


Sample Input 2

4
3 2
1 2
4 1
4 2
2 2
4 4
2 1
1 3

Sample Output 2

7392


Sample Input 3

4
1 1
2 2
3 3
4 4
1 2
2 1
3 4
4 3

Sample Output 3

4480



明日题目 Leetcode: 636-627


查看所有题目:

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



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


阅读

微信扫一扫
关注该公众号