leetcode 刷题之路

作者按：以此记录leetcode刷题之路。python语言。题号是按作者自己刷题的个数累加的。与leetcode中的编号不一致。

1. Two Sum

暴力求解TLE，发现python将数组变成字典，O(n²) ➡️O(n)。

2. Reverse Integer

看清楚返回值也要在[-2³¹, 2³¹ - 1]之间。

3. Palindrome Number

这个我就是在第2题的基础上做的，只需要把负值那一部分去掉即可。
参考别人答案的时候看到可以使用切片：

return str(x) == str(x)[::-1]

4. Roman to Integer

这个做的时候方法比较笨，将for循环改成while循环，可任意更改步长。因为当两个字符组合在一个后，判断下一个字符时要跳两位。

5. Longest Common Prefix

分治策略【不会】
这道题学了python的私有函数和私有变量

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        # python是把0，空字符串‘ ’和None都看作False，把其他数值和非空字符串都看作True 
        if strs == False or len(strs) == 0: return ""
        else:
            return self.__longestCommonPrefix(strs, 0, len(strs)-1)  
    
    def __longestCommonPrefix(self, strs, l, r):
        if l == r:
            return strs[l]
        else:
            mid = int((l+r)/2)
            lcpleft = self.__longestCommonPrefix(strs, l, mid)
            lcpright = self.__longestCommonPrefix(strs, mid+1, r)
            print(lcpleft, lcpright)
            return self.__commonPrefix(lcpleft, lcpright)
    
    def __commonPrefix(self, left, right):
        min_len = min(len(left), len(right))
        for i in range(min_len):
            if left[:i+1] != right[:i+1]:
                # print(left[:i])
                if left[:i] == False: return ""
                else: return left[:i]
        return left[:min_len]

6. Valid Parentheses

数据结构：栈

7. Merge Two Sorted Lists

递归【不会】

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 == None: return l2
        if l2 == None: return l1
        temp = l2
        sendAgain = l1
        if l1.val < l2.val:
            temp = l1
            sendAgain = l2
        newList = ListNode(temp.val)
        newList.next = self.mergeTwoLists(sendAgain, temp.next)
        return newList

8. Remove Duplicates from Sorted Array

这道题虽然最后要求返回新数组的长度，但是最后结果output是按照return 的数组长度打印新数组。这也是这道题目要求原址的原因。
python删除某一有特定元素的方法：

list.pop(元素在数组中的位置)

9. Remove Element

调用两个函数：list.count(val) 和list.index(val)。前者是返回某一元素在list中出现几次，后者查看某一特定元素在list中的下标。
我在该题的discussion里找了一个更简单的答案：

def removeElement(self, nums, val):
    while val in nums:
        nums.remove(val)
   
 return len(nums)

10. Implement strStr()

这道题让我觉得python中string和list的用法没什么区别。但是python中仍然有list和string类型之间的转换。

# string转换为list
a_list = list(a) 
# list转换为string
a = ''.join(a_list)

11. Search Insert Position

从这个题中学到的是在list中插入元素的两种方法：

# 在list的末尾添加新的元素
list.append()
# 在任意位置添加新的元素
list.insert(索引点(即插入的位置), 插入的元素)

12. Count and Say

这个题没意义，看都看不懂。不做。

13. Maximum Subarray

待续。。。
因为想学一下c语言，就先去刷紫书了～