Uber OA 感恩吐血大放送 求米

第四题晚上做出来了...做到要吐.

第三题 看了10分钟才明白问什么

workworkhard 发表于 2020-12-14 16:41
想问楼主第一题怎么做的

1-D 小dp 当然可以用一个variable解决 dp[num] = dp[num-1] + count(num)

1. def sol(prices, algo, k):
   
2.     ret = rev = 0
   
3.     for i in range(len(prices)):
   
4.         r = prices[i] if algo[i] == 1 else -prices[i]
   
5.         rev += r
   
6. 
   
7.     for start in range(len(prices)-k+1):
   
8.         tmp = rev
   
9.         for j in range(start, start+k):
   
10.             if not algo[j]:
    
11.                 tmp += 2 * prices[j]
    
12.         ret = max(ret, tmp)
    
13.     return ret

复制代码

第三题我这样写然后TLE 只过了13/20。有什么更好的解法吗

第三題sliding window 可以解吧?
麻煩不吝指正

1. 
   
2. func max(a, b int) int {
   
3.         if a > b {
   
4.                 return a
   
5.         }
   
6.         return b
   
7. }
   
8. func buySell(prices []int, algo []int, k int) int {
   
9.         //sliding window
   
10.         diff := 0
    
11.         total := 0
    
12.         for i := range prices {
    
13.                 if algo[i] == 0 {
    
14.                         total -= prices[i]
    
15.                 } else {
    
16.                         total += prices[i]
    
17.                 }
    
18.         }
    
19.         //init
    
20.         for i := 0; i < k; i++ {
    
21.                 if algo[i] == 0 {
    
22.                         diff += 2 * prices[i]
    
23.                 }
    
24.         }
    
25.         max_diff := diff
    
26.         for i := k; i < len(prices); i++ {
    
27.                 if algo[i] == 0 {
    
28.                         diff += 2 * prices[i]
    
29.                 }
    
30.                 if algo[i-k] == 0 {
    
31.                         diff -= 2 * prices[i-k]
    
32.                 }
    
33.                 max_diff = max(max_diff, diff)
    
34.         }
    
35.         return total + max_diff
    
36. }
    
37. 
    
38. func main() {
    
39.         prices, algo, k := []int{2, 4, 1, 5, 2, 6, 7}, []int{0, 1, 0, 0, 1, 0, 0}, 4
    
40.         res := buySell(prices, algo, k) // 21
    
41. }
    

复制代码