普通视图

发现新文章,点击刷新页面。
今天 — 2026年3月3日首页

每日一题-找出第 N 个二进制字符串中的第 K 位🟡

2026年3月3日 00:00

给你两个正整数 nk,二进制字符串  Sn 的形成规则如下:

  • S1 = "0"
  • i > 1 时,Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串联操作,reverse(x) 返回反转 x 后得到的字符串,而 invert(x) 则会翻转 x 中的每一位(0 变为 1,而 1 变为 0)。

例如,符合上述描述的序列的前 4 个字符串依次是:

  • S= "0"
  • S= "011"
  • S= "0111001"
  • S4 = "011100110110001"

请你返回  Snk 位字符 ,题目数据保证 k 一定在 Sn 长度范围以内。

 

示例 1:

输入:n = 3, k = 1
输出:"0"
解释:S3 为 "0111001",其第 1 位为 "0" 。

示例 2:

输入:n = 4, k = 11
输出:"1"
解释:S4 为 "011100110110001",其第 11 位为 "1" 。

示例 3:

输入:n = 1, k = 1
输出:"0"

示例 4:

输入:n = 2, k = 3
输出:"1"

 

提示:

  • 1 <= n <= 20
  • 1 <= k <= 2n - 1

AI辅助开发的基础概念

作者 牛奶
2026年3月2日 23:55

AI辅助开发的基础概念

这是系列第二篇,上一篇聊完"为什么学",我们来看看 AI 辅助开发到底帮我们做了什么,需要掌握哪些概念,以及怎么用好 AI。


上一篇文章,我们聊了为什么前端必须学AI。

简单说就是:AI不会取代前端,但它会重新定义前端。

既然要学,接下来一个很自然的问题就是:到底学什么?怎么学?

市面上关于AI的资料,多的让人头皮发麻。

一会儿有人说要学Prompt工程,一会儿有人说要学LangChain,一会儿又有人说要学向量数据库。一顿操作下来,还没开始就已经晕了。

这篇文章,我帮你把AI辅助开发这件事 全面梳理一遍。不求深,但求全。让你知道整个图景是什么样的,遇到什么该学什么。


原文地址

墨渊书肆/AI辅助开发的基础概念


先理解三个问题

在开始之前,我们先回答三个最基本的问题:

  1. AI能帮我做什么? — 知道它的能力边界
  2. 需要掌握哪些概念? — 理解背后的原理
  3. 怎么用好AI? — 具体的操作方法

这三个问题对应AI辅助开发的三个层次。接下来我们一层一层来讲。


第一层:AI能帮你做什么

这是最实在的东西——AI到底能帮我们干什么活。

1. 写代码

根据你的描述生成代码。

"帮我写一个React组件,功能是:用户可以选择日期范围,支持禁用特定日期,暗色模式适配"

AI能帮你写:

  • 完整的组件(React、Vue)
  • 工具函数
  • API接口
  • 样式代码(CSS、Tailwind)
  • TypeScript类型定义
  • 测试用例

2. 读代码

帮你理解你不懂的代码。

"这个组件的数据流是怎么走的?为什么要用useMemo?"

AI能帮你:

  • 解释代码逻辑
  • 梳理复杂代码
  • 找出潜在问题
  • 理解项目结构

3. 查文档

以前遇到问题,你先去 Google 搜,然后看 Stack Overflow,最后才去翻文档。

现在直接问AI:

"Next.js 15怎么做密码重置?"
"Vercel AI SDK怎么实现流式响应?"

AI直接从文档里给你准确的答案。

4. 修Bug

遇到报错了,直接问AI:

"这个报错是什么意思?TypeError: Cannot read properties of undefined (reading 'map')"

AI会告诉你:错误原因是什么、最可能出在哪个地方、怎么修复。

5. 代码Review

让AI帮你审查代码:

"请审查以下代码,指出:1. 潜在安全问题 2. 性能问题 3. 代码规范问题"

它会从多个角度帮你分析一遍。

6. 重构代码

觉得某段代码写得烂,但不知道怎么改?

"请帮我重构以下代码,要求:1. 使用TypeScript类型 2. 提取可复用逻辑 3. 增加错误处理"

AI会给一个全新的版本,你可以参考它的思路。

7. 写测试

写测试很枯燥,但很重要。

"请为以下函数编写单元测试,覆盖:正常情况、空输入、错误输入"

AI生成测试代码,你再根据需要调整。

8. 帮你想名字

我经常让AI帮我给变量、函数起名字。

"我有一个函数,接受用户ID,返回用户名、邮箱、头像、最后登录时间。请帮我想一个合适的函数名"

AI会给三四个建议,通常都比较规范,符合命名习惯。


第二层:需要掌握哪些概念

知道AI能帮你做什么了,接下来你需要理解一些核心概念。这样你才能更好地和AI配合。

1. 大模型(LLM)

LLM,Large Language Model,大语言模型。

你可以把大模型理解成一个见过海量代码的超级程序员。它看过互联网上几乎所有的开源代码、文档、教程,所以它知道你想要什么。

GPTClaudeDeepSeek通义——这些都是大模型。

它不是真的"智能",而是见过太多了,知道概率最高的答案是什么

作为前端开发者,你不需要会训练模型,你只需要知道怎么调用它们

2. Token

Token 是 AI 处理信息的基本单位

简单理解:AI不是按"字"或"词"来处理文字的,而是按 Token。一个Token可能是半个单词、一个单词、或者一个标点符号。

为什么这个概念重要?因为:

  • API按Token收费:输入和输出都算 Token
  • 上下文长度限制:你给 AI 的上下文不能超过它能处理的Token数

举个例子:Claude 3.5 支持 200K Token 的上下文,意味着你可以一次性把整个项目的代码都丢给它(但这样做很贵,而且AI可能会"忘记"中间部分)。

3. Agent

Agent(智能体)是AI领域最重要的概念之一。

你可以把Agent理解成一个能自己执行任务的AI。不像普通的聊天AI只能"问一句答一句",Agent可以:

  • 自己规划步骤
  • 自己调用工具
  • 自己检查结果
  • 自主完成复杂任务

这就是为什么很多人说"AI不是替代程序员,而是替代不会用AI的程序员"——因为Agent已经可以自主完成很多开发任务了。

4. MCP(Model Context Protocol)

MCP是这两年AI辅助开发领域最重要的新东西。

你可以把它理解成AI的"USB接口"

以前AI只能跟你聊天,它不知道你电脑里有什么、你的项目是什么样子。MCP出现后,AI可以:

  • 读取你电脑上的文件
  • 执行终端命令
  • 访问你的代码仓库
  • 调用各种第三方服务

这就是为什么现在的AI编程工具突然变得超级强大——因为它们不只是"聊天"了,它们真的能"干活"了。

5. Prompt

Prompt就是你给AI说的话。「帮我写个登录功能」就是一个Prompt。

Prompt不是越长越好,而是越精确越好

好的Prompt应该包含:

  • 上下文:你用的技术栈是什么
  • 具体需求:你想要什么功能
  • 约束条件:有什么特殊要求
  • 期望结果:你想要的输出格式

6. 幻觉

AI有时候会"编故事"——生成一些看似正确但实际上是错误的内容。这就是所谓的"幻觉"

为什么会产生幻觉?因为AI本质上是在"预测"下一个最可能的词,而不是真的"理解"事实。

这意味着:

  • AI给出的答案不一定是对的
  • 你要有能力判断答案对不对
  • 重要的代码要自己验证

第三层:怎么用好AI辅助开发

知道能做什么、也理解概念了,接下来就是具体怎么用。

1. 搞清楚什么时候用什么模式

大部分AI编程工具都有两种模式:

对话模式(Chat):你问一句,它答一句。

我一般用来:

  • 问具体问题:「这个报错是什么意思?」
  • 查知识点:「PostgreSQL的索引类型有哪些?」
  • 解释代码:「这个函数做了什么?」

任务模式(Agent):你描述一个任务,它自己去分析和执行。

我一般用来:

  • 帮我重构整个模块:「把这个登录从JWT改成Session」
  • 帮我修bug:「登录一直返回401,帮我看看是什么原因」
  • 帮我实现一个功能:「帮我实现用户注册功能,包含表单验证、数据库存储」

简单说:小问题用对话,大任务用Agent。

2. 喂上下文是有技巧的

AI最强的地方是它能理解你的整个项目。但有时候它也会犯傻——给你一些牛头不对马嘴的回答。

这时候,你得学会喂上下文

我犯过的错误:

「怎么优化这个查询?」

AI回了半天,什么加索引、分页、缓存讲了一套,我根本不知道它说的是什么,因为我连我的表结构都没告诉它。

后来我学乖了:

「我的Prisma查询是这样的:prisma const users = await prisma.user.findMany() 数据量大概10万条,现在查询要3秒,请问怎么优化?」

这次AI直接告诉我:1. 加索引 2. 用select只查需要的字段 3. 考虑分页。

我的习惯是:至少告诉AI三件事

  1. 技术栈:我用的技术是什么(Next.js + Prisma + PostgreSQL)
  2. 当前代码:现在代码长什么样(贴上代码)
  3. 问题:遇到了什么问题(查询慢、报错、不知道怎么做)

3. 选中代码让AI帮你改

选中一段代码,让AI帮你修改。这是一个核心技巧。

比如我选中一个函数,这样用:

「请帮我添加错误处理和类型定义」

AI直接在原代码基础上帮我改好了,我只需要确认一下就行。

比让它生成一段新代码然后我再替换,效率高很多。

再举几个我常用的场景:

  • 选中一段面条式代码:「请帮我重构这段代码」
  • 选中一个API接口:「请帮我添加参数校验」
  • 选中一个组件:「请把这个组件改成响应式」

4. 用@引用代替复制粘贴

大部分AI编程工具支持用@符号引用特定内容:

  • @File :引用当前打开的文件
  • @components/UserCard.tsx :直接引用某个文件
  • @Folder :引用整个文件夹
  • @Docs :引用官方文档
  • @Search :搜索项目内的代码

最常用的场景:

@components/UserCard.tsx 请帮我在这个组件里添加一个编辑用户信息的功能

AI直接读取文件内容,在正确的位置帮我添加代码。

@Docs 请帮我查一下Next.js的metadata怎么用来做SEO

AI直接读官方文档,给我准确的答案。

用@引用比复制粘贴代码更省Token,而且AI能更准确地理解你的需求。

5. 一次性把需求说清楚

让AI一次性完成所有需求,别分开问:

  • ❌ 「先帮我写HTML」「再帮我写样式」「再加个交互」
  • ✅ 「帮我写一个登录组件,包含表单验证、错误提示、暗色模式支持」

一次说清楚,AI能更好地理解你的整体需求,生成的代码也更连贯。

6. 设置好项目规范

我在每个项目都会设置规范文件。

设置好之后,AI每次生成代码都会自动遵循这些规范。

举个例子:我不用每次都说「API错误要返回success和error字段」,AI自己就知道。

规范内容包括:

  • 技术栈和版本
  • 目录结构
  • 代码规范(命名、格式)
  • 常用的工具函数

7. 积累自己的Prompt模板

AI 的输出质量很大程度上取决于你的 Prompt,好的 Prompt 能让AI 生成更准确、更符合你需求的代码。

在平时的开发中,可以把一些常用的场景总结成模板,方便后续快速调用。


工作流程:AI怎么融入日常开发

知道有什么工具了,接下来我们看看AI是怎么融入日常开发工作的。

我总结了一个我自己常用的工作流程:

1. 需求分析阶段

  • 解释需求文档里的技术术语
  • 给出技术选型的建议
  • 评估实现难度和时间

2. 编码实现阶段

  • 根据描述生成代码
  • 解释你不熟悉的API
  • 帮你写测试用例
  • 优化现有代码

3. 代码审查阶段

  • 检查代码安全性
  • 找出潜在性能问题
  • 审查代码规范
  • 解释复杂逻辑

4. Bug修复阶段

  • 分析报错信息
  • 定位问题原因
  • 给出修复建议

5. 文档输出阶段

  • 从代码生成注释
  • 生成README文档
  • 写API文档

写在最后

这篇文章帮你把AI辅助开发这件事,从概念到工具,从流程到趋势,全面梳理了一遍。

你不需要记住所有细节,你只需要知道:

  1. AI能帮你做什么:写代码、读代码、查文档、修Bug、代码Review、重构、写测试
  2. 需要理解什么概念:大模型、Token、Agent、MCP、Prompt、幻觉
  3. 怎么用好AI:喂上下文、选对模式、用@引用、一次性说清楚需求

知道了能做什么、懂了概念,剩下的就是多练习。

AI辅助开发不是玄学,就是一个工具。用多了,你会发现:会问问题的人,效率比不会问的人高十倍。


篇预告

下一篇,我会讲讲《2026年大模型怎么选?前端人实用对比》。

市面上有那么多大模型,GPT、Claude、DeepSeek、通义千问......到底该用哪个?不同的场景该怎么选?怎么才能低成本使用?

我会从实际开发的角度,给你一个清晰的选型建议。

感兴趣的话,下一篇见。

从递归到 O(1) 数学公式(Python/Java/C++/C/Go/JS/Rust)

作者 endlesscheng
2026年2月26日 08:55

方法一:递归 / 迭代

我们需要确定第 $k$ 个字符位于 $S_n$ 的左半、正中间还是右半。为此,首先要知道 $S_n$ 的长度。

用 $|s|$ 表示字符串 $s$ 的长度。根据题意,$|S_1| = 1$,$|S_n| = 2|S_{n-1}| + 1$,所以有

$$
|S_n| + 1 = 2(|S_{n-1}| + 1)
$$

所以 ${|S_n| + 1}$ 是个首项为 $2$,公比为 $2$ 的等比数列,得

$$
|S_n| = 2^n - 1
$$

所以 $|S_{n-1}| = 2^{n-1} - 1$,这说明 $S_n$ 的左半是第 $1$ 个字符到第 $2^{n-1}-1$ 个字符,正中间是第 $2^{n-1}$ 个字符,右半是第 $2^{n-1} + 1$ 个字符到第 $2^n-1$ 个字符。

分类讨论:

  • 如果 $k < 2^{n-1}$,那么第 $k$ 个字符位于 $S_n$ 的左半,问题变成 $S_{n-1}$ 的第 $k$ 个字符。这可以递归解决。
  • 如果 $k > 2^{n-1}$,那么第 $k$ 个字符位于 $S_n$ 的右半,问题变成 $S_{n-1}$ 反转后的第 $k-2^{n-1}$ 个字符,即反转前的第 $2^{n-1}-(k-2^{n-1}) = 2^n-k$ 个字符(比如 $k=2^n-1$ 对应反转前的第 $1$ 个字符)。这个字符再翻转,即为 $S_n$ 的第 $k$ 个字符。这也可以递归解决。

递归边界:

  • 如果 $n=1$,那么返回 $S_1$ 唯一的字符 $\texttt{0}$。
  • 如果 $k = 2^{n-1}$,那么返回 $S_n$ 正中间的字符 $\texttt{1}$。

递归写法

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return '0'
        if k == 1 << (n - 1):
            return '1'
        if k < 1 << (n - 1):
            return self.findKthBit(n - 1, k)
        res = self.findKthBit(n - 1, (1 << n) - k)
        return '0' if res == '1' else '1'
class Solution {
    public char findKthBit(int n, int k) {
        if (n == 1) {
            return '0';
        }
        if (k == 1 << (n - 1)) {
            return '1';
        }
        if (k < 1 << (n - 1)) {
            return findKthBit(n - 1, k);
        }
        char res = findKthBit(n - 1, (1 << n) - k);
        return (char) (res ^ 1);
    }
}
class Solution {
public:
    char findKthBit(int n, int k) {
        if (n == 1) {
            return '0';
        }
        if (k == 1 << (n - 1)) {
            return '1';
        }
        if (k < 1 << (n - 1)) {
            return findKthBit(n - 1, k);
        }
        return findKthBit(n - 1, (1 << n) - k) ^ 1;
    }
};
char findKthBit(int n, int k) {
    if (n == 1) {
        return '0';
    }
    if (k == 1 << (n - 1)) {
        return '1';
    }
    if (k < 1 << (n - 1)) {
        return findKthBit(n - 1, k);
    }
    return findKthBit(n - 1, (1 << n) - k) ^ 1;
}
func findKthBit(n, k int) byte {
if n == 1 {
return '0'
}
if k == 1<<(n-1) {
return '1'
}
if k < 1<<(n-1) {
return findKthBit(n-1, k)
}
return findKthBit(n-1, 1<<n-k) ^ 1
}
var findKthBit = function(n, k) {
    if (n === 1) {
        return '0';
    }
    if (k === 1 << (n - 1)) {
        return '1';
    }
    if (k < 1 << (n - 1)) {
        return findKthBit(n - 1, k);
    }
    return findKthBit(n - 1, (1 << n) - k) === '1' ? '0' : '1';
};
impl Solution {
    pub fn find_kth_bit(n: i32, k: i32) -> char {
        if n == 1 {
            return '0';
        }
        if k == 1 << (n - 1) {
            return '1';
        }
        if k < 1 << (n - 1) {
            return Self::find_kth_bit(n - 1, k);
        }
        (Self::find_kth_bit(n - 1, (1 << n) - k) as u8 ^ 1) as _
    }
}

迭代写法

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        rev = 0  # 翻转次数的奇偶性
        while True:
            if n == 1:
                return '1' if rev else '0'
            if k == 1 << (n - 1):
                return '0' if rev else '1'
            if k > 1 << (n - 1):
                k = (1 << n) - k
                rev ^= 1
            n -= 1
class Solution {
    public char findKthBit(int n, int k) {
        int rev = 0; // 翻转次数的奇偶性
        while (true) {
            if (n == 1) {
                return (char) ('0' ^ rev);
            }
            if (k == 1 << (n - 1)) {
                return (char) ('1' ^ rev);
            }
            if (k > 1 << (n - 1)) {
                k = (1 << n) - k;
                rev ^= 1;
            }
            n--;
        }
    }
}
class Solution {
public:
    char findKthBit(int n, int k) {
        int rev = 0; // 翻转次数的奇偶性
        while (true) {
            if (n == 1) {
                return '0' ^ rev;
            }
            if (k == 1 << (n - 1)) {
                return '1' ^ rev;
            }
            if (k > 1 << (n - 1)) {
                k = (1 << n) - k;
                rev ^= 1;
            }
            n--;
        }
    }
};
char findKthBit(int n, int k) {
    int rev = 0; // 翻转次数的奇偶性
    while (true) {
        if (n == 1) {
            return '0' ^ rev;
        }
        if (k == 1 << (n - 1)) {
            return '1' ^ rev;
        }
        if (k > 1 << (n - 1)) {
            k = (1 << n) - k;
            rev ^= 1;
        }
        n--;
    }
}
func findKthBit(n, k int) byte {
rev := byte(0) // 翻转次数的奇偶性
for {
if n == 1 {
return '0' ^ rev
}
if k == 1<<(n-1) {
return '1' ^ rev
}
if k > 1<<(n-1) {
k = 1<<n - k
rev ^= 1
}
n--
}
}
var findKthBit = function(n, k) {
    let rev = 0; // 翻转次数的奇偶性
    while (true) {
        if (n === 1) {
            return rev ? '1' : '0';
        }
        if (k === 1 << (n - 1)) {
            return rev ? '0' : '1';
        }
        if (k > 1 << (n - 1)) {
            k = (1 << n) - k;
            rev ^= 1;
        }
        n--;
    }
};
impl Solution {
    pub fn find_kth_bit(mut n: i32, mut k: i32) -> char {
        let mut rev = 0; // 翻转次数的奇偶性
        loop {
            if n == 1 {
                return (b'0' ^ rev) as _;
            }
            if k == 1 << (n - 1) {
                return (b'1' ^ rev) as _;
            }
            if k > 1 << (n - 1) {
                k = (1 << n) - k;
                rev ^= 1;
            }
            n -= 1;
        }
    }
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(n)$。
  • 空间复杂度:$\mathcal{O}(1)$。

方法二:数学公式

奇数位

$S_4 = \texttt{011100110110001}$,只看奇数位(下标从 $1$ 开始)的字符,是 $\texttt{01010101}$,这是一个 $\texttt{01}$ 交替序列,为什么?

只看奇数位:

  • $S_1 = \texttt{0}$。
  • $S_2$ 把 $\texttt{0}$ 反转再翻转,得到 $\texttt{1}$,拼起来是 $\texttt{01}$。
  • $S_3$ 把 $\texttt{01}$ 反转再翻转,得到 $\texttt{01}$,拼起来是 $\texttt{0101}$。
  • $S_4$ 把 $\texttt{0101}$ 反转再翻转,得到 $\texttt{0101}$,拼起来是 $\texttt{01010101}$。

一般地,由于 $\texttt{01}$ 交替序列反转再翻转,结果不变,所以从 $S_{i-1}$ 到 $S_i\ (i\ge 3)$,其中奇数位相当于复制了一份自身,拼在了自身后面,得到的仍然是 $\texttt{01}$ 交替序列。

所以,当 $k$ 是奇数时,可以立刻得出答案:

  • 设 $k' = \dfrac{k-1}{2}$。这会把 $k=1,3,5,7,\ldots$ 变成 $k'=0,1,2,3,\ldots$
  • 如果 $k'$ 是偶数,那么答案是 $\texttt{0}$。
  • 如果 $k'$ 是奇数,那么答案是 $\texttt{1}$。
  • 一般地,答案为 $k'\bmod 2$ 对应的字符。

偶数位

奇数位的字符,都发源于 $S_1 = \texttt{0}$。

偶数位的字符呢?都发源于 $S_i\ (i\ge 2)$ 正中间的那个 $\texttt{1}$,即位置为 $2,4,8,16,\ldots$ 的字符 $\texttt{1}$。

根据方法一的结论,$S_{n-1}$ 的第 $k$ 个字符,反转后,是 $S_n$ 的第 $2^n-k$ 个字符。

$2^n-k$ 有什么性质?

比如二进制 $10000 - 100 = 1100$,去掉末尾的两个 $0$,相当于 $100 - 1 = 11$,结果最低位一定是 $1$,所以 $100$ 和 $1100$ 的尾零个数相同。一般地,$k$ 和 $2^n-k$ 的尾零个数是相同的,这是个不变量!我们可以根据 $k$ 的尾零个数,找到 $k$ 发源于哪个 $S_i$ 正中间的 $\texttt{1}$。

以 $S_2$ 的中间字符(第 $2$ 个字符)为例:

  • 我们把 $S_2$ 的第 $2$ 个字符反转到了 $S_3$ 的第 $8-2=6$ 个字符。把 $\texttt{1}$ 反转再翻转,得到 $\texttt{0}$,拼起来是 $\texttt{10}$。
  • 我们把 $S_3$ 的第 $2,6$ 个字符反转到了 $S_4$ 的第 $14,10$ 个字符。把 $\texttt{10}$ 反转再翻转,得到 $\texttt{10}$,拼起来是 $\texttt{1010}$。注意 $2,6,10,14$ 的二进制尾零个数都是 $1$,且这些位置上的字符拼起来是一个 $\texttt{10}$ 交替序列。

一般地,设 $t$ 为 $k$ 去掉尾零后的值,即 $k = t\cdot 2^x$ 且 $t$ 是奇数。比如 $k=2,6,10,14,\ldots$ 对应着 $t=1,3,5,7,\ldots$

  • 设 $t' = \dfrac{t-1}{2}$。这会把 $t=1,3,5,7,\ldots$ 变成 $t'=0,1,2,3,\ldots$
  • 如果 $t'$ 是偶数,那么答案是 $\texttt{1}$。
  • 如果 $t'$ 是奇数,那么答案是 $\texttt{0}$。
  • 一般地,答案为 $1 - t'\bmod 2$ 对应的字符。

如何去掉 $k$ 的尾零?把 $k$ 除以其 $\text{lowbit}$ 即可。关于 $\text{lowbit}$ 的原理,请看 从集合论到位运算,常见位运算技巧分类总结

class Solution:
    def findKthBit(self, _, k: int) -> str:
        if k % 2:
            return str(k // 2 % 2)
        k //= k & -k  # 去掉 k 的尾零
        return str(1 - k // 2 % 2)
class Solution {
    public char findKthBit(int n, int k) {
        if (k % 2 > 0) {
            return (char) ('0' + k / 2 % 2);
        }
        k /= k & -k; // 去掉 k 的尾零
        return (char) ('1' - k / 2 % 2);
    }
}
class Solution {
public:
    char findKthBit(int, int k) {
        if (k % 2) {
            return '0' + k / 2 % 2;
        }
        k /= k & -k; // 去掉 k 的尾零
        return '1' - k / 2 % 2;
    }
};
char findKthBit(int, int k) {
    if (k % 2) {
        return '0' + k / 2 % 2;
    }
    k /= k & -k; // 去掉 k 的尾零
    return '1' - k / 2 % 2;
}
func findKthBit(_, k int) byte {
if k%2 > 0 {
return '0' + byte(k/2%2)
}
k /= k & -k // 去掉 k 的尾零
return '1' - byte(k/2%2)
}
var findKthBit = function(_, k) {
    if (k % 2) {
        return (k - 1) / 2 % 2 ? '1' : '0';
    }
    k /= k & -k; // 去掉 k 的尾零
    return (k - 1) / 2 % 2 ? '0' : '1';
};
impl Solution {
    pub fn find_kth_bit(_: i32, mut k: i32) -> char {
        if k % 2 > 0 {
            return (b'0' + k as u8 / 2 % 2) as _;
        }
        k /= k & -k; // 去掉 k 的尾零
        (b'1' - k as u8 / 2 % 2) as _
    }
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(1)$。
  • 空间复杂度:$\mathcal{O}(1)$。

相似题目

见下面回溯题单的「五、其他递归/分治」。

分类题单

如何科学刷题?

  1. 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针/分组循环)
  2. 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
  3. 单调栈(基础/矩形面积/贡献法/最小字典序)
  4. 网格图(DFS/BFS/综合应用)
  5. 位运算(基础/性质/拆位/试填/恒等式/思维)
  6. 图论算法(DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流)
  7. 动态规划(入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
  8. 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
  9. 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
  10. 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
  11. 链表、树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA)
  12. 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)

我的题解精选(已分类)

欢迎关注 B站@灵茶山艾府

找出第 N 个二进制字符串中的第 K 位

2020年8月20日 20:51

方法一:递归

观察二进制字符串 $S_n$,可以发现,当 $n>1$ 时,$S_n$ 是在 $S_{n-1}$ 的基础上形成的。用 $\text{len}n$ 表示 $S_n$ 的长度,则 $S_n$ 的前 $\text{len}{n-1}$ 个字符与 $S_{n-1}$ 相同。还可以发现,当 $n>1$ 时,$\text{len}n=\text{len}{n-1} \times 2 + 1$,根据 $\text{len}_1=1$ 可知 $\text{len}_n=2^n-1$。

由于 $S_1=``0"$,且对于任意 $n \ge 1$,$S_n$ 的第 $1$ 位字符也一定是 $0'$,因此当 $k=1$ 时,直接返回字符 $0'$。

当 $n>1$ 时,$S_n$ 的长度是 $2^n-1$。$S_n$ 可以分成三个部分,左边 $2^{n-1}-1$ 个字符是 $S_{n-1}$,中间 $1$ 个字符是 $1'$,右边 $2^{n-1}-1$ 个字符是 $S_{n-1}$ 翻转与反转之后的结果。中间的字符 $1'$ 是 $S_n$ 的第 $2^{n-1}$ 位字符,因此如果 $k=2^{n-1}$,直接返回字符 $`1'$。

当 $k \ne 2^{n-1}$ 时,考虑以下两种情况:

  • 如果 $k<2^{n-1}$,则第 $k$ 位字符在 $S_n$ 的前半部分,即第 $k$ 位字符在 $S_{n-1}$ 中,因此在 $S_{n-1}$ 中寻找第 $k$ 位字符;

  • 如果 $k>2^{n-1}$,则第 $k$ 位字符在 $S_n$ 的后半部分,由于后半部分为前半部分进行翻转与反转之后的结果,因此在前半部分寻找第 $2^n-k$ 位字符,将其反转之后即为 $S_n$ 的第 $k$ 位字符。

上述过程可以通过递归实现。

###Java

class Solution {
    public char findKthBit(int n, int k) {
        if (k == 1) {
            return '0';
        }
        int mid = 1 << (n - 1);
        if (k == mid) {
            return '1';
        } else if (k < mid) {
            return findKthBit(n - 1, k);
        } else {
            k = mid * 2 - k;
            return invert(findKthBit(n - 1, k));
        }
    }

    public char invert(char bit) {
        return (char) ('0' + '1' - bit);
    }
}

###JavaScript

const invert = (bit) => bit === '0' ? '1' : '0';

var findKthBit = function(n, k) {
    if (k == 1) {
        return '0';
    }
    const mid = 1 << (n - 1);
    if (k == mid) {
        return '1';
    } else if (k < mid) {
        return findKthBit(n - 1, k);
    } else {
        k = mid * 2 - k;
        return invert(findKthBit(n - 1, k));
    }
};

###C++

class Solution {
public:
    char findKthBit(int n, int k) {
        if (k == 1) {
            return '0';
        }
        int mid = 1 << (n - 1);
        if (k == mid) {
            return '1';
        } else if (k < mid) {
            return findKthBit(n - 1, k);
        } else {
            k = mid * 2 - k;
            return invert(findKthBit(n - 1, k));
        }
    }

    char invert(char bit) {
        return (char) ('0' + '1' - bit);
    }
};

###Python

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if k == 1:
            return "0"
        
        mid = 1 << (n - 1)
        if k == mid:
            return "1"
        elif k < mid:
            return self.findKthBit(n - 1, k)
        else:
            k = mid * 2 - k
            return "0" if self.findKthBit(n - 1, k) == "1" else "1"

###C#

public class Solution {
    public char FindKthBit(int n, int k) {
        if (k == 1) {
            return '0';
        }
        int mid = 1 << (n - 1);
        if (k == mid) {
            return '1';
        } else if (k < mid) {
            return FindKthBit(n - 1, k);
        } else {
            k = mid * 2 - k;
            return Invert(FindKthBit(n - 1, k));
        }
    }

    private char Invert(char bit) {
        return (char)('0' + '1' - bit);
    }
}

###Go

func findKthBit(n int, k int) byte {
    if k == 1 {
        return '0'
    }
    mid := 1 << (n - 1)
    if k == mid {
        return '1'
    } else if k < mid {
        return findKthBit(n - 1, k)
    } else {
        k = mid*2 - k
        return invert(findKthBit(n - 1, k))
    }
}

func invert(bit byte) byte {
    if bit == '0' {
        return '1'
    }
    return '0'
}

###C

char invert(char bit) {
    return '0' + '1' - bit;
}

char findKthBit(int n, int k) {
    if (k == 1) {
        return '0';
    }
    int mid = 1 << (n - 1);
    if (k == mid) {
        return '1';
    } else if (k < mid) {
        return findKthBit(n - 1, k);
    } else {
        k = mid * 2 - k;
        return invert(findKthBit(n - 1, k));
    }
}

###TypeScript

function findKthBit(n: number, k: number): string {
    if (k === 1) {
        return '0';
    }
    const mid = 1 << (n - 1);
    if (k === mid) {
        return '1';
    } else if (k < mid) {
        return findKthBit(n - 1, k);
    } else {
        k = mid * 2 - k;
        return invert(findKthBit(n - 1, k));
    }
}

function invert(bit: string): string {
    return bit === '0' ? '1' : '0';
}

###Rust

impl Solution {
    pub fn find_kth_bit(n: i32, k: i32) -> char {
        Self::find_kth_bit_recursive(n, k)
    }
    
    fn find_kth_bit_recursive(n: i32, k: i32) -> char {
        if k == 1 {
            return '0';
        }
        let mid = 1 << (n - 1);
        if k == mid {
            return '1';
        } else if k < mid {
            return Self::find_kth_bit_recursive(n - 1, k);
        } else {
            let new_k = mid * 2 - k;
            return Self::invert(Self::find_kth_bit_recursive(n - 1, new_k));
        }
    }
    
    fn invert(bit: char) -> char {
        if bit == '0' {
            '1'
        } else {
            '0'
        }
    }
}

复杂度分析

  • 时间复杂度:$O(n)$。字符串 $S_n$ 的长度为 $2^n-1$,每次递归调用可以将查找范围缩小一半,因此时间复杂度为 $O(\log 2^n)=O(n)$。

  • 空间复杂度:$O(n)$。空间复杂度主要取决于递归调用产生的栈空间,递归调用层数不会超过 $n$。

递归——双百(logn)

作者 233999
2020年8月9日 12:13

解题思路

递归 将时间复杂度降到logn
力扣.png

代码

###cpp

class Solution {
private:
    char ch_not(char ch) {
        if(ch == '0') { return '1'; }
        else          { return '0'; }
    }
public:
    char findKthBit(int n, int k) {
        if(n == 1) { return '0'; }
        int mid = (1<<(n-1));
        if(k == mid) { return '1'; }
        if(k < mid) { return findKthBit(n-1, k); }
        return ch_not(findKthBit(n-1, (1<<n) - k)); 
    }
};

AI需求驱动,半导体上市公司2025年营收增长

2026年3月3日 07:30
近期,A股半导体板块上市公司密集披露2025年度业绩快报。数据显示,截至3月2日,按申万行业分类的173家半导体公司中,已有115家披露业绩快报。其中,101家实现营业总收入的同比增长。记者注意到,寒武纪、佰维存储、拓荆科技等公司营收增长幅度居前,反映出当前市场的算存需求景气与前道设备的强劲增长。有分析人士认为,当前全球科技巨头的资本开支正处于一个高强度、高增长的周期。AI算力需求仍为增长主线,先进逻辑与存储扩产上量,进而带动刻蚀、薄膜等核心制造设备需求上涨。 (上证报)

3月A股市场资源品行情可期

2026年3月3日 07:28
近期,受国际地缘冲突升级、国内春季开工提速以及PPI回升预期等多重因素影响,A股资源品行业持续走强。分析人士认为,3月资源品涨价主线仍具延续性,顺周期品种的配置价值凸显,可聚焦有色金属、石油石化等方向。在地缘局势催化与政策预期共振下,资源品结构性机会有望持续。(中证网)

派拉蒙天舞赢得WBD竞标

2026年3月3日 07:20
在奈飞撤回其竞标后,派拉蒙天空之舞传媒以约1110亿美元的交易额成功收购华纳兄弟探索公司,这将使埃里森家族得以整合各大制片厂、流媒体平台和有线电视网络,目前尚待批准。(新浪财经)

MiniMax:2月公司ARR(年度经常性收入)超过1.5亿美元

2026年3月3日 07:15
36氪获悉,3月2日晚,MiniMax 创始人、CEO 闫俊杰在电话会上透露,2026年2月公司 ARR(年度经常性收入)已超过1.5亿美元,面向企业客户和个人开发者的开放平台产品,2026年2月新注册用户数已经达到2025年12月的4倍以上。业绩报显示,MiniMax 2025年实现总收入7903.8万美元,同比增长158.9%。其中,AI 原生产品收入5307.5万美元,同比增长143.4%。

格力电器回应“未来每年将不再派发股息”传闻

2026年3月3日 07:13
针对近期网络上传闻称“格力电器未来每年将不再派发股息”,格力电器最新回应称,公司重视投资者回报,积极通过现金分红或股份回购等方式回报投资者,分红及回购金额均位于A股上市公司前列。公司未来分红安排将结合战略规划、经营业绩与资金状况综合研究确定。(证券时报)

华为首次在海外展出全液冷AI超节点

2026年3月3日 07:12
在MWC 2026巴塞罗那期间,华为首次在海外展出了全液冷AI超节点Atlas 950 SuperPoD,以及业界首款通算超节点TaiShan 950 SuperPoD。超节点是计算节点通过高速互联协议组成更大内存空间的计算系统。2025年3月,华为已推出了Atlas 900超节点,满配支持384卡。基于灵衢 1.0 的Atlas 900超节点自2025年3月开始交付,至今已商用部署数百套,涵盖互联网、电信、制造等多个行业。(财联社)

英伟达将向Coherent投资20亿美元,就光学技术达成合作

2026年3月3日 07:10
英伟达3月2日宣布同Coherent达成多年合作协议,旨在推进先进光学技术发展,包括产能和研发,从而助力下一代人工智能基础设施建设。这项非独家协议包括英伟达数十亿美元采购承诺,以及未来先进激光和光网络产品的使用权和产能。此外,英伟达还将向Coherent投资20亿美元,支持其研发、未来产能和运营,助力Coherent在美国本土拓展制造能力。(界面)

美关税诉讼案重回贸易法庭,退税程序或加速推进

2026年3月3日 07:06
美国一家上诉法院当地时间3月2日将此前导致美国总统特朗普大规模关税被裁定无效的多起诉讼发回至美国国际贸易法院。而美国国际贸易法院有权裁决退还进口商缴纳的相关税款。进口商此前已请求国际贸易法院,一旦案件重新归其管辖,应命令特朗普政府立即着手制定退税程序。 (CCTV国际时讯)

美股三大指数收盘涨跌不一,大型科技股多数上涨

2026年3月3日 07:00
36氪获悉,3月2日收盘,美股三大指数涨跌不一,道指跌0.15%,标普500指数涨0.04%,纳指涨0.36%。大型科技股多数上涨,英伟达涨近3%,微软涨超1%,苹果、特斯拉、奈飞、Meta小幅上涨;谷歌跌超1%,英特尔、亚马逊小幅下跌。热门中概股普跌,小鹏汽车、蔚来跌超3%,哔哩哔哩跌超2%,阿里巴巴、爱奇艺跌超1%,拼多多、京东、理想汽车小幅下跌。
❌
❌