2024年1月25日每日一题--2859. 计算 K 置位下标对应元素的和

2859. 计算 K 置位下标对应元素的和

题目分析

最简单的方法是枚举，但是尝试进行优化的时候发现没有成功实现，实现复杂度比较高。

方案一

枚举

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {

        // 枚举
        int result = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (sum1(i) == k) {
                result += nums.get(i);
            }
        }
        return result;
    }

    public int sum1(int num) {
        int result = 0;

        while (num != 0) {
            result += (num % 2);
            num = num / 2;
        }

        return result;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了45.53% 的Java用户
内存消耗:43.5 MB,击败了5.29% 的Java用户

分析

时间复杂度：
O( n * long(n) )

空间复杂度：
O( 1 )

官方题解

https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/solutions/2614602/ji-suan-k-zhi-wei-xia-biao-dui-ying-yuan-axzr/

方法一：枚举所有的下标

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (bitCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }

    public int bitCount(int x) {
        int cnt = 0;
        while (x != 0) {
            cnt += (x % 2);
            x /= 2;
        }
        return cnt;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/solutions/2614602/ji-suan-k-zhi-wei-xia-biao-dui-ying-yuan-axzr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：对计算置位个数进行优化

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (bitCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }

    public int bitCount(int x) {
        x = (x & 0b0101010101) + ((x & 0b1010101010) >> 1);
        x = ((x & 0b0011001100) >> 2) + (x & 0b1100110011);
        x = (x >> 8) + ((x >> 4) & 0b1111) + (x & 0b1111);
        return x;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/solutions/2614602/ji-suan-k-zhi-wei-xia-biao-dui-ying-yuan-axzr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。