讨论两个面经题

第二题只能用高斯消元法吧，递归是解不出来的

参考https://www.1point3acres.com/bbs/thread-689100-1-1.html 的话，那应该是用高斯消元法？   难道是考数学能力？

请问一下楼主像“T3 = T4 + T5”这样的string具体要如何parse建图啊？

请问第一题的input是什么样？target和text都是string吗？还是需要从text file里面读取string input？

tchhh 发表于 2021-3-24 14:56
请问一下楼主像“T3 = T4 + T5”这样的string具体要如何parse建图啊？

不需要建图，也不需要高斯。我当时后来自己写了下ruby代码，就是字符串parse然后每次把只一个变量放到左边。

1. # 第二题： 给一个target 比如T3, 还有 T1 = 2, T2 = 3, T3 = T4 + T5, T4 = T1 - T2, T5 = T4 + T1, 计算出 T3 = 0, 我的解法是build mappings from T3 -> T4 + T5, T4 -> T1 - T2, T5 = T4 + T1, 然后用recursion计算。
   
2. 
   
3. # Q: is it possible it's given 'T5 = T3 -T4' but target is T3
   
4. def variables_from(expression)
   
5.   output = []
   
6.   window = ''
   
7.   expression.each_char do |char|
   
8.     next if char == ' '
   
9. 
   
10.     if '+-'.include?(char)
    
11.       output << window if !window.empty?
    
12.       window = ''
    
13.     end
    
14.     window << char
    
15.   end
    
16.   output << window if !window.empty?
    
17.   return output
    
18. end
    
19. 
    
20. # 默认不会有相同左值的表达式
    
21. def evaluate(target, expressions)
    
22.   @var_values_map = Hash.new {|h,k| h[k] = []}
    
23.   is_number = Proc.new do |str|
    
24.     str.to_i != 0 || str == '0'
    
25.   end
    
26. 
    
27.   expressions.each do |expression|
    
28.     left, right = expression.split('=')
    
29.     @var_values_map[left.strip] = variables_from(right)
    
30.   end
    
31. 
    
32.   @var_values_map.each do |key, values|
    
33.     values.map! do |value|
    
34.       if is_number.call(value)
    
35.         value.to_i
    
36.       elsif '+-'.include?(value[0])
    
37.         value
    
38.       else
    
39.         '+' + value
    
40.       end
    
41.     end
    
42.   end
    
43. 
    
44.   @visiting = Set.new  # T1 = T2 , T2 = T3, T3 = T1
    
45.   return evaluate_from('+' + target)
    
46. end
    
47. 
    
48. def evaluate_from(variable)
    
49.   return variable if variable.is_a?(Numeric)
    
50.   sign, variable = variable[0], variable[1..-1]
    
51.   raise 'there is cycle' if @visiting.include?(variable)
    
52. 
    
53.   @visiting.add(variable)
    
54. 
    
55.   output = @var_values_map[variable].sum do |next_var|
    
56.     evaluate_from(next_var)
    
57.   end
    
58.   @var_values_map[variable] = [output]
    
59.   output = output * (sign == '+' ? 1 : -1)
    
60. 
    
61.   @visiting.delete(variable)
    
62.   return output
    
63. end
    
64. 
    
65. target = 'T3'
    
66. expressions = ['T1 = 4', 'T2 = 3', 'T3 = T4 + T5', 'T4=T1-T2+2', 'T5 = T4 + T1']
    
67. p evaluate(target, expressions) # 10
    
68. 
    
69. expressions = ['T1 =-3', 'T2 = 8', 'T3 = +T4 +T5', 'T4 = T1- T2', 'T5 = T4 + T1']
    
70. p evaluate(target, expressions) # -25
    
71. 
    
72. expressions = ['T1 =T2', 'T2 =T3', 'T3 =T1']
    
73. p evaluate(target, expressions) # exception

复制代码

不过这题估计愿意肯定不是这样，否则有点复杂了。



补充内容 (2021-03-25 14:00 +08:00):
应该说要建图 但是不是高斯

Smilenceyu 发表于 2021-3-25 13:27
不需要建图，也不需要高斯。我当时后来自己写了下ruby代码，就是字符串parse然后每次把只一个变量放到左 ...

请问一下parse具体如何处理吗？不好意思不会Ruby

tchhh 发表于 2021-03-24 22:52:05
请问一下parse具体如何处理吗？不好意思不会Ruby

就是把等号左右两边分开 然后把每个变量换到左边取负， 并且把其他变量都换到右边 这样每个变量都有会有几个表达式 每个表达式就是一个child node

不知道小帅 发表于 2021-1-26 12:09
第一个我觉得greedy是更好的解法啊。第二个的话，感觉常规是高斯消元。

你所说的贪心本质应该就是暴力搜索，o(MN)的复杂度，不算很好。
当然，DP也是o(MN)的复杂度。
我怀疑wildcard matching并没有线性解。

wisdompeak2 发表于 2021-03-24 23:37:38
你所说的贪心本质应该就是暴力搜索，o(MN)的复杂度，不算很好。
当然，DP也是o(MN)的复杂度。
我怀疑wildcard matching并没有线性解。

看一下原帖 greedy就是线性 我发现你们都是看了第一句话就开始解题了 lol

Smilenceyu 发表于 2021-3-25 22:54
看一下原帖 greedy就是线性 我发现你们都是看了第一句话就开始解题了 lol

你说的原贴是哪一个？有代码吗，我来看看。如果你说的是楼主发的那一层，那么看一下这个例子：
s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaad"
p = "*aaaaaaaaaaaaaaad"

对于s的每一个位置，你都会把p遍历到底，然后发现失败；再移动s的下一个位置。所以这是o(MN)