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。