Bluefissure's Blog

A Place for Recording

0%

LeetCode Weekly Contest 155

Posted on In , Disqus:

是切题怪中的豪杰

##1200. Minimum Absolute Difference

求问数组中有多少对数字的绝对值在数组中任意两数的绝对值中是最小的。

思路：排序即可，甚至不用处理绝对值为0的情况，因为题目一开始就说了数组是distinct的。（但是我最后才看到）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        min_abs = 10**7
        arr.sort()
        ans = []
        for i in range(0, len(arr)-1):
            min_abs = min(min_abs, abs(arr[i+1]-arr[i]))
        for i in range(0, len(arr)-1):
            if min_abs == abs(arr[i+1]-arr[i]):
                ans.append((arr[i],arr[i+1]))
        return ans

1201. Ugly Number III

求出能被 a 或 b 或 c 整除的第 n 个数。

思路：二分

详解：求一个数前面有多少个a的倍数，b的倍数，c的倍数就可以知道这个数是第几个数了，注意要用容斥原理处理ab, bc, ac 和 abc，在倍数相关处理的过程中要算LCM。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def gcd(x, y):
    return x if not y else gcd(y, x%y)
def lcm(x, y):
    return x*y//gcd(x, y)
class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def number(n, a, b, c):
            return n//a+n//b+n//c-n//(lcm(a,b))-n//(lcm(a,c))-n//(lcm(c,b))+n//(lcm(a,lcm(b,c)))
        l = 1
        r = 2 * 10**9
        while l < r - 1:
            mid = (l+r)//2
            if number(mid, a, b, c) < n:
                l = mid + 1
            else:
                r = mid
        while number(l, a, b, c) < n:
            l += 1
        return l

结合代码，要给出第一个number >= n的数，否则其有可能不是 a 或 b 或 c 的倍数。

PS: 孩子二分老不会处理边界，多半是废了。

1202. Smallest String With Swaps

可以任意按照pairs中的数对调换两个位置的字母，求经过任意次调换后能达到的最小字符串。

思路：冰茶几 并查集

详解：每个二元数对连接起来会成为一个独立集（是这么叫吗），然后我们只需要对每个独立集的位置的字符进行排序即可。

举例：

1
2
3
4
nchdbshdurh
 c d   d   
n   b h   h
  h  s  ur

只需要对下面三行进行排序后再合起来就行了。

所以，使用并查集（Union-Find Set）来维护每个位置所在的集合即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    def union(self, x, y):
        fax = self.find(x)
        fay = self.find(y)
        if fax == fay: return
        if(self.r[fax] < self.r[fay]):
            self.fa[fax] = fay
        else:
            if(self.r[fax] == self.r[fay]):
                self.r[fax] += 1
            self.fa[fay] = fax
    def smallestStringWithSwaps(self, s: str, pairs) -> str:
        self.fa = [i for i in range(len(s))]
        self.r = [0 for i in range(len(s))]
        for x, y in pairs:
            self.union(x, y)
        d = collections.defaultdict(str)
        for i, ch in enumerate(s):
            fai = self.find(i)
            d[fai] += ch
        for (k, v) in d.items():
            d[k] = sorted(v)
        n = collections.Counter()
        ans = ""
        for i, ch in enumerate(s):
            fai = self.find(i)
            ans += d[fai][n[fai]]
            n[fai] += 1
        return ans

PS: 并查集最好按秩优化，否则可能TLE（别问我怎么知道的）。

1203. Sort Items by Groups Respecting Dependencies

若干group包含若干item，group内的items需要相邻，没有group的item可以随意放置。同时要满足一系列诸如“item[i]要在item[j]”之前的顺序限制，输出一种排列方法。

思路：双层拓扑排序

详解：首先，如果存在u->v的顺序限制，有以下两种情况：

  • u和v在同一个group，此时我们在group内做拓扑排序。
  • u和v在不同group，由于group内的item必须相邻，所以可以把item之间的顺序限制转化为group之间的顺序限制。之后我们在最外层对group进行拓扑排序。

至于什么是拓扑排序，即在一张图内重复“寻找入度为0的点，删掉它出发的边”，最后的输出即为一种满足限制的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def topoSort(graph):
    in_degrees = dict((u,0) for u in graph)
    vertex_num = len(in_degrees)
    for u in graph:
        for v in graph[u]:
            in_degrees[v] += 1
    Q = [u for u in in_degrees if in_degrees[u] == 0]
    Seq = []
    while Q:
        u = Q.pop()
        Seq.append(u)
        for v in graph[u]:
            in_degrees[v] -= 1
            if in_degrees[v] == 0:
                Q.append(v)
    if len(Seq) == vertex_num:
        return Seq
    return "Fail"

class Solution:    
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        groups = [[] for i in range(m)]
        for i, g in enumerate(group):
            # 将无group的item添加到只包含他自己的group，方便最后进行group间的拓扑排序
            if g == -1:
                group[i] = len(groups)
                groups.append([i])
            else:
                groups[g].append(i)
        for i, grp in enumerate(groups):
            graph = {}
            for u in grp:
                graph[u] = []
            for u in grp:
                for v in beforeItems[u]:
                    if group[v] == group[u]:
                        graph[v].append(u)
            # 对每个group进行内部拓扑排序
            groups[i] = topoSort(graph)
            if groups[i] == "Fail":
                return []
        graph = {}
        for i in range(len(groups)):
            graph[i] = []
        # 转换item间的before关系为group之间
        for u, ll in enumerate(beforeItems):
            for v in ll:
                if group[u] != group[v]:
                    graph[group[v]].append(group[u])
        # group间的拓扑排序，排的是下标（index）
        group_idx = topoSort(graph)
        if group_idx == "Fail":
            return []
        ans = []
        # join together
        for idx in group_idx:
            ans += groups[idx]
        return ans