目录
  1. 1. 日常警醒
  2. 2. 剑指offer15-二进制中1的个数
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 剑指offer18.删除链表节点
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 剑指offer16.数值的整数次方
    1. 4.1. 题目
    2. 4.2. 题解
  5. 5. 只出现一次的数字
    1. 5.1. 题目
    2. 5.2. 题解
  6. 6. 多数元素
    1. 6.1. 题目
    2. 6.2. 题解
每日一刷5

日常警醒

菜就要刷题,不要偷懒!

剑指offer15-二进制中1的个数

题目

  • 难度:简单

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

题解

  • 触宝一面面试题,仅要求口述,掌握二进制似乎是一件很重要的事情。面试后时候是输入十进制,问二进制1的个数,这里是输入二进制数。
  • 每次看到二进制就会想到位运算

1.逐位判断

  • 根据与运算定义,设二进制数字n,则有:
    • 若n&1=0,说明n二进制最右一位是0
    • 若n&1=1,说明n二进制最右一位是1
  • 根据以上特点,考虑循环判断:
    • 判断n最右一位是否是1,根据结果计数
    • 将n右移一位(本题要求把数字 n 看作无符号数,因此使用 无符号右移 操作)
  • 初始化数量统计变量res=0
  • 循环逐位判断:当n=0跳出
  • res +=n&1:若n=1,res加1
  • 右移一位n>>=1,将二进制数字 nn 无符号右移一位
  • 返回res
  • 时间复杂度:O(log2nlog_{2}n)
    • 此算法循环内部仅有移位、与、加等基本运算,占用O(1)
    • 逐位循环需要log2nlog_{2}n次,其中log2nlog_{2}n代表数字n最高位1的所在位数(例如log24=2log_{2}4=2
  • 空间复杂度:O(1)
def hammingWeight(n):

res = 0

while n:
res += n & 1
n >>= 1
return res

if __name__ == '__main__':

n = 9
print(hammingWeight(n))

2.巧用n&(n-1)

  • (n - 1)解析:二进制数字n最右边的1变成0,此1右边的0都变成1
  • n &(n - 1)解析:二进制数字n最右边的1变成0,其余不变
  • 初始化数量统计变量res=0
  • 循环消去最右边的1,当n=0跳出
  • res += 1:统计变量加1
  • n &= n - 1:消去数字n最右边的1
  • 返回res
  • 时间复杂度:O(M)
    • 此算法循环内部仅有移位、与、加等基本运算,占用O(1)
    • 设 M为二进制数字n中1的个数,则需循环 M 次(每轮消去一个 1 ),占用 O(M)
  • 空间复杂度:O(1)
def hammingWeight(n):

res = 0

while n:
res += 1
n &= n - 1
return res

if __name__ == '__main__':

n = 9
print(hammingWeight(n))

剑指offer18.删除链表节点

题目

  • 难度:简单

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

**注意:**此题对比原题有改动

示例1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

  • 题目保证链表中节点的值互不相同
  • 若使用 C 或 C++ 语言,你不需要 freedelete 被删除的节点

题解

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def deleteNode(head, val):
if not head:
return head
if head.val == val:
return head.next

cur = head

while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
break
cur = cur.next
return head

if __name__ == '__main__':

n1 = ListNode(4)
n2 = ListNode(5)
n3 = ListNode(1)
n4 = ListNode(9)
n1.next = n2
n2.next = n3
n3.next = n4

val = 5
node = deleteNode(n1,5)

while node:
print(node.val)
node = node.next

剑指offer16.数值的整数次方

题目

  • 难度:中等

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例1:

输入: 2.00000, 10
输出: 1024.00000

示例2:

输入: 2.10000, 3
输出: 9.26100

示例3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

题解

  • 快速幂,实际上是一种二分思想的一种应用
  • 二分推导:xn=xn/2xn/2=x2(n/2)x^n = x^{n/2} * x ^{n/2} = x^{2(n/2)},令n/2为整数,则需要考虑n的奇偶性:
    • n为偶数:x2=x2(n//2)x^2 = x^{2(n//2)}
    • n为奇数:x2=xx2(n//2)x^2=x * x^{2(n//2)}
  • 幂结果获取:
    • 根据二分推导,可通过循环x=x2x = x^2操作,每次把幂从n降到n//2,直到降为0
    • 设res=1,则初始状态xn=xnresx^n = x^n * res。在循环二分时,每当n为奇数时,将多出的一项x乘入res,则最终可化至xn=x0res=resx^n = x^0 * res = res,返回res
  • 转化为位运算:
    • 向下整除n//2等价于右移一位n>>1
    • 取余数n%2等价于判断二进制最右一位值n&1
  • 算法流程:
    • 当x=0时,直接返回0
    • 初始化res=1
    • 当n<0时,把问题转化为n≥0的范围,即执行x=1/x,n=-n
    • 循环计算,当n=0时跳出
      • 当n&1=1时,将当前x乘入res
      • 执行x=x2x = x^2
      • 执行n右移一位
    • 返回res
  • 时间复杂度:O(log2nlog_{2}n)
  • 空间复杂度:O(1)
def myPow(x, n):

if x == 0:
return 0

res = 1

if n < 0:
x = 1/x
n = -n

while n:
if n & 1:
res *= x
x *= x
n >>= 1
return res

if __name__ == '__main__':

x, n = 2.00000, 10
print(myPow(x, n))

只出现一次的数字

题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例1:

输入: [2,2,1]
输出: 1

示例2:

输入: [4,1,2,1,2]
输出: 4

题解

  • 第一想法,用哈希表记录遍历过的元素,返回value=1的key,时间复杂度和空间复杂度都是O(n)
def singleNumber(nums):
dict = {}
for num in nums:
if num in dict:
dict[num] += 1
else:
dict[num] = 1
for k,v in dict.items():
if v == 1:
return k

if __name__ == '__main__':

nums = [4,1,2,1,2]
print(singleNumber(nums))
  • 第二想法,异或运算,任何数异或0都等于本身。两个相同的数异或等于0,时间复杂度:O(n),空间复杂度:O(1)
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
for num in nums:
a ^= num
return a

多数元素

题目

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例1:

输入: [3,2,3]
输出: 3

示例2:

输入: [2,2,1,1,1,2,2]
输出: 2

题解

  • 第一想法,还是用哈希表记录每个元素出现的次数,然后返回value > n/2的key,时间复杂度:O(n),空间复杂度:O(n)
def majorityElement(nums):

dict = {}

for num in nums:
if num in dict:
dict[num] += 1
else:
dict[num] = 1
for k,v in dict.items():
if v > len(nums) // 2:
return k

if __name__ == '__main__':

nums = [2,2,1,1,1,2,2]
print(majorityElement(nums))
  • 第二想法,投票法,数组中有一个数字出现的次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现次数的和还要多。因此,我们可以考虑在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数。当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1;如果下一个数字和我们之前保存的数字不同,则次数减一。如果次数为零,我们需要保存下一个数字,并把次数设置为1。由于我们要找的数字出现的次数比其他所有数字出现的次数和要多,那么要找的数字肯定是最后一次把次数设为1时的对应数字。时间复杂度:O(n),空间复杂度:O(1)
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
vote = 0
count= 0

for num in nums:
if vote == 0:
x = num
vote += 1 if num == x else -1

for num in nums:
if num == x:
count += 1
return x if count > len(nums)//2 else 0
文章作者: Lesy
文章链接: https://lesylin.com/2020/08/05/%E6%AF%8F%E6%97%A5%E4%B8%80%E5%88%B75/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment