侯瑞哲的博客

Ruizhe's Blog

0%

发表于 Valine：

5535. 括号的最大嵌套深度

比较简单，不贴代码了

5536. 最大网络秩

计算每个点的边，如果两点相连，减去一条重复的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        neigh = defaultdict(set)
        for x, y in roads:
            neigh[x].add(y)
            neigh[y].add(x)
        res = 0

        def maxRank(x, y):
            if y in neigh[x]:
                return len(neigh[x]) + len(neigh[y]) - 1
            return len(neigh[x]) + len(neigh[y])

        for x in range(n):
            for y in range(x + 1, n):
                res = max(res, maxRank(x, y))
        return res

5537. 分割两个字符串得到回文串

找到a b从中心开始的最长回文串，从al, ar, bl, br，然后比较a[:al] == b[ar+1:] or a[:bl] == b[br + 1] or b[:al] == a[ar+1:] or b[:bl] == a[br+1:]

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
class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def isPalindrome(s):
            return s == s[::-1]

        if isPalindrome(a) and isPalindrome(b):
            return True
        n = len(a)

        if n & 1:
            l = r = n >> 1
        else:
            l, r = (n >> 1) - 1, n >> 1
        # print(len(a))
        # print(l, r)
        al, ar = l, r
        while al >= 0 and ar < n and a[al] == a[ar]:
            al -= 1
            ar += 1
        bl, br = l, r
        while bl >= 0 and br < n and b[bl] == b[br]:
            bl -= 1
            br += 1
        # print(a[:al + 1], b[ar:][::-1])
        # print(b[:bl + 1], a[br:][::-1])
        return a[:al + 1] == b[ar:][::-1] or b[:bl + 1] == a[br:][::-1] \
               or b[:al + 1] == a[ar:][::-1] or a[:bl + 1] == b[br:][::-1]

5538. 统计子树中城市之间最大距离

状压枚举所有集合，以集合的每一个点为根顶点，bfs计算这个点为根顶点时的树的高度，最大值即为这个集合构成子树的最大距离

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
class Solution(object):

    def countSubgraphsForEachDiameter(self, n, edges):
        G = [[] for _ in range(n)]
        for i, j in edges:
            G[i - 1].append(j - 1)
            G[j - 1].append(i - 1)

        def maxd(mask0):
            res = 0
            for i in range(n):
                if (1 << i) & mask0:
                    mask = mask0
                    bfs, bfs2 = [i], []
                    cur = 0
                    while bfs:
                        for i in bfs:
                            mask ^= 1 << i
                            for j in G[i]:
                                if mask & (1 << j):
                                    bfs2.append(j)
                        cur += 1
                        bfs, bfs2 = bfs2, []
                    if mask:
                        return 0
                    res = max(res, cur - 1)
            return res

        res = [0] * (n - 1)
        for mask in range(1 << n):
            if mask & (mask - 1) == 0:
                continue
            d = maxd(mask)
            if d:
                res[d - 1] += 1

        return res

AcWing《LeetCode究极班》拼团优惠！https://www.acwing.com/activity/content/introduction/31/group_buy/1154/

发表于 Valine：

5515. 设计停车系统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.big = big
        self.medium = medium
        self.small = small

    def addCar(self, carType: int) -> bool:
        if carType == 1:
            if self.big == 0:
                return False
            self.big -= 1
            return True
        elif carType == 2:
            if self.medium == 0:
                return False
            self.medium -= 1
            return True
        else:
            if self.small == 0:
                return False
            self.small -= 1
            return True

5516. 警告一小时内使用相同员工卡大于等于三次的人

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
class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        res = set()
        record = defaultdict(list)
        for name, time in zip(keyName, keyTime):
            if name in res:
                continue
            tmp = self.to_minute(time)
            loc = bisect.bisect_left(record[name], tmp)
            record[name].insert(loc, tmp)
            if loc - 2 >= 0 and tmp - record[name][loc - 2] <= 60:
                res.add(name)
                continue
            if loc - 1 >= 0 and loc + 1 < len(record[name]) and record[name][
                loc + 1] - record[name][loc - 1] <= 60:
                res.add(name)
                continue
            if loc + 2 < len(record[name]) and record[name][loc + 2] - tmp <= \
                    60:
                res.add(name)
                continue
        res = list(res)
        res.sort()
        return res

    def to_minute(self, time_str):
        h, m = map(int, time_str.split(":"))
        return h * 60 + m

5518. 给定行和列的和求可行矩阵

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def restoreMatrix(self, rowSum: List[int],
                      colSum: List[int]) -> List[List[int]]:
        m = len(rowSum)
        n = len(colSum)
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                res[i][j] = min(rowSum[i], colSum[j])
                rowSum[i] -= res[i][j]
                colSum[j] -= res[i][j]
        return res

5517. 找到处理最多请求的服务器

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
class Solution:
    def busiestServers(self, ks: int, a: List[int], d: List[int]) -> List[int]:
        from sortedcontainers import SortedList
        ans = [0] * ks
        pq = []
        fu = SortedList(range(ks))
        v = 0
        for i, j in zip(a, d):
            heappush(pq, [i, 1, i + j, v])
            v += 1
        # print(pq,fu)
        while pq:
            i, k, j, num = heappop(pq)
            if k == 1 and fu:
                v = fu.bisect_left(num % ks)
                if v == len(fu):
                    v = 0
                v = fu[v]
                fu.remove(v)
                ans[v] += 1
                heappush(pq, [j, 0, v, num])
            elif k == 0:
                fu.add(j)
            # print(pq,fu)
        # print(ans)
        t = max(ans)
        return [i for i in range(ks) if ans[i] == t]

发表于 Valine：

5531. 特殊数组的特征值

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n + 1):
            c = 0
            for num in nums:
                if num >= i:
                    c += 1
            if c == i:
                return i
        return -1

5532. 奇偶树

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
class Solution:
    def isEvenOddTree(self, root: TreeNode) -> bool:
        q, nq = [root], []
        flag = True
        while q:
            if flag:
                pre = float('-inf')
                for node in q:
                    if node.val & 1 == 0 or node.val <= pre:
                        return False
                    pre = node.val
                    if node.left:
                        nq.append(node.left)
                    if node.right:
                        nq.append(node.right)
            else:
                pre = float('inf')
                for node in q:
                    if node.val & 1 == 1 or node.val >= pre:
                        return False
                    pre = node.val
                    if node.left:
                        nq.append(node.left)
                    if node.right:
                        nq.append(node.right)
            q, nq = nq, []
            flag = not flag
        return True

5534. 可见点的最大数目

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
class Solution:
    def visiblePoints(self, points: List[List[int]],
                      angle: int, location: List[int]) -> int:
        import math
        angle = angle / 360 * 2 * math.pi
        cnt = 0
        a = []
        for x, y in points:
            if x == location[0] and y == location[1]:
                cnt += 1
            else:
                xx, yy = x - location[0], y - location[1]
                a.append(math.atan2(yy, xx))
        a.sort()
        n = len(a)
        b = [x + math.pi * 2 for x in a]
        a += b
        j = 0

        ret = 0
        for i in range(n):
            while j < len(a):
                if a[j] - a[i] > angle:
                    break
                j += 1
            ret = max(ret, j - i)
        return ret + cnt

5533. 使整数变为 0 的最少操作次数

1
2
3
4
5
6
7
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        ans = 0
        while n:
            ans ^= n
            n >>= 1
        return ans
1
2
3
4
5
6
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n == 0:
            return 0
        p = n.bit_length()
        return (1 << p) - 1 - self.minimumOneBitOperations(n - (1 << (p - 1)))

两种做法

发表于 Valine：

1. 文件夹操作日志搜集器

简单模拟

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minOperations(self, logs: List[str]) -> int:
        cur = 0
        for log in logs:
            if log == '../':
                if cur:
                    cur -= 1
            elif log == './':
                continue
            else:
                cur += 1
        return cur

2. 经营摩天轮的最大利润

模拟

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
class Solution:
    def minOperationsMaxProfit(self, customers: List[int],
                               boardingCost: int, runningCost: int) -> int:
        ans = 0
        res = 0
        p = 0
        w = 0
        i = 0
        for c in customers:
            i += 1
            w += c
            b = min(w, 4)
            w -= b
            p += b * boardingCost - runningCost
            if p > res:
                res = p
                ans = i
        while w:
            i += 1
            b = min(w, 4)
            w -= b
            p += b * boardingCost - runningCost
            if p > res:
                res = p
                ans = i
        return ans if ans else -1

3. 皇位继承顺序

树节点的设计，和dfs先序遍历

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 TreeNode:
    def __init__(self, name):
        self.name = name
        self.children = []
        self.is_death = False


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.root = TreeNode(kingName)
        self.mem = {kingName: self.root}

    def birth(self, parentName: str, childName: str) -> None:
        p_node = self.mem[parentName]
        c_node = TreeNode(childName)
        p_node.children.append(c_node)
        self.mem[childName] = c_node

    def death(self, name: str) -> None:
        node = self.mem[name]
        node.is_death = True

    def getInheritanceOrder(self) -> List[str]:
        res = []
        stack = [self.root]
        while stack:
            node = stack.pop()
            if not node.is_death:
                res.append(node.name)
            for child in reversed(node.children):
                stack.append(child)
        return res

4. 最多可达成的换楼请求数目

状态压缩dp，以及了解图中任何一个节点入度与出度相等时，就满足净变化为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
class Solution {
    int tot[25];
public:
    int maximumRequests(int n, vector<vector<int>> &req) {
        int ans = 0;
        int m = req.size();
        int lim = (1 << m) - 1;
        for (int i = 1; i <= lim; ++i) {
            for (int j = 0; j < n; ++j) tot[j] = 0;
            int cnt = 0;
            for (int j = 0, k = 1; j < m; ++j, k <<= 1)
                if (i & k) {
                    ++tot[req[j][1]], --tot[req[j][0]];
                    ++cnt;
                }
            bool flag = true;
            for (int j = 0; j < n; ++j) {
                if (tot[j] != 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) ans = max(ans, cnt);
        }
        return ans;
    }
};

发表于 Valine：

1. K步编辑

描述

给出一个只含有小写字母的字符串的集合以及一个目标串(target)，输出所有可以经过不多于 k 次操作得到目标字符串的字符串。

你可以对字符串进行一下的3种操作:

  • 加入1个字母
  • 删除1个字母
  • 替换1个字母

思路：一个应用编辑距离的问题，使用python语言会超时。

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
class Solution {
public:
    /**
     * @param words: a set of stirngs
     * @param target: a target string
     * @param k: An integer
     * @return: output all the strings that meet the requirements
     */

    int minDistance(string word1, string word2, int k) {
        int m = word1.size();
        int n = word2.size();
        if (m - n > k || n - m > k) return k + 1;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j]));
                }
            }
        }
        return dp[m][n];
    }

    vector<string> kDistance(vector<string> &words, string &target, int k) {
        // write your code here
        vector<string> res;
        for (auto &word: words) {
            if (minDistance(word, target, k) <= k) {
                res.push_back(word);
            }
        }
        return res;
    }
};

2. 折纸

描述

折纸，每次都是将纸从右向左对折，凹痕为 0，凸痕为 1，求折 n 次后，将纸展开所得折痕组成的 01 序列。

1<=n<=20

思路：类似中序遍历，加入一个是正是反的变量，模拟折纸过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    """
    @param n: The folding times
    @return: the 01 string
    """

    def getString(self, n):
        # Write your code here
        def printProcess(i, N, down):
            if i > N:
                return
            printProcess(i + 1, N, True)
            if down is True:
                res.append('0')
            else:
                res.append('1')
            printProcess(i + 1, N, False)

        res = []
        printProcess(1, n, True)
        return "".join(res)

3. 字符串的不同排列

描述

给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。 请以字典序从小到大输出。 0<=n<=20

思路：提前去重，输出排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    """
    @param str: A string
    @return: all permutations
    """

    def stringPermutation(self, s):
        # write your code here
        li = list(s)
        li.sort()
        q, nq = [""], []
        for char in li:
            for ans in q:
                for i in range(len(ans), -1, -1):
                    if i < len(ans) and char == ans[i]:
                        break
                    nq.append(ans[:i] + char + ans[i:])
            q, nq = nq, []
        q.sort()
        return q

4. 硬币排成线

描述

有 n 个硬币排成一条线, 第 i 枚硬币的价值为 values[i].

两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. 拿到硬币总价值更高的获胜.

请判定 第一个玩家 会赢还是会输.

1<=n<=2000 0<=value[i]<=1e7

思路：一个常见的dp问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    """
    @param values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """

    def firstWillWin(self, values):
        # write your code here
        n = len(values)
        dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][0] = values[i]
        for gap in range(1, n):
            for i in range(n - gap):
                j = i + gap
                left = dp[i + 1][j][1] + values[i]
                right = dp[i][j - 1][1] + values[j]
                if left > right:
                    dp[i][j][0] = left
                    dp[i][j][1] = dp[i + 1][j][0]
                else:
                    dp[i][j][0] = right
                    dp[i][j][1] = dp[i][j - 1][0]
        return dp[0][n - 1][0] > dp[0][n - 1][1]

PS: 今天第一次答阿里云，阿里云的罚时有点多，罚时时间还没有写出来，要注意有十足的保证再提交

发表于 Valine：

上帝，请赐予我平静，

去接受我无法改变的。

给予我勇气，

去改变我能改变的，

赐我智慧，

分辨这两者的区别。

过好我的每一天，

享受你所赐每一刻，

把困苦当成通往平安的道路，

像主耶稣那样，接受这罪恶的世界，

按其现实本相，而非如我所愿

相信他会使一切变得美好，

只要我顺服他的旨意；

我可以在此生有合宜的欢乐，

并在永生里，与他永享至福。

阿门。

无神论者，只是汲取其中的营养

发表于 Valine：

桶排序适用于待排序数据值域较大但分布比较均匀的情况，是一个期望时间复杂度为O(n)的排序算法。

其大致思想是对值域进行分块，每块分别排序。由于每块元素不多，一般使用插入排序。如果使用稳定的内层排序，并且将元素插入桶中时不改变相对顺序，那么桶排序就是稳定的。

如果待排序数据是随机生成的，将值域平均分成n块的期望时间复杂度是O(n)，证明可以参考算法导论或维基百科。

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
const int N = 100010;

int n, w, a[N];
vector<int> bucket[N];

void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A{j};
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; k < bucket[i].size() ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

发表于 Valine： 
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
void max_heapify(int arr[], int start, int end) {
  // 建立父结点指标和子结点指标
  int dad = start;
  int son = dad * 2 + 1;
  while (son <= end) {  // 子结点指标在范围内才做比较
    if (son + 1 <= end && arr[son] < arr[son + 1])  // 先比较两个子结点大小，选择最大的
      son++;
    if (arr[dad] > arr[son])  // 如果父结点比子结点大，代表调整完毕，直接跳出函数
      return;
    else {  // 否则交换父子内容，子结点再和孙结点比较
      swap(arr[dad], arr[son]);
      dad = son;
      son = dad * 2 + 1;
    }
  }
}

void heap_sort(int arr[], int len) {
  // 初始化，i从最后一个父结点开始调整
  for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1);
  // 先将第一个元素和已经排好序的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
  for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    max_heapify(arr, 0, i - 1);
  }
}