[leetcode]easy

Reverse interger

python 
helloworld 

9.Palindrome

检查输入数字是否位回文，比如121 颠倒后也为121，-121颠倒后121-显然不是。

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """   
        y = str(x)[::-1]
        if y == str(x):
            return True
        else :
            return False

12. Roman to Integer

这个题目是吧罗马文的字符串转化为阿拉伯数字，比如：

Input: "IV"
Output: 4

值得注意的是：
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

基于此， 考虑从后向前，遍历字符串。每一字符都和它后一个进行比较，若小于后者，则在计算结果中减去它，比如
I < V
result = V - I
代码如下：

class Solution(object):
    def romanToInt(self, s):
        Symboldic = {'I':1,
                     'V':5,
                     'X':10,
                     'L':50,
                     'C':100,
                     'D':500,
                     'M':1000}
        if len(s) == 1 :
            return  Symboldic[s]
        res  = Symboldic[s[-1]] 
        temp = s[-1]  #将字符串最后一个保存
        for c in s[len(s)-2::-1]: #从右第二个向左 遍历字符串
            if Symboldic[c] < Symboldic[temp]: #比较它和后者的大小
                res -= Symboldic[c]  #若小于，意味着这是一个组合罗马数 
            else:
                res += Symboldic[c] #若大于，意味着这是一个单独罗马数，加入总和即可
            temp = c #向前滚动
        return res

其中，用到了字符串的倒置操作

s = '12345'
s[::-1] = '54321'
s[包含：不包含：step/-1代表从后向前]
exp:
     s[:0:-1] = s[3:0:-1] =  432

网友给出的简洁版：

d = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}

def romanToInt(self, s):
    res, p = 0, 'I'
    for c in s[::-1]:
        res, p = res - d[c] if d[c] < d[p] else res + d[c], c
    return res

14. Longest Common Prefix

这个题目是xunzhao 一个字符串链表中所有字符串的最长相同前缀。思路是另外写一个寻找一对字符串最长前缀的副函数。然后，在主函数中遍历每个字符串并调用副函数。代码如下：

class Solution(object):
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        temp = strs[0]
        for s in strs[1:]:
            temp = self.comstri(temp,s)
            if temp == "":
                return ""
        return temp 
  def comstri(self,s1,s2): #计算一对字符串的最长前缀
        res = ''
        for i in range(min(len(s1),len(s2))):
            if s1[i] == s2[i]:
                res += s1[i]
            else:
                break
        return res 

网友给出的代码：

class Solution:
    # @return a string
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""     
        for i, letter_group in enumerate(zip(*strs)):
            if len(set(letter_group)) > 1: 
                return strs[0][:i]
        else:
            return min(strs) #eg:  s =['flow', 'flowa','flowab'] , min(s) = flow
           #return min(strs, key = lambda str : len(str))

代码中中到了 zip()方法，用法如下：

>>>a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b)     # 打包为元组的列表
[(1, 4), (2, 5), (3, 6)]
>>> zip(a,c)              # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]
>>> zip(*zipped)          # 与 zip 相反，*zipped 可理解为解压，返回二维矩阵式
[(1, 2, 3), (4, 5, 6)]

20. Valid Parentheses

这道题是计算是否括号成对出现：

Input: "()"
Output: true
Input: "([)]"
Output: false
Input: "{[]}"
Output: true

首先考虑用栈来实现，代码如下：

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'(':')', '{': '}', '[' : ']',')':'(','}':'{',']':'['}
        stack = []
        for e in s:
            if not stack:
                stack.append(e)
            else:
                if stack[-1] == dic[e]:
                    stack.pop()
                else :
                    stack.append(e)
        if not stack:
            return True
        else :
            return False

21. Merge Two Sorted Lists

合并两个有序链表

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        NL = ListNode(None)
        n1 = l1 
        n2 = l2 
        Nl = l1
        end = Nl
        i = 1 
        while n1 != None and n2!= None :
            if n1 == None :
                end.next = n2
            if n2 == None :
                end.next = n1
            if i %2 == 0:
                end.next = n1
                end = end.next
                n1 = n1.next
            elif i %2 !=  0:
                Nl.next = n1
                end = end.next
                n2 = n2.next
            i += 1
        return Nl

26. Remove Duplicates from Sorted Array

这个题是返回列表中不重复的元素个数，不知道为什么用set()通过不了

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        l = 0
        for i in range(1,len(nums)):
            if (nums[i]!= nums[l]):
                l += 1
                nums[l] = nums[i]
        return l+1

27. Remove Element

去除列表中给定值的元素，返回剩余元数个数。
这个题和上个题的难点都在于，只能对该列表操作和修改，不能通过构建新的表来实现功能。道理与上题类似

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        rel = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[rel] = nums[i]
                rel+= 1  
        return rel

28. Implement strStr()

这个题是返回字符串中子串的位置，python用index() 或 find()很容易实现.

1 find()方法：查找子字符串，若找到返回从0开始的下标值，若找不到返回-1

info = 'abca'
print info.find('a')##从下标0开始，查找在字符串里第一个出现的子串，返回结果：0
 
info = 'abca'
print info.find('a',1)##从下标1开始，查找在字符串里第一个出现的子串：返回结果3
 
info = 'abca'
print info.find('333')##返回-1,查找不到返回-1

2 index()方法：
python 的index方法是在字符串里查找子串第一次出现的位置，类似字符串的find方法，不过比find方法更好的是，如果查找不到子串，会抛出异常，而不是返回-1

info = 'abca'
print info.index('a')
print info.index('33')

rfind 和 rindex与上面类似，只是从字符串尾端查找。题目代码如下：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle not in haystack:
            return -1
        return haystack.index(needle)

35. Search Insert Position

list 的 index方法与上面类似

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target not in nums:
            if target < nums[0]:
                return 0 
            if target > nums[-1]:
                return len(nums)
            for i in range(len(nums)-1):
                if target>nums[i] and target<nums[i+1]:
                    return i+1
        return nums.index(target)
###或者
    def searchInsert(self, nums: List[int], target: int) -> int:
        for k in range(len(nums)):
            if nums[k]>=target:
                return k
            
        return len(nums)
###或者二分法查找？