Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求一个数列中最长的等差数列子串长度,python的dict的妙用
参考了Discussion -> https://leetcode.com/problems/longest-arithmetic-subsequence/solutions/3671637/hashmap-video-java-c-python/


 1 #1027
 2 #Runtime: 2571 ms (Beats 66.4%)
 3 #Memory: 45.1 MB (Beats 60.38%)
 4 
 5 class Solution(object):
 6     def longestArithSeqLength(self, nums):
 7         """
 8         :type nums: List[int]
 9         :rtype: int
10         """
11         ans = 0
12         n = len(nums)
13         dp = [defaultdict(int) for _ in range(n)]
14         for i in range(n):
15             for j in range(i):
16                 dif = nums[j] - nums[i]
17                 dp[i][dif] = dp[j].get(dif, 1) + 1
18                 ans = max(ans, dp[i][dif])
19         return ans

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