1. 每日一言
不论何时,我们所有人所做的一切事,都跟彼此有所连结。
2. 题目(76)位 1 的个数
题目链接:(76)位 1 的个数
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为 汉明重量).)。
提示:
请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用 二进制补码 记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。
-
示例 1:
输入:n = 11 (控制台输入 00000000000000000000000000001011)
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 ‘1’。 -
示例 2:
输入:n = 128 (控制台输入 00000000000000000000000010000000)
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 ‘1’。 -
示例 3:
输入:n = 4294967293 (控制台输入 11111111111111111111111111111101,部分语言中 n = -3)
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 ‘1’。
提示:
输入必须是长度为 32 的 二进制串 。
2.1 解题思路
2.1.1 位运算1
- 首先,定义一个整型变量 sum,用于统计二进制表示中1的个数,初始化为0。
- 使用一个循环,从二进制表示的最低位开始,依次检查每一位是否为1。循环条件是 i < 32,因为一个无符号整数有32位。
- 在循环体中,通过右移操作 n >> i 将要检查的位移到最低位,然后通过与操作 (n >> i) & 1 取得该位的值(0或1)。
- 将每次得到的位值累加到 sum 变量中。
- 循环结束后,sum 中存储的就是二进制表示中1的个数。
- 最后,返回 sum。
2.1.2 位运算2
2.2 代码
- 首先,定义一个整型变量 sum,用于统计二进制表示中1的个数,初始化为0。
- 使用一个循环,条件是 while(n),即当 n 不为0时执行循环。这样可以一直循环到 n 中所有的1都被清零。
- 在循环体中,通过 n & (n-1) 的操作,将 n 中最低位的1清零。这样每执行一次操作,就会将 n 中的一个1变为0。
- 每执行一次清零操作,就将 sum 变量加1,表示检测到了一个1。
- 循环结束后,sum 中存储的就是二进制表示中1的个数。
- 最后,返回 sum。
2.2.1 位运算1
int hammingWeight(uint32_t n) {
int sum = 0;
for(int i = 0; i < 32 ; i++) {
sum += (n >> i) & 1;
}
return sum;
}
2.2.2 位运算2
int hammingWeight(uint32_t n) {
int sum = 0;
while(n) {
n = n & (n-1);
++sum;
}
return sum;
}
3. 题目(77)二分查找
题目链接:二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
-
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4 -
示例 2
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
3.1 解题思路
- 首先,定义整型变量 mid 用于表示中间元素的索引,left 表示数组的左边界,right 表示数组的右边界。初始时,left 设置为数组的第一个元素索引,right 设置为数组的最后一个元素索引。
- 使用一个循环,条件是 left <= right,即当左边界小于等于右边界时执行循环。这样可以保证在每一轮循环中数组仍然是有序的,并且还有未检查的元素。
- 在循环体中,计算中间元素的索引 mid,这里采用了一种避免整型溢出的方式 mid = left + (right-left) / 2。如果直接使用 (left + right) / 2 可能会导致整型溢出,所以采用了这种方式。
- 判断目标元素 target 与中间元素 nums[mid] 的关系:
- 如果 target 大于 nums[mid],说明目标元素在数组的右半部分,更新 left = mid + 1。
- 如果 target 小于 nums[mid],说明目标元素在数组的左半部分,更新 right = mid - 1。
- 如果 target 等于 nums[mid],说明找到了目标元素,直接返回 mid。
- 循环结束后,如果没有找到目标元素,返回 -1,表示目标元素不在数组中。
3.2 代码
int search(int* nums, int numsSize, int target) {
int mid = 0;
int left = 0;
int right = numsSize - 1;
while(left <= right) {
mid = left + (right-left) / 2;
if (target > nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}