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

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

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

1.题目描述

给定两个整数 L 和 R ，找到闭区间 [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, R 是 L <= 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

相关文章