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