1545. 找到第 N 个二进制字符串中的第 K 位
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定正整数 n 和 k，生成二进制字符串 Sn：S1 = '0'，Si = Si-1 + '1' + reverse(invert(Si-1))。目标是找到 Sn 的第 k 位。通过递归方法，若 k 在前半部分，递归查找；若在中间，返回 '1'；若在后半部分，映射到前半部分并翻转结果。时间和空间复杂度均为 O(n)。
🎯
关键要点
- 给定正整数 n 和 k，生成二进制字符串 Sn。
- S1 = '0'，Si = Si-1 + '1' + reverse(invert(Si-1))。
- 目标是找到 Sn 的第 k 位。
- 通过递归方法查找 k 位：如果 k 在前半部分，递归查找；如果在中间，返回 '1'；如果在后半部分，映射到前半部分并翻转结果。
- Si 的长度为 2^i - 1，且中间位总是 '1'。
- 时间和空间复杂度均为 O(n)。
- 递归步骤包括计算中间索引，如果 k 小于中间索引，则在前半部分查找；如果 k 大于中间索引，则在反转的后半部分查找并翻转结果。
- 通过递归和字符串构造的性质，避免生成整个字符串，提高效率。
➡️
