算法节公开课-面试算法机器学习.pdf

面试算法与机器学习 七月算法 邹博 2015年7月7日 即将进行的…  7 月算法基础班  7 月11 日起每周六、周日下午2-4 点，一周双课。  8月面试求职班  7 月25 日起每周六、周日上午10-12点，一周双课 算法节公开课 2/42 正在进行与已经完成的  6月机器学习班  6月27 日正式开课，共计20 次课。 已经进行了前 4 次数学知识的回顾和总结，本周末开始第5 次：线性回归。  已经结束的  3 月机器学习班  4 月算法班  5月算法班 算法节公开课 3/42 内容提要  算法：  三字母字符串组合  最短路径条数问题  分割词汇问题  机器学习 ：  贝叶斯网络 算法节公开课 4/42 三字母字符串组合  仅由三个字符A 、B 、C构成字符串，且字符 串任意三个相邻元素不能完全相同。如 “ACCCAB”不合法，“ABBCBCA”合法。求 满足条件的长度为n 的字符串个数。  假定不考虑整数溢出  要求时间和空间复杂度不高于O(N) 。 算法节公开课 5/42 问题分析  若当前已经有了所有长度为n-1的合法字符 串，如何在末端增加一个字符 ，形成长度为 n 的字符串呢？  将长度为n-1字符串分成“ 末尾两个字符不相 等”和“ 末尾两个字符相等” 两种情况，各自 数目记做dp[n-1][0], dp[n-1][1]： 算法节公开课 6/42 dp[n][0]结尾不相等/ dp[n][1]结尾相等  ××……×AB / ××……×AA  dp[n][0]=2*dp[n-1][0]+ 2*dp[n-1][1]  ××…… ×ABA ，××……×ABC  ××…… ×AAB ，××……×AAC  dp[n][1]=dp[n-1][0]  ××…… ×ABB  初始条件  dp[1][0]=3  dp[1][1]=0 算法节公开课 7/42 状态转移方程总结与改进  状态转移方程 ： dp[n][0]  2 *dp[n1][0] 2 *dp[n1][1]   dp[n][1]  dp[n1][0]   滚动数组 ： dp[0]  2 *dp[0] 2 *dp[1]   dp[1]  dp[0]   使用滚动数组，将空间复杂度由O(N) 降到O(1) 算法节公开课 8/42 dp[0]  2 *dp[0] 2 *dp[1]