974. 和可被 K 整除的子数组

974. 和可被 K 整除的子数组

前缀和+同余定理

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        hashtable = {0: 1}
        total = 0
        ans = 0
        for i in range(len(nums)):
            total += nums[i]
            mod = total % k
            same_mod = hashtable.get(mod, 0)
            ans += same_mod
            hashtable[mod] = same_mod + 1
        return ans

68. 文本左右对齐

68. 文本左右对齐

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        info = []
        line = []
        rest_chars = maxWidth
        now_chars = 0
        for i in range(len(words)):
            if len(words[i]) > rest_chars:
                average = (maxWidth - now_chars) // ((len(line) - 1) if (len(line) - 1) != 0 else 1)
                mod = (maxWidth - now_chars) % ((len(line) - 1) if (len(line) - 1) != 0 else 1)
                tmp_list = []
                for j in range(len(line) - 1):
                    tmp_list.append(line[j])
                    tmp_list.append(' ' * (average + (1 if mod > 0 else 0)))
                    mod -= 1
                tmp_list.append(line[-1])
                info.append(''.join(tmp_list))
                info[-1] = info[-1].ljust(maxWidth, ' ')
                line = []
                rest_chars = maxWidth
                now_chars = 0
            line.append(words[i])
            now_chars += len(words[i])
            rest_chars -= (len(words[i]) + 1)
        if line:
            info.append(" ".join(line))
            info[-1] = info[-1].ljust(maxWidth, ' ')
        return info

526. 优美的排列

526. 优美的排列

from typing import List
class Solution:
    def __init__(self):
        self.ans = 0
    def countArrangement(self, n: int) -> int:
        match = [[] for i in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i % j == 0 or j % i == 0:
                    match[i].append(j)
        self.search(match, 1, set())
        return self.ans

    def search(self, match: List[List[int]], index: int, used: set):
        if index >= len(match):
            self.ans += 1
            return
        for i in range(len(match[index])):
            if match[index][i] not in used:
                used.add(match[index][i])
                self.search(match, index + 1, used)
                used.discard(match[index][i])