基础算法之动态规划

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,属于过程优化的范畴,在现在的很多程序处理过程中广泛运用,直接正题吧,概念性的可以百度更深入了解,
今天我先来点简单的例子:

来一道题:找出给定字符串中的最长回文串;
回文串:即对称串,比如aaabbb、adda、a,除了字符本身外,回文串一定是偶数个字符,是基于中心对称的.
我们试试最常规的写法(暴力):
遍历每一个起始位置,再遍历每一个结束位置,再遍历每一个起始到结束位置的字符判断是不是回文,balabalalalalalalalla….时间复杂度O(n^3)
还是放弃吧…

下面看看动态规划的处理方式:
dp[i][j]=0表示子串[i,j]不是回文串。dp[i][j]=1表示子串[i,j]是回文串
则:
状态转移方程:dp[i,j]{=dp[i+1,j-1],if(s[i]==s[j]) || =0,if(s[i]!=s[j])}

我们把当前状态转移到了他的子集,这样就好处理了许多;

public static void main(String[] args) {
String s = “aaabbbbbbaaasss”;
if(s.length() <=1) //字符长度小于等于1,直接输出
System.out.println(s);
int maxLength = 0;
int start = 0;//记录最长回文串的开始位置
int[][] dp = new int[s.length()][s.length()];//二维数组,用于状态转移
for (int i = 0; i < s.length(); i++) {//初始化能保证[i,i]第i个位置到第i个位置即单个字符一定是回文串,如果[i,i+1]也等的话也一并初始化
dp[i][i] = 1;
if(i<s.length()-1 && s.charAt(i)==s.charAt(i+1))
{
dp[i][i+1]=1;
start=i;
maxLength=2;
}
}
for (int l = 3; l <= s.length(); l++) {//遍历所有的子串长度
for (int i = 0; i <= s.length()-l; i++) {//遍历所有长度的起始位置
int j = i + l – 1;//那么计算出子串的结束位置就该是它了
if(dp[i+1][j-1] == 1 && s.charAt(i)==s.charAt(j)){//对每个子串向前回溯,如果当前的起止位置字符相等并且向里缩进的子串是回文串,那么当前的起止串一定也是回文串
dp[i][j]=1;//当前的起止串标记为回文串
maxLength=l;//记录最大长度(如果有更长的,之前的就会被覆盖)
start=i;//记录每个长度的起始位置
}
}
}
if(maxLength >= 2)
System.out.println(s.substring(start,maxLength));
else
System.out.println(“没有最长回文!!!”);
}
动态规划处理这个问题的时间复杂度O(n^2),比之前快了很多,但是这个例子不够形象,我们从最简单的地方入手:

我们看一个数塔问题:TIM图片20170913144601

图片不清晰,再描述下问题:要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
状态转移方程dp [i] = max(dp[左孩子] , dp[右孩子]) + dp[i]
public static void main(String[] args) {
int[][] dp= {//初始化数塔
{9,0,0,0,0},
{12,15,0,0,0},
{10,6,8,0,0},
{2,18,9,5,0},
{19,7,10,4,16}
};
for(int i = 4; i > 0; i–) {
for (int j = 0; j < i; j++) {
dp[i – 1][j] += dp[i][j] > dp[i][j + 1] ? dp[i][j] : dp[i][j + 1];//如果左边比右边大,那么只加左孩子,反之加右孩子
//每次加完之后的值都会赋给上一层,直到dp[0][0],这样总能保证和最大
}
}
System.out.println(dp[0][0]);
}

暂时就这些吧,下次再补充~~~

mysql分表分页

之前涛哥建议用代码拼接的方式去分表分页,而不是sql拼接(不要union,也不要list分页),我就这么做了,贴一下代码分享下,有点乱,有更好的建议欢迎提出:
详细代码参考(axxBank)com.aixuexi.axxBank.dao.IncomeRecordDetailDao#getActualAccountInfoByCondition

List<IncomeRecordDetailInfo> list = new ArrayList<IncomeRecordDetailInfo>();
DateFormat df = new SimpleDateFormat(DateConstant.FORMAT_PATTERN_YMD1);
List<String> dateList = FinaicialCommon.getDateArrayByDate(actualAccountParams.getStartDate(), actualAccountParams.getEndDate());//对接入的起始日期作处理,决定接下来要查哪些表
int startIndex = (pageBean.getPageNum() – 1) * pageBean. getPagesize();//分页的开始位置
int endIndex = pageBean.getPageNum() * pageBean.getPagesize();//分页的结束位置
int sum = 0,start,end;//sum(记录开始到当前的总结果数) start(limit的开始位置) end(limit的大小)
Map<String, Integer> mapCount = getIncomeCountList(actualAccountParams, dictionaryIds, dateList, df);//获取每个分表对应的结果数 以及总结果数 (key:dateString value:各分表的结果数)
for (int date = dateList.size() – 1; date >= 0; date –) {//默认按时间倒序
String dateString = dateList.get(date);
String tableIncomeString = new StringBuilder(“income_record_”).append(dateString).toString();//分表名
String tableAmountString = new StringBuilder(“amount_record_”).append(dateString).toString();//分表名
StringBuilder sb = 。。。。//对分表的sql查询,我就不贴代码了,可以到对应的代码处查看
if(isPage) {//是否需要分页()
int resultCount = mapCount.get(dateString) == null ? 0 : mapCount.get(dateString);//每次(每个分表)查询的结果数
/**以下是分表分页算法,用于拼接分表之后的分页查询结果**/
sum += resultCount;//记录当前的结果总数,用于分页拼接
if (sum >= startIndex) {//sum 当前的结果总数 startIndex 分页的开始位置
if (sum > endIndex) {//当前结果总数是否大于分页的结束位置(当前表已经满足分页请求了)
start = startIndex – (sum – resultCount) < 0 ? 0 : (startIndex – (sum – resultCount)); //计算查询当前表的开始位置 如果为负置为0
end = startIndex – (sum – resultCount) + pageBean.getPagesize();//查询当前表的结束位置
sb.append(” LIMIT “).append(start).append(“,”).append(end-start);//对当前表指定分页,分页大小直接pageSize也行
list.addAll(jdbcTemplate.query(sb.toString(), new IncomeRecordDetailMapper()));
break;
} else if (sum <= endIndex) {//当前结果总数小于 分页的结束位置(当前表不满足分页请求,拼接完当前表,则继续拼接下一个表)
start = (startIndex – (sum – resultCount)) < 0 ? 0 : (startIndex – (sum – resultCount));//当前表的开始位置 如果为负置0
end = resultCount; //当前表的结束位置,结束位置直接是当前表的总结果数
sb.append(” LIMIT “).append(start).append(“,”).append(end);//当前表指定分页
list.addAll(jdbcTemplate.query(sb.toString(), new IncomeRecordDetailMapper()));
}
}
}else {//不需要分页的话直接拼接所有结果
list.addAll(jdbcTemplate.query(sb.toString(),new IncomeRecordDetailMapper()));
}
}

新人培训的感想和建议

感想:业务性的整体培训以及整体技术架构的普及对于新员工来说是非常有必要的,不仅让我们对公司整体的发展方向有一个清晰的认识,也丰富了我们的技术和业务认知,对今后的工作也有了清晰的定位。

建议:1.随着业务体系的庞大,我觉得上线这个流程应该是对于项目团体来说的,项目组应该有自己的上线服务权限,也就是说运维和业务技术团队应该独立;2.日志体系,随着业务线的增长,日志将来会应用于许多场景,如统计分析,行为分析采集,以及系统性能诊断等方面;3.代码质量审查,降低代码的重构率,规范编码质量,是有必要的;4.新项目开发或是重构的流程规范。我能想到的暂时就这些,不知道对不对或是符不符合,请大家指出~