中国象棋将帅问题与单字节状态压缩基于 leetcode 仓库每日一题的位运算编码实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以 leetcode 仓库每日一题系列中的「将帅问题」源自《编程之美》1.2 节为骨架完整还原题目规则、同列判定原理与从双字节到单字节的状态压缩思路并结合仓库中位运算专题thinkings/bit.md与每日一题活动机制daily/README.md展开源码级佐证。读完本文你将掌握「用取余判定同列合法性」「以单变量商与余数拆分双层循环」「将 81 种状态编码进一个字节」三类数据压缩与位运算实战技巧并理解其在 IP 地址压缩等场景中的通用价值。题目背景与信息卡片这道题出自 leetcode 仓库的每日一题系列对应的文档为 daily/2019-07-26.md其信息卡片如下时间2019-07-26题目链接无来自编程之美tag数据压缩从仓库中「每日一题」总览daily/README.md可以看到这道题与「三门问题」「赛马问题」「称球问题」「洗牌算法」等同属经典趣味智力题序列被归类为数据压缩一类。值得注意的是这类每日一题并非来自 LeetCode 题库而是社区交流群中大家共同拆解的经典问题目的是锻炼算法思维与工程技巧——「将帅问题」正是其中极具代表性的一道。题目描述题目配图存放在 assets/daily/2019-07-26.jpeg展示了完整的中国象棋棋盘与将帅的活动范围题目核心规则如下中国象棋中「将」A与「帅」B不能照面即二者不能处于同一纵列同一列直线可视。将、帅都只能在己方的 3 × 3 格子内移动每次横移或纵移一格不能斜向移动。需要输出将、帅的所有合法位置组合。核心约束状态存储只允许使用一个字节8 bit即必须把 A、B 两个棋子的位置信息压缩进 8 位之内。这道题的关键难点不在遍历本身9 × 9 至多 81 种组合而在于如何理解「压缩」二字——这正是它被贴上数据压缩标签的原因。核心观察如何判断「将帅照面」不考虑单字节存储时我们只需要解决「如何判断位置是否合法」。将、帅各自的活动范围都是 3 × 3 的九宫格。如果我们把行、列坐标从 1 到 9 编号那么可以观察到一条关键规律坐标对 3 取余的结果相同的两个格子就处于同一列。这是本题最核心的数学观察。因为 3 × 3 的九宫格只有 3 列取余运算天然地把 9 个位置划分为 3 组同一组的格子共享同一纵列。因此「将帅是否照面」可以等价转换为「将的行列坐标取余结果与帅的行列坐标取余结果是否相同」。基于这个观察我们就能写出朴素的判定逻辑进而完成全部合法状态的枚举。解法一双重循环的朴素实现两字节存储最直观的思路是让 A、B 分别遍历各自 9 个位置用双重循环枚举全部 9 × 9 81 种组合并利用取余判定过滤掉同列不合法的组合for (let i 0; i 9; i) { for (let j 0; j 9; j) { if (i % 3 ! j % 3) { console.log(${i 1}, ${j 1}); } } }代码逐行解读i代表将的位置08输出时加 1 映射到 19j代表帅的位置i % 3 ! j % 3即为「不在同一列」的判定条件满足条件的组合输出该写法在循环控制上使用了两个独立变量i和j对应着两个独立的字节来存储两个棋子的位置状态。这正是题目要求压缩的对象两个字节的信息量能否塞进一个字节解法二单变量循环的状态压缩一个字节存储仔细观察内外两层循环可以发现内层循环与外层循环的长度完全一样都是 9。既然如此内外循环完全可以用一个变量来表示。内外循环总共执行 81 次于是我们定义一个从 81 开始的变量然后用i / 9表示外层循环的值将的位置用i % 9表示内层循环的值帅的位置。原理是i每增加 9 次内层循环值会增加 9、外层循环值会增加 1整个过程与原来的双重循环完全等价——这本质上就是把二维坐标(row, col)线性化为一维索引row * 9 col再通过除法和取余还原坐标。实现代码如下let i 81; while (i-- 0) { if (((i / 9) 0) % 3 ! (i % 9) % 3) { console.log(${((i / 9) 0) 1}, ${(i % 9) 1}); } }代码细节说明while (i-- 0)i从 80 递减到 0恰好执行 81 次循环等价于原来两层 9 × 9 的遍历(i / 9) 0JavaScript 中整数除法默认产生浮点数 0利用位运算将其截断为整数等价于向下取整得到外层循环值08(i % 9)得到内层循环值08判定条件((i / 9) 0) % 3 ! (i % 9) % 3与朴素解法中的i % 3 ! j % 3完全一致输出时对两个坐标各加 1映射为 19 的棋盘编号。复杂度分析时间复杂度$O(81)$即常量级 $O(1)$与双重循环方案一致空间复杂度$O(1)$只使用了一个循环变量。从「两个变量」到「一个变量」存储状态从两个字节压缩到一个字节而算法逻辑与输出结果没有任何损失——这就是数据压缩的精髓在不丢失信息的前提下减少表达状态所需的空间。数据压缩的通用思想与 IP 地址压缩的类比原文档特别提到这类问题属于「数据压缩问题中的一种」并举了一个经典例子如何将 IP 地址用 4 个字节来表示。这两道题在思想上完全同构场景原始表达压缩表达压缩手段将帅问题两个变量两字节存两个位置单变量 81 次循环一字节一维索引 除法/取余还原坐标IP 地址形如192.168.1.1的字符串4 个字节每段 1 字节按点分段数值化段号映射到字节IP 地址的每一段0255恰好能用 1 个字节8 bit表达4 段合起来就是 4 个字节而将帅问题中每个棋子的位置有 9 种可能理论上需要 4 bit$2^3 8 9 16 2^4$两个棋子就需要 8 bit——刚好是一个字节。这就是「一个字节存将帅」的底层信息论依据。这类思维在真实工程中无处不在紧凑的数据结构、网络协议头的字段压缩、数据库索引的位图编码等本质上都是「用尽可能少的比特表达尽可能多的状态」。仓库源码佐证位运算专题与编码细节「将帅问题」虽然只有短短一篇每日一题文档但其背后的位运算与编码思想在仓库的 thinkings/bit.md 位运算专题中有更系统的阐述。该专题指出灵活运用位运算是这类题目的关键并给出了异或运算的两条核心规律任何数和本身异或结果为 0任何数和 0 异或结果是其本身异或运算满足交换律。该专题用 136只出现一次的数字、137只出现一次的数字 II、260、645 四道题系统训练了位运算套路。例如 137 题通过逐位统计「当前 bit 有多少个 1」并配合num bit、res | bit等按位操作还原唯一出现一次的数字。这些正是「将帅问题」单字节压缩方案的底层工具——理解、%、、|等运算符的位级语义才能真正吃透压缩编码的每一步。仓库中每日一题系列daily/README.md与解答示例daily/answers 目录也印证了这一活动机制题目讨论集中、反馈充分优秀解答会被记录并沉淀进仓库。每日一题文档的写作模板见 templates/daily/2019-06-03.md其中明确了「思路要讲明白、语言不做要求、扩展引申可自拟」等规范。扩展思考从「一个变量」到「按位编码」原文档给出的单变量方案已经完成了「一字节存储」的要求但从位运算的角度还可以再深入一步既然每个棋子的位置19需要 4 bit 表达那么两个棋子恰好可以放进一个字节的 8 bit 中——高 4 位存将的位置低 4 位存帅的位置。例如可以将编码与解码实现如下// 编码将位置 a(1-9) 存入高 4 位帅位置 b(1-9) 存入低 4 位 // 8 bit 状态 ((a - 1) 4) | (b - 1) let state 0; for (let a 1; a 9; a) { for (let b 1; b 9; b) { if ((a - 1) % 3 ! (b - 1) % 3) { state ((a - 1) 4) | (b - 1); // 一个字节存下双坐标 const decodedA (state 4) 1; const decodedB (state 0x0f) 1; console.log(${decodedA}, ${decodedB}); } } }这段扩展代码演示了更「位级」的压缩思路 4将 A 的位置推进高 4 位|把 B 的位置拼进低 4 位解码时用 4取高 4 位、用 0x0f取低 4 位。虽然本题状态数81 种组合用一字节存储绰绰有余但这种「按位切分、各取所需」的编码方式正是网络协议与二进制文件格式中常见的字段压缩手法。边界与注意事项编码时坐标从 0 开始a - 1才能恰好放进 4 bit015否则 9 会溢出 4 bit 的表示范围JavaScript 位运算在 32 位整数上进行对负数高位补 1而 thinkings/bit.md 中特别提醒了 Python 等语言在处理符号位时的坑如 137 题中负数结果会变成2^32 - n需要显式减去2 ** 32还原跨语言实现时务必留意符号位语义差异本解法与单变量循环方案各有侧重前者更贴近「一字节存储」的工程语义后者在循环控制上更简洁二者都是同一压缩思想的不同侧面。小结「将帅问题」以一道小小的棋盘题串起了三个层次的能力数学建模通过「坐标对 3 取余」把「同列照面」的几何约束转化为可计算的数值条件状态压缩用「一维索引 除法/取余」把两字节的双重循环压缩为一字节的单变量循环与 IP 地址 4 字节表示同源同理位运算功底进一步可演进为「高 4 位 低 4 位」的按位编码而仓库的 thinkings/bit.md 专题为这类技巧提供了系统的训练题集。当你再遇到「如何用最小空间表达一组有限状态」这类问题时不妨回想一下这道将帅题先数清状态数、算清所需比特数再用取余、除法和移位把坐标塞进最紧凑的容器里——这就是数据压缩最朴素也最实用的方法论。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 中国象棋将帅问题与单字节状态压缩：基于 leetcode 仓库每日一题的位运算编码实战
中国象棋将帅问题与单字节状态压缩基于 leetcode 仓库每日一题的位运算编码实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以 leetcode 仓库每日一题系列中的「将帅问题」源自《编程之美》1.2 节为骨架完整还原题目规则、同列判定原理与从双字节到单字节的状态压缩思路并结合仓库中位运算专题thinkings/bit.md与每日一题活动机制daily/README.md展开源码级佐证。读完本文你将掌握「用取余判定同列合法性」「以单变量商与余数拆分双层循环」「将 81 种状态编码进一个字节」三类数据压缩与位运算实战技巧并理解其在 IP 地址压缩等场景中的通用价值。题目背景与信息卡片这道题出自 leetcode 仓库的每日一题系列对应的文档为 daily/2019-07-26.md其信息卡片如下时间2019-07-26题目链接无来自编程之美tag数据压缩从仓库中「每日一题」总览daily/README.md可以看到这道题与「三门问题」「赛马问题」「称球问题」「洗牌算法」等同属经典趣味智力题序列被归类为数据压缩一类。值得注意的是这类每日一题并非来自 LeetCode 题库而是社区交流群中大家共同拆解的经典问题目的是锻炼算法思维与工程技巧——「将帅问题」正是其中极具代表性的一道。题目描述题目配图存放在 assets/daily/2019-07-26.jpeg展示了完整的中国象棋棋盘与将帅的活动范围题目核心规则如下中国象棋中「将」A与「帅」B不能照面即二者不能处于同一纵列同一列直线可视。将、帅都只能在己方的 3 × 3 格子内移动每次横移或纵移一格不能斜向移动。需要输出将、帅的所有合法位置组合。核心约束状态存储只允许使用一个字节8 bit即必须把 A、B 两个棋子的位置信息压缩进 8 位之内。这道题的关键难点不在遍历本身9 × 9 至多 81 种组合而在于如何理解「压缩」二字——这正是它被贴上数据压缩标签的原因。核心观察如何判断「将帅照面」不考虑单字节存储时我们只需要解决「如何判断位置是否合法」。将、帅各自的活动范围都是 3 × 3 的九宫格。如果我们把行、列坐标从 1 到 9 编号那么可以观察到一条关键规律坐标对 3 取余的结果相同的两个格子就处于同一列。这是本题最核心的数学观察。因为 3 × 3 的九宫格只有 3 列取余运算天然地把 9 个位置划分为 3 组同一组的格子共享同一纵列。因此「将帅是否照面」可以等价转换为「将的行列坐标取余结果与帅的行列坐标取余结果是否相同」。基于这个观察我们就能写出朴素的判定逻辑进而完成全部合法状态的枚举。解法一双重循环的朴素实现两字节存储最直观的思路是让 A、B 分别遍历各自 9 个位置用双重循环枚举全部 9 × 9 81 种组合并利用取余判定过滤掉同列不合法的组合for (let i 0; i 9; i) { for (let j 0; j 9; j) { if (i % 3 ! j % 3) { console.log(${i 1}, ${j 1}); } } }代码逐行解读i代表将的位置08输出时加 1 映射到 19j代表帅的位置i % 3 ! j % 3即为「不在同一列」的判定条件满足条件的组合输出该写法在循环控制上使用了两个独立变量i和j对应着两个独立的字节来存储两个棋子的位置状态。这正是题目要求压缩的对象两个字节的信息量能否塞进一个字节解法二单变量循环的状态压缩一个字节存储仔细观察内外两层循环可以发现内层循环与外层循环的长度完全一样都是 9。既然如此内外循环完全可以用一个变量来表示。内外循环总共执行 81 次于是我们定义一个从 81 开始的变量然后用i / 9表示外层循环的值将的位置用i % 9表示内层循环的值帅的位置。原理是i每增加 9 次内层循环值会增加 9、外层循环值会增加 1整个过程与原来的双重循环完全等价——这本质上就是把二维坐标(row, col)线性化为一维索引row * 9 col再通过除法和取余还原坐标。实现代码如下let i 81; while (i-- 0) { if (((i / 9) 0) % 3 ! (i % 9) % 3) { console.log(${((i / 9) 0) 1}, ${(i % 9) 1}); } }代码细节说明while (i-- 0)i从 80 递减到 0恰好执行 81 次循环等价于原来两层 9 × 9 的遍历(i / 9) 0JavaScript 中整数除法默认产生浮点数 0利用位运算将其截断为整数等价于向下取整得到外层循环值08(i % 9)得到内层循环值08判定条件((i / 9) 0) % 3 ! (i % 9) % 3与朴素解法中的i % 3 ! j % 3完全一致输出时对两个坐标各加 1映射为 19 的棋盘编号。复杂度分析时间复杂度$O(81)$即常量级 $O(1)$与双重循环方案一致空间复杂度$O(1)$只使用了一个循环变量。从「两个变量」到「一个变量」存储状态从两个字节压缩到一个字节而算法逻辑与输出结果没有任何损失——这就是数据压缩的精髓在不丢失信息的前提下减少表达状态所需的空间。数据压缩的通用思想与 IP 地址压缩的类比原文档特别提到这类问题属于「数据压缩问题中的一种」并举了一个经典例子如何将 IP 地址用 4 个字节来表示。这两道题在思想上完全同构场景原始表达压缩表达压缩手段将帅问题两个变量两字节存两个位置单变量 81 次循环一字节一维索引 除法/取余还原坐标IP 地址形如192.168.1.1的字符串4 个字节每段 1 字节按点分段数值化段号映射到字节IP 地址的每一段0255恰好能用 1 个字节8 bit表达4 段合起来就是 4 个字节而将帅问题中每个棋子的位置有 9 种可能理论上需要 4 bit$2^3 8 9 16 2^4$两个棋子就需要 8 bit——刚好是一个字节。这就是「一个字节存将帅」的底层信息论依据。这类思维在真实工程中无处不在紧凑的数据结构、网络协议头的字段压缩、数据库索引的位图编码等本质上都是「用尽可能少的比特表达尽可能多的状态」。仓库源码佐证位运算专题与编码细节「将帅问题」虽然只有短短一篇每日一题文档但其背后的位运算与编码思想在仓库的 thinkings/bit.md 位运算专题中有更系统的阐述。该专题指出灵活运用位运算是这类题目的关键并给出了异或运算的两条核心规律任何数和本身异或结果为 0任何数和 0 异或结果是其本身异或运算满足交换律。该专题用 136只出现一次的数字、137只出现一次的数字 II、260、645 四道题系统训练了位运算套路。例如 137 题通过逐位统计「当前 bit 有多少个 1」并配合num bit、res | bit等按位操作还原唯一出现一次的数字。这些正是「将帅问题」单字节压缩方案的底层工具——理解、%、、|等运算符的位级语义才能真正吃透压缩编码的每一步。仓库中每日一题系列daily/README.md与解答示例daily/answers 目录也印证了这一活动机制题目讨论集中、反馈充分优秀解答会被记录并沉淀进仓库。每日一题文档的写作模板见 templates/daily/2019-06-03.md其中明确了「思路要讲明白、语言不做要求、扩展引申可自拟」等规范。扩展思考从「一个变量」到「按位编码」原文档给出的单变量方案已经完成了「一字节存储」的要求但从位运算的角度还可以再深入一步既然每个棋子的位置19需要 4 bit 表达那么两个棋子恰好可以放进一个字节的 8 bit 中——高 4 位存将的位置低 4 位存帅的位置。例如可以将编码与解码实现如下// 编码将位置 a(1-9) 存入高 4 位帅位置 b(1-9) 存入低 4 位 // 8 bit 状态 ((a - 1) 4) | (b - 1) let state 0; for (let a 1; a 9; a) { for (let b 1; b 9; b) { if ((a - 1) % 3 ! (b - 1) % 3) { state ((a - 1) 4) | (b - 1); // 一个字节存下双坐标 const decodedA (state 4) 1; const decodedB (state 0x0f) 1; console.log(${decodedA}, ${decodedB}); } } }这段扩展代码演示了更「位级」的压缩思路 4将 A 的位置推进高 4 位|把 B 的位置拼进低 4 位解码时用 4取高 4 位、用 0x0f取低 4 位。虽然本题状态数81 种组合用一字节存储绰绰有余但这种「按位切分、各取所需」的编码方式正是网络协议与二进制文件格式中常见的字段压缩手法。边界与注意事项编码时坐标从 0 开始a - 1才能恰好放进 4 bit015否则 9 会溢出 4 bit 的表示范围JavaScript 位运算在 32 位整数上进行对负数高位补 1而 thinkings/bit.md 中特别提醒了 Python 等语言在处理符号位时的坑如 137 题中负数结果会变成2^32 - n需要显式减去2 ** 32还原跨语言实现时务必留意符号位语义差异本解法与单变量循环方案各有侧重前者更贴近「一字节存储」的工程语义后者在循环控制上更简洁二者都是同一压缩思想的不同侧面。小结「将帅问题」以一道小小的棋盘题串起了三个层次的能力数学建模通过「坐标对 3 取余」把「同列照面」的几何约束转化为可计算的数值条件状态压缩用「一维索引 除法/取余」把两字节的双重循环压缩为一字节的单变量循环与 IP 地址 4 字节表示同源同理位运算功底进一步可演进为「高 4 位 低 4 位」的按位编码而仓库的 thinkings/bit.md 专题为这类技巧提供了系统的训练题集。当你再遇到「如何用最小空间表达一组有限状态」这类问题时不妨回想一下这道将帅题先数清状态数、算清所需比特数再用取余、除法和移位把坐标塞进最紧凑的容器里——这就是数据压缩最朴素也最实用的方法论。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考