给定一个整数数组 A
,返回 A
中最长等差子序列的长度。
回想一下,A
的子序列是列表 A[i_1], A[i_2], ..., A[i_k]
其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1
。并且如果 B[i+1] - B[i]
( 0 <= i < B.length - 1
) 的值都相同,那么序列 B
是等差的。
示例 1:
输入:[3,6,9,12]
输出:4
解释:
整个数组是公差为 3 的等差数列。
示例 2:
输入:[9,4,7,2,10]
输出:3
解释:
最长的等差子序列是 [4,7,10]。
示例 3:
输入:[20,1,15,3,10,5,8]
输出:4
解释:
最长的等差子序列是 [20,15,10,5]。
提示:
2 <= A.length <= 2000
0 <= A[i] <= 10000
假设有俩在数组上的数字 A[i]
与 A[j]
则他们的差值则为 A[i] - A[j] = d
。
(0 ≤ j < i < A.length)
假设 dp[d][i]
为公差为 d
,索引为 i
的等差数列子串的元素个数,则有动态规划方程:
有了动态规划方程接下来写代码就很简单了,代码如下:
class Solution:
def longestArithSeqLength(self, A: List[int]) -> int:
from collections import defaultdict
length = len(A)
if length == 2:
return 2
m = 2
dp = defaultdict(dict)
for j in range(length):
for i in range(j + 1, length):
d = A[i] - A[j]
if j in dp[d]:
dp[d][i] = dp[d][j] + 1
else:
dp[d][i] = 2
m = max(dp[d][i], m)
return m
《97 Things Every Programmer Should Know》- Automate Your Coding Standard
这篇文章写的是如何让编码规范在团队中得以实行,文章举了一个很扎心的例子:
在项目的开启动会议的时候,项目主要负责人们会定下一些编码规范,但是在项目开始开发时,同一个项目的开发者们往往并没有去遵守,可能是迫于各种各样的原因,最后项目完成后,项目代码简直不堪入目,最后负责人们也会迫于项目进度等压力睁一只眼闭一只眼。
那么问题来了,我们应该怎么去避免出现这种情况呢,文章给了几个建议:
给出的这几条建议笔者觉得非常的有用,毕竟也是遇到过这种问题,并且利用自动化的方式去管理编码规范。
在 Github 上无意中看到一个项目:
SQLI labs to test error based, Blind boolean based, Time based.
是一个 PHP 项目,帮助开发者理解和学习 SQL 注入,提高编码安全意识。
当然很多人没有 Apache 和 PHP 环境,这里推荐使用 docker,下面是一个仓库链接:
《高效学习:深度,归纳和坚持实践》- 陈皓
学习一个技术需要知道了解:
学习一个技术、知识还要归纳总结。我们积累的知识越多,在知识剑进行联系和区辨能力就越强,对知识进行归纳总结也就越轻松。
不过需要注意的是,如果只学了部分知识或者还没学透,就开始进行归纳总结,那么总结归纳出来的知识结构会是混乱和幼稚的。因此,学习的阶段,可以不急于归纳总结,不急于下判断、作结论,而应该保留部分知识的不确定性,保持对知识的开放太对。
所谓时间出真知,就是学以致用,不然只是纸上谈兵。这里截取一段感触非常深的话。
坚持不懈是一句正确的废话。特别是坚持学习真的是一件反人性的事情。
就像我每周的 ARTS,每天的 Leetcode 算法练习,一开始真的是非常的痛苦,很想放弃,但是现在已经成了一种习惯。能形成这种习惯的主要原因是,把自己坚持形成的成果晒出来,让别人给你点赞,形成正反馈,然后慢慢的就形成了一种习惯,就像吃饭喝水一样。
要做到以上几点,真的需要对技术有热情。引用那句话:
“很多时候,你缺少的不是知识而是热情”!
- 程序员的谎谬之言还是至理名言?