(leetcode) 四日四题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 暴力，但忘记素数怎么求
def check(x):
    cnt = 0
    while x != 0:
        x -= x & -x  # x & -x
        cnt += 1
    return isPrime(cnt)

def isPrime(x):
    if x < 2:
        return False
    for i in range(2, int(x**0.5)+1):  # 优化循环次数
        if x % i == 0:
            return False
    return True

def countPrimeSetBits(left, right):
    ans = 0
    for i in range(left, right + 1):
        if check(i):
            ans += 1
    return ans
# python库
def countPrimeSetBits(left, right):
    prime = (2, 3, 5, 7, 11, 13, 17, 19)  # 因为right最大不超过20位
    return sum(bin(i).count('1') in prime for i in range(left, right + 1))
# 10100010100010101100存储上述素数
# 当x中1的个数与该数求&不为0，则说明1的个数在上述素数组合内
# python3
def countPrimeSetBits(left, right):
    return sum(((1 << x.bit_count()) & 665772) != 0 for x in range(left, right + 1))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution(object):
    def rotateString(self, s, goal):
        for i in range(0, len(s)):
            newS = s[1] + s[2:len(s)] + s[0]
            if newS == goal:
                return True
            s = newS
        return False
# 首尾相连包括所有可能
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in s + s

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def levelOrder(self, root: 'Node') -> List[List[int]]:
    if not root:
        return []

    ans = list()
    q = deque([root])

    while q:
        cnt = len(q)
        level = list()
        for _ in range(cnt):
            cur = q.popleft()
            level.append(cur.val)
            for child in cur.children:
                q.append(child)
        ans.append(level)
    return ans