LeetCode 93. Restore IP Addresses

思路 回溯(backtracing),用s的起始位置pos表示当前的状态(pos之前的已经处理完)。那么就依次尝试1~3位的字符看看是否符合要求,符合就把结果更新到buffer里,未完成就递归继续,然后递归返回的时候记得把buffer恢复到之前的状态。 按照题目的意思,应该不允许IP地址有前导0,即01.01.01.01这种状态. 对了,stoi函数很好用,应该是C++11新加的。 代码

 

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 43. Multiply Strings

注意/思路 保存 被乘数*[0…9]的结果备用,然后移位相加即可 乘数末尾是0 代码 9ms

 

LeetCode 385. Mini Parser

思路 一开始还以为又回到了编译原理,想到了状态转换图啊之类的。后来发现这个题目没有这么变态,要考虑的是个栈的问题。 为什么会想到栈呢?因为看到了括号,因为括号结束的时候我们要把某个部分的内容添到更大的括号里头去。 我的处理方式是: 构造一个工作栈,一开始是空的  碰到数字 生成一个只包含数字的NestedInteger 如果工作栈空,那么字符串就是个纯数字,直接返回 如果工作栈非空,那么这个字符串就要加到当前工作栈顶端的元素后面(考虑情况[35,345]这种) 碰到'[‘ 新建一个空的NestedInteger(至于里面填什么,不是这里要考虑的事儿) 把它压入栈 碰到’]’ 取出当前栈顶元素formerTop 判断栈是否空了 非空,则formerTop要加到当前栈顶的后面 空,可以返回了 碰到’,’ 其实没什么用,往前挪动吧 这个步骤还能再精简一下的,判断栈是否空,是否返回的部分是重复了 代码

题目 Given a nested list of integers represented as a string, implement a parser to deserialize it. Each element is either an integer, or a list — whose elements may also be integers
Continue reading LeetCode 385. Mini Parser

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

LeetCode 151. Reverse Words in a String

题目 Given an input string, reverse the string word by word. For example, Given s = “the sky is blue“, return “blue is sky the“. Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space. 思路 一!定!要!考!虑!各!种!情!况!比如

然后这种倒转问题的原地处理思路应该都明白的,先把整个字符串倒转一遍,然后按照单词再倒转回来,拿”the sky is blue”为例: “eulb si yks eht“ “blue si yks eht” “blue is
Continue reading LeetCode 151. Reverse Words in a String