shelterofly

目标

给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且 每个 小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个 特殊字母 。

返回 word 中 特殊字母 的数量。

示例 1:

输入：word = "aaAbcBC"
输出：3
解释：
特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = "abc"
输出：0
解释：
word 中不存在特殊字母。

示例 3:

输入：word = "AbBCab"
输出：0
解释：
word 中不存在特殊字母。

说明：

• 1 <= word.length <= 2 * 10^5
• word 仅由小写和大写英文字母组成。

思路

有一个字符串 word，返回其中大小写同时存在，且 所有小写都在其大写之前出现 的的字母个数。

与 3120_统计特殊字母的数量I 相比，本题多了顺序条件。

使用两个数组标记字母（无论大小写，统一用 0 ~ 25 表示）是否被计数以及是否被删除：

• 如果当前字母是大写：
  • 之前大小写都已出现（计数 或者 删除都已经处理过了），直接跳过
  • 对应的小写已经出现，计数（上面的条件保证了不会重复计数），并标记为已计数
• 如果当前字母是小写：
  • 之前大小写都已出现，且已计数（不一定被计数，因为小写可能后出现）未被标记为已删除，则计数减一，并标记为已删除
  • 注意如果之前只出现过大写，不用处理，因为没有被计数

代码

/**
 * @date 2026-05-26 9:06
 */
public class NumberOfSpecialChars3121 {

    /**
     * A(65):  1000001
     * Z(90):  1011010
     * a(97):  1100001
     * z(122): 1111010
     * 31: 0011111
     * 32: 0100000
     */
    public int numberOfSpecialChars_v1(String word) {
        Set<Integer> set = new HashSet<>();
        int n = word.length();
        boolean[] rm = new boolean[26];
        boolean[] add = new boolean[26];
        int res = 0;
        for (int i = 0; i < n; i++) {
            int c = word.charAt(i);
            // 将字母映射到 0 ~ 25，不区分大小写
            int index = (c & 31) - 1;
            // flag 为 0 表示大写字母，为 1 是小写字母
            int flag = c & 32;
            // 如果之前已经遇到过字母的大小写
            if (set.contains(c) && set.contains(c ^ (1 << 5))) {
                // 如果当前是大写，无需处理，因为需要加的话前面已经加了，需要减的前面已经减了
                if (flag == 0){
                    continue;
                }
                // 如果当前是小写，计数过且没减过，计数减一，并标记
                // 注意，如果之前只遇到过大写，不用处理，因为不满足条件没有被计数
                if (!rm[index] && add[index]){
                    rm[index] = true;
                    res--;
                }
            }
            // 如果当前是大写并且之前出现过小写，标记并计数
            if (flag == 0 && set.contains(c + 32)){
                add[index] = true;
                res++;
            }
            set.add(c);
        }
        return res;
    }

}

性能

目标

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

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

说明：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

思路

数组 nums的 元素值互不相同，它由一个升序数组经过旋转而成，返回 target 在数组中的下标，如果不在返回 -1，要求时间复杂度为 O(log n)。

所谓的旋转可以理解为以 k 为分界点将数组分为两段，后面的放到前面，前面的放到后面。相当于两个有序数组拼在一起，且前面数组的每个元素都比后面数组的每个元素都大。

• 如果 target 在左侧，m 在右侧，直接排除右侧
• 如果 target 在右侧，m 在左侧，直接排除左侧
• 如果在同一侧直接按照正常的有序二分即可

进阶的版本是 81.搜索旋转排序数组II。

代码

/**
 * @date 2026-05-22 09:13
 */
public class Search33 {

    public int search_v3(int[] nums, int target) {
        int r = nums.length - 1, l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            // 如果 target 在左侧，m 在右侧，直接排除右侧
            if (target >= nums[0] && nums[m] < nums[0]) {
                r = m - 1;
            } else if (target < nums[0] && nums[m] >= nums[0]) {
                // 如果 target 在右侧，m 在左侧，直接排除左侧
                l = m + 1;
                // 如果在同一侧直接按照正常的有序二分即可
            } else if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return -1;
    }

}

性能

目标

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

说明：

• 1 <= arr1.length, arr2.length <= 5 * 10^4
• 1 <= arr1[i], arr2[i] <= 10^8

思路

有两个数组 arr1 和 arr2，返回所有数对 (arr1[i], arr2[j]) 中最长公共前缀的长度。

将 arr1 中每个数字的前缀都计入哈希表，同时判断 arr2 中每个元素的的前缀是否在哈希表中，取前缀的最大长度即可。

或者可以将 arr1 的每个元素都加入 字典树，枚举 arr2 的每一个元素，计算其在字典树中公共前缀的最大长度。

代码

/**
 * @date 2026-05-21 9:03
 */
public class LongestCommonPrefix3043 {

    static class Trie {
        public Trie[] children = new Trie[10];

        public void insert(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    cur.children[d] = new Trie();
                }
                cur = cur.children[d];
            }
        }

        public int prefixLength(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            int l = 0;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    break;
                }
                cur = cur.children[d];
                l++;
            }
            return l;
        }
    }

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Trie root = new Trie();
        for (int num : arr1) {
            root.insert(num);
        }
        int res = 0;
        for (int num : arr2) {
            res = Math.max(res, root.prefixLength(num));
        }
        return res;
    }

}

性能

目标

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。

A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

请你返回 A 和 B 的 前缀公共数组 。

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。

示例 1：

输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。

示例 2：

输入：A = [2,3,1], B = [3,1,2]
输出：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。

说明：

• 1 <= A.length == B.length == n <= 50
• 1 <= A[i], B[i] <= n
• 题目保证 A 和 B 两个数组都是 n 个元素的排列。

思路

有两个长度为 n 的整数排列 A 和 B，整数 1 ~ n 恰好出现一次，C[i] 表示 A[0, i] 和 B[0, i] 中的公共元素个数（注意不是公共前缀长度），返回 C。

直接依题意模拟，使用哈希表（或者数组计数），A 中元素 +1， B 中元素 -1，然后累加出现次数为 0 的元素个数即可。注意元素相同时避免重复累加，并且当前位置公共元素的个数应该以前一个位置公共元素的个数为基础再加上新增公共元素的个数。

网友题解使用的是位运算，注意到 n <= 50，可以使用两个 long 型变量来记录元素是否出现，将这两个变量相与然后 bitcount 就是公共元素个数。

代码

/**
 * @date 2026-05-20 8:58
 */
public class FindThePrefixCommonArray2657 {

    public int[] findThePrefixCommonArray_v1(int[] A, int[] B) {
        int n = A.length;
        int[] cnt = new int[n + 1];
        int[] C = new int[n];
        cnt[A[0]]++;
        cnt[B[0]]--;
        if (A[0] == B[0]) {
            C[0] = 1;
        }
        for (int i = 1; i < n; i++) {
            cnt[A[i]]++;
            cnt[B[i]]--;
            C[i] = C[i - 1];
            if (cnt[A[i]] == 0) {
                C[i]++;
            }
            if (A[i] != B[i] && cnt[B[i]] == 0) {
                C[i]++;
            }
        }
        return C;
    }

}

性能