j*****8
发帖数: 3635 | 1 题目如下：
Given a string that contains only digits 0-9 and a target value, return all
possibilities to add binary operators (not unary) +, -, or * between the
digits so they evaluate to the target value.
给的几个例子：
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
下面是我的java code，有个test case一直超时，求大牛指点优化。我的思路很简单，
先生成所有可能的计算式，然后对每个计算式求值与target比较。
public List addOperators(String num, int target) {
List result = new ArrayList();
if(num == null || num.length() == 0) return result;
List expressions = new ArrayList();
generate(num, expressions, 0, "");
for(String str : expressions)
if(evaluate(str) == target) result.add(str);
return result;
}
private void generate(String num, List result, int pos, String
currResult) {
if(pos == num.length()) {
result.add(currResult);
return;
}
String currStr = currResult + num.substring(pos, pos+1);
if(pos == num.length() - 1) {
generate(num, result, pos+1, currStr);
} else {
// apply '+'
generate(num, result, pos+1, currStr+"+");
// apply '-'
generate(num, result, pos+1, currStr+"-");
// apply '*'
generate(num, result, pos+1, currStr+"*");
// no operator, combine digits
generate(num, result, pos+1, currStr);
}
}
private long evaluate(String str) {
LinkedList operand = new LinkedList<>();
LinkedList operator = new LinkedList<>();
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) == '+' || str.charAt(i) == '-' || str.charAt(i)
== '*') {
operator.offer(str.charAt(i));
continue;
}
long val = 0;
while(i < str.length() && str.charAt(i) >= '0' && str.charAt(i)
<= '9') {
val = val * 10 + str.charAt(i) - '0';
i++;
}
i--;
operand.offer(val);
if(operator.size() > 0 && operator.peekLast() == '*') {
operator.pollLast();
operand.offer(operand.pollLast() * operand.pollLast());
}
}
// evaluate the remaining part
while(!operator.isEmpty()) {
char optor = operator.poll();
long operand1 = operand.poll();
long operand2 = operand.poll();
if(optor == '+') {
operand.offerFirst(operand1 + operand2);
} else {
operand.offerFirst(operand1 - operand2);
}
}
return operand.poll();
} | g******z
发帖数: 893 | | s***f
发帖数: 457 | 3 发信人: svcef (svcef), 信区: JobHunting
标 题: 你是否愿意通过自学转行成为一个软件工程师
发信站: BBS 未名空间站 (Sat Jun 13 18:23:13 2015, 美东)
(这个机会仅仅适用于位于硅谷南湾的人, 谢谢。 Our office is on Walsh Ave,
Santa Clara. CA, 95050 )
这个帖子， 前一阵子， 发过一次， 由于大家反馈非常好， 就再发一次， 希望对更
多的朋友有帮助。绝对不收任何费用， 我们提供完全免费的转行软件工程师的机会。
这个帖子是写给那些朋友， 以前由于各种原因， 没能够成为计算机专业学
生，现在愿意通过自学成为一个软件工程师.
这可以做到嘛 ？
实际上， 任何人通过自学成为一个软件编程的高手都不是什么难的事情。只要肯花许
多时间学习和练习， 加上有人可以指导答疑, 每个愿意成为软件工程师的人都可以通
过一段时间的学习成为一个不错的软件工程师。
如果你正想成为一个软件工程师， 请联系我们。 我们能够提供机会帮助你成为一个软
件工程师。绝对不收任何费用。
我们提供一个边工作， 边学习的机会。
只有一个要求， 希望你现在还有努力学习的动力和勤奋精神。
注1: 许多软件编程的高手都不是计算机专业学生. 举例来说， 微软的Bill Gates，
Facebook的Mark Zuckerberg, 都是软件编程的高手，但都不是学计算机专业的. Bill
Gates本来大概要学法律， Mark Zuckerberg本来是心理学专业的。
只要你有真材实料， 转行到软件， 是不需要一个CS的学位的。
注2: 如果您本身是一个软件工程师， 读到这个帖子， 请您手下留情， 请不要为
“码工”这个职业泼冷水。您也许不知道， 有许多人羡慕你的职业呢 ？ 正想成为一
个软件工程师 ？ 软件工程师, 工作有挑战性， 收入也不错。我们就是希望提供机会
给这样的朋友。
注3: 我们这个项目绝对不收任何费用。
注4： 我们和硅谷任何别的软件培训，职业培训， bootcamp没有任何关系。
我们也不是这样的一个软件培训，职业培训， bootcamp机构。 我们提供的学习
机会是完全免费的。
如果你正在考虑下一个工作方向, 如果你正想成为一个软件工程师， 有许多时间可以
用来学习， 站内请联系我们。 我们能够提供机会帮助你成为一个软件工程师。
关于我们这个项目的说明：
我们是一家初创startup Internet software 公司， 这个项目为我们自己公司培养人
才。 希望你可以用来学习工作的时间不少于一周至25小时,来我
们位于硅谷南湾的办公室工作。对于有意和我们共同长期把公司做成功的，
公司会发原始股。
我们主要开发Internet software for Enterprise Application， 用的语言是：
Python, Java, PHP, MySQL. (不要求你有相关语言和背景， 只要求你有强烈意愿学
习)。
技术工作主要做网站server端的开发 （包括， Python, Java, PHP, Django, etc)，
也有客户端的开发。 客户端的开发包括 web front end 以及手机App和Facebook Apps.
详情, 请站内联系。
请给我们一个机会， 也给你自己一个机会。也许这就是你长久等待的一个机会。
(This opportunity is 仅仅限于硅谷南湾, 谢谢, Our office is on Walsh Ave,
Santa Clara. CA, 95050.
如果你不在硅谷南湾， 很对不起， 我们这个项目不合适你。)
如果您对这个项目不感兴趣， 请不要给别人泼冷水。
已经有多人从我们这个项目受益。 | a**a
发帖数: 316 | 4 要做事先做人
你这么长的广告贴直接把别人的帖子给劫持了
这种没底线的行为足以说明你和你的团队是什么德行
【在 s***f 的大作中提到】
: 发信人: svcef (svcef), 信区: JobHunting
: 标 题: 你是否愿意通过自学转行成为一个软件工程师
: 发信站: BBS 未名空间站 (Sat Jun 13 18:23:13 2015, 美东)
: (这个机会仅仅适用于位于硅谷南湾的人, 谢谢。 Our office is on Walsh Ave,
: Santa Clara. CA, 95050 )
: 这个帖子， 前一阵子， 发过一次， 由于大家反馈非常好， 就再发一次， 希望对更
: 多的朋友有帮助。绝对不收任何费用， 我们提供完全免费的转行软件工程师的机会。
: 这个帖子是写给那些朋友， 以前由于各种原因， 没能够成为计算机专业学
: 生，现在愿意通过自学成为一个软件工程师.
: 这可以做到嘛 ？
| f****8
发帖数: 33 | 5 这个复杂度是O(4^n)了，所以超时。
我使用dp保存部分前面的结果(+,-分隔的部分)
all
【在 j*****8 的大作中提到】
: 题目如下：
: Given a string that contains only digits 0-9 and a target value, return all
: possibilities to add binary operators (not unary) +, -, or * between the
: digits so they evaluate to the target value.
: 给的几个例子：
: "123", 6 -> ["1+2+3", "1*2*3"]
: "232", 8 -> ["2*3+2", "2+3*2"]
: "105", 5 -> ["1*0+5","10-5"]
: "00", 0 -> ["0+0", "0-0", "0*0"]
: "3456237490", 9191 -> []
| l*3
发帖数: 2279 | 6 我就好奇问一句，关于
"00", 0 这个例子，难道只有0+0,0-0和0*0吗？
理论上来说，00这个数本身不也是0？ | r****7
发帖数: 2282 | 7 我觉得dp也降不了复杂度吧，每段都有4^n个结果要存啊
【在 f****8 的大作中提到】
: 这个复杂度是O(4^n)了，所以超时。
: 我使用dp保存部分前面的结果(+,-分隔的部分)
:
: all
| j**********3
发帖数: 3211 | 8 同球这个题的答案，看了这个题之后我眼中怀疑自己智商了。。。 | a*****a
发帖数: 46 | 9 这个题目估计主要的trick估计就是怎么去掉楼主的evaluate那一步，
http://pastie.org/10434648
。这个可以过，ps，leetcode的讨论的版面看起来不少不错的答案。
主要的想法是处理完的前面的expression总是可以表达成 a+b，如果接下来是加号，
下一个数字是c，那么接下来这个expression就是 (a+b) + c,如果接下来是 乘号，那
么 就是 a+(b*c)， 如果是减号，那么就是 (a+b) + (-c) | l*3
发帖数: 2279 | 10 我的c++过了。之前也是超时，改进方法就是要把每一步临时算出来的结果保存，不要
在最后的时候重复算。不过说实话我觉得这个影响不大，理论上讲无非就是把一个最坏
是 O(n * 4^n) 的东西降到了 O(4^n)，少了一个factor而已，不过确实是过例子很快
。。只要44ms（我不知道超时一般判定是多少，不过之前有的题跑了600ms也算过了，
不过也不知道是不是所有题的超时判定都一样?我估计是1000ms，如果这么说的话其实
实际上改进还挺大）
贴一段我的代码，最tricky的地方就是楼上说的，你需要知道这些：
乘法运算的优先级比加减法高，所以你要保存一个 “连乘串” 的结果。直到你某一步
走到了某个你想插入加减法的地方，你才把连乘串的结果去添加到临时的sum结果中，
否则就要一直保留。
另外什么是加法和减法呢？其实就相当于你update你临时的sum，并且把新的乘积起始
点赋值成 1 （对应加法） 或者 -1 （对应减法）
code 如下：
class Solution {
public:
//主函数，没有干什么大事，就是预处理一下字符串，把两个位置之间的字符转换的整
数结果都保存下来记录在一个叫nums的二维数组中，这一步复杂度是O(n^3), 并没有仔
细优化，因为整个算法是指数级的所以这里没必要太抠
vector addOperators(string num, int target) {
vector results;
if (num.empty()) {
return results;
}
vector > nums(num.size(), vector(num.size(), -1));
for (int i = 0; i < num.size(); i++) {
for (int j = 0; j < num.size(); j++) {
if (num[i] != '0' || j == i) {
try {
nums[i][j] = stoi(num.substr(i, j - i + 1));
} catch (...) {
nums[i][j] = -1;
}
}
}
}
vector ops(num.size() - 1, 0);
helper(num, nums, target, ops, results, 0, 0, 0, 1);
return results;
}
private:
// helper function. 对于关键的参数做一下说明：ops是记录如何选取运算符的，没
有什么特别的地方。
cur 表示的是当前所在的位置，prev表示的是在走到cur下标前最近的一个连续数字串
的起始位置（没有被运算符打断的），sum表示的是目前当前已经处理过的加加减减的
临时和。mul是表示从最后一次加减运算开始的连乘积，在乘积没有被另一个运算符打
断（或者是被走到终点打断）之前，乘积需要单独保存出来不要添加到sum里面。
void helper(string& num, vector >& nums, int target, vector<
char>& ops, vector& results, int cur, int prev, int sum, int mul) {
if (cur == num.size() - 1) {
if (nums[prev][cur] != -1 && sum + mul * nums[prev][cur] ==
target) {
string numOps;
for (int j = 0; j < num.size() - 1; j++) {
numOps.push_back(num[j]);
if (ops[j] != 0) {
numOps.push_back(ops[j]);
}
}
numOps.push_back(num[num.size() - 1]);
results.push_back(numOps);
}
} else {
if (nums[prev][cur] != -1) {
ops[cur] = '+';
helper(num, nums, target, ops, results, cur + 1, cur + 1,
sum + mul * nums[prev][cur], 1);
ops[cur] = '-';
helper(num, nums, target, ops, results, cur + 1, cur + 1,
sum + mul * nums[prev][cur], -1);
ops[cur] = '*';
helper(num, nums, target, ops, results, cur + 1, cur + 1,
sum, mul * nums[prev][cur]);
}
ops[cur] = 0;
helper(num, nums, target, ops, results, cur + 1, prev, sum, mul);
}
}
}; | | | j**********3
发帖数: 3211 | 11 求代码
【在 g******z 的大作中提到】
: DFS+递归可以过
| m******3
发帖数: 346 | 12 贴个leetcode讨论区的解答，思想就是一边生成一边计算
void addOperators(vector& result, string nums, string t, long long
last, long long curVal, int target) {
if (nums.length() == 0) {
if (curVal == target)
result.push_back(t);
return;
}
for (int i = 1; i<=nums.length(); i++) {
string num = nums.substr(0, i);
if(num.length() > 1 && num[0] == '0')
return;
string nextNum = nums.substr(i);
if (t.length() > 0) {
addOperators(result, nextNum, t + "+" + num, stoll(num), curVal
+ stoll(num), target);
addOperators(result, nextNum, t + "-" + num, -stoll(num), curVal
- stoll(num), target);
addOperators(result, nextNum, t + "*" + num, last * stoll(num),
(curVal - last) + (last * stoll(num)), target);
}
else
addOperators(result, nextNum, num, stoll(num), stoll(num),
target);
}
}
vector addOperators(string num, int target) {
vector result;
addOperators(result, num, "", 0, 0, target);
return result;
} | j**********3
发帖数: 3211 | 13 cannot read c++
is there a java/python version?
【在 m******3 的大作中提到】
: 贴个leetcode讨论区的解答，思想就是一边生成一边计算
: void addOperators(vector& result, string nums, string t, long long
: last, long long curVal, int target) {
: if (nums.length() == 0) {
: if (curVal == target)
: result.push_back(t);
: return;
: }
: for (int i = 1; i<=nums.length(); i++) {
: string num = nums.substr(0, i);
| l*3
发帖数: 2279 | 14 不会写java，但是我网上搜过其他题目在program creek上面java的solution，
个人认为c++和java的语法风格还是基本一致的，读起来应该通用，连蒙带猜的应该知
道代码是啥意思。
【在 j**********3 的大作中提到】
: cannot read c++
: is there a java/python version?
| j**********3
发帖数: 3211 | 15 他家没有这道题答案。。。你在哪看到的。。。
【在 l*3 的大作中提到】
: 不会写java，但是我网上搜过其他题目在program creek上面java的solution，
: 个人认为c++和java的语法风格还是基本一致的，读起来应该通用，连蒙带猜的应该知
: 道代码是啥意思。
| t**r
发帖数: 3428 | 16 Leetcode题目爆棚了 则是要骗钱还是要累死刷题er | j**********3
发帖数: 3211 | 17 不行了，看了一个晚上这个题，智商hold不住了 | C****p
发帖数: 6 | 18 我的java代码，暴力两层dfs，672ms竟然过了。。。
第一层遍历所有数字组合，第二层遍历所有运算符组合，calculate的时候用了deque来
处理乘法优先的情况
不得不说这题有点变态，好像是G家的面试题？
public class Solution {
public List addOperators(String num, int target) {
List ans = new ArrayList();
if (num == null || num.length() == 0) {
return ans;
}
char[] digits = num.toCharArray();
List numbers = new ArrayList();
dfs(ans, target, numbers, digits, 0);
return ans;
}
private void dfs(List ans, int target, List numbers, char[
] digits, int pos) {
if (pos == digits.length) {
if (numbers.size() == 1) {
if (numbers.get(0) == target) {
ans.add(String.valueOf(target));
}
} else {
char[] operators = new char[numbers.size()-1];
for (int i = 0; i < operators.length; ++i) {
operators[i] = '+';
}
dfsOperator(ans, target, numbers, operators, 0);
}
return;
}
long number = 0;
for (int i = pos; i < digits.length; ++i) {
number = number * 10 + digits[i] - '0';
numbers.add(number);
dfs(ans, target, numbers, digits, i+1);
numbers.remove(numbers.size()-1);
if (i == pos && digits[i] == '0') break;
}
}
private void dfsOperator(List ans, int target, List digits
, char[] operators, int pos) {
if (pos == operators.length) {
if (calculate(digits, operators) == target) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < digits.size(); ++i) {
builder.append(digits.get(i));
if (i < operators.length) {
builder.append(operators[i]);
}
}
ans.add(builder.toString());
}
return;
}
dfsOperator(ans, target, digits, operators, pos+1);
operators[pos] = '-';
dfsOperator(ans, target, digits, operators, pos+1);
operators[pos] = '*';
dfsOperator(ans, target, digits, operators, pos+1);
operators[pos] = '+';
}
private long calculate(List digits, char[] operators) {
Deque deque = new LinkedList();
Queue opList = new LinkedList();
deque.offerLast(digits.get(0));
for (int i = 0; i < operators.length; ++i) {
int j = i + 1;
char op = operators[i];
long digit = digits.get(j);
if (op == '*') {
long lastDigit = deque.pollLast();
deque.offerLast(lastDigit * digit);
} else {
opList.offer(op);
deque.offerLast(digit);
}
}
while (!opList.isEmpty()) {
char op = opList.poll();
long num1 = deque.pollFirst();
long num2 = deque.pollFirst();
long num = (op == '+') ? (num1 + num2) : (num1 - num2);
deque.offerFirst(num);
}
return deque.peekFirst();
}
} | b**w
发帖数: 78 | 19 Python的，写的比较乱
class Solution(object):
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
result = self.helper(num, 0, target)
return result
def helper(self, num, pos, target):
result = []
if pos>=len(num):
if target==0:
result.append("")
return result
if pos==len(num)-1:
if int(num[pos])==target:
result.append(num[pos])
return result
buf_cur = {}
for i in range(pos, len(num)):
buf_next = self.computeNext(buf_cur, num, i)
for left in buf_next:
right_add = self.helper(num, i+1, target-buf_next[left])
for item in right_add:
new_item = left+"+"+item if len(item)>0 else left
result.append(new_item)
right_sub = self.helper(num, i+1, buf_next[left]-target)
for item in right_sub:
if len(item)>0:
result.append(left+"-"+self.reverse(item))
buf_cur = buf_next
return result
def reverse(self, item):
result = ""
for i in range(len(item)):
if item[i]=="-":
result += "+"
elif item[i]=="+":
result += "-"
else:
result += item[i]
return result
def computeNext(self, buf, num, i):
buf_next = {}
if not buf:
buf_next[num[i]] = int(num[i])
return buf_next
for item in buf:
item_arr = item.split('*')
if len(item_arr)>0 and item_arr[-1]!="0":
item_n1 = "*".join(item_arr[:-1]+[item_arr[-1]+num[i]])
if buf[item]!=0:
val_n1 = buf[item]/int(item_arr[-1])*(int(item_arr[-1])*
10+int(num[i]))
else:
val_n1 = 0
buf_next[item_n1] = val_n1
# pdb.set_trace()
item_n2 = "*".join(item_arr+[num[i]])
val_n2 = buf[item]*int(num[i])
buf_next[item_n2] = val_n2
return buf_next
【在 j**********3 的大作中提到】
: 求代码
| l********l
发帖数: 91 | 20 我用的跟你一样的思路，也是同一个例子超时。我理解就是很多步骤都被重算了。
比如123456789这个序列，要是遍历的前半段是1+2+3+4+5的话，每次便利后面的4个数
字的组合时，都要重新计算这个1+2...+5……所以就超时啦～ | j**j
发帖数: 4 | 21 看了大家的思路，也整理一下java的解法，用static的函数弄的，没测试过速度。。。
public static ArrayList mathToTarget(String nums, long target) {
ArrayList result = new ArrayList<>();
long val1 = 0;
long val2 = 0;
for (int i = 1; i <= nums.length(); i++) {
val2 = Long.parseLong(nums.substring(0, i));
dfs(nums, i, val1, val2, target, nums.substring(0, i), result);
if (nums.charAt(0) == '0') break;
}
return result;
}
public static void dfs(String nums, int index, long val1, long val2, long
target, String path, ArrayList result) {
if (index == nums.length()) {
if (val1 + val2 == target) result.add(path);
return;
}
for (int i = index + 1; i <= nums.length(); i++) {
String str = nums.substring(index, i);
long temp = Long.parseLong(str); // parse to Integer is in Integer
class
dfs(nums, i, val1 + val2, temp, target, path + "+" + temp, result);
// for +
dfs(nums, i, val1 + val2, -temp, target, path + "-" + temp, result);
// for -
dfs(nums, i, val1, val2*temp, target, path + "*" + temp, result); //
for *
if (nums.charAt(index) == '0') break; // remove 0xxx
}
}
public static void main(String[] args) {
System.out.println(mathToTarget("123", 6)); // [1+2+3, 1*2*3]
System.out.println(mathToTarget("232", 8)); // [2+3*2, 2*3+2]
System.out.println(mathToTarget("00", 0)); // [0+0, 0-0, 0*0]
System.out.println(mathToTarget("3456237490", 9191)); // []
} |
|
