力扣题目汇总(二进制表示中质素个数,分糖

2023-01-31 00:01:09 汇总 制表 质素

二进制表示中质数个计算置位

1.题目描述

给定两个整数 LR ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。

(注意,计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有,1 不是质数。)

示例 1:

输入: L = 6, R = 10
输出: 4
解释:
6 -> 110 (2 个计算置位,2 是质数)
7 -> 111 (3 个计算置位,3 是质数)
9 -> 1001 (2 个计算置位,2 是质数)
10-> 1010 (2 个计算置位,2 是质数)

示例 2:

输入: L = 10, R = 15
输出: 5
解释:
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)

注意:

  1. L, RL <= R 且在 [1, 10^6] 中的整数。
  2. R - L 的最大值为 10000。

2.解题思路

1.应为他R的范围为10的6次方,所以二进制后最大的1的个数为20,所以我们可以列出20里的质素制作出表格
one_list = [2,3,5,7,11,13,17,19],
然后就是循环了,根据1的个数来判断他是不是质素

3.解题

class Solution:
    def countPrimeSetBits(self, L: int, R: int) -> int:
        count = 0
        one_list = [2,3,5,7,11,13,17,19]
        for a in range(L,R+1):
            if bin(a).count('1') in one_list:
                count += 1
        print(count)
        return count

分糖果

1.题目描述

输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果,每一种都有两个。
     最优分配方案:妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 :

输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1],妹妹有两种不同的糖果,弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

注意:

  1. 数组的长度为[2, 10,000],并且确定为偶数。
  2. 数组中数字的大小在范围[-100,000, 100,000]内。

2.解题思路

用元祖去重

3.解题

class Solution:
    def distributeCandies(self, candies: List[int]) -> int:
        candies_set = set(candies)
        if len(candies_set) >= len(candies)/2:
            return int(len(candies)/2)
        else:
            return len(candies_set)

快乐数

1题目描述

  1. 编写一个算法来判断一个数是不是“快乐数”。

    一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。

    示例:

    输入: 19
    输出: true
    解释: 
    12 + 92 = 82
    82 + 22 = 68
    62 + 82 = 100
    12 + 02 + 02 = 1

2.解题思路

安装他示例,我们可以想到他解释里面的内容是
sum([int(i)**2 for i in str(n) ])
问题就在于他如果步等于1他无线循环会是什么有没有规律
class Solution:
    def isHappy(self, n: int) -> bool:
        a = True
        new_list = [4,16,37,58,89,145,42,20]
        while n != 1:
            n = sum([int(i)**2 for i in str(n) ])
            print(n)
所有我们在PyCharm输入几个 n打印出n看看情况
然后我们发现无论什么数字他会进入一个循环
[4,16,37,58,89,145,42,20],
所有我们只要数到这里就停止程序即可,
class Solution:
    def isHappy(self, n: int) -> bool:
        a = True
        new_list = [4,16,37,58,89,145,42,20]
        while n != 1:
            n = sum([int(i)**2 for i in str(n) ])
            if n in new_list:
                a = False
                break
        print(a)
        return a

3.解题

class Solution:
    def isHappy(self, n: int) -> bool:
        a = True
        new_list = [4,16,37,58,89,145,42,20]
        while n != 1:
            n = sum([int(i)**2 for i in str(n) ])
            if n in new_list:
                a = False
                break
        print(a)
        return a

相关文章