Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数和等差数列的相邻数之差,问符合这个差值的最长的子串长度,DP+hash


 1 #1218
 2 #Runtime: 499 ms (Beats 50%)
 3 #Memory: 24.2 MB (Beats 100%)
 4 
 5 class Solution(object):
 6     def longestSubsequence(self, arr, difference):
 7         """
 8         :type arr: List[int]
 9         :type difference: int
10         :rtype: int
11         """
12         ans = 0
13         num = {}
14         for i in range(len(arr)):
15             t = arr[i]
16             if t - difference in num:
17                 num[t] = num[t - difference] + 1
18             else:
19                 num[t] = 1
20             ans = max(ans, num[t])
21         return ans

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