【重点】【位操作】剑指offer56-II：数组中数字出现的次数

Allenlzcoder

已于 2025-05-20 01:12:20 修改

阅读量214

点赞数 3

分类专栏：剑指offer题目笔记文章标签：位运算

于 2023-11-23 10:38:39 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/134571341

版权

剑指offer题目笔记专栏收录该内容

80 篇文章

订阅专栏

本文介绍了一种使用Java实现的解决方案，通过有限状态自动机简化问题，计算给定动作序列actions中每个数字出现次数对3的余数。Solution类中的trainingPlan方法利用计数器数组counter存储每个位上的动作影响，最后通过位操作得到结果。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

力扣
 思路参考
有限状态自动机推导式太复杂，略去~
在这里插入图片描述

Python

class Solution:
    def trainingPlan(self, actions: List[int]) -> int:
        res, m = 0, 3
        counter_arr = [0] * 32
        for act in actions:
            for i in range(32):
                counter_arr[i] += act & 1
                act >>= 1
        for i in range(31, -1, -1):
            res <<= 1
            res += counter_arr[i] % m
        
        return res

Java

class Solution {
    public int trainingPlan(int[] actions) {
        int res = 0, m = 3;
        int[] counter = new int[32]; // java中int型数据包含4个byte, 1byte=8bit, 共32位;最高位是符号位
        for (int act : actions) {
            for (int i = 0; i < 32; ++i) {
                counter[i] += act & 1;
                act >>= 1;
            }
        }

        for (int i = 31; i >= 0; --i) {
            res <<= 1;
            res += counter[i] % m; // 这俩顺序不能颠倒, 否则会导致最后往左多挪动1位
        }

        return res;
    }
}