数组算法练习

本文最后更新于：2023年12月5日下午

记录数组刷题方案。

1043. 分隔数组以得到最大和

给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort(reverse=True)
        pq = []
        p = 0
        counter = 0
        while True:
            if not pq:
                if  not events:
                    break
                else:
                    p = events[-1][0]
            # 添加事件
            while events and events[-1][0] == p:
                heapq.heappush(pq, events.pop()[1])

            # 开会
            while pq:
                finish_date = heapq.heappop(pq)
                if p <= finish_date:
                    counter += 1
                    break
            p += 1

        return counter

2771. 构造最长非递减子数组

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度均为 n 。

让我们定义另一个下标从 0 开始、长度为 n 的整数数组，nums3 。对于范围 [0, n - 1] 的每个下标 i ，你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。

你的任务是使用最优策略为 nums3 赋值，以最大化 nums3 中 最长非递减子数组 的长度。

以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列。

class Solution:
    
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        import numpy as np
        length = len(nums1)
        if not length:
            return 0
        dp = np.zeros([length, 2], dtype='int32')
        for index, (num1, num2) in enumerate(zip(nums1, nums2)):
            if index == 0:
                dp[index, 0] = 1
                dp[index, 1] = 1
            else:
                num1_max_temp = 1
                if nums1[index] >= nums1[index - 1]:
                    num1_max_temp = max(num1_max_temp, dp[index - 1, 0] + 1)
                if nums1[index] >= nums2[index - 1]:
                    num1_max_temp = max(num1_max_temp, dp[index - 1, 1] + 1)

                num2_max_temp = 1
                if nums2[index] >= nums1[index - 1]:
                    num2_max_temp = max(num2_max_temp, dp[index - 1, 0] + 1)
                if nums2[index] >= nums2[index - 1]:
                    num2_max_temp = max(num2_max_temp, dp[index - 1, 1] + 1)
                dp[index, 0] = num1_max_temp
                dp[index, 1] = num2_max_temp
        return int(dp.max())

该思路过分了，其实仅保留当前值，维护最大值就行

统计参与通信的服务器

这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。

如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        row_num = len(grid)
        col_num = len(grid[0])
        if col_num == 0:
            return 0
        
        count_r = [0] * row_num
        count_c = [0] * col_num

        for index_r in range(row_num):
            for index_c in range(col_num):
                if grid[index_r][index_c]:
                    count_r[index_r] += 1
                    count_c[index_c] += 1
        
        total_num = 0
        for index_r in range(row_num):
            for index_c in range(col_num):
                if grid[index_r][index_c] and (count_r[index_r] > 1 or count_c[index_c] > 1):
                    total_num += 1
        return total_num

1524. 和为奇数的子数组数目

给你一个整数数组 arr 。请你返回和为奇数的子数组数目。

由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:

        array_length = len(arr) + 1

        pre_sum = [0] * array_length
        pre_even_num_sum = [0] * array_length
        pre_odd_num_sum = [0] * array_length

        even_sum = 0

        for index, value in enumerate(arr):
            pre_sum[index + 1] = pre_sum[index] + value
            if pre_sum[index + 1] % 2 == 1:
                pre_even_num_sum[index + 1] = pre_even_num_sum[index] + 1
                pre_odd_num_sum[index + 1] = pre_odd_num_sum[index]
                even_sum += 1
                even_sum += pre_odd_num_sum[index + 1]
            else:
                pre_even_num_sum[index + 1] = pre_even_num_sum[index]
                pre_odd_num_sum[index + 1] = pre_odd_num_sum[index] + 1
                even_sum += pre_even_num_sum[index + 1]


        return int(even_sum %(1e9 +7))

2488. 统计中位数为 K 的子数组

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的不同整数组成。另给你一个正整数 k 。

统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

注意：

数组的中位数是按递增顺序排列后位于中间的那个元素，如果数组长度为偶数，则中位数是位于中间靠左的那个元素。
- 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        k_index = None
        for index in range(len(nums)):
            if nums[index] < k:
                nums[index] = -1
            elif nums[index] > k:
                nums[index] = 1
            else:
                nums[index] = 0
                k_index = index

        left_sum_counter_dict = dict()
        cur_sum = 0
        for index in range(k_index, -1 ,-1):
            cur_sum += nums[index]
            if cur_sum not in left_sum_counter_dict:
                left_sum_counter_dict[cur_sum] = 0
            left_sum_counter_dict[cur_sum] += 1

        cur_sum = 0
        total_num = 0
        for index in range(k_index, len(nums)):
            cur_sum += nums[index]
            if -cur_sum in left_sum_counter_dict:
                total_num += left_sum_counter_dict[-cur_sum]
            if 1-cur_sum in left_sum_counter_dict:
                total_num += left_sum_counter_dict[1-cur_sum]
        return total_num

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = dict()
        for value in nums:
            if value not in counter:
                counter[value] = 0
            counter[value] += 1
        
        res_list = [(0, 0)] * k
        for key, value in counter.items():
            heapq.heappushpop(res_list, (value, key))
        
        res = list()
        for item in res_list:
            res.append(item[1])
        
        return res

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo = 0
        hi = len(nums) - 1

        while True:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
            
            if lo > hi:
                return -1

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if n == 0:
            return
        if m == 0:
            for index, value in enumerate(nums2):
                nums1[index] = value
            return

        p = m - 1
        q = n - 1
        s = m + n - 1

        while p >= 0 or q >= 0:

            if p >= 0 and (q < 0 or nums1[p] >= nums2[q]):
                nums1[s] = nums1[p]
                p -= 1
            else:
                nums1[s] = nums2[q]
                q -= 1
            s -= 1

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if len(nums) == 0:
            return 0

        p = 0
        q = len(nums) - 1

        while p < q:
            if nums[p] != val:
                p += 1
            if nums[q] == val:
                q -= 1
            if p < q and nums[p] == val and nums[q] != val:
                nums[p], nums[q] = nums[q], nums[p]

        if nums[p] == val:
            return p
        else:
            return p + 1

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        counter = dict()
        for index in range(len(nums) - 1, -1, -1):
            if nums[index] not in counter:
                counter[nums[index]] = 0
            if counter[nums[index]] < 2:
                counter[nums[index]] += 1
            else:
                nums.pop(index)
        return len(nums)

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        earn = 0
        hold = -1
        
        day_num = len(prices)

        if day_num < 2:
            return earn
        
        for index in range(day_num):
            if index + 1 < day_num:
                if hold < 0:
                    if prices[index + 1] > prices[index]:
                        hold = prices[index]
                else:
                    if prices[index + 1] < prices[index]:
                        earn += prices[index] - hold
                        hold = -1
            else:
                if hold >= 0 and prices[index] > hold:
                    earn += prices[index] - hold
        return earn

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        p = len(nums) - 1
        for q in range(len(nums) - 1, -1, -1):
            if p - q <= nums[q]:
                p = q
        if p == 0:
            return True
        else:
            return False

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        p = 0
        q = len(height) - 1
        max_water = 0
        def cal_water(height, p, q):
            return min(height[p], height[q]) * (q - p)
        
        while p < q:
            max_water = max(max_water, cal_water(height, p, q))
            if height[p] < height[q]:
                p += 1
            else:
                q -= 1
        return max_water

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        counter_dict = dict()
        for index in range(len(nums)-1, -1, -1):
            if nums[index] not in counter_dict:
                counter_dict[nums[index]] = 0
            if counter_dict[nums[index]] < 3:
                counter_dict[nums[index]] += 1
            else:
                nums.pop(index)

        target_dict = dict()
        for index, value in enumerate(nums):
            if -value not in target_dict:
                target_dict[-value] = set()
            target_dict[-value].add(index)
        
        res_set = set()
        visted_12 = set()
        for index1, value1 in enumerate(nums):
            for index2, value2 in enumerate(nums):
                if index1 == index2:
                    continue
                cur_sum = value2 + value1
                if cur_sum in target_dict:
                    for index3 in target_dict[cur_sum]:
                        if index1 != index3  and index2 != index3:
                            res_set.add(tuple(sorted([value1, value2, -cur_sum])))

        return [list(res) for res in res_set]

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_sum = - float('inf')
        l = 0
        cur_sum = 0
        for num in nums:
            cur_sum += num
            max_sum = max(max_sum, cur_sum)
            if cur_sum < 0:
                cur_sum = 0
        return max_sum