2020年2月26日 星期三

[LeetCode] Medium - 1043. Partition Array for Maximum Sum

Source From Here
Question
Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:
Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]


Note:
* 1 <= K <= A.length <= 500
* 0 <= A[i] <= 10^6

Solution

Naive Approach (DP)
  1. class Solution:  
  2.     def maxSumAfterPartitioning(self, A, K):  
  3.         # 0) Initialization  
  4.         #    best_a is used to keep past computation result  
  5.         #    best_a[i] is to keep local optimal result of A[0:i-1]  
  6.         best_a = [0] * len(A)  
  7.         best_a[0] = A[0]  
  8.   
  9.         # 1) Iteratively fill the best_a with local optimal result  
  10.         #    best_a[0] = A[0]  
  11.         #    best_a[1] = max(best_a[0] + A[1], max(A[0:2]) * 2)  
  12.         #    best_a[2] = max(best_a[1] + A[2], best_a[0] + max(A[1:3]) * 2, max(A[0:3]) * 3)  
  13.         #    ...  
  14.         #    best_a[n] = max(best_a[n-1] + A[n], best_a[n-2] + max(A[n-1:n+1]) * 2, ..., max(A[n-K+1:n+1]) * K)  
  15.         for i in range(1, len(A)):  
  16.             max_v = 0  
  17.             for j in range(i, max(-1, i-K), -1):  
  18.                 sa = A[j:i+1]  
  19.                 v = best_a[j-1] + max(sa) * len(sa)  
  20.                 if v > max_v:  
  21.                     max_v = v  
  22.   
  23.             best_a[i] = max_v  
  24.   
  25.         # 2) The global optimal result is kept in last element  
  26.         return best_a[-1]  

Supplement
花花酱 LeetCode 1043. Partition Array for Maximum Sum - 刷题找工作 EP250

2020年2月22日 星期六

[Linux 常見問題] grep + add time out after some time if not find the relevant match

Source From Here
Question
I use the following command syntax to search params in my script
# grep -qsRw -m1 "any_param" /dir/..../

Some times the search take a very long time. The question is how to add time out to grep command. For example after 20 seconds grep will break out

How-To
There is a Linux command timeout that can do this for you. For example:
# time grep -R -m 1 -e "pattern to search" Github/

real 0m3.627s
user 0m1.824s
sys 0m1.798s


# echo $?
1 // Return code from command grep

# timeout 2s grep -R -m 1 -e "pattern to search" Github/ // Force the grep to timeout after 2 second
# echo $?
124 // Return code from command timeout


2020年2月21日 星期五

[LeetCode] Medium - 1130. Minimum Cost Tree From Leaf Values

Source From Here
Question
Given an array arr of positive integers, consider all binary trees such that:
* Each node has either 0 or 2 children;
* The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
* The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

Example 1:
  1. Input: arr = [6,2,4]  
  2. Output: 32  
  3. Explanation:  
  4. There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.  
  5.   
  6.     24            24  
  7.    /  \          /  \  
  8.   12   4        6    8  
  9. /  \               / \  
  10. 6    2             2   4  
Constraints:
* 2 <= arr.length <= 40
* 1 <= arr[i] <= 15
* It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Solution
Naive Solution
  1. #!/usr/bin/env python  
  2. import sys  
  3.   
  4. class Solution:  
  5.     def mctFromLeafValues(self, arr):  
  6.         sum_of_non_leaf = 0  
  7.   
  8.         print("### arr={}".format(arr))  
  9.         def look_4_min(arr):  
  10.             mi = 0  
  11.             mv = arr[0] * arr[1]  
  12.             for i in range(1, len(arr)-1):  
  13.                 v = arr[i] * arr[i+1]  
  14.                 if v < mv:  
  15.                     mi = i  
  16.                     mv = v  
  17.   
  18.             rst = (mi, max(arr[mi], arr[mi+1]), mv)  
  19.             print('\t{}'.format(rst))  
  20.             return rst  
  21.   
  22.         while len(arr) > 2:  
  23.             print("{}: {}".format(arr, sum_of_non_leaf))  
  24.             mi, mx, mv = look_4_min(arr)  
  25.             sum_of_non_leaf += mv  
  26.             arr[mi:mi+2] = [mx]  
  27.   
  28.         print("{}: {}".format(arr, sum_of_non_leaf))  
  29.         sum_of_non_leaf += arr[0] * arr[1]  
  30.   
  31.         print("[]: {}".format(sum_of_non_leaf))  
  32.         return sum_of_non_leaf  
  33.   
  34. if __name__ == '__main__':  
  35.     s = Solution()  
  36.     for arr, aw in [  
  37.                 ([6,2,4], 32),  
  38.                 ([15,13,5,3,15], 500),  
  39.                 ([1,2,3,4], 20),  
  40.                 ([4,3,2,1], 20),  
  41.                 ([1,3,4,2], 23),  
  42.                 ([4,2,3,1], 21)  
  43.                ]:  
  44.         rel = s.mctFromLeafValues(arr)  
  45.         assert aw == rel  
  46.         print("")  
Execution result:
### arr=[6, 2, 4]
[6, 2, 4]: 0
(1, 4, 8)
[6, 4]: 8
[]: 32

### arr=[15, 13, 5, 3, 15]
[15, 13, 5, 3, 15]: 0
(2, 5, 15)
[15, 13, 5, 15]: 15
(1, 13, 65)
[15, 13, 15]: 80
(0, 15, 195)
[15, 15]: 275
[]: 500
...


Supplement
米开:LeetCode 1130. Minimum Cost Tree From Leaf Values

2020年2月13日 星期四

[NodeJS 文章收集] NodeJS accessing file with relative path

Source From Here
Question
It seemed like a straight forward problem. But I am not able to crack this. Within helper1.js I would like to access foobar.json (from config/dev/)
  1. root  
  2.   -config  
  3.    --dev  
  4.     ---foobar.json  
  5.   -helpers  
  6.    --helper1.js  
Any help here would be great.

How-To
You can use the path module to join the path of the directory in which helper1.js lives to the relative path of foobar.json. This will give you the absolute path to foobar.json:
  1. var fs = require('fs');  
  2. var path = require('path');  
  3.   
  4. var jsonPath = path.join(__dirname, '..''config''dev''foobar.json');  
  5. var jsonString = fs.readFileSync(jsonPath, 'utf8');  

[ Python 常見問題 ] When using unittest.mock.patch, why is autospec not True by default?

  Source From  Here Question When you patch a function using  mock , you have the option to specify  autospec  as True: If you set  autospec...