递归 – shelterofly

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

目标

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：

S1 = "0"
当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))

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

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

S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"

请你返回 Sn 的第 k 位字符，题目数据保证 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 <= 2^n - 1

思路

长度为 n 的二进制字符串的递推公式为 S_1 = 0, S_i = S_(i-1) + "1" + reverse(invert(S_(i-1)))，返回 S_n 的 第 k 位 字符，k 从 1 开始。

简单的做法是根据题意模拟，改写一下递推公式的下标，从 i = 0 开始，已知递推公式 s[0] = '0', s[i] = s[i - 1] + '1' + invertAndReverse(s[i - 1])，求 s[n - 1].charAt(k - 1)。

一个更优的做法是递归。s[i] 的长度 len[i] = 2 * len[i - 1] + 1 => len[i] + 1 = 2 (len[i - 1] + 1)，len[i] + 1 是一个首项为 2，公比为 2 的等比数列，第 i 项长度为 2^i - 1。可以将它划分成三部分，注意这里下标从 1 开始：

1 ~ 2^(i - 1) - 1 即 s[i - 1]，如果 k 在左半边，问题变为 s[i - 1] 的第 k 个字符
2^(i - 1) 值是 1，直接返回
2^(i - 1) + 1 ~ 2^i - 1 即 invertAndReverse(s[i - 1])，如果 k 在右半边，问题变为 invertAndReverse(s[i - 1]) 的第 k - 2^(i - 1) 个字符，也是 invert(s[i - 1]) 的第 2^(i - 1) - k + 2^(i - 1) = 2^i - k 个字符。

代码


/**
 * @date 2026-03-03 14:13
 */
public class FindKthBit1545 {

    public char findKthBit(int n, int k) {
        StringBuilder[] s = new StringBuilder[n];
        Arrays.setAll(s, x -> new StringBuilder());
        s[0].append('0');
        for (int i = 1; i < n; i++) {
            s[i].append(s[i - 1]).append('1').append(invertAndReverse(s[i - 1]));
        }
        return s[n - 1].charAt(k - 1);
    }

    public StringBuilder invertAndReverse(StringBuilder origin) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < origin.length(); i++) {
            if (origin.charAt(i) == '0') {
                res.append('1');
            } else {
                res.append('0');
            }
        }
        return res.reverse();
    }

}

性能

3307.找出第K个字符II

目标

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k 和一个整数数组 operations，其中 operations[i] 表示第 i 次操作的类型。

现在 Bob 将要求 Alice 按顺序执行所有操作：

如果 operations[i] == 0，将 word 的一份副本追加到它自身。
如果 operations[i] == 1，将 word 中的每个字符更改为英文字母表中的下一个字符来生成一个新字符串，并将其追加到原始的 word。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行所有操作后，返回 word 中第 k 个字符的值。

注意，在第二种类型的操作中，字符 'z' 可以变成 'a'。

示例 1:

输入：k = 5, operations = [0,0,0]
输出："a"
解释：
最初，word == "a"。Alice 按以下方式执行三次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "aa" 附加到 "aa"，word 变为 "aaaa"。
将 "aaaa" 附加到 "aaaa"，word 变为 "aaaaaaaa"。

示例 2:

输入：k = 10, operations = [0,1,0,1]
输出："b"
解释：
最初，word == "a"。Alice 按以下方式执行四次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "bb" 附加到 "aa"，word 变为 "aabb"。
将 "aabb" 附加到 "aabb"，word 变为 "aabbaabb"。
将 "bbccbbcc" 附加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。

说明：

1 <= k <= 10^14
1 <= operations.length <= 100
operations[i] 可以是 0 或 1。
输入保证在执行所有操作后，word 至少有 k 个字符。

思路

开始的时候有一个字符 a，根据操作数组 operations 执行以下操作：

当 operations[i] == 0 时，将现有的所有字母拼接到当前字符后面。
当 operations[i] == 1 时，将现有的所有字母替换为它在字母表中的下一个字母（z 的下一个字母为 a），拼接到当前字符后面。

返回执行所有操作之后的第 k 个字母。

计算 tail = ceil(log2(k)) 表示操作次数的上界，如果 k <= 1 << tail，说明在左半边无需操作，否则在右半边，需要操作，它是从左半边的第 k - (1 << tail) 个元素转移而来，需要根据 operations[tail] 来确定字母是否变化。按照这个逻辑递归，直到 tail < 0，返回字母 a。

代码


/**
 * @date 2025-07-04 9:19
 */
public class KthCharacter3307 {

    public char kthCharacter(long k, int[] operations) {
        return kthCharacter(k, operations, 63 - Long.numberOfLeadingZeros(k - 1));
    }

    public char kthCharacter(long k, int[] operations, int tail) {
        if (tail < 0) {
            return 'a';
        }
        long p = 1L << tail;
        if (k <= p) {
            return (char) ('a' + ((kthCharacter(k, operations, tail - 1) - 'a') % 26));
        }
        return (char) ('a' + (kthCharacter(k - p, operations, tail - 1) - 'a' + operations[tail]) % 26);
    }

}

性能

1367.二叉树中的链表

目标

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

示例 1：

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。

示例 2：

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true

示例 3：

输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：false
解释：二叉树中不存在一一对应链表的路径。

说明：

二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
链表包含的节点数目在 1 到 100 之间。
二叉树包含的节点数目在 1 到 2500 之间。

思路

判断二叉树中是否存在给定的路径 head，路径以链表的形式给出。

dfs 判断是否存在相同的路径。这道题的难点在于没有要求起点为 root，因此需要枚举所有节点为起点的情况。针对每一个起点我们最多检查 100 次，总共大概 2.5 * 10^5 次。

代码


/**
 * @date 2024-12-30 8:56
 */
public class IsSubPath1367 {

    public ListNode head;

    public boolean isSubPath(ListNode head, TreeNode root) {
        this.head = head;
        return dfs(root, head);
    }

    public boolean dfs(TreeNode cur, ListNode node) {
        if (node == null) {
            return true;
        }
        if (cur == null) {
            return false;
        }
        return cur.val == node.val && (dfs(cur.left, node.next) || dfs(cur.right, node.next))
                || node == head && (dfs(cur.left, head) || dfs(cur.right, head));
    }

}

性能

494.目标和

目标

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

说明：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

思路

有一个数组，可以在数组元素前加上正负号来组成表达式，问表达式等于target的数目。

如果当前元素为正则累加，否则相减，递归直到所有元素都已列入表达式，如果累加结果等于target则返回1，否则返回0。

//todo 改为递推，或记忆化搜索

代码

/**
 * @date 2024-06-30 20:07
 */
public class FindTargetSumWays494 {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 1, nums[0], target) + dfs(nums, 1, -nums[0], target);
    }

    public int dfs(int[] nums, int i, int res, int target) {
        if (i == nums.length) {
            return res - target == 0 ? 1 : 0;
        }
        return dfs(nums, i + 1, res + nums[i], target) + dfs(nums, i + 1, res - nums[i], target);
    }

}

性能

2786.访问数组中的位置使分数最大

目标

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你一开始在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

如果你当前在位置 i ，那么你可以移动到满足 i < j 的任意位置 j 。
对于你访问的位置 i ，你可以获得分数 nums[i] 。
如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的奇偶性不同，那么你将失去分数 x 。

请你返回你能得到的最大得分之和。

注意，你一开始的分数为 nums[0] 。

示例 1：

输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：

输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。

说明：

2 <= nums.length <= 10^5
1 <= nums[i], x <= 10^6

思路

给定一个数组 nums 与正整数 x，从下标 0 开始，允许从任意位置 i 开始向后访问位置 j，如果nums[i] 与 nums[j] 的奇偶性相同，则可以获得 nums[j] 分，否则获得 nums[j] - x 分。求能够获得的分数总和的最大值。

刚开始就想到要从后向前，自底向上动态规划，如果当前的奇偶性与与后面的奇偶性相同就累加，否则就将后面的值减去x。接着又想到并不是要每一个节点都要访问，如果节点没有访问奇偶性和谁比较呢？并且后面的得分取决于前一个元素的奇偶性，考虑到昨天的题子序列最大优雅度，觉得可能方向又错了。

于是就尝试贪心算法，从下标0开始，执行while循环，如果后面的元素奇偶性与之相同，直接累加。对于奇偶性不同的，我们可以考虑累加或者跳过。这样问题就变成了从这个新位置开始向后能获取的最大分数。注意新的位置奇偶性发生了变化。

这么一想问题又变成记忆化搜索了，于是就可以转换为递推/动态规划问题。

// todo 转换为动态规划的写法

代码

/**
 * @date 2024-06-14 8:43
 */
public class MaxScore2786 {

    public long maxScore(int[] nums, int x) {
        int n = nums.length;
        long[][] mem = new long[n + 1][2];
        for (int i = 0; i < mem.length; i++) {
            mem[i] = new long[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
        }
        long res = nums[0];
        int flag = nums[0] % 2;
        int i = 1;
        while (i < n && nums[i] % 2 == flag) {
            res += nums[i];
            i++;
        }
        res += Math.max(0, maxScore(nums, x, i, flag, mem));
        return res;
    }

    public long maxScore(int[] nums, int x, int start, int preFlag, long[][] mem) {
        int n = nums.length;
        if (start >= n) {
            return 0;
        }
        // 如果选择该节点
        int flag = nums[start] % 2;
        long select = nums[start];
        if (preFlag != flag) {
            select -= x;
        }
        int i = start + 1;
        while (i < n && nums[i] % 2 == flag) {
            select += nums[i];
            i++;
        }
        if (mem[i][flag] == Integer.MIN_VALUE) {
            mem[i][flag] = maxScore(nums, x, i, flag, mem);
        }
        select += Math.max(0, mem[i][flag]);
        // 如果跳过该节点
        if (mem[start + 1][preFlag] == Integer.MIN_VALUE) {
            mem[start + 1][preFlag] = maxScore(nums, x, start + 1, preFlag, mem);
        }
        return Math.max(select, mem[start + 1][preFlag]);
    }

}

性能

1379.找出克隆二叉树中的相同节点

目标

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。

其中，克隆树 cloned 是原始树 original 的一个副本。

请找出在树 cloned 中，与 target 相同的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回节点指针，其他语言返回节点本身）。

注意：你不能对两棵二叉树，以及 target 节点进行更改。只能返回对克隆树 cloned 中已有的节点的引用。

说明：

树中节点的数量范围为 [1, 10^4] 。
同一棵树中，没有值相同的节点。
target 节点是树 original 中的一个节点，并且不会是 null 。

进阶：如果树中允许出现值相同的节点，将如何解答？

思路

这道题挺简单的，这让我想起 100.相同的树 这道题，都是两棵树的同步遍历。

代码

/**
 * @date 2024-04-03 0:01
 */
public class GetTargetCopy1379 {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (original == null) {
            return null;
        } else if (target.equals(original)) {
            return cloned;
        } else {
            TreeNode res = getTargetCopy(original.left, cloned.left, target);
            if (res == null) {
                res = getTargetCopy(original.right, cloned.right, target);
            }
            return res;
        }
    }
}

2026 年 4 月
一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30