小菜鸟

java菜鸟号正在起航

0%

发表于 分类于 阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

八皇后问题

八皇后问题是经典的回溯算法应用案例，由国际象棋棋手马克斯・贝瑟尔于 1848 年提出。问题要求在 8×8 的国际象棋棋盘上放置 8 个皇后，使得任意两个皇后不能处于同一行、同一列或同一斜线上，最终找出所有可能的摆放方案。

一、问题核心约束

放置皇后时需满足以下条件：

  1. 不同行：每一行只能放置 1 个皇后（可通过按行放置天然满足）。
  2. 不同列：任意两个皇后不能在同一列。
  3. 不同斜线：任意两个皇后不能在同一对角线（包括主对角线和副对角线）。

若用坐标 (row, col) 表示皇后位置，则对于两个皇后 (r1, c1) 和 (r2, c2)，需满足：

  • $ c1 \neq c2 $（不同列）
  • $(|r1 - r2| \neq |c1 - c2|)$（不同斜线，即行差不等于列差）

二、解决方案：回溯算法

回溯算法是解决八皇后问题的最优方法，其核心思想是逐行尝试放置皇后，若当前位置不满足约束则回退到上一行，尝试下一列，直到找到所有合法方案。

算法步骤：

  1. 初始化：创建一个数组 queens 记录每一行皇后的列位置（索引为行号，值为列号）。

  2. 递归放置：从第 0 行开始，逐行尝试在每一列放置皇后：

    • 检查当前列是否与已放置的皇后冲突（列冲突或斜线冲突）。

  • 若不冲突，放置皇后并递归处理下一行。

    • 若冲突，尝试下一列。

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

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

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

基本概念

与传统表达式的对比

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

核心原理

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

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

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 3.4k 阅读时长 ≈ 3 分钟

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

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

稀疏数组的核心概念

适用场景

当一个二维数组中：

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

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

核心思想

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

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

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

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

原始数组（11×11）

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

约瑟夫问题（Josephus Problem）

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

问题背景

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

问题描述

标准问题：

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

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 3.5k 阅读时长 ≈ 3 分钟

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 为例）

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