Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出两个数列arr1和arr2,可以进行操作将arr1[i]换为arr2[j],求问最少操作几次可以让arr1变为严格递增数列,如果不存在输出-1,DP+二分搜索+memorization
参考了Discussion-> https://leetcode.com/problems/make-array-strictly-increasing/solutions/2290360/python-detailed-explanation-intution-explained-dp-clear-and-concise/


 1 #1187
 2 #Runtime: 4197 ms (Beats 25%)
 3 #Memory: 193.2 MB (Beats 25%)
 4 
 5 class Solution(object):
 6     def makeArrayIncreasing(self, arr1, arr2):
 7         """
 8         :type arr1: List[int]
 9         :type arr2: List[int]
10         :rtype: int
11         """
12         n1 = len(arr1)
13         n2 = len(arr2)
14         arr2.sort()
15         dp = {}
16 
17         def cal(i, j, pre):
18             if i == n1:
19                 return 0
20             if (i, j, pre) in dp:
21                 return dp[(i, j, pre)]
22             k = bisect.bisect_right(arr2[j:], pre) + j
23             if k == n2:
24                 ans = float('inf')
25             else:
26                 ans = cal(i + 1, k + 1, arr2[k]) + 1
27             if arr1[i] > pre:
28                 ans = min(ans, cal(i + 1, j, arr1[i]))
29             dp[(i, j, pre)] = ans
30             return ans
31             
32         ans = cal(0, 0, -float('inf'))
33         return ans if ans != float('inf'else -1

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理