【leetcode】1027. Longest Arithmetic Sequence
2024-09-05 22:10:51
题目如下:
Given an array
A
of integers, return the length of the longest arithmetic subsequence inA
.Recall that a subsequence of
A
is a listA[i_1], A[i_2], ..., A[i_k]
with0 <= i_1 < i_2 < ... < i_k <= A.length - 1
, and that a sequenceB
is arithmetic ifB[i+1] - B[i]
are all the same value (for0 <= i < B.length - 1
).Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].Note:
2 <= A.length <= 2000
0 <= A[i] <= 10000
解题思路:首先用字典记录A中每个元素出现的下标,接下来求出任意A[i]与A[j]的差值d,依次判断A[j] += d是否存在于A中,并且要求A[j] + d的下标的最小值要大于j,最终即可求出最长的等差数列。
代码如下:
class Solution(object):
def longestArithSeqLength(self, A):
"""
:type A: List[int]
:rtype: int
"""
import bisect
res = 0
dic = {}
for i,v in enumerate(A):
dic[v] = dic.setdefault(v,[]) + [i]
for i in range(len(A)):
for j in range(i+1,len(A)):
count = 2
diff = A[j] - A[i]
next = A[j] + diff
smallestInx = j
while True:
if next not in dic:
break
inx = bisect.bisect_right(dic[next],smallestInx)
if inx == len(dic[next]):
break
smallestInx = dic[next][inx]
next = next + diff
count += 1
res = max(res,count)
return res
最新文章
- PHP匿名函数的使用
- 完整的Ajax及三级联动小练习
- Reduce inversion count 求最小逆序数
- Linux Deepin 2014安装Lenovo LJ2600D驱动
- 【Servlet】doGet()与doPost()的区别
- dynamic调用时报RuntimeBinderException:“object”未包含“xxx”的定义 错误
- 近期Responsive web design项目经验分享
- bzoj3932
- 前后端分手大师——MVVM 模式
- 【Linux搭建创建FTP服务器】---完美解决 - 费元星
- Web开发问题记录
- Xilinx Vivado的使用详细介绍(4):Zedboard+vivado之流水灯(加SDK)
- QUARTZ系列之二-监听器
- Shell脚本- 单条命令循环执行重复工作
- 转://oracle deadlock死锁trace file分析之一
- 七牛 qshell 全命令实践
- Python撰写mail
- web自动化测试---css方式定位页面元素
- mysql 自增长
- Entry point (0x08000000) points to a Thumb instruction but is not a valid Thumb code pointer.
热门文章
- 监听整个页面上的DOM树变化
- Delphi XE2 之 FireMonkey 入门(29) - 数据绑定: TBindingsList: 表达式的 Evaluate() 方法
- 四种方法给Vmware虚拟机清理瘦身
- PHP多图片上传 并检查 加水印 源码
- SoapUI常用的参数化方法
- 阅读笔记09-Java程序员必备的Intellij插件
- 绕过安全狗Apache4.0版本
- Git利用命令行提交代码步骤
- css-sprite 雪碧图的使用,合并多张小图,背景图片当按钮的设置
- React入门教程1---初见面