破晓的知识屋
0%

2023年3月

发表于 更新于 分类于 ， ， 阅读次数： Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

[toc]

2023-03-30#

453. 最小操作次数使数组元素相等 - 力扣（Leetcode）

想复杂了，用了个公式推导结果忘记了约束条件，想着公式取整数得到结果

实际上肯定是先处理低的，再处理第二低的，就很容易知道怎么处理了， 需要注意每次记录前面增加的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        nums = sorted(nums)
        n = len(nums)
        if n== 1:
            return 0
        res = 0
        lastAdd = 0
        for i in range(0, n-1):
            num = nums[i]
            nextNum = nums[i+1]
            add = nextNum - num + lastAdd
            res += add
            lastAdd = add
        return res

试着用了python

排序是sorted

更优答案：#

每次操作既可以理解为使 n−1n-1n−1 个元素增加 111，也可以理解使 111 个元素减少 111。显然，后者更利于我们的计算

1
2
3
4
5
6
7
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        min_num = min(nums)
        res = 0
        for num in nums:
            res += num - min_num
        return res

注意foreach语法是in

2023-03-31#

2367. 算术三元组的数目 - 力扣（Leetcode）

对于这种三元问题，尝试了三种方式， 最简单的暴力，不能局限于暴力，然后哈希表， 接着再三指针

主要是因为题目要求的是严格递增的，所以可以考虑三指针，3个指针一定只会增加，不存在跑回来重新走的情况，所以是O(N)且空间复杂度1的场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        map = {}
        res = 0
        n = len(nums)
        i = 0
        j = 1
        k = 2
        for i in range(0, n):
            j = max(i+1, j)
            while j < n and nums[j] < nums[i] + diff:
                j +=1
            if j < n and nums[j] == nums[i]+ diff:
                k = max(j+1, k)
                while k < n and nums[k] < nums[j]+ diff:
                    k += 1
                if k < n and nums[k] == nums[j]+ diff:
                    res +=1
            if j >= n or k >=n:
                break

        return res