2024.4.1力扣（1200-1400）刷题记录

一、1475. 商品折扣后的最终价格

1.模拟

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # 模拟
        # 时复O(n^2)，空复O(1)
        n = len(prices)
        if n == 1:
            return prices
        for i in range(n):
            for j in range(i+1, n):
                if prices[i] >= prices[j]:
                    prices[i] -= prices[j]
                    break
        return prices

2.单调栈。方法来自题解（. - 力扣（LeetCode））和评论（. - 力扣（LeetCode））。

写法1

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # 单调栈
        # 栈单调递增（对应的值）
        n = len(prices)
        stack, ans = [0] * n, [0] * n
        top = -1    #栈顶指针
        for i,x in enumerate(prices):
            while top >= 0 and prices[stack[top]] >= x:
                # 非空栈或x小于等于栈顶，出栈
                idx = stack[top]
                ans[idx] = prices[idx] - x
                top -= 1
            top += 1
            stack[top] = i  #将下标入栈   
        while top >= 0:
            idx = stack[top]
            ans[idx] = prices[idx] 
            top -= 1
        return ans 

写法2，来自评论上面评论

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # 单调栈2
        stack = []
        for i,x in enumerate(prices):
            while stack and prices[stack[-1]] >= x:
                # 非空栈或x小于等于栈顶，出栈
                prices[stack.pop()] -= x
            stack.append(i)  #将下标入栈   
        # 只改变折扣的，其他的不变
        return prices

二、2656. K 个元素的最大和

贪心+数学

class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int:
        # 贪心+数学
        # 最大值加k次就行
        return max(nums)*k + (k - 1) * k // 2

三、973. 最接近原点的 K 个点

暴力+排序

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # 暴力+排序
        points.sort(key = lambda x: x[0]**2+x[1]**2)
        return points[:k]

还有一种方法是堆，不会，现在先不写。

四、3042. 统计前后缀下标对 I

暴力

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        # 暴力
        def isPrefixAndSuffix(str1, str2):
            n1, n2 = len(str1), len(str2)
            if n1 > n2:
                return False
            return str1 == str2[:n1] and str1 == str2[n2-n1:]
        cnt, n = 0, len(words)
        for i in range(n-1):
            for j in range(i+1,n):
                cnt += isPrefixAndSuffix(words[i],words[j])
        return cnt

完

感谢你看到这里！一起加油吧！