标签： 集合

1930.长度为3的不同回文子序列

目标

给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文 是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列。

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)

示例 2：

输入：s = "adc"
输出：0
解释："adc" 不存在长度为 3 的回文子序列。

示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)

说明：

  • 3 <= s.length <= 10^5
  • s 仅由小写英文字母组成

思路

求长度为 3 的不同回文子序列个数。

枚举中间元素，同时枚举 a - z 作为左右两侧的字母，判断是否前后都存在。

对字母计数，在枚举过程中记录前面出现字母的次数，结合总次数可以快速判断后面是否存在相同的字母。注意，如果前面出现的字母与枚举的中间字母相同需要将次数减 1。

代码


/**
 * @date 2025-11-21 8:44
 */
public class CountPalindromicSubsequence1930 {

    public int countPalindromicSubsequence_v1(String s) {
        int[] total = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            total[c - 'a']++;
        }
        boolean[][] visited = new boolean[26][26];
        int[] prefix = new int[26];
        int res = 0;
        for (char c : chars) {
            prefix[c - 'a']++;
            for (int j = 0; j < 26; j++) {
                if (!visited[j][c - 'a'] && total[j] > prefix[j] && ((j == c - 'a' && prefix[j] > 1) || j != c - 'a' && prefix[j] > 0)) {
                    visited[j][c - 'a'] = true;
                    res++;
                }
            }
        }
        return res;
    }

}

性能

2154.将找到的值乘以2

目标

给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。

接下来，你需要按下述步骤操作：

  1. 如果在 nums 中找到 original ，将 original 乘以 2 ，得到新 original（即，令 original = 2 * original）。
  2. 否则，停止这一过程。
  3. 只要能在数组中找到新 original ，就对新 original 继续 重复 这一过程。

返回 original 的 最终 值。

示例 1：

输入：nums = [5,3,6,1,12], original = 3
输出：24
解释： 
- 3 能在 nums 中找到。3 * 2 = 6 。
- 6 能在 nums 中找到。6 * 2 = 12 。
- 12 能在 nums 中找到。12 * 2 = 24 。
- 24 不能在 nums 中找到。因此，返回 24 。

示例 2：

输入：nums = [2,7,9], original = 4
输出：4
解释：
- 4 不能在 nums 中找到。因此，返回 4 。

说明：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], original <= 1000

思路

有一个数组 nums 和一个整数 original，如果数组中存在 original，可以执行操作将 original 变为 2 * original，重复执行直到无法继续为止，返回 original 的最终值。

需要反复地判断 original 是否在数组中，可以将数组放入哈希表，然后从小到大模拟操作过程。

代码


/**
 * @date 2025-11-19 8:46
 */
public class FindFinalValue2154 {

    public int findFinalValue(int[] nums, int original) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        while (true) {
            if (set.contains(original)) {
                original *= 2;
            } else {
                return original;
            }
        }
    }

}

性能

3226.使两个整数相等的位更改次数

目标

给你两个正整数 n 和 k。

你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

示例 1：

输入： n = 13, k = 4
输出： 2
解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，
我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。

示例 2：

输入： n = 21, k = 21
输出： 0
解释：
n 和 k 已经相等，因此不需要更改。

示例 3：

输入： n = 14, k = 13
输出： -1
解释：
无法使 n 等于 k。

说明：

  • 1 <= n, k <= 10^6

思路

有两个整数 n 和 k，每次操作可以将 n 的二进制位从 1 改为 0，求使 n 等于 k 所需的操作次数，如果无法实现返回 -1。

注意到这两个整数最大为 10^6，而 2^20 = 1048576，因此最高 bit 位不会超过 20。

依次比较这两个数的第 19 位到第 0 位：

  • 如果相等则跳过
  • 如果 n 的 bit 位为 0 则返回 -1，因为这时 k 对应位置的 bit 位为 1，无法通过操作使之相等
  • 否则累加操作次数

官网题解提供了另一种解法，将每个 bit 为 1 的位置视为一个元素，如果可以通过操作将 n 变为 k， 说明 k 的 bit 1 的集合是 n 的 bit 1 集合的子集。因此 n & k = k，这时我们需要统计 n 与 k bit 位不同的个数，直接使用异或运算统计 bit 1 的个数即可。

return (n & k) == k ? Integer.bitCount(n ^ k) : -1;。

代码


/**
 * @date 2024-11-02 5:00
 */
public class MinChanges3226 {

    public int minChanges(int n, int k) {
        int res = 0;
        for (int i = 19; i >= 0; i--) {
            int bitn = n & 1 << i;
            int bitk = k & 1 << i;
            if (bitn == bitk) {
                continue;
            }
            if (bitn == 0) {
                return -1;
            } else {
                res++;
            }
        }
        return res;
    }
}

性能