LeetCode高频100题刷题记录之——两数求和

终于开始刷LeetCode了，还没有系统学习过数据结构，导致第一题做出来就很垃圾，只会使用暴力求解，还使用了巨多判断来试图简化计算过程，结果是计算量没有省不说，还严重增加了调试成本。

但是毕竟刚开始，接受自己是个菜鸡的事实也不丢人嘿嘿，因此记录一下用python实现两数求和的过程，包括暴力破解和哈希表查找法，不得不说，哈希表在处理这种问题时真的很有优势，刚刚接触哈希表，后续再不断学习吧！

1 暴力破解法

1.1 思路

做题的时候看到要求尽可能复杂度小于$O(N^2)$，但是暴力破解基本上不可能实现，只能尽可能想办法降低到侠义的$O(N^2)$以下，其实算法复杂度从大$O$计算法来说还是$O(N^2)$。

输入：nums: List[int], target: int

输出：result: List[int]，预定义result为None

具体思路是：

Step1：判断target是正还是非正；

Step2：构建六个空list，分别存储nums中等于0，等于target，等于target/2，以及根据正负号判断其在不同区间内的nums的索引；

Step3：判断target是否为0，若是，进一步判断nums中为0的数是否有两个，若有，则输出前两个作为result，结束程序；若无，转Step4；

Step4：判断是否存在nums中有为0与target的数，若存在，输出这两种情况各自的第一个数的索引作为result，结束程序；若无，转Step5；

Step5：判断nums中是否存在有两个以上数值为target/2的数，若存在，则输出符合条件的前两个数的索引为result，结束程序；若不存在，则转Step6；

Step6：判断nums中处于①(0, target/2)与②(target/2, target)（target为正）或处于①(target, target/2)与②(target/2, 0)（target为负）的数的存在情况，若①②都存在，遍历两组的数据，若能找到①+②=target的数，取出对应索引，作为result的值，结束程序；若①或②不存在，或者不满足①+②=target，转Step7；

Step7：判断nums中处于①(target, +∞)与②(-∞, 0)（target为正）或处于①(-∞, target)与②(0, +∞)（target为负）的数的存在情况，若①②都存在，遍历两组的数据，若能找到①+②=target的数，取出对应索引，作为result的值，若①或②不存在，或者不满足①+②=target，报错，结束程序。

1.2 Python代码

代码可在Leetcode中直接运行。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = None
        neg_idx = []    # 存储nums中数值小于0（target为正）或小于target（target为负）的数
        pos_idx = []    # 存储nums中大于target（target为正）或大于0（target为负）的数

        small_idx = []  # 储存nums中大于0但小于target/2的数
        large_idx = []  # 存储nums中大于target/2但小于target的数

        zero_idx = []   # 存储nums中为0的数
        half_idx = []   # 存储nums中为target/2的数
        equal_idx = []  # 存储nums中为target的数

        if target > 0:          # target为正的情况
            for i in range(len(nums)):
                if nums[i] == 0:
                    zero_idx.append(i)
                elif nums[i] == target:
                    equal_idx.append(i)
                elif nums[i] == target/2:
                    half_idx.append(i)
                elif nums[i] < 0:
                    neg_idx.append(i)
                elif nums[i] < target/2:
                    small_idx.append(i)
                elif nums[i] < target:
                    large_idx.append(i)
                else:
                    pos_idx.append(i)
        
        else:  # target <=0的情况
            for j in range(len(nums)):
                if nums[j] == 0:
                    zero_idx.append(j)
                elif nums[j] == target:
                    equal_idx.append(j)
                elif nums[j] == target/2:
                    half_idx.append(j)
                elif nums[j] > 0:
                    pos_idx.append(j)
                elif nums[j] > target/2:
                    large_idx.append(j)
                elif nums[j] > target:
                    small_idx.append(j)
                else:
                    neg_idx.append(j)

        if (target == 0) & (len(zero_idx) >= 2):
            result = [zero_idx[0], zero_idx[1]]
            return result
        elif (len(zero_idx) > 0) & (len(equal_idx) > 0):  # 判断是不是有简单结果1存在
            result = [zero_idx[0], equal_idx[0]]
            return result
        elif len(half_idx) >= 2:
            result = [half_idx[0], half_idx[1]]
            return result
        elif (len(neg_idx) > 0) & (len(pos_idx) > 0):

            for sub_i in neg_idx:
                if result is not None:
                    break

                for sub_j in pos_idx:
                    if nums[sub_i] + nums[sub_j] == target:
                        result = [sub_i, sub_j]
                        break
            if result is not None:
                return result
        if result is None:
            if (len(small_idx) > 0) & (len(large_idx) > 0):
                for sub_i in small_idx:
                    if result is not None:
                        break

                    for sub_j in large_idx:
                        if nums[sub_i] + nums[sub_j] == target:
                            result = [sub_i, sub_j]
                            break
                if result is not None:
                    return result
                else:
                    raise ValueError("数组中没有和为target的两个数！")
            else:
                raise ValueError("数组中没有和为target的两个数！")

1.3 算法评价

判断过程过多，容易出错，过于冗余，虽然理论上可以减少一点计算量，但计算值过多时性能优势不明显。时间复杂度为$O(N^2)$。

2 哈希表实现

2.1 思路分析

计算target与nums的差，再以差为key创建字典，判断时进行索引，方法较为简单，不做算法说明了。

2.2 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = None

        len_nums = range(len(nums))
        keys = [target - nums[i] for i in len_nums]  # 散列函数构造，以target与nums中每个数的差作为key
        nums_dict = dict(zip(keys, len_nums))  # 根据key与值建立对应的哈希表，在python中是字典
        
        for i in len_nums:
            if nums[i] in nums_dict.keys():
                if i != nums_dict[nums[i]]:
                    result = [nums_dict[nums[i]], i]
                    return result
                    break
        if result is None:
            raise ValueError("nums中没有符合条件的两个数！")

对比官方题解，发现我的代码真的太繁琐了，官方的代码非常整洁，真的强。

下面是官方题解，思路值得学习。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []
    
#  作者：LeetCode-Solution
#  链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
#  来源：力扣（LeetCode）
#  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LeetCode高频100题刷题记录之——电话号码的字母组合

解法1

根据ASCII码表进行查表，不自己计算字符，然后每增加一个字符，扩充返回列表的结果数目为原来的l（新数字包含的字母数目）倍：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        if len(digits) > 0:
            for s in digits:
                a = len(result)
                if a == 0:
                    result = self.getcode(s)
                else:
                    newcode = self.getcode(s)
                    result = result*len(newcode)
                    for i in range(len(result)):
                        result[i] = result[i] + newcode[i//a]
        return result


    def getcode(self, s: str) -> List[str]:  # 查表
        if ord(s) <= 55:
            baseord = ord('2')+47+(ord(s)-ord('2'))*3
            if s == '7':
                lennum = 4
            else:
                lennum = 3
        elif s == '8':
            baseord = ord('8') + 60
            lennum = 3
        elif s == '9':
            baseord = ord('9') + 62
            lennum = 4
        return [chr(baseord + i) for i in range(lennum)]

解法2

用递归回溯的方法，将所有可能存成一个哈希表，对所有可能的组合进行递归遍历：（参考自leetcode中相关题解，非原创！！！）

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        if len(digits) > 0:
            cond = {
                "2": "abc" ,
                "3": "def" ,
                "4": "ghi" ,
                "5": "jkl" ,
                "6": "mno" ,
                "7": "pqrs",
                "8": "tuv" ,
                "9": "wxyz",
            }
            def backcheck(now, nextdigits):
                if len(nextdigits) == 0:
                    result.append(now)
                else:
                    for code in cond[nextdigits[0]]:
                        backcheck(now + code, nextdigits[1:])
            backcheck('', digits)
        return result

LeetCode高频100题刷题记录之——盛水最多的容器

1 问题描述

假设在$x$轴上有若干条直线，高度为$h$，因此，我们可以拥有若干个数据点$(x_i,h_i)$，以任意两条直线作为一个水桶的两边，二者之间的垂直距离（$x$轴的差）为水桶底面的长度，则水桶的深度由最短边长决定，找到可以使水桶容量最大的两条直线，算出二者围成的最大面积。

图像来自leetcode官方题解（链接：https://leetcode-cn.com/problems/container-with-most-water/）

2 代码实现

太久没刷题了，基础知识都忘得差不多了，导致完全没有想到使用双指针来解决，如果能把双指针思想记在心里，那很容易就能找到答案。

具体来说，这些直线是按照顺序排列的，他们的$x$轴坐标有明显的顺序之差，我们可以定义左右指针，分别指向直线数据list的两端，这时，我们可以计算得到一个初始面积，这个面积是桶的底面最长时候的结果，由于每两根直线之间的距离都是1，接下来，我们只需要不断缩短底面长度，就可以知道在底面长度不同时的最大面积是多少，最终就可以获取所有直线能够围成的最大面积的长度。

那么如何知道不同底面长度时最大的桶高呢？非常简单，每次缩短底面长度时判断一下两端直线的长度，假如直线较短，那从这边缩短肯定比从右边缩短能够获得更长的底面长度，因此只需要用双指针不断往中间靠拢，留下来的每一阶段的面积一定是当前桶底长度中最大的。

class Solution:
    def maxArea(self, height: List[int]) -> int:

        l     = len(height)
        left  = 0
        right = l-1
        area  = min(height[left], height[right]) * (right-left)
        while (left != right):
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
            
            area = max(area, min(height[left], height[right]) * (right-left))
        
        return area

时间复杂度$O(n)$，只需要遍历所有桶高一次，空间复杂度$O(1)$。