京东笔试京东秋招 0906

笔试时间：2025年9月6日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目描述： 小明是一个魔法项链回收商，他的工作是将这些魔法项链进行无害化处理。魔法项链由若干颗魔法石组成，可以视作一个字符串，不同种类的魔法石可以用小写字母 a~z 来进行表示。小明可以将魔法项链切割为若干段（也可以不切割），每一段中相同种类的魔法石可以进行能量抵消，如果最终宝石全部抵消或者只剩一颗，那么就算完成了无害化处理。

输入描述

一个字符串，只包含小写字母，用来表示小明回收的魔法项链，长度不超过 100000

输出描述

一个整数，表示最小需要切割为多少段，可以使所有项链子段都能完成无害化处理。

样例输入

xyz

样例输出

3

参考题解

将一段可"无害化"的充要条件转成字符奇偶性的判断：一段内每个字母出现次数全为偶数，或仅有一个字母为奇数。使用26位比特的前缀奇偶掩码，通过动态规划和哈希表优化找出最少分割段数。

C++：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    const int INF = 1e9;
    unordered_map<int,int> best_by_mask;
    best_by_mask.reserve(s.size() * 2 + 32);
    best_by_mask[0] = 0;
    
    int mask = 0, segments = 0;
    
    for (char ch : s) {
        mask ^= 1 << (ch - 'a');
        int min_prev = INF;
        
        auto it = best_by_mask.find(mask);
        if (it != best_by_mask.end()) min_prev = it->second;
        
        for (int k = 0; k < 26; ++k) {
            int neigh = mask ^ (1 << k);
            auto jt = best_by_mask.find(neigh);
            if (jt != best_by_mask.end()) min_prev = min(min_prev, jt->second);
        }
        
        segments = min_prev + 1;
        if (it == best_by_mask.end() || segments < it->second) 
            best_by_mask[mask] = segments;
    }
    
    cout << segments << '\n';
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        final int INF = 1000000000;
        Map<Integer, Integer> bestByMask = new HashMap<>();
        bestByMask.put(0, 0);
        
        int mask = 0, segments = 0;
        
        for (char ch : s.toCharArray()) {
            mask ^= 1 << (ch - 'a');
            int minPrev = INF;
            
            Integer val = bestByMask.get(mask);
            if (val != null) minPrev = val;
            
            for (int k = 0; k < 26; k++) {
                int neigh = mask ^ (1 << k);
                Integer neighVal = bestByMask.get(neigh);
                if (neighVal != null) minPrev = Math.min(minPrev, neighVal);
            }
            
            segments = minPrev + 1;
            if (val == null || segments < val) {
                bestByMask.put(mask, segments);
            }
        }
        
        System.out.println(segments);
    }
}

Python：

def solve():
    s = input().strip()
    
    INF = 10**9
    best_by_mask = {0: 0}
    
    mask = 0
    segments = 0
    
    for ch in s:
        mask ^= 1 << (ord(ch) - ord('a'))
        min_prev = INF
        
        if mask in best_by_mask:
            min_prev = best_by_mask[mask]
        
        for k in range(26):
            neigh = mask ^ (1 << k)
            if neigh in best_by_mask:
                min_prev = min(min_prev, best_by_mask[neigh])
        
        segments = min_prev + 1
        if mask not in best_by_mask or segments < best_by_mask[mask]:
            best_by_mask[mask] = segments
    
    print(segments)

solve()