LeetCode简单类型01(1-7-9-13-14)

发表于 | 分类于 | 阅读次数

这篇文章记录了leetcode上1.两数之和、7.反转整数、9.回文数、13.罗马数字转整数 、14.最长公共前缀五道题目的答案和解析。

1、两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例：

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)
        rlist=[]
        if length==0:
            return False
        for i in xrange(length-1): # n
            #print(nums[i+1:length])
            if (target-nums[i]) in nums[i+1:length]:
                rlist.append(i)
                rlist.append(nums[i+1:length].index(target-nums[i])+i+1)
                return rlist

首先呢，这道题的考点在于算法，因为你可以暴力解决，但显然有更高效的方法，所以我们就要想办法不去一次又一次的遍历整个列表，如果过一遍就能找到答案？或者更少的遍历？

1
2
if length==0:
    return False

这是排除掉极端情况，给的列表为空的时候，这也是最容易忽视的，虽然对于整个算法来说不是那么复杂，不是那么重要，但是没有它，你的算法一定会出bug。

1
for i in xrange(length-1):

用来遍历整个数组，因为你要找到整个数组中符合要求的索引，那么最优算法的最坏情况就是遍历一遍。

1
if (target-nums[i]) in nums[i+1:length]:

这句是算法的精髓，我们从头开始遍历整个列表，遇到一个元素使用in来判断一下target-nums[i]是否在剩下的列表中nums[i+1:length]（想一下为什么是在剩余的列表中找，而不是在整个列表中），若没有，则可以肯定，当前的num[i]一定不是我们想要的，继续往后找，如果发现差值存在与列表的剩余部分，则现在我们已经找到了和为target的两个值，最后只需使用list.index(value),即可找到他们对应的索引。

1
2
rlist.append(i)
rlist.append(nums[i+1:length].index(target-nums[i])+i+1)

7、反转整数

给定一个 32 位有符号整数，将整数中的数字进行反转。假设我们的环境只能存储 32 位有符号整数，其数值范围是 [ − 2^31 , 2^31 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def __init__(self):
	    self.min_int = -pow(2,31)
        self.max_int = pow(2,31)-1
        self.maxint_10 = self.max_int//10
        self.maxint__10 = self.max_int%10
    def reverse(self, x):
        import sys
        """
        :type x: int
        :rtype: int
        """
        rSum = 0
        neg_flag=0
        if x==self.min_int:
	        return 0
        if x<0:
            x = -x
            neg_flag=1
        while(x!=0):
            a = x%10
            x = x//10
            if (rSum > self.maxint_10) or (rSum == self.maxint_10 and a>self.maxint__10):
                return 0
            else:
                rSum = rSum*10+a
        if neg_flag:
            rSum = -rSum
        return rSum

这道题重点不在算法，解法比较直观，考察了怎么判断变量值是否溢出，下面根据代码来梳理一下思路：

1
2
3
4
5
def __init__(self):
    self.min_int = -pow(2,31)
    self.max_int = pow(2,31)-1
    self.maxint_10 = self.max_int//10
    self.maxint__10 = self.max_int%10

这里我新添加了构造函数，用来生成几个频繁使用的大数，因为他们每一次循环都要使用，如果用的时候在计算浪费时间。

1
2
3
4
5
6
7
rSum = 0
neg_flag=0
if x==self.min_int:
	return 0
if x<0:
    x = -x
    neg_flag=1

这里为什么要进行最小值的判断呢？在下一段在解释，由于本题的极端情况就是溢出，所以在开始并不需要进行额外的判断，在这里我们要说明一点，也是比较坑爹的一点，关于C++和Python的不同：

1
2
3
c++: 
	int a = -123 % 10; // a = -3
	int b = -123 / 10; // b = -12

1
2
3
python:
	a = -123 % 10 # a = 7
	b = -123 % 10 # b = -13

知道以上区别后，我第一反应是赶紧把负数取反，当作正数来处理，但是你的正数的最大值是2^31-1，而最小值是-2^31，如果给你一个最小值，你直接取反，那就会溢出了，所以需要提前判断一下，若等于最小值，则直接判定为溢出。

1
2
3
4
5
6
7
while(x!=0):
    a = x%10
    x = x//10
    if (rSum > self.maxint_10) or (rSum == self.maxint_10 and a>self.maxint__10):
        return 0
    else:
        rSum = rSum*10+a

while里面的判断是整个解决方法中最精髓的地方，你要判断的数还不是一下就给你了，而是每循环一次增加着，这就会出现一个问题，你每次增加的时候不能判断是否溢出，只有你增加完后才能进行判断，这就需要我们进行超前判断，就是在溢出值之前就进行判断，提前预知是否可能会溢出。结合本题中数值增长的特点，我们取self.max_int//10做为判断点，如果当前值大于这个数，那么你的下一次增长一定溢出，如果等于，则需要再判断一下预增长的量是否大于self.max_int%10这个值，如果大于则还是会溢出，当上面都不满足的时候才进行增加。

1
2
if neg_flag:
    rSum = -rSum

最后，我们再将得到的数根据实际情况求相反数，毕竟我们是把所有数都当作正数处理了，最后还是要对应上的。

9、回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

进阶: 你能不将整数转为字符串来解决这个问题吗？

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        str_x = str(x)
        if str_x[0]=='-':
            return False
        len_x = len(str_x) 
        if len_x==1:
            return True
        inv_x = str_x[len_x-1]
        for i in xrange(1,len_x//2):
            inv_x += str_x[len_x-1-i]
            
        if inv_x == str_x[:len_x//2]:
            return True
        else:
            return False

这个解决方法也有技巧，最直接方法是暴力遍历法，但是不可取，因为这种有规律性的问题，一般都有更高效率的方法，你想一下回文数，正反都一样，规律性很强。

1
2
3
4
5
6
str_x = str(x)
if str_x[0]=='-':
    return False
len_x = len(str_x) 
if len_x==1:
    return True

按照惯例，先把特征情况给解决了，首先，负数肯定不是回文数，因为它有负号，并且个位数（正数）一定是回文数，这个不需要过多解释了，一点就知道。

1
2
3
4
5
6
7
inv_x = str_x[len_x-1]
for i in xrange(1,len_x//2):
    inv_x += str_x[len_x-1-i]
if inv_x == str_x[:len_x//2]:
    return True
else:
    return False

这是算法的主要部分，排除完特殊情况，剩下的回文数中，假设一个数字是由a和b组成，其中a代表前半段，b代表后半段，如果数字的个数是奇数个，则中间剩余一个数字不用管。所以回文数符合 -b = a，其中-b表示b段的倒序，则我们只需要遍历整个数字长度的一半构造出-b就可以了。

13、罗马数字转整数

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def trans(self,r):
        if r=='I':
            return 1
        elif r=='V':
            return 5
        elif r=='X':
            return 10
        elif r=='L':
            return 50
        elif r=='C':
            return 100
        elif r=='D':
            return 500
        elif r=='M':
            return 1000
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        len_s = len(s)
        r_int = 0
        cur_t = 0
        next_t = 0
        i=0
        if len_s==1:
            return self.trans(s)
        while i<len_s:
            cur_t = self.trans(s[i])
            next_t = self.trans(s[i+1])
            if next_t>cur_t:
                r_int = r_int+next_t-cur_t
                i+=2
            else:
                r_int = r_int+cur_t
                i+=1
            if i==(len_s-1):
                r_int+=self.trans(s[i])
                break
        return r_int

这道题感觉不是靠算法的，就是逻辑测试，常规的思路结题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def trans(self,r):
    if r=='I':
        return 1
    elif r=='V':
        return 5
    elif r=='X':
        return 10
    elif r=='L':
        return 50
    elif r=='C':
        return 100
    elif r=='D':
        return 500
    elif r=='M':
        return 1000

这个函数很直观，就是对于单独的一个罗马数字，通过这个函数找到对应的阿拉伯数字。

1
2
3
len_s = len(s)
if len_s==1:
    return self.trans(s)

首先判断特殊情况，字符串长度为1时，直接转换，不同考虑左置情况。

1
2
3
4
5
6
7
8
9
10
11
12
while i<len_s:
    cur_t = self.trans(s[i])
    next_t = self.trans(s[i+1])
    if next_t>cur_t:
        r_int = r_int+next_t-cur_t
        i+=2
    else:
        r_int = r_int+cur_t
        i+=1
    if i==(len_s-1):
        r_int+=self.trans(s[i])
        break

算法的精髓，最优情况肯定是只遍历一遍，就能得到结果，由于罗马数字向阿拉伯数字进行转换的时候存在左置问题，所以我们每次都需要同时考虑前后两个数。当前面的大于或者等于后面的，ok，当前的这个可以直接加了，没问题，因为左置情况中左面一定是小于右面，并将索引加1；当前面的小于后面时，就出现了左置情况，我们要根据定义，加上右面值和左面值的差值，然后索引加2。当遍历到最后一位时（如果最后两位是左置情况，索引会超出数字的长度），说明最后一位是单独的，此时需要特殊处理，因为不能再取它的后面一位了。

14、最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ““，所有输入只包含小写字母 a-z。

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        
        #**********method-1**********
        # r_str = ''
        # for _ ,i in enumerate(zip(*strs)):
        #     if len(set(i))>1:
        #         return r_str
        #     else:
        #         r_str += i[0]
        # return r_str

		#**********method-2**********
        r_str=''
        if len(strs)==0:
            return r_str
        max_len = len(strs[0])
        for i in xrange(max_len):
            temp_str = strs[0][i]
            for item in strs:
                if i>=len(item) or temp_str!=item[i]:
                    return r_str
            r_str+=temp_str
        return r_str

这道题我的理解是属于考察编程能力的题，思路不难。我这实现了两种方法，其中第一种是用了特殊的函数，比较凑巧；第二种比较常规。

1
2
3
4
5
6
7
r_str = ''
for _ ,i in enumerate(zip(*strs)):
	if len(set(i))>1:
		return r_str
	else:
		r_str += i[0]
return r_str

这是第一种方法，使用了zip()和set()函数，其中zip(*list)表示将list中的每个元素拆分开，对应位置形成一个元组，并且按照最短元素的长度对其它元组进行截断，然后整个元组再形成列表，set()函数是去除给定元组中的重复值。

1
2
3
4
5
6
7
8
9
10
strs= ['flower','flow','flat']
zip(*strs):
	[('f','f','f'),
	('l','l','l'),
	('o','o','a'),
	('w','w','t')]

item = strs[0]
item:
	('f')

使用zip()函数很容易看出来，当item的长度等于1时，说明还处于公共前缀中，因为所有元素当前位置的元素都相等，只要不等于1，那就说明至少有一个是和其它不一样的，那么公共前缀也就到此为止了。

1
2
3
4
5
6
7
8
9
10
r_str=''
if len(strs)==0:
    return r_str
max_len = len(strs[0])
for i in xrange(max_len):
    temp_str = strs[0][i]
    for item in strs:
        if i>=len(item) or temp_str!=item[i]:
            return r_str
    r_str+=temp_str

第二种方法比较常规，首先考虑特殊情况，当输出的列表为空时，返回空列表。取第一个元素的长度为遍历范围，为什么？这样想，剩下的元素长度要么大于它，要么小于它，大于的就不考虑了，因为公共前缀最长是最短元素的长度。所以我们现在只要每遍历到一个元素就判断是不是它的最后一位，若是就直接结束，反之则继续。第一次取strs[0]的第一位字符，然后遍历剩余元素的第一位，只要遇到不相同的就退出u，如果都一样，则读取strs[0]的第二位字符，继续进行判断，直到遇到不相同的，或者strs[0]遍历完了，或者遇到了比strs[0]更短的元素，提前结束。