CodingTour
ARTS #171

Algorithm

本周选择的算法题是:The Number of Weak Characters in the Game

规则

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

Example 1:

Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Explanation: No character has strictly greater attack and defense than the other.

Example 2:

Input: properties = [[2,2],[3,3]]
Output: 1
Explanation: The first character is weak because the second character has a strictly greater attack and defense.

Example 3:

Input: properties = [[1,5],[10,4],[4,3]]
Output: 1
Explanation: The third character is weak because the second character has a strictly greater attack and defense.

Constraints:

  • 2 <= properties.length <= 105
  • properties[i].length == 2
  • 1 <= attacki, defensei <= 105

Solution

impl Solution {
    pub fn number_of_weak_characters(mut properties: Vec<Vec<i32>>) -> i32 {
        properties.sort_unstable_by_key(|key| (key[0], -key[1]));

        let (mut ans, mut min) = (0, i32::min_value());
        for i in (0..properties.len()).rev() {
            if properties[i][1] < min {
                ans += 1;
            }
            min = min.max(properties[i][1]);
        }
        ans
    }
}

Review

Will Modular Monolith Replace Microservices Architecture?

作者在这篇文章中介绍了什么是单体模块化架构(也称为 macroservices)、迷你服务和微服务,以及它们的优势和劣势,并总结成了一张图:

以保险系统为例:

有三种拆分方式:

  • 水平拆分 - 基于业务,如车险、意外险等

  • 垂直拆分 - 基于功能,如客户、保单、赔付等
  • 混合拆分 - 结合水平拆分和垂直拆分,如客户一般是通用的,拆分为微服务;而汽车保单基本和人寿、家庭等没有共同之处,则将它们拆分为迷你服务

作者最后建议如果是构建一个新的系统,尽量用微服务与迷你服务组合的方式来构建,即混合拆分。

不过其实对新系统而言,单体架构或单体模块化架构也未尝不是好的构建方式,单体应用有助于聚焦业务需求和功能,而不是将注意力集中在基础设施上。而且在项目初期,单体应用会更容易维护和管理。

只有随着业务规模不断变大,才需要进一步考虑拆分的问题,而设计良好的单体架构也能以很低的成本接入微服务 or something else,这其中最大的挑战不是单体架构的问题,而是架构的决策者是否能杀伐果断,及时调整到新方向,拖延往往会带来长期问题 - 不仅仅是单体架构。

Tip

一个买卖代码的平台:Envato Market

Share

为什么苹果在 Xcode 14 中废弃了 Bitcode