LeetCode 368. Largest Divisible Subset

思路: 想到一个词叫“传递性”,在这边应该也适用。就是如果b%a==0,然后c%b==0,那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了,应该是动态规划的思想,results[i]保存包含数组元素nums[i]的最佳集合,构建集合的时候,首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳(相当于找到c%b==0,当然这里的b是之前results[j]里面的最大元素,即nums[j])然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合,如此继续… 时间复杂度应该是O(n^2)

 

最长递增子串 (只能忽略m个元素)

记录一道碰到的笔试题。 题目 给定一个int数组,求其最长的连续递增子序列,但递增过程中可以忽略m个数组元素。在最优子序列长度相同时,以子序列元素之和较小的一个为最优解*。 即实现方法

思路 八成是动态规划,参考最长连续子序列。 需要存储状态:第i个元素的{最优序列,忽略元素个数} 从i向前寻找m个位置的最优解(因为最多只能忽略m个)。假设那个“之前的”元素是array[j],那如果array[i]>array[j]并且array[j]+1>=当前最优序列长度,则判断限制条件*以确定是否更新最优解。 整个方法的复杂度应该是,其中n为array的长度。 代码

   

LeetCode 91. Decode Ways

思路 警告:千万注意’0’这个异类,当然了还有空输入:(。 其实也是个动态规划?的问题,有点像那个走楼梯的题 当前能decode的方法数与之前的两种状态有关,就是 判断当前的字母s[i]能不能单个decode,如果可以,那方法数就要加上解码s[i-1]时的方法数,如果不能解那就不加; 判断两个字符s[i-1]s[i]的组合能不能解码(就是在不在10-26的范围内),如果可以,拿加上解码s[i-2]时的方法数; 所以事实上只要保存s[i],s[i-1]两个方法数的结果就行,我的代码空间复杂度还比较大,但是不想改了。 代码

 

LeetCode 64. Minimum Path Sum

思路 动态规划的问题,某一格的状态由它左侧及上侧的状态决定,即 当然了,第一行只由左侧决定,第一列只由上侧决定。 代码

 

LeetCode 139. Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = “leetcode”, dict = [“leet”, “code”]. Return true because “leetcode” can be segmented as “leet code”. 思路 字符串处理的一个题目,首先想到的办法就是穷举:从头开始找N-letter word,查一下在不在字典里呗。但是纯穷举的话显然就会超时,因为这个问题可以分解成下面的子问题,即给定字符串s及起始位置start,寻找s[start…end]能不能够被拆分。这个子问题在暴力搜索的时候很容易被重复,所以得找个东西记录一下状态,碰到相同的子问题就不用再去查字典了。 所以,他是个动态规划的题。 代码

 

LeetCode 139. Word Break

题目 Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = “leetcode”, dict = [“leet”, “code”]. Return true because “leetcode” can be segmented as “leet code”. 思路1 写的第一个版本是超时的,但是思路应当是正确的,反正就是动态规划,但我用的是递归方法。 就是如果找到s[start,end]是单词表中的单词时,有两种处理,一种是算入然后往后走;另一种是忽略这次匹配成功,继续往后寻找。 代码大概这样:

但是如果这里出现了超级多的单字,比如字符串是

然后字典是
Continue reading LeetCode 139. Word Break

Longest Common Subsequence 最长公共子序列

这是个很老的问题了,最近总是碰到,大三时候学的算法好多都忘记了,不如重新学一遍。 比起XXblog上的教程,我最喜欢的还是这个版本:http://www.ics.uci.edu/~eppstein/161/960229.html 里面的代码干净利落,解释也非常的清晰,一步一步怎么来的都很好。 这个问题是个动态规划的问题,最基本的样子是这样的:

由于这样递归能弄出的子问题里面,好多是重复的,因此我们可以像计算斐波那契数列那样,采用自底向上的方法,用非递归的方式实现。即从字符的末尾往前推导LCS[i][j],这样当计算LCS[i][j]的时候, LCS[i+1][j]或LCS[i][j+1]已经计算好了。 具体还是看英文教程吧,这里给出C++实现的代码。因为下午例会还得讲PPT,下面的代码用了全局变量传递计算好的序列,有点丑。