[数据结构与算法]LeetCode Cookbook 数组习题（5）

LeetCode Cookbook 数组习题（5）

??篇接上回，开始！

219. 存在重复元素 II

题目链接：219. 存在重复元素 II
题目大意：给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

解题思路：相较于 217. 存在重复元素 稍微复杂了些，使用哈希表是不错的选择。

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

229. 多数元素 II

题目链接：229. 多数元素 II
题目大意：给定一个大小为 n 的整数数组，找出其中所有出现超过 ? n/3 ? 次的元素。

解题思路： 区别于 169. 多数元素 这道题的n/2 ，返回的答案不是唯一的，我们为了便于后续记忆使用，不用 摩尔投票法，就用py3的collections中的Counter() 计数器，太香了！

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n < 3:return nums if len(nums) == len(set(nums)) else [nums[0]]
        ans = []
        counter = collections.Counter(nums)
        for num in set(nums):
            if counter[num] > n//3:
                ans.append(num)
        return ans

283. 移动零

题目链接：283. 移动零
题目大意：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

解题思路： 双指针题，不用想的特别复杂，一个走快一点，一个走慢一点。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if sum(nums) == 0: return nums
        low,fast = 0,0
        n = len(nums)
        while fast < n:
            if nums[fast] != 0:
                nums[low],nums[fast] = nums[fast],nums[low]
                low += 1
            fast += 1

287. 寻找重复数

题目链接：287. 寻找重复数
题目大意：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

解题思路： 不是很喜欢这道题，这里的快慢指针没什么意思，还是 Counter 好用，下面是其子函数 most_common()，特别好用啊！

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        
        counter  = collections.Counter(nums)
        return counter.most_common(1)[0][0]

414. 第三大的数

题目链接：414. 第三大的数
题目大意： 给你一个非空数组，返回此数组中 第三大 的数 。如果不存在，则返回数组中最大的数。

解题思路： （一）排序；（二）三个指针。

（一）排序

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        n = len(set(nums))
        if n < 3: return sorted(set(nums),reverse=True)[0]
        return sorted(set(nums),reverse=True)[2]

（二）三个指针

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        a, b, c = float('-inf'), float('-inf'), float('-inf')
        for num in nums:
            if num > a:
                a, b, c = num, a, b
            elif a > num > b:
                b, c = num, b
            elif b > num > c:
                c = num
        return a if c == float('-inf') else c

448. 找到所有数组中消失的数字

题目链接：448. 找到所有数组中消失的数字
题目大意： 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果

解题思路： （一）利用集合无重复元素的性质，优点是挺快的，不足在于有点费空间；（二）两次遍历，有些费时间，省空间。

（一）集合法

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        return list(set(range(1,len(nums)+1))-set(nums))

（二）两次遍历法

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            x = (num - 1) % n
            nums[x] += n
        # print(nums)        
        ret = [i + 1 for i, num in enumerate(nums) if num <= n]
        return ret

454. 四数相加 II

题目链接：454. 四数相加 II
题目大意：给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

解题思路：

• 使用 dict() 需要一一进行赋值
• 在本题中由于一上来就需要使用一个默认好的字典，所以需要使用
• collections.defaultdict(int) 这个函数一上来就初始化好了

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        # 这里需要初始化一下字典的存储数据的类型 所以使用 dict() 不太行
        # 要用 collections.defaultdict(int)
        hash_map = collections.defaultdict(int)
        for a in nums1:
            for b in nums2:
                hash_map[a+b] += 1
        ans = 0
        for c in nums3:
            for d in nums4:
                ans += hash_map[0-c-d]
        return ans

457. 环形数组是否存在循环（不熟悉）*

题目链接：457. 环形数组是否存在循环
题目大意：存在一个不含 0 的 环形 数组 nums ，每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数：

• 如果 nums[i] 是正数，向前（下标递增方向）移动 |nums[i]| 步
• 如果 nums[i] 是负数，向后（下标递减方向）移动 |nums[i]| 步
• 因为数组是 环形 的，所以可以假设从最后一个元素向前移动一步会到达第一个元素，而第一个元素向后移动一步会到达最后一个元素。数组中的 循环 由长度为 k 的下标序列 seq 标识：
• （1） 遵循上述移动规则将导致一组重复下标序列 seq[0] -> seq[1] -> … -> seq[k - 1] -> seq[0] -> …；
• （2）所有 nums[seq[j]] 应当不是 全正 就是 全负；
• （3）k > 1。
  如果 nums 中存在循环，返回 true ；否则，返回 false 。

解题思路： 与141. 环形链表思路一致，需要设置快慢指针，慢指针每下走一步，快指针每下走两步，如果相遇则说明形成闭环。

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)
        
        def next(cur):
            return (cur+nums[cur]) % n 
        
        for i in range(n):
            slow = i
            fast = next(slow)
            while nums[fast]*nums[i] > 0 and nums[next(fast)] * nums[i] > 0:
                if fast == slow:
                    if slow == next(slow):
                        break
                    return True
                slow = next(slow)
                fast = next(next(fast))
        return False 

463. 岛屿的周长

题目链接：463. 岛屿的周长
题目大意：给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

• 网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
• 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

解题思路：这道题很有意思了，从第一行往下或往右走，相邻的格子减少两个边，抓住这个规律做题。

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    down = 2 if i < m - 1 and grid[i + 1][j] == 1 else 0
                    right = 2 if j < n - 1 and grid[i][j + 1] == 1 else 0
                    ans += 4 - down - right
        return ans   

485. 最大连续 1 的个数

题目链接：485. 最大连续 1 的个数
题目大意：给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

解题思路： 不难，需要两个变量维持结果，有点动态规划的意思。

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        ans,cur = 0,0
        n = len(nums)
        for num in nums:
            if num == 1:
                cur += 1
            else:
                cur = 0
            ans = max(ans,cur)
        return ans

498. 对角线遍历

题目链接：498. 对角线遍历
题目大意：给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

解题思路： 需要找规律，具体看代码，这道题挺巧妙的。

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m,n = len(mat),len(mat[0])
        ans = []
        for i in range(m+n-1):
            # 偶数 自上至下
            if i % 2 == 0:
                x = i if i<m else m-1
                y = 0 if i<m else i-m+1
                while x >= 0  and y<n:
                    ans.append(mat[x][y])
                    x -= 1
                    y += 1
            else:
                x = 0 if i<n else i-n+1
                y = i if i<n else n-1
                while x < m and y>=0:
                    ans.append(mat[x][y])
                    x += 1
                    y -= 1
        return ans  

509. 斐波那契数

题目链接：509. 斐波那契数
题目大意：斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

• F(0) = 0，F(1) = 1
• F(n) = F(n - 1) + F(n - 2)，其中 n > 1
• 给定 n ，请计算 **F(n) **。

解题思路： 注意与剑指 Offer 10- I. 斐波那契数列一摸一样，直接按照思路做就可以了。

class Solution:
    def fib(self, n: int) -> int:
        F0,F1 = 0,1;
        while n != 0:
            F1 = F1 + F0;
            F0 = F1 - F0;
            n -= 1;
        return F0 % 1000000007;

532. 数组中的 k-diff 数对

题目链接：532. 数组中的 k-diff 数对
题目大意：给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：

• 0 <= i, j < nums.length
• i != j
• nums[i] - nums[j] == k
• 注意，|val| 表示 val 的绝对值。

解题思路： 两个哈希表的较量，哈哈！

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        # 建两个哈希表
        ans,visited = set(),set()
        for num in nums:
            if num+k in visited:
                ans.add(num)
            if num-k in visited:
                ans.add(num-k)
            visited.add(num)
        return len(ans)

总结

??这次的题目开始以为很简单，越往下做，出现些难点，再往后又简单了些，今天不多说，继续，努力，奋斗！