力扣记录 4.8

本文主要是介绍力扣记录 4.8，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

50. Pow(x, n)

递归：
终止条件：x0 = 1，n=1
递归主体：xn = x**(n//2) * x**(n//2) 在N为偶数时；奇数时需要单独拎出来一个x1，使得也能两个一半相乘
分解问题：每个xn都可以表示为两个x**n的一半

class Solution:def myPow(self, x: float, n: int) -> float:# 递归函数def fast_pow(x,n):if n == 0:return 1half = fast_pow(x, n//2)# 偶数if n % 2 == 0:return half * half# 奇数else:return half * half * x# 区分n的正负if n < 0:x = 1/xn = -n# 正常计算return fast_pow(x,n)

169. 多数元素

要找出数组中出现次数大于 (\lfloor \frac{n}{2} \rfloor)
的元素（即多数元素），而不使用collections模块的Counter函数，一个非常有效的方法是使用
Boyer-Moore投票算法。这个算法的核心思想是在一对一对地消除不同的元素之后，剩下的元素（如果存在）一定是多数元素。

Boyer-Moore投票算法的步骤：

1. 初始化：选择数组中的第一个元素作为候选多数元素，将其计数设为1。
2. 遍历：遍历数组中剩余的元素：
   • 如果计数器为0，选择当前元素作为新的候选多数元素，并将计数设为1。
   • 如果当前元素等于候选多数元素，将计数器加1。
   • 否则，将计数器减1。
3. 结果：由于多数元素的数量超过数组长度的一半，所以经过一对一对的消除，最后剩下的元素（候选多数元素）一定是多数元素。

这个算法之所以有效，是因为每次当计数器变为0时，我们都忽略了之前的所有元素，而这之中多数元素和非多数元素的数量是相等的。因此，剩下的部分仍然保持了多数元素的性质。

示例代码：

def majorityElement(nums):count = 0candidate = Nonefor num in nums:if count == 0:candidate = numcount += (1 if num == candidate else -1)return candidate

说明：

• 这段代码首先初始化candidate为None，计数器count为0。
• 然后遍历数组，通过逐个比较元素和当前候选者，以及增减计数器的方式，最终找到多数元素。
• 由于题目假设数组总是存在多数元素，所以最后candidate一定是多数元素。

Boyer-Moore投票算法的时间复杂度是(O(n))，空间复杂度是(O(1))，非常高效。这个方法不仅适用于找多数元素问题，还可以扩展到其他类似的问题中。

53. 最大子数组和

一种是用辅助数组，走动态规划；另一种是迭代，因为当前最大和取决于上一个的。

class Solution:def maxSubArray(self, nums: List[int]) -> int:  # 辅助数组dp = [0] * len(nums)dp[0] = nums[0]for i in range(1, len(nums)):if dp[i-1] >= 0:dp[i] = dp[i-1] + nums[i]else:dp[i] = nums[i]return max(dp)

class Solution:def maxSubArray(self, nums: List[int]) -> int:  # 辅助数组temp_max = global_max = nums[0]for num in nums[1:]:temp_max = max(num, temp_max+num)global_max = max(global_max, temp_max)return global_max

0932. 漂亮数组

递归和分治算法。
[1]是一个最小的漂亮数组。
需要对其进行转换，等式 A[k] * 2 = A[i] + A[j] 的左侧是一个偶数，右侧的两个元素分别来自两个部分。要想等式恒不成立，一个简单的办法就是让 left 部分的数都是奇数，right 部分的数都是偶数。

所以对左边进行奇数序列映射，右边进行偶数序列映射。

class Solution:def beautifulArray(self, n: int) -> List[int]:# 递归终止：1就是最基本的漂亮数组if n == 1: return [1]# 左边的left = self.beautifulArray((n+1)//2)# 右边的right = self.beautifulArray(n//2)# 奇数序列，偶数序列return [2*x-1 for x in left] + [2*x for x in right]

漂亮数组的问题可以通过分治算法的思想来解决。关键的观察点是，如果A是一个漂亮数组，那么对A中的每个元素乘以一个常数和加上一个常数后，得到的数组B也是一个漂亮数组。这是因为乘法和加法操作不会改变数组中元素的相对大小关系，也不会引入满足2*nums[k] == nums[i] + nums[j]的新的三元组(i, j, k)。

基于这个观察，我们可以采用如下策略构造一个漂亮数组：

1. 开始：从最简单的漂亮数组[1]开始。
2. 分治：通过将已有的漂亮数组A拆分为两部分——A的所有元素乘以2减1（构成奇数序列），以及A的所有元素乘以2（构成偶数序列）——来构造更大的漂亮数组。这样做的好处是，奇数序列和偶数序列内部各自保持了漂亮数组的性质，同时由于奇数和偶数之间的关系，它们合并后也保持了漂亮数组的性质。
3. 递归：递归地应用上述操作，直到构造出长度为n的漂亮数组。

241. 为运算表达式设计优先级

解决这个问题的关键在于使用分治策略。对于给定的表达式，我们可以通过递归的方式来解决。基本思路是：对于每个运算符，将表达式分割成两部分，分别计算左半部分和右半部分可能产生的结果，然后根据当前运算符将左右两部分的结果组合起来。

这个方法依赖于观察到的事实：当你在某个运算符处分割表达式时，该运算符左边的表达式和右边的表达式都可以独立计算，并且它们的计算结果可以独立组合。

步骤概述：

1. 遍历表达式：对于表达式中的每个字符，如果它是一个运算符（+，-，*），则对该运算符执行以下步骤。
2. 分割表达式：将表达式在当前运算符处分割为两个部分，左半部分和右半部分。
3. 递归计算：递归地计算左半部分和右半部分可能产生的所有结果。
4. 合并结果：根据当前运算符，将左右两部分的结果组合起来。
5. 处理基本情况：如果表达式中没有运算符（即只有数字），则直接返回该数字作为结果。

示例代码：

    # 如果表达式仅包含数字，则直接返回包含该数字的列表if expression.isdigit():return [int(expression)]res = []# 遍历表达式的每个字符for i, char in enumerate(expression):# 如果当前字符是运算符if char in {'+', '-', '*'}:# 分割表达式，并递归计算左右两部分left = diffWaysToCompute(expression[:i])right = diffWaysToCompute(expression[i+1:])# 根据运算符合并左右两部分的结果for l in left:for r in right:if char == '+':res.append(l + r)elif char == '-':res.append(l - r)elif char == '*':res.append(l * r)return res ```

23. 合并 K 个升序链表

困难题根本不想做

合并K个升序链表的问题可以通过多种方法解决。一种高效的方法是使用最小堆（优先队列），这种方法的时间复杂度是O(N log K)，其中N是所有链表中元素的总数，K是链表的数量。使用最小堆可以帮助我们每次都从所有链表的当前头节点中找到最小的那个，然后将它合并到结果链表中。

以下是使用Python中的heapq模块实现的步骤：

1. 初始化最小堆：首先，将每个链表的第一个元素（如果存在）加入到最小堆中。我们还需要存储节点所在链表的信息，以便于后续操作。

2. 合并链表：然后，我们从堆中弹出最小元素，将它添加到结果链表的末尾，并将这个元素所在链表的下一个元素（如果存在）加入到堆中。重复这个过程，直到堆为空。

3. 返回合并后的链表。

以下是具体的实现：

# Definition for singly-linked list. class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextimport heapqclass Solution:def mergeKLists(self, lists):# 初始化一个虚拟头节点，方便操作dummy = ListNode(0)current = dummy# 初始化堆heap = []# 将每个链表的头节点加入堆中for i, list_head in enumerate(lists):if list_head:# 堆中存储元素值、所在链表的索引、节点，以确保比较的唯一性和完整性heapq.heappush(heap, (list_head.val, i, list_head))# 当堆不为空时，进行合并操作while heap:# 弹出堆中最小元素val, i, node = heapq.heappop(heap)# 将最小元素所在节点添加到结果链表current.next = nodecurrent = current.next# 如果最小元素所在链表还有下一个节点，则将下一个节点加入堆中if node.next:heapq.heappush(heap, (node.next.val, i, node.next))return dummy.next ```

这种方法通过最小堆保证了每次都能从K个链表的当前头节点中选出最小的那个，从而高效地合并了链表。由于Python的heapq库默认是最小堆，我们可以直接利用它来实现这一过程。

这篇关于力扣记录 4.8的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---