小菜鸟

逆波兰表达式（Reverse Polish Notation, RPN）

逆波兰表达式是一种数学表达式的表示方法，其特点是运算符位于操作数之后，无需使用括号来指定运算顺序，因此也被称为 “后缀表达式”。它在计算机科学中被广泛应用于表达式求值、编译器设计等领域。

基本概念

与传统表达式的对比

• 中缀表达式（日常使用）：运算符位于操作数中间，如 3 + 4 × 2 ÷ (1 - 5)。 缺点：需要括号和运算符优先级（先乘除后加减）来确定运算顺序，计算机解析复杂。
• 逆波兰表达式（后缀表达式）：运算符位于操作数之后，如 3 4 2 × 1 5 - ÷ +。 优点：无需括号，仅通过顺序扫描即可确定运算顺序，计算机解析高效。

核心原理

逆波兰表达式的求值过程可通过栈（Stack）数据结构实现，步骤如下：

1. 从左到右扫描表达式的每个元素（操作数或运算符）。
2. 若遇到操作数，将其压入栈中。
3. 若遇到运算符，从栈中弹出两个操作数（注意顺序：后弹出的是第一个操作数），使用该运算符计算结果，再将结果压回栈中。
4. 扫描结束后，栈中仅剩的元素即为表达式的结果。

稀疏数组（Sparse Array）：高效压缩稀疏数据的优化方案

稀疏数组是一种针对大部分元素为默认值（如 0、null） 的二维数组设计的压缩存储结构，通过仅记录有效元素的位置和值，大幅减少存储空间和数据传输开销。本文详细解析稀疏数组的原理、转换流程、应用场景及实现代码。

稀疏数组的核心概念

适用场景

当一个二维数组中：

• 绝大多数元素是默认值（如 0、空值）；
• 仅有少量元素具有实际意义（如 1、2 等非默认值）。

此时直接存储原始数组会造成大量空间浪费，而稀疏数组通过 “保留有效信息，舍弃默认值” 实现压缩。

核心思想

稀疏数组不存储默认值，仅记录：

• 原始数组的总行数、总列数；
• 所有非默认值元素的位置（行号、列号）和值。

原始数组与稀疏数组的转换

以五子棋棋盘为例（11×11 的二维数组，0 表示空位，1 表示黑子，2 表示白子），演示转换过程。

原始数组（11×11）

约瑟夫问题（Josephus Problem）

约瑟夫问题是一个经典的数学和计算机科学问题，属于递归与循环算法的典型案例。其核心是模拟一群人围成圈，按固定规则依次淘汰成员，最终寻找最后剩下的人的位置。

问题背景

传说源于古罗马历史学家约瑟夫斯（Flavius Josephus）的真实经历：在公元 1 世纪的犹太战争中，约瑟夫斯和 40 名士兵被罗马军队围困，他们约定围成一圈，从第 1 个人开始报数，每数到第 3 个人就将其杀死，直到最后一人。约瑟夫斯通过数学计算找到了最后存活的位置，从而保住了自己的性命。

问题描述

标准问题：

有 n 个人围成一圈，从第 1 个人开始依次报数，当报到 k 时，该人被淘汰；然后从下一个人开始重新报数，重复此过程，直到最后只剩下 1 个人。求最后存活者的初始位置（通常从 1 开始计数）。

Redis 字符串实现详解：SDS 与编码机制（基于 6.0.10 版本）

Redis 中的字符串并非直接使用 C 语言的原生字符串（以 \0 结尾的字符数组），而是通过SDS（Simple Dynamic String，简单动态字符串） 实现。SDS 解决了 C 字符串的诸多缺陷（如长度获取低效、缓冲区溢出风险等），并结合灵活的编码机制，在性能和内存效率上进行了极致优化。本文结合源码结构，详解 SDS 的设计与字符串对象的编码策略。

SDS 的设计动机：为何不使用 C 字符串？

C 语言原生字符串（char*）存在以下缺陷，无法满足 Redis 高性能、高可靠性的需求：

1. 长度获取低效：需遍历整个字符串（strlen 函数，O (N) 时间复杂度）。
2. 缓冲区溢出风险：修改字符串时（如 strcat），若未提前分配足够空间，会覆盖相邻内存。
3. 不支持二进制安全：以 \0 作为结束标志，无法存储包含 \0 的二进制数据（如图片、音频）。
4. 修改效率低：每次修改都需重新分配内存（扩展或收缩），频繁操作会导致性能损耗。

SDS 针对这些问题进行了优化，核心目标是：高效获取长度、杜绝缓冲区溢出、支持二进制安全、减少内存重分配次数。

SDS 的结构体设计

SDS 提供了多种结构体（sdshdr5 到 sdshdr64），根据字符串长度选择合适的类型，避免内存浪费。源码结构如下（简化自 sds.h）：

1. 核心结构体（以 sdshdr8 为例）

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;         // 已使用长度（字符串实际字节数，不包含结尾的\0）
    uint8_t alloc;       // 总分配空间（不包含头部和结尾\0，= len + 未使用空间）
    unsigned char flags; // 类型标记（低3位表示结构体类型，如 SDS_TYPE_8）
    char buf[];          // 柔性数组，存储字符串数据（含结尾\0，确保兼容C函数）
};

字段详解：

CentOS 7 升级 GCC 版本：从 4.8.5 到 9+ 的完整解决方案

在 CentOS 7 中编译高版本软件（如 Python 3.9+）时，常因系统默认 GCC 版本过低（4.8.5）导致编译失败。本文详细记录从问题排查到成功升级 GCC 的全过程，解决依赖冲突和源配置问题。

问题背景与原因分析

1. 编译报错的根源

编译 Python 3.9.2 时出现如下错误，核心原因是 GCC 版本不足：

SystemError: <built-in function compile> returned NULL without setting an error
generate-posix-vars failed

• Python 3.9+ 要求 GCC 5.0 及以上版本，而 CentOS 7 默认 GCC 为 4.8.5，无法满足编译需求。

2. 尝试升级

尝试一

sudo yum install gcc

然后显示4.8.5已是最新版本，我这是假的yum吗？

尝试二

那我安装整体工具包呢？

sudo yum groupinstall "Development Tools"

版本依然没变。

尝试三

更新下yum？

sudo yum update
# 然后在进行安装gcc
sudo yum install gcc

版本依然没变。

尝试四

好吧，那我指定版本总行了吧，我下载个9的

sudo yum install devtoolset-9-gcc devtoolset-9-gcc-c++ devtoolset-9-binutils

显示没有软件包

3. 直接升级失败的原因

• CentOS 7 官方仓库维护的 GCC 版本停留在 4.8.5，通过 yum install gcc 无法获取更高版本。
• 第三方源配置不当或未启用，导致无法找到 devtoolset-9 等高版本 GCC 包。

升级 GCC 的完整步骤

1. 备份并更换 YUM 源

CentOS 7 官方源可能存在访问缓慢或版本滞后问题，建议更换为阿里云镜像：