## 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

## 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

## 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 常見問題 ] How to get symbolic link target in Python?

Source From  Here Question How do I extract the target path from a  symbolic link ? HowTo The problem with  os .readlink()  is it will onl...