Learning Python With LeetCode

用leetcode学习python (一)

学而不思则罔, 思而不学则殆. 以学促练, 以练固学, 巩固知识, 扩大优势.

余之学从此始也.

1001

1002

一个处理链表, 防止因为跳转而找不到头指针的思路就是: 新建一个头节点. 更便于统一代码, 更美观了.

python 在函数传递对象的时候, 都是传递的“地址”, 这里是统一的.
区别在于修改的时候. Python中分为不可变和可变对象, 对于不可变的对象(如数字, 元组, 字符), 你不能修改其值, 只能通过更改地址指向另外一个值. 所以它们传入时地址不变, 而改变值也就改变了地址, 就和原本的对象区分开了. 因此也就造成了”传参”的假象. 此外, 类的实例本身也是不可变对象(但里面的对象不一定是).

python 里面, 如果两个对象保存了一样数字或者字符串, 地址也会相同. 这里面真是奇妙啊…… 希望我能很快接触到其底层的实现逻辑( 等把某几本书看完就一定 )

学到了一个类似三目的写法, 还有一个divmod支持同时返回商和余数的元组.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        result = ListNode(0)
        result_tail = result
        carry = 0
                
        while l1 or l2 or carry:            
            val1  = (l1.val if l1 else 0)
            val2  = (l2.val if l2 else 0)
            carry, out = divmod(val1+val2 + carry, 10)    
                      
            result_tail.next = ListNode(out)
            result_tail = result_tail.next                      
            
            l1 = (l1.next if l1 else None)
            l2 = (l2.next if l2 else None)
               
        return result.next

1003

寻找最长的不包含重复字符的子串。 当然是用两个指针O（n）。

已经想到用字典判断一个字符是否出现过了，为什么想不到直接记录出现的位置呢……省事很多……

循环的时候, range()只指定结束, 默认从0开始.
判断某个key是否在字典中, 使用 in

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        usedChar = {}
        
        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)

            usedChar[s[i]] = i

        return maxLength

1004

两个有序数组的共同中位数.
写代码的时候脑子一定要清醒, 先想好边界条件再动手.

因为原题目两个数组可能都没有元素, 而且访问容易超界, 所以可以在开头和结尾各补一个很小的数, 一个很大的数. 这样子不会影响中位数.

学到了一个很好的方法:
一个*可以展开列表,两个**可以展开字典,所以可以这样写:
num1 = [-100001, *num1, 100001]

如果用dict =[**dict1,**dict2] 的话, 后面的相同key会覆盖前面的

'''
I assume you have already known that:
the quantities of elements before and after the medium number is equal, which  are both equal to (m+n)/2. And the numbers before the medium number must be the prefix of both arraies.
However, there are some exceptions:  one of the two arraies may don't contain any number, the prefix of one array may is equal to the array itself. So you must pay your whole attention on boundary conditions to assure that your program won't access an invalid position like nums1[-1] or nums[n].
You can just avoid this by inserting -1MAXN at the beginning and MAXN at the end, where MAXN means a large enough number that bigger than the max number in the previous array. In this case you can use -100000 and 100000.
since you are supposed to find the medium number, inserting a smallest and a biggest number doesn't matter. And then you can ignore the condition that array is empty, cause there must be at least two numbers.
What's more, you can insert an extra inf at the end or an extra -inf at the beginning. Then you won't consider accessing an invalid position.
Here is my code. I know is ugly to read, but is easy to write. :)
#散装塑料英文
'''
class Solution:
        
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        len1, len2 = len(nums1)+2, len(nums2)+2
        tlen = int( (len1+len2) / 2 )  # need's length
        lt, rt = 1, len1  
        
        nums1.append(1000001)
        nums1.append(1000001)
        nums2.append(1000001)
        nums2.append(1000001)
        nums1.insert(0,-1000001)
        nums1.insert(0,-1000001)
        nums2.insert(0,-1000001)
        nums2.insert(0,-1000001)
        while(lt < rt):
            mid = int ( (lt + rt + 1 ) / 2 )
            t = tlen - mid 
            if(t > len2):
                lt = mid
                continue
            if(t < 0):
                rt = mid -1
                continue
            if( nums2[t+1] < nums1[mid] ):
                rt = mid - 1
            else:
                lt = mid
        
        if( (len1+len2) %2 != 0):
            return min( nums1[lt+1] , nums2[tlen-lt+1] )
        else:
            summ = max ( nums1[lt], nums2[tlen-lt] )
            summ += min ( nums1[lt+1] , nums2[tlen-lt+1])
            return summ / 2