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 or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Example 1:

Example 2:

LeetCode 38. Count and Say

题目

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

思路

好几题没刷leetcode手痒痒,又没太多时间,就选了个Easy的题啦…这个题目确实挺简单的,统计一下前面是不是重复就行了。在句末加一个特殊符号可以避免多写几行代码的样子~

代码

 

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]是单词表中的单词时,有两种处理,一种是算入然后往后走;另一种是忽略这次匹配成功,继续往后寻找。

代码大概这样:

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

然后字典是

这就搞笑了,得匹配死,所以肯定是超时。

思路2

这个是讨论组里看来的,突然发现一般来说DP递归能做的,就可以从后往前用非递归的方法写。对于这个问题来说,从后往前并不像做LCS那样时要完全倒着写。举个例子,有字符串str= thisisawesome 和字典 {this, is, a, we, some, awesome} 的时候,可以用一个缓存cache来记录是否在str[i]位置有单词结束,比如str[3]位置就是”this”这个词结束的地方。当顺着继续搜索的时候,往前查找缓存记录,可以知道如果cache[i]=true的话,那才有可能从i这个位置往后到当前位置组成新单词,接着去查找字典看看有没有这个单词,如果没有的话,就得继续往前找到新的可用的开头i。这里加黑的“才有可能”是比较关键的。

代码大概是这样

这里面向前迭代不断寻找cache[i]并尝试的情况,对应于之前思路1里面找到可用单词后的决定是否使用的分支情况。但是由于减少了一大堆递归调用,所以实际情况下的复杂度降低了不少。

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”为例:

  1. eulb si yks eht
  2. blue si yks eht”
  3. “blue is yks eht”
  4. “blue is sky the”

代码