LeetCode Cookbook 数组习题（4）

  篇接上回，开始！

127. 单词接龙 * （典型BFS）

题目链接： 题目大意：字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

每一对相邻的单词只差一个字母。 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。 sk == endWord 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

解题思路：看这篇blog

主要学习： （1）字符串数组的正则表达；（2）BFS的编写的流程。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        
        neighbors = collections.defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                neighbors[word[:i]+*+word[i+1:]].append(word)
        
        visited = set()
        q = collections.deque()
        q.append((beginWord,1))
        
        while q:
            word,step = q.popleft()
            if word == endWord:
                return step
            for i in range(len(word)):
                for nei in neighbors[word[:i]+*+word[i+1:]]:
                    if nei not in visited:
                        q.append((nei,step+1))
                        visited.add(nei)
        
        return 0

126. 单词接龙 II

题目链接： 题目大意：是 的提升版本需要返回全部的最短的转换序列。

解题思路：看这篇blog

不用考虑其他花里胡哨的算法 专注于BFS和helper的编写 注意使用的语言是py3 那就专注于 py3

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        
        def append_path(start,end,curr_path,level,length):
            if level>length:
                return
            curr_path.append(end)
            if end==start:
                ans.append(curr_path[::-1].copy())
            for parent in path[end]:
                append_path(start,parent,curr_path,level+1,length)
            curr_path.pop()
        
        adj = collections.defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                adj[word[:i]+*+word[i+1:]].append(word)
        
        visited = set()
        q = collections.deque()
        q.append((beginWord,1))
        path = collections.defaultdict(set)
        length=0
        while q:
            word,k = q.popleft()
            if word == endWord:
                length = k
                break
                
            if word not in visited:
                visited.add(word)
                
                for i in range(len(word)):
                    neighbors = word[:i]+*+word[i+1:]
                    for neigh in adj[neighbors]:
                        if neigh not in visited:
                            path[neigh].add(word)
                            q.append((neigh,k+1))
        ans = []
        append_path(beginWord,endWord,[],1,length)
        return ans

128. 最长连续序列 *

题目链接： 题目大意：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路： 典型 哈希 表题目，建立的字典 是数组中每一个的值（val）与左右的邻居个数（cur_length）。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_dict = dict()
        max_length = 0
        for num in nums:
            # print(hash_dict)
            if num not in hash_dict:
                L = hash_dict.get(num-1,0)
                R = hash_dict.get(num+1,0)
                cur_length = 1+L+R
                if cur_length > max_length:
                    max_length = cur_length
                hash_dict[num] = cur_length
                hash_dict[num-L] = cur_length
                hash_dict[num+R] = cur_length
        # print(hash_dict)
        return max_length

152. 乘积最大子数组

题目链接： 题目大意：给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。子数组 是数组的连续子序列。

解题思路： 动态规划题，细节看代码注释，其实这道题还可以求连续的最小乘积。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 注意这道题 没说正负
        n = len(nums)
        numMin,numMax,ans = nums[0],nums[0],nums[0]
        for i in range(1,n):
            num = nums[i]
            # 一个动态变化的问题
            # 如果当前数字是正数 没必要做交换
            # 如果当前数字是负数 需要最大最小值交换一下 毕竟 负负得正
            if num < 0: 
                numMax,numMin = numMin,numMax
            numMax = max(num,numMax*num)
            numMin = min(num,numMin*num)
            ans = max(ans,numMax)
            print(numMax,numMin)
        return ans

153. 寻找旋转排序数组中的最小值 *

题目链接： 题目大意：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解题思路： 二分模板的灵活应用，模板就是与右边界死磕到底，即使下一题 154. 寻找旋转排序数组中的最小值 II](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/) 的去重也是与右边界进行死磕。

令mid与最右侧的R比较重新确定区间边界 if nums[mid] >= nums[R]: 注意，这不是寻找target的例题，所以需要遍历mid所在的数组值，即R = mid。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        if n==1: return nums[0]
        L,R  = 0,n-1
        # 这办法绝了 真的好用啊！！！
        while L<R:
            mid = L+(R-L)//2
            if nums[mid] >= nums[R]:
                L = mid+1
            else:
                R = mid
        return nums[L]

154. 寻找旋转排序数组中的最小值 II

题目链接： 题目大意： 区别于，这里的数组含有重复元素。给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

解题思路： 同上一题，需要注意去重操作，与右边界R 死磕到底，即： if nums[mid] == nums[R]: R -= 1。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        L,R = 0,len(nums)-1
        while L <R:
            mid = L + (R-L)//2
            if nums[mid] == nums[R]:
                R -= 1
            elif nums[mid] > nums[R]:
                L = mid+1
            else:
                R = mid
        return nums[L]

162. 寻找峰值 *

题目链接： 题目大意：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

解题思路：二分模板灵活应用，注意这是与相邻元素的比较。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int: 
        L,R = 0,len(nums)-1
        while L<R:
            mid = L+(R-L)//2
            # 就使劲找呗 往上爬坡
            if nums[mid] < nums[mid+1]:
                L = mid+1
            else:
                R = mid
        return L

852. 山脉数组的峰顶索引

题目链接： 题目大意：符合下列属性的数组 arr 称为 山脉数组 ：（1）arr.length >= 3；（2）存在 i（0 < i < arr.length - 1）使得：arr[0] < arr[1] < … arr[i-1] < arr[i]，arr[i] > arr[i+1] > … > arr[arr.length - 1]；（3）给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

解题思路： 与一模一样的解题思路，代码也没什么变动。

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        L,R = 0,len(arr)-1
        while L<R:
            mid = L+(R-L)//2
            if arr[mid] < arr[mid+1]:
                L = mid+1
            else:
                R = mid
        return L

167. 两数之和 II - 输入有序数组

题目链接： 题目大意：给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。

解题思路：双指针常规操作。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        id1,id2 = 0,n-1
        while id1 < n and id2 >= 0 and id1<id2:
            ret = numbers[id1] + numbers[id2]
            if ret == target:
                return [id1+1,id2+1] 
            elif ret < target:
                id1 += 1
            else:
                id2 -= 1

169. 多数元素*

题目链接： 题目大意：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路： 摩尔投票，算是贪心做法吧！有时间多看看，其实看来也属于一个动态维护。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans,cnt = 0,0
        for num in nums:
            if cnt == 0:
                ans,cnt = num,1
            else:
                if num == ans: cnt += 1
                else: cnt -= 1
        return ans

209. 长度最小的子数组

题目链接： 题目大意：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解题思路： 动态规划，指定滑窗的起始点 start 与 终止点 end，当 < target 时，窗口延展 end += 1；当 >= target 后，缩小窗口，start += 1.

注意，需要动态地管理 中间值也就是 窗口的总和 total。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        if n==1: return 1 if nums[0] >= target else 0
        start,end,total = 0,0,0
        ans = n+1
        while end < n:
            total += nums[end]
            # print(start)
            while total >= target:
                # 与答案进行比较
                ans = min(ans,end-start+1)
                #  起始点移除
                total -= nums[start]
                start += 1
            end += 1
        return ans if ans != n+1 else 0

216. 组合总和 III

题目链接： 题目大意：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

(1) 只使用数字1到9; (2) 每个数字 最多使用一次。 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

解题思路： 注意与和 进行联合学习 这道题使用回溯还是比较简单的

不过，注意 tmp+[c]不能写在 if 条件之前，会导致回溯失败的窘境。

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:

        def backTrace(start: int,tmp: List[int],target: int) -> None:
            for i in range(start,9):
                c = candidate[i]
                # print(tmp,k)
                if c == target and len(tmp)==k-1:
                    ans.append(tmp+[c])
                    return
                if c < target and len(tmp) < k:
                    backTrace(i+1,tmp+[c],target-c)
                else:
                    return

        candidate = [1,2,3,4,5,6,7,8,9]
        if n < 6: return []
        ans = []
        backTrace(0,[],n)
        return ans

217. 存在重复元素

题目链接： 题目大意：给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

解题思路： （1）集合特性；（2）哈希表；（3）collections的计数器。

（1）集合特性

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

（2）哈希表

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hash_map = dict()
        for num in nums:
            if num not in hash_map:
                hash_map[num] = 1
            else:
                return True
        return False

（3）collections的计数器

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        counter = collections.Counter(nums)
        for num in nums:
            if counter[num] > 1:
                return True
        return False

总结

  这次的题目和二分法（、、、）、动态规划（、、 ），尤其是这两道题和非常值得好好的进行专题归纳总结，现在我不求每道题的用时和占用内存都非常优秀，我只想得到一个不错的、能让我接受又容易记忆复现的方法，继续加油吧！ 努力，奋斗！