LeetCode 每日一题 2025/4/14-2025/4/20

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

4/14 1534. 统计好三元组

穷举

def countGoodTriplets(arr, a, b, c):
    """
    :type arr: List[int]
    :type a: int
    :type b: int
    :type c: int
    :rtype: int
    """
    n=len(arr)
    ans = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
            for k in range(j+1,n):
                if abs(arr[i]-arr[j])<=a and abs(arr[j]-arr[k])<=b and abs(arr[i]-arr[k])<=c:
                    ans+=1
    return ans

4/15 2179. 统计数组中好三元组数目

遍历中间位置y
树状数组记录
https://leetcode.cn/problems/count-good-triplets-in-an-array/solutions/1277695/deng-jie-zhuan-huan-shu-zhuang-shu-zu-by-xmyd/?envType=daily-question&envId=2025-04-15

class Tree:
    def __init__(self,size):
        self.t = [0]*(size+1)
    def update(self,ind,delta):
        ind+=1
        while ind<=len(self.t)-1:
            self.t[ind]+=delta
            ind += ind&-ind
    def query(self,ind):
        ind+=1
        ans=0
        while ind>0:
            ans+=self.t[ind]
            ind-=ind&-ind
        return ans
    
def goodTriplets(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: int
    """
    n=len(nums1)
    ans = 0
    pos2,indmap=[0]*n,[0]*n
    for i,num2 in enumerate(nums2):
        pos2[num2]=i
    for i,num1 in enumerate(nums1):
        indmap[pos2[num1]]=i
    
    t=Tree(n)
    for v in range(n):
        pos = indmap[v]
        l=t.query(pos)
        t.update(pos,1)
        r = (n-1-pos)-(v-l)
        ans+=l*r
    return ans
    
    return ans

4/16 2537. 统计好子数组的数目

滑动窗口 对于好子数组nums[i:j] 所有x,x>j nums[i:x]都必定是好子数组
遍历左侧位置l，寻找到满足好子数组的右侧位置r
存在以l为起始位置的n-r个好子数组

def countGood(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    n=len(nums)
    ans=0
    same=0
    r=-1
    cnt={}
    for l in range(n):
        while same<k and r+1<n:
            r+=1
            same+=cnt.get(nums[r],0)
            cnt[nums[r]]=cnt.get(nums[r],0)+1
        if same>=k:
            ans+=n-r
        cnt[nums[l]]-=1
        same-=cnt[nums[l]]
    return ans

4/17 2176. 统计数组中相等且可以被整除的数对

遍历

def countPairs(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    ans=0
    n=len(nums)
    for i in range(n-1):
        for j in range(i+1,n):
            if nums[i]==nums[j] and (i*j)%k==0:
                ans+=1
    return ans

4/18 2364. 统计坏数对的数目

计算nums[i]-i
从左到右遍历

def countBadPairs(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    m={}
    ans=0
    for i,x in enumerate(nums):
        ans+=i-m.get(x-i,0)
        m[x-i]=m.get(x-i,0)+1
    return ans

4/19 2563. 统计公平数对的数目

排序 确定一个值x后 在剩余数字中双指针确定范围

def countFairPairs(nums, lower, upper):
    """
    :type nums: List[int]
    :type lower: int
    :type upper: int
    :rtype: int
    """
    nums.sort()
    ans=0
    n=len(nums)
    l,r,=n,n
    for i,x in enumerate(nums):
        while r and nums[r-1]>upper-x:
            r-=1
        while l and nums[l-1]>=lower-x:
            l-=1
        ans+=min(i,r)-min(i,l)
    return ans

4/20 781. 森林中的兔子

假设回答相同为同一种颜色
回答0的是单独一种颜色

def numRabbits(answers):
    """
    :type answers: List[int]
    :rtype: int
    """
    m = {}
    for ans in answers:
        m[ans] = m.get(ans,0)+1
    ret = 0
    for ans in  m.keys():
        num = 0
        if m[ans]%(ans+1)==0:
            num = m[ans]//(ans+1)
        else:
            num = m[ans]//(ans+1)+1
        ret += num*(ans+1)
    return ret