leetcode水题记:很久没有写解题报告了,拙劣的代码水准,完成作业就逃~

本周是第一周,主要水一点简单题目练练手,它们分别是

  • 1  Two Sum
  • 7  Reverse Integer
  • 9  Palindrome Number
  • 13  Roman to Integer
  • 14  Longest Common Prefix

1 Two Sum

一句话题意:

给你一组整数,其中两个数相加的值恰好等于目标数,求这两个数对应的数组下标。

需要注意的是,同一个数只能用一次,该数组有且仅有一对符合条件的数字。

解题思路1:时间复杂度O(n^2)  空间复杂度O(n)

很容易想到,遍历两遍枚举两两相加,找到和等于目标值两个数就返回答案,跳出循环。

解题思路2:时间复杂度O(n)  空间复杂度O(n)

对于数组中的任意一个数,我们可以用目标数减去它然后就得到所需要的另一个数(假设它存在的话)。为了迅速找到另一个数是否在数组中以及它的位置,我们可以使用哈希表。哈希表让每个数查找时间降到常数级别O(1)。

这样我们在读入一个数时,求得所需的另一个数,就可以通过查询哈希表来判断另一个数是否存在,如果存在那么返回其位置结束;如果不存在,将当前数存入哈希表,继续处理下一个数。这样每次查找求值操作的时间复杂度都是O(1),一共进行n次,故最终时间复杂度为O(n),比解题思路1 的O(n^2)大大降低了。

代码:由于题目过于简单以及写得太丑,想套用STL但垃圾LeetCode不支持hash_map,就不放源代码了。有一次提交用了C11的unordered_map,反而比map更慢了,玄学。

7  Reverse Integer

一句话题意:

32位整数,从最高位到最低位依次反转(如123->321),保留符号。

注意32位整数翻转后可能越界,自行判断。

解题思路:

太基本了,过于简单。

while(x) {

res = res*10 + x%10;

x /= 10;

}

9  Palindrome Number

一句话题意:

判断这个整数是否是回文数,即最高位到最低位依次反转之后仍是一样的数。

解题思路:时间复杂度O(logN) 空间复杂度O(1)

负数不是回文数,除了0以外个位为0的正整数也不可能是回文数。

对于其他情况,跟上题一样,求其反转之后的数,比较是否相等即可。

13  Roman to Integer

一句话题意:

罗马数字转成十进制数。

解题思路:时间复杂度O(n) 空间复杂度O(1)

罗马数字规则简明

1. 罗马单个数字共有7个,即I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)
2.一个罗马数字重复几次,就表示这个数的几倍。但同一数码不能出现三次以上。
3.遵循右加左减的规则。
左减的数字有限制,仅限于I、X、C。比如45不可以写成VL,只能是XLV
但是,左减时不可跨越一个位数。比如,99不可以用IC(100 – 1)表示,
而是用XCIX([100 – 10] + [10 – 1])表示。(等同于阿拉伯数字每位数字分别表示。)
左减数字必须为一位,比如8写成VIII,而非IIX。

罗马数字转十进制数

基本思路:把输入的罗马数字分段处理,分段相加。从左到右,一个个检测过去。
设置 当前位current,上一位pre,分段值temp。
如果当前位对应的值和上一位的一样(current == pre),那么分段值加上当前值{temp += current;}。比如III = 3
如果当前位对应的值大于上一位的(current > pre),说明分段值应该是当前值减去现有的分段值{temp = current – temp;}。比如IV = 5 – 1
如果当前位对应的值小于上一位的(current < pre),那么可以先将当前分段值加到结果中,重新开始记录分段值{result += temp;temp = current;}。比如XI = 10 + 1

源代码略。

14  Longest Common Prefix

一句话题意:

找到一堆字符串中的最长公共前缀子串。

解题思路:时间复杂度O(nm) 其中n为字符串个数,m为最长子串长度

无脑题,将第一个字符串的第一个值跟其它每个字符串的第一个值相比,如果相等则保存当前值并比较下一位,如果不相等则退出循环返回刚刚保存下来的字符串。

源代码略。

本周小结

LeetCode的水题也太水了。。。比USCOW的超级大模拟水多了。。。。

总的来说,好久没有打代码,出了好多次CE,是时候重新认真来过了。嗯,就这样。

——子灵

2017年9月12日


0 条评论

发表评论