1850. 邻位交换的最小次数

1850. 邻位交换的最小次数

贪心

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        cnt = 0
        num = list(num)
        row_num = [i for i in num]
        for i in range(k):
            self.next_max(num)
        for i in range(len(num)):
            if num[i] == row_num[i]:
                continue
            for j in range(i + 1, len(num)):
                if row_num[j] == num[i]:
                    for k in range(j, i, -1):
                        row_num[k], row_num[k - 1] = row_num[k - 1], row_num[k]
                        cnt += 1
                    break
        return cnt

    # 下一个排列 https://leetcode.cn/problems/next-permutation/solutions/479151/xia-yi-ge-pai-lie-by-leetcode-solution/
    def next_max(self, nums):
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] > nums[i - 1]:
                a = i - 1
                break
        else:
            nums.sort()
            return
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] > nums[a]:
                b = i
                break
        nums[a], nums[b] = nums[b], nums[a]
        nums[a + 1:] = sorted(nums[a + 1:])

2834. 找出美丽数组的最小和

2834. 找出美丽数组的最小和

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        if target // 2 < n:
            ans = self.sum(1, target // 2)
            n = n - target // 2 - 1
            ans += self.sum(target, target + n)
        else:
            ans = self.sum(1, n)
        return int(ans) % (10 ** 9 + 7)

    def sum(self, l, r):
        return int(((l + r) * (r - l + 1)) / 2)

82. 删除排序链表中的重复元素 II

82. 删除排序链表中的重复元素 II

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        delete_val = set()
        pointer = head
        while pointer.next:
            if pointer.val == pointer.next.val:
                delete_val.add(pointer.val)
            pointer = pointer.next

        p = ListNode(val=0, next=head)
        ans = p
        while p.next:
            if p.next.val in delete_val:
                p.next = p.next.next
            else:
                p = p.next
        return ans.next

791. 自定义字符串排序

791. 自定义字符串排序

from collections import defaultdict
class Solution:
    def customSortString(self, order: str, s: str) -> str:
        weight = defaultdict(int)
        for i in range(len(order)):
            weight[order[i]] = i + 1
        s = list(s)
        s.sort(key=lambda c: weight[c])
        return ''.join(s)

LCR 166. 珠宝的最高价值

LCR 166. 珠宝的最高价值

class Solution:
    def jewelleryValue(self, frame: List[List[int]]) -> int:
        max_table = [[0 for j in range(len(frame[0]) + 1)] for i in range(len(frame) + 1)]
        for i in range(len(frame)):
            for j in range(len(frame[i])):
                max_table[i][j] = max(max_table[i - 1][j], max_table[i][j - 1]) + frame[i][j]
        return max_table[-2][-2]