[数据结构与算法]leetcode 1-5 总结

1. Two Sum

方法1：暴力群举

没学算法前，觉得只要暴力能解决的问题就不叫问题，于是幼稚的认为这样就可以：

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

至少想到了边界条件，没有错误的输出， O(n^2)没什么。

方法二：二分查找

后来学了算法后，觉得可以改善：

class Solution: # wrong in leetcode
    def twoSum(self, nums, target):
        def binary_search(arr1, num):
            arr = arr1.copy()
            # arr  changed arr1 not change, need to find the value of arr1 idx
            arr.sort()
            i, j = 0, len(arr) - 1
            while i <= j:
                mid = round((i + j) / 2)
                if arr[mid] < num:
                    i = mid + 1
                elif arr[mid] > num:
                    j = mid - 1
                else:
                    return arr1.index(arr[mid])
            return -1
        # binary search changed the idx
        for i in range(len(nums)):
            res = target - nums[i]
            if res != nums[i]:
                idx = binary_search(nums, res)
                if idx != -1:
                    return [i, idx]
            else:
                nums[i] = res -100000
                idx = binary_search(nums, res)
                if idx != -1:
                    return [i, idx]

这时已经达到O(nlogn)了，勉强可以接受，但这种算法也是自己花了几个小时， 考虑到各种边界条件写出了了，虽然能通过，但在真实的面试中，20分钟绝对写不出来。自能是当作练习，以后决不不用该类算法，因为自己都无法保证下次可以写出来。

方法三：双指针

双指针是极力推荐的一种算法，虽然对于本体是大材小用，但如果变态的面试官就要求O(nlogn)的时间， 这种方法至少满足了条件，也是一种好的算法思想。通过对排好序的数组高低指针的不断接近，最终达到理想的输出。

class Solution: # need to think about the sort changed the idx
    def twoSum(self, nums, target):
        nums_final = nums.copy()
        nums.sort() # nlog(n)
        # binary search to find the idx from both side
        # shift the right and left pointer, because, if nums[left] + nums[right] > target
        # means nums[right] is too big, need to have a smaller, right -= 1
        left, right = 0, len(nums) - 1
        while right > left:
            if nums[left] + nums[right] > target:
                right -= 1
            elif nums[left] + nums[right] < target:
                left += 1
            else:
                if nums[left] != nums[right]:
                    return [nums_final.index(nums[left]), nums_final.index(nums[right])]
                else:
                    x = nums_final.index(nums[left])
                    nums_final[x] = -100000 # in case nums[left] = nums[right]
                    return [x, nums_final.index(nums[right])]

方法四：哈希表

哈希表，就不用都说了，通过牺牲空间换取时间，最好不过了。

class Solution:
    def twoSum(self, nums, target):
        d = {}
        for idx, val in enumerate(nums):
            res = target - val
            if res in d:
                return [d[res],idx]
            else:
                d[val] = idx

• nums = [2,7,11,15]
• target = 9
• 1st loop: d = {}, idx = 0, val = 2, res = 7, 7 is not in d = {}, d = {2: 0}
• 2nd loop: d = {2: 0}, idx = 1, val = 7, res = 2, 2 is in d = {2: 0}, return [d[2], 1], d[2] = 0
  这里已经达到了O(n), 是最理想的算法，以后此类提可以用这种思想。
  In order to get less than O(n^2) time complexity, we need to prepare a dict, increase a bit memory, but decreased time complexity
  一道算法题绝不是学了某一个方法，而是在不断的总结到底需要用什么样的算法。比如顺便还学习了二分法：

def binary_search(arr, num):
    i, j = 0, len(arr) - 1
    while i <= j:
        mid = (i + j + 1) // 2
        if arr[mid] < num:
            i = mid + 1
        elif arr[mid] > num:
            j = mid - 1
        else:
            return mid
    return -1
binary_search([2,7,11,15,16], 16)

2. Add Two Numbers

前期写的代码太多的重复，虽然可以运行，但可读性太差，写了太多的重复，后来经过不多的改善，最终达到了理想的状态。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # prepare a dummy node, can be any value
        dummy = ListNode(0)
        # temp pointed to ListNode(0)
        temp = dummy
        # carry is defined 0
        carry = 0
        # if there is value in l1 and l2
        while l1 and l2:
            val1 = l1.val
            val2 = l2.val
            if (val1 + val2 + carry >= 10):
                dummy.next = ListNode((val1 + val2 + carry) % 10)
                dummy = dummy.next
                carry  = 1
            else:
                dummy.next = ListNode(val1 + val2 + carry)
                dummy = dummy.next
                carry  = 0
            l1 = l1.next
            l2 = l2.next
        
        # if l1 is empty first
        if not l1:
            while l2:
                val2 = l2.val
                if (val2 + carry >= 10):
                    dummy.next = ListNode((val2 + carry) % 10)
                    dummy = dummy.next
                    carry  = 1
                else:
                    dummy.next = ListNode(val2 + carry)
                    dummy = dummy.next
                    carry  = 0
                l2 = l2.next
        
        # if l2 is empty first
        if not l2:
            while l1:
                val1 = l1.val
                if (val1 + carry >= 10):
                    dummy.next = ListNode((val1 + carry) % 10)
                    dummy = dummy.next
                    carry  = 1
                else:
                    dummy.next = ListNode(val1 + carry)
                    dummy = dummy.next
                    carry  = 0
                l1 = l1.next
                    
        if carry == 1:
            dummy.next = ListNode(1)
        return temp.next

改善后, 代码由50多行变成了16行，而且是完全一样的逻辑。改善后的更加符合算法的逻辑，容易固化。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        p = dummy = ListNode()
        carry = 0
        while l1 or l2:
            if l2 and l1:
                val = l1.val + l2.val + carry
            elif l1:
                val = l1.val + carry
            else:
                val = l2.val + carry
            p.next = ListNode(val % 10)
            p = p.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
            carry = val // 10
        if carry: p.next = ListNode(1)
        return dummy.next

Single Linked List plus

• 1 Prepare a dummy
• 2 Use a carry
• 3 the result is a new linked list

3. Longest Substring Without Repeating Characters

方法一：暴力

class Solution:
    def lengthOfLongestSubstring(self, s):
        if s == '':
            return 0
        final = []
        for i in range(len(s)):
            arr = []
            arr.append(s[i])
            for j in range(i + 1, len(s)):
                if s[j] not in arr:
                    arr.append(s[j])
                else:
                    break
            final.append(arr)
        return max([len(item) for item in final])

方法二：滑动窗口

虽然能运行，但没有必要用数组存储，应为不是求字符串，是求长度。

class Solution: # 126s, 111s
    def lengthOfLongestSubstring(self, s):
        if s == '':
            return 0
        temp = []
        res = []
        for i in range(len(s)):
            if s[i] not in temp:
                temp.append(s[i])
            else:
                res.append(temp)
                temp = temp[temp.index(s[i]) + 1:]
                temp.append(s[i])
        res.append(temp)
        return max([len(i) for i in res])

方法三：优化后滑动窗口

求长度，可以直接定义整型变量，时间和空间均为最优。但是s[right] not in s[left: right]，需要消耗大量时间，可以用哈希表处理。

longest, left, right = 1, 0, 1
        if len(s) < 2:
            return len(s)
        while right < len(s):
            if s[right] not in s[left: right]:
                longest = max(longest, right - left + 1)
            else:
                left = s.index(s[right], left, right) + 1
            right += 1
        return longest

方法四：滑动窗口+哈希表

原本认为使用set后时间会加快，结果变差，可能set增加删除消耗时间太多，不如list的直接访问，不需要额外空间。总之后两种算法都是O(n^2).

longest, left, right = 0, 0, 0
        hash_set = set()
        while right < len(s):
            if s[right] not in hash_set:
                hash_set.add(s[right])
                right += 1
                longest = max(longest, right - left)
            else:
                hash_set.remove(s[left])
                left += 1
        return longest

4. Median of Two Sorted Arrays

方法1：排序

O((m+n)*log(m+n)), 不满足要求, 这可是难度级别的题，不可能比容易的题都简单。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums1.extend(nums2)
        nums1.sort()
        if len(nums1) % 2 == 1:
            return nums1[len(nums1) // 2]
        return (nums1[len(nums1) // 2 - 1] + nums1[len(nums1) // 2]) / 2

方法2：归并数组

O(m+n), 不满足要求

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums1.extend(nums2)
        nums1.sort()
        if len(nums1) % 2 == 1:
            return nums1[len(nums1) // 2]
        return (nums1[len(nums1) // 2 - 1] + nums1[len(nums1) // 2]) / 2

方法3：D & Q 分治

O(log(m+n)), 重来没用过在两个数组中同时用二分查找，更多的难点是边界条件，另外在

• return self.findMedianSortedArrays(nums2, nums1)
  这条语句上不太理解返回结果，一度怀疑自己的指针理解有问题，函数理解有问题，总之始终要保持nums1的长度小于nums2，否则会出现index out of range.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        x, y = len(nums1), len(nums2)
        low, high = 0, x
        while low <= high:
            partitionX = (low + high) // 2
            partitionY = (x + y + 1) // 2 - partitionX
            
            maxLeftX = -float('inf') if partitionX == 0 else nums1[partitionX - 1]
            minRightX = float('inf') if partitionX == x else nums1[partitionX]
            maxLeftY = -float('inf') if partitionY == 0 else nums2[partitionY - 1]
            minRightY = float('inf') if partitionY == y else nums2[partitionY]
            
            if maxLeftX <= minRightY and maxLeftY <= minRightX:
                if (x + y) % 2 == 1:
                    return max(maxLeftX, maxLeftY)
                else:
                    return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
            elif maxLeftX > minRightY:
                high = partitionX - 1
            else:
                low = partitionX + 1

5. Longest Palindromic Substring

方法1: 暴力

n^3

class Solution:
    """
    T = O(n^3)
    """
    def Palindrome(self, List): # check from outside to middle
        for i in range(len(List)):
            if List[i] != List[len(List) - i - 1]:
                return False
        return True
    def longestPalindrome(self, s):
        # 1 put all the palindromic substrings in a container list
        # 2 choose the longest
        L_str = list(s)
        if len(L_str) == "":
            return ""
        L_new = [] # for all the palindromic substrings
        for i in range(len(L_str)):
            for j in range(i, len(L_str)):
                if Solution.Palindrome(self, L_str[i:j + 1]) == True:
                    L_new.append(L_str[i:j + 1])
        l = max([len(item) for item in L_new]) # need only one max
        for item in L_new:
            if len(item) == l:
                return "".join(item)

方法2：双指针

class Solution:
    """
    T = O(n^2) is better, but there is nlog(n) method
    two case: odd and even of res
    from center to edge
    """
    def longestPalindrome(self, s):
        res = ''
        length = 0
        for i in range(len(s)):
            # odd case
            l, r = i, i
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > length:
                    res = s[l: r + 1]
                    length = r - l + 1
                l -= 1
                r += 1
            # even case
            l, r = i, i + 1
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > length:
                    res = s[l: r + 1]
                    length = r - l + 1
                l -= 1
                r += 1
        return res

方法3：双指针+函数

用函数优化代码，因为有复用，另外检查回型文，如果指针重中间出发，可以大大减少运算量。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def helper(l, r):
            while l >= 0 and r < len(s) and s[r] == s[l]:
                l -= 1
                r += 1
            return s[l+1: r]
        
        res = ""
        for i in range(len(s)):
            test = helper(i, i)
            if len(test) > len(res): res = test
            test = helper(i, i + 1)
            if len(test) > len(res): res = test
        return res

通过前期和后期刷题对比发现，之前只要能运行就行，后来更多的考虑时间与空间。