榆林网站建设推广在线排名优化
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 <= 105
- 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)。