Chapter 53 Linkedin 2016 12
53.1 149. Max Points on a Line
http://www.1point3acres.com/bbs/thread-216630-1-1.html
只需要返回number.从n个点可以得到\(n*(n-1)/2\)个斜率.用counter记录斜率.
http://fisherlei.blogspot.com/2013/12/leetcode-max-points-on-line-solution.html
53.2 number of possible triangles
http://www.geeksforgeeks.org/find-number-of-triangles-possible/
53.3 282. Expression Add Operators(H)
https://leetcode.com/problems/expression-add-operators/
https://segmentfault.com/a/1190000003797204
复杂度
时间 \(O(N^2)\) 空间 \(O(N)\)
思路
因为要输出所有可能的情况,必定是用深度优先搜索.问题在于如何将问题拆分成多次搜索.加减法很好处理,每当我们截出一段数字时,将之前计算的结果加上或者减去这个数,就可以将剩余的数字字符串和新的计算结果代入下一次搜索中了,直到我们的计算结果和目标一样,就完成了一次搜索.
然而,乘法如何处理呢?这里我们需要用一个变量记录乘法当前累乘的值,直到累乘完了,遇到下一个加号或减号再将其算入计算结果中.这里有两种情况:
乘号之前是加号或减号,例如2+3*4,我们在2那里算出来的结果,到3的时候会加上3,计算结果变为5.在到4的时候,因为4之前我们选择的是乘号,这里3就应该和4相乘,而不是和2相加,所以在计算结果时,要将5先减去刚才加的3得到2,然后再加上3乘以4,得到2+12=14,这样14就是到4为止时的计算结果.
另外一种情况是乘号之前也是乘号,如果2+3*4*5,这里我们到4为止计算的结果是14了,然后我们到5的时候又是乘号,这时候我们要把刚才加的3*4给去掉,然后再加上3*4*5,也就是14-3*4+3*4*5=62.这样5的计算结果就是62.
因为要解决上述几种情况,我们需要这么几个变量,一个是记录上次的计算结果currRes,一个是记录上次被加或者被减的数prevNum,一个是当前准备处理的数currNum.当下一轮搜索是加减法时,prevNum就是简单换成currNum,当下一轮搜索是乘法时,prevNum是prevNum乘以currNum.
注意
第一次搜索不添加运算符,只添加数字,就不会出现+1+2这种表达式了.
我们截出的数字不能包含0001这种前面有0的数字,但是一个0是可以的.这里一旦截出的数字前导为0,就可以return了,因为说明前面就截的不对,从这之后都是开始为0的,后面也不可能了.
struct Solution {
vector<string> addOperators(string num, int target) {
vector<string> res;
dfs(num, target, 0, 0L, "", res);
return res;
}
void dfs(string& num, int target,
int d, long c, string p, vector<string> &res)
{
if (num.empty() && c==target) res.push_back(p); //termination condition
for (int i=1; i<=num.size(); ++i) {
string cur = num.substr(0, i);// first operand
if (cur.size()>1 && cur[0]=='0') return;//0 good, 01 bad
string n = num.substr(i);// second operand
long t = stol(cur);
if (p.empty()) // first time, top level of stackframes
dfs(n, target, t, t, cur, res);
else {
dfs(n, target, t, c+t, p+"+"+cur, res);
dfs(n, target, -t, c-t, p+"-"+cur, res);
dfs(n, target, d*t, (c-d)+d*t, p+"*"+cur, res);
}
}
}
};除法的话,divisor cannot be 0.
case 1: 2+6/4, 上一层加上的数是6,cumulative结果是8,因为division has hinger priority, we do (8-6)+(6/4)=3
case 2: 2+6/4/2,上一层加上的数是1,cumulative结果是3,在这一层我们做(3-1)+(1/2)=2
所以我们需要track上一层加上的数,cumulative sum两个中间变量.
对除法,我们只需要加一行如下代码:
Others: (H) Basic Calculator (M) Basic Calculator II (M) Different Ways to Add Parentheses
53.4 Union and Intersection of two Linked Lists
我followup问了数据量很大的时候,有什么并行策略..
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=215434
http://www.1point3acres.com/bbs/thread-218010-1-1.html
