ARTS 打卡 (20.06.08-20.06.14)

用户头像
小王同学
关注
发布于: 2020 年 06 月 14 日

Algorithm:

LeetCode-5 求最长回文数

1、动态规划解法

动态规划要求:

1、定义状态

1、归纳出状态转移方程

2、思考初始化方法

3、思考输出,有时可能要综合之前计算结果

4、考虑空间优化



动态规划就是一个填表的过程



解法:

一个回文字符串去掉两头的字符依然是回文,我们将字符串抽血成一个二维数组,行和列都是字符串字符下标。

1、状态定义

  • boolean dp[i][j] = true 表示s[i....j]是一个回文子串,s是一个左闭右闭区间

2、归纳状态转义方程

  • 要想一个字符串是回文字符串,那么去掉头尾的字符串也是回文字符串,我们可以利用计算好的短字符的结果,再对比首尾向外扩展一个的字符是否想等就可以知道首尾往外扩充一个字符的字符串是不是回文字符串了,总结出状态转移方程为:

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

  • i表示数组左边索引,j表示数组右边索引,因此i,j的边界位于 j-1 - (i+1) < 1,整理方程可得 j - i < 3

  • 两个相邻的字符比如“aa”可以认为该字符串是一个回文字符串,套用表达式为 j -1 - (i + 1) = 1,只要s[i+1] == s[j-1]的时候就可以判定该字符串是回文字符串。

  • 三个字符串时比如“aba”也可以认为它是一个回文字符串,套用表达式j -1 - (i + 1) = 2,只要s[i+1] == s[j-1]的时候就可以判定该字符串是回文字符串。

3、考虑初始化

  • 单个字符一定是回文数,因此我们初始化对角线为true

4、考虑输出

  • 只要dp[i][j]为true的时候就记录初始位置i与步长,最后输出结果的时候截取字符串,截取字符串是一个性能开销较大的操作,没必要步步都截取。

5、表空间优化

  • 暂不处理



public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
//最长的回文字符串的长度
int maxLen = 1;
//回文字符串起始下标
int begin = 0;
//定义二维表格
boolean[][] dp = new boolean[len][len];
char[] charArray = s.toCharArray();
for (int i = 0; i < len; i++) {
// 表格对角线都表示单个字符,都是回文字符
dp[i][i] = true;
}
//从s[0,1]开始判断,然后是s[0,2],s[1,2] s[0,3],s[1,3],s[2,3] s[0,4,s[1,4],s[2,4]....
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
// i j 处于边界 也就是说s[i,j]的长度为2或者为1时,该子串就是回文字符串(最小子串)
dp[i][j] = true;
} else {
// 如果i j 没有处于边界位置,如果s[i + 1, j - 1]是回文字符串那么s[i,j]就是回文字符串
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxLen) {
//记录步长,+1是因为substring取的是左闭右开区间
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}

从代码中可以看出两层for循环,定义了一个二维数组可知时间复杂度是O(N^2)空间复杂度是O(N^2)

Review:

阅读了EnumSet java 1.8的源码以及英文注释,EnumSet从java1.5引入的一种枚举的集合类,EnumSet是基于位向量(bit vectors)的操作,它在时间和空间两个维度上看都是非常高效并且是类型安全的,甚至是批量操作效率也很高。EnumSet是非线程安全类,我们可以在外部加锁或者Collections.synchronizedSet(EnumSet.noneOf(MyEnum.class))方式对EnumSet加锁



EnumSet构造函数中可以看到如果枚举类中的枚举产量数量小于64个时,会去构造RegularEnumSet实例,否则去构造JumboEnumSet实例,JumboEnumSet和RegularEnumSet都是EnumSet的实现,他们内部的实现方法都是通过位运算操作,所以效率非常高。



Tip:

1、通过右移运算符可以实现对一个正数除以2的n次方的操作,

例如

public class Test {
public static void main(String[] args) {
System.out.println(16 >>> 3); //相当于16除以2的3次方
}
}
输出2



2、Enum中可以定义行为,属性,代码块,每个枚举常量中存在属性时,需要在Enum类中定义构造函数,入参就会枚举常量的类型,也可以在Enum中定义抽象方法,枚举常量中可以进行实现,实现多态特性

例如:

enum Fruit {
APPLE("hongfushi", 10) {
public String getInfo() {
return name + price;
}
},
PEAR("shuijingli", 5){
public String getInfo() {
return name + price;
}
};
String name;
int price;
public abstract String getInfo();
Fruit(String dali, int i) {
}
}

Share:

分享一篇耗子叔叔在CoolShell的文章《加班与效率》

https://coolshell.cn/articles/10217.html

我们做的事情不是劳动密集型的工作,而是知识密集型工作,用工时衡量一个人或者团队的产出说明领导或者老板已经找不到公司的核心竞争力,他们只能抓住工时作为救命稻草死死不放。好的产品需要找到核心的竞争力和价值,不是功能的堆砌,要衡量好需求能影响多少客户群体,提个需求开发和收益成本是否得当。

用户头像

小王同学

关注

还未添加个人签名 2019.03.04 加入

还未添加个人简介

评论

发布
暂无评论
ARTS 打卡(20.06.08-20.06.14)