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 条评论