LeetCode-Contest 103,104

In a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

Each group has exactly X cards. All the cards in each group have the same integer.

Example 1: Input: [1,2,3,4,4,3,2,1] Output: true Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Example 2: Input: [1,1,1,2,2,2,3,3] Output: false Explanation: No possible partition.

Example 3: Input: [1] Output: false Explanation: No possible partition.

Example 4: Input: [1,1] Output: true Explanation: Possible partition [1,1]

Example 5: Input: [1,1,2,2,2,2] Output: true Explanation: Possible partition [1,1],[2,2],[2,2]

Note: 1 <= deck.length <= 10000 0 <= deck[i] < 10000

题目的意思是给一组数，把这组数分成若干小组，每小组包含的元素数目相同，至少为2，且组内的元素值相同。

# 我的代码  
def hasGroupsSizeX(self, deck):
    def gcd(a, b):
        while b: a, b = b, a % b
        return a

    if len(deck) < 2: return False
    values = list(collections.Counter(deck).values())
    values.sort()

    mina, maxa = values[0], values[-1]
    if mina == maxa: return True

    for i in range(1, len(values)):
        if values[i] != mina:
            maxa = values[i]
            break
    gg = gcd(mina, maxa)

    if gg < 2:
        return False
    for i in values:
        if i % gg:
            return False
    return True

# 大佬的代码
def hasGroupsSizeX(self, deck):
    def gcd(a, b):
        while b: a, b = b, a % b
        return a
    count = collections.Counter(deck).values()
    return reduce(gcd, count) > 1

We are given two arrays A and B of words. Each word is a string of lowercase letters.

Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, “wrr” is a subset of “warrior”, but is not a subset of “world”.

Now say a word a from A is universal if for every b in B, b is a subset of a.

Return a list of all universal words in A. You can return the words in any order.

Example 1: Input: A = [“amazon”,“apple”,“facebook”,“google”,“leetcode”], B = [“e”,“o”] Output: [“facebook”,“google”,“leetcode”]

Example 5: Input: A = [“amazon”,“apple”,“facebook”,“google”,“leetcode”], B = [“ec”,“oc”,“ceo”] Output: [“facebook”,“leetcode”]

Note: 1 1 <= A.length, B.length <= 10000 2 1 <= A[i].length, B[i].length <= 10 3 A[i] and B[i] consist only of lowercase letters. 4 All words in A[i] are unique: there isn’t i != j with A[i] == A[j].

题目的意思就是说找出A中所有的word A[i]，它满足，B中每一个（所有）的word B[j]都是A[i]的子集。

def wordSubsets(self, A, B):
    uni = collections.Counter()
    for b in B:
        for c, n in collections.Counter(b).items():
            uni[c] = max(uni[c], n)
    res = []
    for a in A:
        count = collections.Counter(a)
        if all(count[c] >= uni[c] for c in uni):
            res.append(a)
    return res

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once). After this process, we have some array B. Return the smallest possible difference between the maximum value of B and the minimum value of B. Example 1: Input: A = [0,10], K = 2 Output: 6 Explanation: B = [2,8] Example 2: Input: A = [1,3,6], K = 3 Output: 3 Explanation: B = [4,6,3] Note: 1 <= A.length <= 10000 0 <= A[i] <= 10000 0 <= K <= 10000

 def smallestRangeII(self, A, K):
    A.sort()
    res = A[-1] - A[0]
    for i in range(len(A) - 1):
        big = max(A[-1], A[i] + 2 * K)
        small = min(A[i + 1], A[0] + 2 * K)
        res = min(res, big - small)
    return res