leetcode-软柿子专场一

发表于 | 分类于 | 页面访问量 次
字数统计: 723 字 | 阅读时长 ≈ 3 分钟

总结：本来想捏的软柿子。结果发现，被柿子给捏了。

326. 3的幂（Dx）

分析：妙解。用数论的知识：3的幂次的质因子只有3.

输入时int型，正数范围0~2^31. 即最大的数为3^19 = 1162261467 只需要看这个数是否能被n整除即可。

质因子（或质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。只有一个质因子的正整数为质数。

1
2
3
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

38. 报数（B-）

分析：？什么情况，菜鸟难度的题，题意看了半天。我是来虐菜的，不是来被虐的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countAndSay(self, n: int) -> str:
        b = '1'  #将第一行的1换成字符类型，便于下一行的读出
        for i in range(n-1): #(n-1)是因为第一行不需要处理，直接可以读出
            
            a, c, count = b[0], '', 0             
            #a用来读取上一行的第一个字符，c用来存放读出的内容(char)，count用来统计
           
        	for j in b:
                if a == j:
                    count += 1
                else:
                    c += str(count) + a   #注意一定要将count转换为字符型，否则两个数就会相加
                    a = j
                    count = 1
            c += str(count) + a
            b = c
        return b

58. 最后一个单词的长度（D）

分析：蛮简单的一道题，知道长度就可以从后往前遍历了。注意空集存在。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        cnt, tail = 0, len(s) - 1
        while tail >= 0 and s[tail] == ' ':  #去掉末尾空格，再计数。
            tail -= 1
        while tail >= 0 and s[tail] != ' ':
            cnt += 1
            tail -= 1
        return cnt

66. 加一（D+）

分析：短小不错的一道题。

精简版，把数列直接拼接成数字，加一之后再转化为数组。

1
2
3
4
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        num = str(int(''.join([str(a) for a in digits])) + 1)
        return [int(i) for i in num]

常规做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits.reverse()
        i = 0
        flag = 1
        while i < len(digits):
            if digits[i] + flag == 10:
                digits[i] = 0
                flag = 1
            else:
                digits[i] += flag
                flag = 0
            i += 1
        if flag == 1:
            digits.append(1)
        digits.reverse()
        return digits

67. 二进制求和（Dx）

巧妙的做法

1
2
3
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a,2) + int(b,2))[2:]

69. x 的平方根（Dx）

牛顿迭代法。求平方的方式。

1
2
3
4
5
6
7
8
class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            return x
        r = x
        while r > x / r:
            r = (r + x / r) // 2
        return int(r)
0%
undefined