【力扣】191.位 1 的个数、485.最大连续 1 的个数

191.位 1 的个数

题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。

提示：

• 1 <= n <= 231 - 1

进阶：

• 如果多次调用这个函数，你将如何优化你的算法？

解题方法

• C 循环检查

int hammingWeight(int n) {int cnt = 0;unsigned int m = 0x1; // 必须定义为“无符号”型for (int i = 0; i < 32; i++) {if (n & (m << i)) {cnt++;}}return cnt;
}

复杂度分析：
时间复杂度为 O(k)，其中 k 是 int 型的二进制位数，k = 32。
空间复杂度为 O(1)。

---

485. 最大连续 1 的个数

题目描述

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

示例 2：

输入：nums = [1,0,1,1,0,1]
输出：2

提示：

• 1 <= nums.length <= 10⁵
• nums[i] 不是 0 就是 1.

解题方法

• C 遍历取最大

// #define MAX(a, b) ((a) > (b) ? (a) : (b)) // 取最大值int my_max(int a, int b) {if (a > b)return a;elsereturn b;
}int findMaxConsecutiveOnes(int* nums, int numsSize) {int max_cnt = 0, cnt = 0; // 定义最大计数变量，计数变量for (int i = 0; i < numsSize; i++) {if (nums[i] == 1) {cnt++; // 对 1 计数} else {max_cnt = my_max(max_cnt, cnt); // 存储最大 1 的个数cnt = 0;                        // 重新计数}}max_cnt = my_max(max_cnt, cnt);return max_cnt;
}

复杂度分析
时间复杂度为 O(n)，其中 n 是数组的长度。
空间复杂度为 O(1)。