TagArray

算法数据结构.png

Array

# 1. Two Sum
# array of integers,specific target ==> return indices
class Solution:
    def twoSum(self,num,target):
        map={}  # 字典 k-v存放 i的匹配值-i；对于{}，用in, map[key]
        for i in range(len(num)):  # 遍历num,获取i匹配的下标;range();
            if num[i] not in map:  # 字典 O(1)查找 当前num[i]是否已被前面匹配；
                map[target-num[i]]=i  # map标记 当前i的目标匹配项
            else:
                return i,map[num[i]]  # i已经被标记，通过map[num[i]]找寻前面匹配脚标
            # 返回的是位置，字典通过“数值”查询“位置”
        return -1,-1  #循环所有都没有匹配
    

# # Trapping Rain Water
# # elecation map; width 1; trap??
# # ==>300T/60=>5h
# 输入：height_List；
# 挖掘边界 最外层==>l_index&r_index  
# 挖掘固定参考边界 固定一侧 内层&&l_max&r_max&&ans
# 挖掘具体移动l+=或边界更新 及取值ans+= &&height[l]&height[r]&ans
class Solution:
    def trap(self, height: List[int]) -> int:
#       结果&边界点&边界值
        ans = 0
        l,r = 0 , len(height) -1
        l_max, r_max = 0,0
#       边界点内；
        while l < r:
#           右侧高点
            if height[l] < height[r]:
#               左侧高点置换
                if height[l] >= l_max:
                    l_max = height[l]
#               至左侧积水  
                else:
                    ans += l_max - height[l]
                l += 1            
#            左侧高点
            else:
#               右侧高点置换
                if height[r] >= r_max:
                    r_max = height[r]
                else:
                    ans += r_max - height[r]
                r -= 1   
        return ans

# 4. Median of Two Sorted Arrays
# two sorted arrays nums1 and nums2 of size m and n
# Find the median of the two sorted arrays
class Solution:
    def findMedianSortedArrays(self, A,B) -> float:
        l = len(A) + len(B)
        if l % 2 == 1:
            return self.kth(A, B, l // 2)
        else:
            return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2.   
    def kth(self, a, b, k):
        if not a:
            return b[k]
        if not b:
            return a[k]
        ia, ib = len(a) // 2 , len(b) // 2
        ma, mb = a[ia], b[ib]
        # when k is bigger than the sum of a and b's median indices 
        if ia + ib < k:
            # if a's median is bigger than b's, b's first half doesn't include k
            if ma > mb:
                return self.kth(a, b[ib + 1:], k - ib - 1)
            else:
                return self.kth(a[ia + 1:], b, k - ia - 1)
        # when k is smaller than the sum of a and b's indices
        else:
            # if a's median is bigger than b's, a's second half doesn't include k
            if ma > mb:
                return self.kth(a[:ia], b, k)
            else:
                return self.kth(a, b[:ib], k)

# Maximum Subarray
# In: Array
#=>contiguous subarray ; Largest Sum

class Solution:
    def maxSubArray(self, A: List[int]) -> int:
        if not A:
            return 0
        curSum = maxSum = A[0]
        for num in A[1:]:                    #遍历一遍 同时寻找当前局部最大和 与历史最大和
            curSum = max(num, curSum + num)  #当前值 加入 或开始
            maxSum = max(maxSum, curSum)     #当前处的最大和
        return maxSum

# 15. 3Sum
# array nums: a + b + c = 0? 
# all unique triplets;

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l +=1 
                elif s > 0:
                    r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1; r -= 1
        return res

• Tips:

1. 警惕自以为是的懂得；
   大体懂得——细节全懂——弦外之音；