Adam's Blog

2021 leetcode 秋季赛

这次比赛本周重在参与的态度，提前准备不多，没想到最后成绩还比去年高。废话不多说放成绩，今年的战绩：接下来讲解下ac的题目由于篇幅有限只提供题目，忽略用例,所有解答代码见note 1. 无人机方阵在「力扣挑战赛」开幕式的压轴节目「无人机方阵」中，每一架无人机展示一种灯光颜色。无人机方阵通过两种操作进行颜色图案变换： 1 调整无人机的位置布局 2 切换无人机展示的灯光颜色给定两个大小均为 N*M 的二维数组 source 和 target 表示无人机方阵表演的两种颜色图案，由于无人机切换灯光颜色的耗能很大，请返回从 source 到 target 最少需要多少架无人机切换灯光颜色。注意：调整无人机的位置布局时无人机的位置可以随意变动。这道签到题比春季赛的简单，由于位置可以随意调换，我们可以用两个hash分别存储已有的颜色和需要的颜色的数量，需要的颜色-已有的颜色之和就是答案了。 2. 心算挑战「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。显然该题适用贪心算法，我们先观察条件，分数之和必须是偶数，所以我们的卡牌只能由偶数个奇数和任意个偶数组成。首先我们把卡牌分成奇数和偶数，再分别进行排序。我们考虑每两张奇数卡牌之和和两张偶数卡牌之和，取其最大的组合，这样我们就能保证我们取的卡牌是分数且为偶数，如果遇到卡牌不足的情况则说明不存在满足条件的情况则返回0。 PS：如果需要去的卡牌为奇数说明必又一个偶数，我们先将最大的偶数加入结果，这样需要的卡牌数就能保证是偶数。 3. 黑白翻转棋在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 “X”, 白棋记作字母 “O”，空余位置记作 “."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。注意：若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以继续翻转白棋输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置

数学相关算法题推荐

数学是计算机的重要基础，算法题中常常会用到数学知识，尤其是离散、具体的数学，以数论、排列组合、概率期望、多项式为代表，可以出现在几乎任何类别的题目中，所有题目涉及到的数学知识点都已标出，建议去oi-wiki 学习。强烈建议小伙伴先尝试用非数学的常规解法思考以下题目（也许会更简单更好理解），再用数学的解法。第一周 5月3日开胃小菜: 斐波那契数列，在这道题中，你会学到算法题中必会的一个数学知识点中国剩余定理。建议独自完成四种做法，并完成快速幂的普通写法（模版）以及公式法。灯泡开关尝试使用数学的思维分析n轮后灯泡亮着必须满足什么条件。 5月5日超级丑数做这题之前先学习求质数的几种方法（强烈建议掌握）,之后只需要思考如果求出第n个即可. 石子游戏经典的石子游戏肯定是不能错过的，建议用动态规划解一遍。 5月7日循环码排列，可以先用朴素做法，再了解格雷码，优化解法。飞机座位这道题是很明显可以利用数学优化的题目。第二周 5月12日各位相加尽量优化你的时间复杂度和空间复杂度至 $O(1)$ 。放松一下：不浪费原料的汉堡制作方案我愿称之为最简单中等题。 5月14日使数组和能被 P 整除剩余定理的应用，加上前缀和的思想。最简分数思路很简单，可以学习到求最大公约数的做法。 5月16日检查「好数组」建议了解裴蜀定理之后再做这题，通过这个定理你还可以解决以下题目水壶问题安排邮筒动态规划中数学的应用，中位数的思想非常常用。第三周 5月19日剪绳子 II leetcode中有许多类似的题目掌握其中的思想，就能解决许多类似的问题：剪绳子整数拆分好因子的最大数目 … 构造乘积数组记得考虑特殊情况。 5月21日字符串相乘高精度计算，行列式模拟即可。航班预订本题可以利用差分的思想来快速求解区间和（对于不会线段树和树状数组的小伙伴是很有利的）。 5月23日石子游戏5 石子游戏又来啦。完全平方数可以先尝试搜索算法，再看数学解答拉格朗日四平方定理。第四周 5月26日阶乘后的零，我们只需要思考什么数相乘会等于零。阶乘函数后 K 个零有了上面的基础这题就会容易一些。 5月28日形成两个异或相等数组的三元组数目思考如何利用异或的性质。消失的两个数希望能用三中解法解决本题其中位运算法和此题相似 5月30日结业考试乐团站位思考怎样通过坐标判断是第几圈，总结每圈的公式。（本题是全站通过率最低的简单题）奇妙序列预备知识：乘法逆元 +快速幂+剩余定理。有能力的小伙伴也可以用树状数组来解答。（本题是全站通过率最低的困难题）

Envoy introduction

简介 Envoy 是一个高性能的网络代理服务，可以用于 Service Mesh。它是专为大型现代 SOA（面向服务架构）架构设计的 L7 代理和通信总线，体积小，性能高。它可以提供通用的网络功能，如负载均衡、服务发现、路由、健康检查、认证、授权等⁵。它还支持动态配置和热重启，以适应不断变化的服务环境²。 Envoy的架构基于一个高度模块化的设计，其中每个模块都专注于不同的网络功能。这种模块化的设计使得Envoy非常灵活，可以轻松地扩展和自定义以满足各种用例和需求。 Envoy的代理是分层的，其中包括网络层，传输层和应用层。网络层负责处理IP包，传输层负责处理TCP和UDP报文，应用层代理负责处理HTTP请求和响应等高级协议。在这些代理层中， Envoy提供了各种过滤器和扩展，以实现各种网络功能，如身份验证，流量转换和日志记录等。其中，网络层代理实现了一个高性能的L3/L4代理，可以在TCP和UDP层提供负载均衡和故障转移。这意味着Envoy可以将请求分发到多个后端服务器，并确保在服务器出现故障时仍能正常工作。传输层代理实现了一个基于HTTP/2的L7代理，支持HTTP/1.1，gRPC和WebSocket等协议。这使得Envoy可以在应用层面上提供更多的功能，例如流控制和请求/响应重试等。除此之外，Envoy还支持TCP代理，可以在L4层对TCP数据进行处理。特性一些比较比较重要的特性如下： Envoy 是一个基于现代 C++ 开发的 L4/L7 高性能代理，可以透明地代理各种协议，如 HTTP/1.1，HTTP/2，GRPC，WebSocket 等。 Envoy 支持流量管理、治理特性、负载均衡、动态配置 API、可观察性设计等功能，可以满足复杂的服务网络需求。 Envoy 是一个数据平面第一的设计，即将 Envoy 作为一个独立进程，与每个应用程序服务并行运行，并通过统一的 API 进行配置和管理。 Envoy的核心设计原则之一是可观测性。Envoy提供了丰富的统计信息，日志和跟踪功能，以帮助用户深入了解其网络流量的性能和行为。此外，Envoy还支持各种开放式标准，如Prometheus，Zipkin和Jaeger等，以便用户可以将其数据与其它系统无缝集成。除此之外，Envoy还支持多种部署方式，例如Docker容器，Kubernetes集群和Mesos框架。这使得Envoy可以轻松地与现代云原生应用程序集成。总结总的来说，Envoy是一个功能强大，灵活和高性能的代理，适用于各种网络和安全用例。它的模块化架构和可观测性设计使得Envoy成为一个理想的选择，无论是在公共云，私有云还是混合云环境下使用。