算法题记录 7

1287.有序数组中出现次数超过25%的元素（1179）

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

涉及知识点

二分/滑动窗口

解决思路

秒答题，常规思路是滑动窗口，但是也可以二分设 m=⌊ 4/n ⌋。一般地，我们至多检查 3 个下标 m,2m+1,3m+2，其中一定有一个 arr[i] 的出现次数至少为 m+1。

二分

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        mx = -1
        for i in range(len(arr) - 1, -1, -1):
            x = arr[i]
            arr[i] = mx
            mx = max(mx, x)  # 维护后缀最大值
        return arrclass 

825.适龄的朋友（1697）

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

ages[y] <= 0.5 * ages[x] + 7
ages[y] > ages[x]
ages[y] > 100 && ages[x] < 100
否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

涉及知识点

滑动窗口

解决思路

枚举年龄 ageX，我们需要知道：

可以发送好友请求的最小年龄 ageY 是多少。
年龄在区间 [ageY,ageX] 中的人数。
由于 ageX 越大，ageY 也越大，可以用滑动窗口解决。

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt = [0] * 121
        for age in ages:
            cnt[age] += 1

        ans = cnt_window = age_y = 0
        for age_x, c in enumerate(cnt):
            cnt_window += c
            if age_y * 2 <= age_x + 14:  # 不能发送好友请求
                cnt_window -= cnt[age_y]
                age_y += 1
            if cnt_window:  # 存在可以发送好友请求的用户
                ans += c * cnt_window - c
        return ans

2535.数组元素和与数字和的绝对差（1222）

给你一个正整数数组 nums 。

元素和 是 nums 中的所有元素相加求和。
数字和 是 nums 中每一个元素的每一数位（重复数位需多次求和）相加求和。
返回 元素和 与 数字和 的绝对差。

注意：两个整数 x 和 y 的绝对差定义为 |x - y| 。

涉及知识点

数组

解决思路

秒答题，按题意做就行，绝对值可以优化掉

class Solution:
    def differenceOfSum(self, nums: List[int]) -> int:
        ans=0
        for x in nums:
            ans+=x
            while x:
                ans-=x%10
                x//=10
        return ans

1367.二叉树中的链表（1650）

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

涉及知识点

树

解决思路

秒答题，按题意做就行。

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def dfs(s: Optional[ListNode], t: Optional[TreeNode]) -> bool:
            if s is None:  # 整个链表匹配完毕
                return True
            # 否则需要继续匹配
            if t is None:  # 无法继续匹配
                return False
            # 节点值相同则继续匹配，否则从 head 开始重新匹配
            return s.val == t.val and (dfs(s.next, t.left) or dfs(s.next, t.right)) or \
                   s is head and (dfs(head, t.left) or dfs(head, t.right))
        return dfs(head, root)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。