- 二进制/位运算
- 67 二进制求和
- 89 格雷编码
- 136 只出现一次的数字
- 190 颠倒二进制位
- 191 位1的个数
- 231 2 的幂
- 338 比特位计数
- 342 4的幂
- 405 数字转换为十六进制数
- 461 汉明距离
- 476 数字的补数
- 504 七进制数
- 693 交替位二进制数
- 762 二进制表示中质数个计算置位
- 四则运算
- 7 整数反转
- 9 回文数
- 43 字符串相乘
- 50 Pow(x,n)
- 66 加一
- 415 字符串相加
- 数学公式
- 118 杨辉三角
- 119 杨辉三角 II
- 268 丢失的数字
- 812 最大三角形面积
- 技巧题
- 168 Excel表列名称
- 169 多数元素
- 171 Excel 表列序号
- 258 各位相加
- 292 Nim 游戏：归纳推理是否能被4整除
- 326 3的幂
- 453 最小操作次数使数组元素相等
- 521 最长特殊序列 Ⅰ
- 575 分糖果
- 717 1比特与2比特字符
- 算就完事了
- 12 整数转罗马数字
- 263 丑数
- 507 完美数
- 728 自除数
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]
提示:
1 <= numRows <= 30
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[1]]
if numRows ==1:
return res
for i in range(1, numRows):
pre = res[i-1]
cur = [1]+[i+j for i,j in zip(pre[1:], pre[:-1])]+[1]
res.append(cur)
return resTips
1.下一行=（[0]+上一行）+（上一行+[0]） 错位相加
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3 输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0 输出: [1]
示例 3:
输入: rowIndex = 1 输出: [1,1]
- 最常规的按行递归解法
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [1]
if rowIndex ==0:
return res
for i in range(rowIndex):
res = [i+j for i,j in zip([0]+res, res+[0])]
return res- 想进一步优化空间使用，可以在长度=N的数组内部直接进行滚动
初始状态N=5 [1,0,0,0,1], 每行从index=rowIndex-1~1开始执行 x[i] = x[i] +x[i-1] 依次得到【注意这里是从右往左更新】
[1,1,0,0,1], [1,2,1,0,1],[1,3,3,1,1],[1,4,6,4,1].
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
if rowIndex <=1:
return [1] *(rowIndex+1)
res = [1] + [0] * (rowIndex-1) + [1]
for i in range(rowIndex):
for j in range(rowIndex-1,0,-1):
res[j] += res[j-1]
print(res)
return res罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
示例 1:
输入: num = 3 输出: "III"
示例 2:
输入: num = 4 输出: "IV"
示例 3:
输入: num = 9 输出: "IX"
示例 4:
输入: num = 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3.
示例 5:
输入: num = 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示：
1 <= num <= 3999
class Solution:
def intToRoman(self, num: int) -> str:
nums = [
(1000, "M"),
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I"),
]
res = ''
for (i,j) in nums:
while num>=i:
num-=i
res+=j
return res
Tips
- 直接遍历出所有可以单独使用的罗马数字，和罗马数字组合，从大到小排列
- 从num中不断减掉最小的罗马数字组合即可
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = nums[0]
for i in nums[1:]:
ans ^=i
return ans Tips
位运算老实说真的是从来没在工作里用过，所以一般是想不起来的。。。。
- 与&：都是1=1，others=0
- 或｜：任意是1=1，others=0
- 异或^:不用=1，相同是0 ->于是a^a=0 a^0=a a^b=b^a,就是这题需要的解法
- 取反～：1变0，0变1
给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。
例如：
A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...
示例 1：
输入：columnNumber = 1 输出："A"
示例 2：
输入：columnNumber = 28 输出："AB"
示例 3：
输入：columnNumber = 701 输出："ZY"
示例 4：
输入：columnNumber = 2147483647 输出："FXSHRXW"
提示：
1 <= columnNumber <= 231 - 1
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
res = ''
while columnNumber>0:
columnNumber-=1
res += chr(ord('A') + columnNumber%26)
columnNumber = columnNumber//26
return res[::-1]Tips
- 可以类比整数反转和回文数，只不过这里不是/10，而是/26
- Ord,chr可以做英文到数字，数字到英文的转换
给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回该列名称对应的列序号。
例如，
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
示例 1:
输入: columnTitle = "A" 输出: 1
示例 2:
输入: columnTitle = "AB" 输出: 28
示例 3:
输入: columnTitle = "ZY" 输出: 701
示例 4:
输入: columnTitle = "FXSHRXW" 输出: 2147483647
提示：
1 <= columnTitle.length <= 7
columnTitle 仅由大写英文组成
columnTitle 在范围 ["A", "FXSHRXW"] 内
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
num = 0
for i in columnTitle:
num = num*26 + (ord(i)-ord('A')+1)
return num Tips
- 可以类比整数反转，回文数，颠倒二进制，只不过是26进制
颠倒给定的 32 位无符号整数的二进制位。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
示例 1：
输入：n = 00000010100101000001111010011100 输出：964176192 (00111001011110000010100101000000) 解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：n = 11111111111111111111111111111101 输出：3221225471 (10111111111111111111111111111111) 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：
输入是一个长度为 32 的二进制字符串
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
res = (res<<1) + (n&1)
n = n>>=1
return res Tips
- 继续位移，类比整数反转 res=res10 + x%10 x//10的方案，换成二进制就是res=res2+x%2 x//2，还有啥问题呢？
- 把运算符换成二进制：分别把%替换成位运算%&1， //替换成>>, * 替换成<<
- 注意尾部的00000，需要被反转到头部，所以只能for range(32)，不能while n
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
示例 1：
输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
输入必须是长度为 32 的 二进制串 。
- 标准解法： O(K=32)
class Solution:
def hammingWeight(self, n: int) -> int:
counter = 0
for i in range(32):
pos = 1<<i
if n & pos:
counter+=1
return counter - 优化版: O(logn)
class Solution:
def hammingWeight(self, n: int) -> int:
counter = 0
while n:
n = n&(n-1)
counter+=1
return counter Tips
- 位运算位移1 << n. 2^n,1->10->100->1000. 记忆很简单箭头指哪边就往哪边移动。
- 判断是否是1，有两种方案
- 生成2^n的二进制，然后用&来判断该位置是否是1
- n-1= 把n的最后一个1变成0，每个iter只干掉1个1
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1 输出：true 解释：20 = 1
示例 2：
输入：n = 16 输出：true 解释：24 = 16
示例 3：
输入：n = 3 输出：false
示例 4：
输入：n = 4 输出：true
示例 5：
输入：n = 5 输出：false
提示：
-231 <= n <= 231 - 1
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n==0:
return False
if n & (n-1)==0:
return True
else:
return False Tips
- 联想到位1的个数那道题，判断哪个位置有1/没有1，当时有两种方案，一种就是用2^n次幂的二进制去做&运算，另一种就是用n-1去做& 运算。因为2^4对应的二进制是1000, 减一后会得到111，做与预算会得到0.
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入: 38 输出: 2 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶: 你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
class Solution:
def addDigits(self, num: int) -> int:
if num==0:
return 0
return (num-1)%9+1Tips
循环解法太简单这里不说了，数学解法比较有意思，真的是梦回小学奥数。最后得到个位数，也就是不需要再进位<=9的意思，于是就会想到9的特殊性质，所有9的倍数，各个位数之和一定还是9的倍数,27,36,45。又回联想到下面的推理
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 6 输出：true 解释：6 = 2 × 3
示例 2：
输入：n = 8 输出：true 解释：8 = 2 × 2 × 2
示例 3：
输入：n = 14 输出：false 解释：14 不是丑数，因为它包含了另外一个质因数 7 。
示例 4：
输入：n = 1 输出：true 解释：1 通常被视为丑数。
提示：
-231 <= n <= 231 - 1
class Solution:
def isUgly(self, n: int) -> bool:
if n <=0:
return False
if n==1:
return True
factors = [5,3,2]
for i in factors:
while n%i==0:
n/=i
if n >1:
return False
else :
return True pyTips
注意0，1，复数的特殊处理就好
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
return int((n+1)*n/2-sum(nums))Tips
继续梦回小学奥数，总有几个公式是刻在脑子里的，比如1-n的和为（1+n)*n/2
你和你的朋友，两个人一起玩 Nim 游戏：
桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例 1：
输入：n = 4 输出：false 解释：如果堆中有 4 块石头，那么你永远不会赢得比赛； 因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
示例 2：
输入：n = 1 输出：true
示例 3：
输入：n = 2 输出：true
提示：
1 <= n <= 231 - 1
class Solution:
def canWinNim(self, n: int) -> bool:
return n%4!=0Tips
- 小时候上奥数，但凡是规则推理类的问题，上来自己先列几个例子准没错。不难发现<=3，自已都能赢，=4，怎么取都会输，[5,7]可以通过不同取法让对方面对=4的情况，=8怎么取，对方都能让自己面对=4的情况。不难发现只要是4的倍数，先手必输
给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
示例 1：
输入：n = 27 输出：true
示例 2：
输入：n = 0 输出：false
示例 3：
输入：n = 9 输出：true
示例 4：
输入：n = 45 输出：false
提示：
-231 <= n <= 231 - 1
- 常规递归解法
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n<=0:
return False
while n>1:
if n%3==0:
n/=3
else:
return False
return True
- 数学解法：哈哈本想往2的幂上套整个位运算啥的后来发现完全想偏。这里是用的MAX_INT之内最大3的n次幂的公约数来求解
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n<=0:
return False
max3 = 3**19
if max3%n==0:
return True
else:
return False 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2 输出：[0,1,1] 解释： 0 --> 0 1 --> 1 2 --> 10
示例 2：
输入：n = 5 输出：[0,1,1,2,1,2] 解释： 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
提示：
0 <= n <= 105
进阶：
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
class Solution:
def countBits(self, n: int) -> List[int]:
def findone(x):
counter=0
while x:
x &=(x-1)
counter+=1
return counter
res = []
for i in range(n+1) :
res.append(findone(i))
return res Tips
logn的时间复杂度来自于1的检索部分的优化，方案和191题位1的个数一样。也叫Brian Kernighan算法
true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
示例 1：
输入：n = 16 输出：true
示例 2：
输入：n = 5 输出：false
示例 3：
输入：n = 1 输出：true
提示：
-231 <= n <= 231 - 1
class Solution:
def isPowerOfFour(self, n: int) -> bool:
if n<=0:
return False
if ( n&(n-1)==0) and n%3==1:
return True
else:
return False 判断4的幂还有一种新解法就是复用2的幂，只需要区别是2不是4的那部分，这部分用3的余数来解决，可以表示为4^n*2的数字mod(3)=2，而4的幂mod(3)=1
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例 1：
输入: 26
输出: "1a"
示例 2：
输入: -1
输出: "ffffffff"
class Solution:
def toHex(self, num: int) -> str:
if num < 0:
num+=2**32
ans = []
mapping = "0123456789abcdef"
while True:
ans.append(mapping[num%16])
num = num//16
if num==0:
break
return ''.join(ans[::-1])Tips
- 转换成任意进制的方式都是一样的， 不断地求模，把模映射到对应进制的值，然后向前进一位
- 负数补码
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = "11", num2 = "123" 输出："134"
示例 2：
输入：num1 = "456", num2 = "77" 输出："533"
示例 3：
输入：num1 = "0", num2 = "0" 输出："0"
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i = len(num1)-1
j = len(num2)-1
total = []
carry = 0
while i>=0 or j >=0:
if (i>=0) and (j>=0):
current = int(num1[i])+ int(num2[j]) + carry
elif j>=0:
current = int(num2[j]) + carry
else:
current = int(num1[i])+ + carry
total.append(str(current%10))
carry = current //10
i-=1
j-=1
if carry:
total.append('1')
return ''.join(total[::-1])Tips
- 双指针向前遍历，一个记录mod一个记录carray
- 注意不要忘记遍历完，如果最后carray！=0要补1
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
class Solution:
def multiply(self, num1: str, num2: str) -> str:
result = 0
base1 = 1
for i in range(len(num1)-1,-1,-1):
remainder =0
base2 = base1
for j in range(len(num2)-1,-1,-1):
tmp = int(num1[i]) * int(num2[j]) + remainder
remainder = tmp//10
tmp = tmp%10
result+=tmp*base2
base2*=10
if remainder:
result+=base2 *remainder
base1*= 10
return str(result)Tips
注意不要出现float，不然bigint会会超出界限
给定一个长度为 n 的 非空 整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。
示例：
输入：
[1,2,3]
输出：
3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
class Solution:
def minMoves(self, nums: List[int]) -> int:
min_n = min(nums)
total = 0
for i in nums:
total+=(i-min_n)
return total
Tips
让n-1元素+1等于让该元素-1，所以只要让所有元素都-1到最小元素即可
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4 输出：2 解释： 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1 输出：1
提示：
0 <= x, y <= 231 - 1
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x^y).count('1')Tips
直接求异或的结果有多少个1，其中bin会返回数字的二进制表达
给你一个 正 整数 num ，输出它的补数。补数是对该数的二进制表示取反。
示例 1：
输入：num = 5 输出：2 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
示例 2：
输入：num = 1 输出：0 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
提示：
给定的整数 num 保证在 32 位带符号整数的范围内。
num >= 1
你可以假定二进制数不包含前导零位。
- 异或解法：求补位就是和相同长度的11111来计算异或，相同长度的11111就是+1长度的（2^n）-1
class Solution:
def findComplement(self, num: int) -> int:
one = 2**(len(bin(num))-2)-1
return one^num- 上面异或解法的另一个思路，a+a的补位 = 2^(n)-1，其中n是a的二进制长度
class Solution:
def findComplement(self, num: int) -> int:
n = len(bin(num))-2
return (2**n) - num -1
作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：
-
你设计的矩形页面必须等于给定的目标面积。
-
宽度 W 不应大于长度 L，换言之，要求 L >= W 。
-
长度 L 和宽度 W 之间的差距应当尽可能小。
你需要按顺序输出你设计的页面的长度 L 和宽度 W。
示例：
输入: 4 输出: [2, 2] 解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。 但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。
说明:
给定的面积不大于 10,000,000 且为正整数。
你设计的页面的长度和宽度必须都是正整数。
class Solution:
def constructRectangle(self, area: int) -> List[int]:
w = int(area**0.5)
while True:
if area %w==0:
l = area//w
return [l,w]
else:
w-=1Tips
可以用二分法来解，也可以直接从开根号的下边界往回遍历
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
class Solution:
def myPow(self, x: float, n: int) -> float:
result = 1
flag = n<0
n = abs(n)
while n>0:
if n%2==1:
result*=x
n>>=1
x*=x
if flag:
return 1/result
else:
return result Tips
二分法的思路，x->x^2->x^4节省 $$ x^n &= (x^{n/2}) ^ {(n//2)} n是奇数\ &= x*(x^{n/2}) ^{(n//2)} n是偶数\ $$ 每一轮先判断当前n是奇数还是偶数
如果是偶数直接把x*=x，然后n//2
如果是奇数，就把余数的x乘到result里，然后再x*=x, n//2
给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。
示例 1:
输入: num = 100 输出: "202"
示例 2:
输入: num = -7 输出: "-10"
提示：
-107 <= num <= 107
class Solution:
def convertToBase7(self, num: int) -> str:
if num==0:
return'0'
flag = int(num<0)
num = abs(num)
ans = []
while num>0:
ans.append(str(num%7))
num=num//7
print(ans)
if flag:
return '-' + ''.join(ans[::-1])
else:
return ''.join(ans[::-1])Tips
常规N进制解法，求mod，//，然后倒叙拼接
于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
给定一个 整数 n， 如果是完美数，返回 true，否则返回 false
示例 1：
输入：28 输出：True 解释：28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, 和 14 是 28 的所有正因子。
示例 2：
输入：num = 6 输出：true
示例 3：
输入：num = 496 输出：true
示例 4：
输入：num = 8128 输出：true
示例 5：
输入：num = 2 输出：false
提示：
1 <= num <= 108
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
if num==1:
return False
total = 1
for i in range(2, int(num**0.5)+1 ):
if num%i==0:
if i**2 == num:
total +=i
else:
total +=(i+num//i)
print(total)
if num==total:
return True
else:
return False Tips
- 技巧之一是不用遍历全部range(num), 只用遍历到是sqrt(num) 即可，因为每次都可以加入正因子和num//正因子两个数，如果i^2=num只用加一次
- 注意num=1 return False
给你两个字符串，请你从这两个字符串中找出最长的特殊序列。
「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。
示例 1：
输入: "aba", "cdc" 输出: 3 解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。
示例 2：
输入：a = "aaa", b = "bbb" 输出：3
示例 3：
输入：a = "aaa", b = "aaa" 输出：-1
提示：
两个字符串长度均处于区间 [1 - 100] 。
字符串中的字符仅含有 'a'~'z' 。
class Solution:
def findLUSlength(self, a: str, b: str) -> int:
na = len(a)
nb = len(b)
if na==nb:
if a==b:
return -1
else:
return na
else:
return max(na,nb)Tips
这题需要非常仔细的审题。。。。你看完解法再去审题就会恍然大悟。更长的字符串一定不会是更短的字符串的字字符串所以会是特殊字符串
给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 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]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。
注意:
数组的长度为[2, 10,000]，并且确定为偶数。
数组中数字的大小在范围[-100,000, 100,000]内。
class Solution:
def distributeCandies(self, candyType: List[int]) -> int:
unique = set(candyType)
return min(len(unique), len(candyType)//2)TIps
把所有unique的糖果都給妹妹就好
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0] 输出：[1]
提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
remainder =0
for i in range(len(digits)-1,-1,-1):
if i == len(digits)-1:
tmp = digits[i]+1+remainder
else:
tmp = digits[i] + remainder
if tmp >=10:
tmp -=10
remainder = 1
else:
remainder =0
digits[i] = tmp
if remainder ==1:
digits.insert(0,1)
return digits Tips
- 没啥好说的进位就完事了
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1" 输出: "100"
示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。
class Solution:
def addBinary(self, a: str, b: str) -> str:
res = []
remainder = 0
#补齐ab
gap = len(a) - len(b)
a = '0' * -gap + a
b = '0' * gap + b
i = len(a)-1
while i >= 0:
tmp = int(a[i]) + int(b[i]) + remainder
res.append(str(tmp%2))
remainder = tmp//2
i-=1
if remainder>0:
res.append(str(remainder))
return ''.join(res[::-1])Tips
-
补齐长度那里非常smart， ‘1’ * -1=‘’
-
有remainder相关的问题注意第一位的remainder不要忘记
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
示例 1：
输入：n = 5 输出：true 解释：5 的二进制表示是：101
示例 2：
输入：n = 7 输出：false 解释：7 的二进制表示是：111.
示例 3：
输入：n = 11 输出：false 解释：11 的二进制表示是：1011.
示例 4：
输入：n = 10 输出：true 解释：10 的二进制表示是：1010.
示例 5：
输入：n = 3 输出：false
提示：
1 <= n <= 231 - 1
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
tmp = n ^ n>>1
return (tmp & (tmp+1))==0Tips
1010 ->101 取异或 得到1111，1111和10000取&
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123 输出：321
示例 2：
输入：x = -123 输出：-321
示例 3：
输入：x = 120 输出：21
示例 4：
输入：x = 0 输出：0
提示：
-231 <= x <= 231 - 1
class Solution:
def reverse(self, x: int) -> int:
flag = 1
if x<0:
flag = -1
x *=flag
reverse =0
while x>0:
reverse = reverse * 10 + x%10
x = x//10
if reverse > 2**31-1:
return 0
return flag * reverseTips
- 整数从尾到头reverse，用%10，判断stop 用0
有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。
现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。
示例 1:
输入: bits = [1, 0, 0] 输出: True 解释: 唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:
输入: bits = [1, 1, 1, 0] 输出: False 解释: 唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
1 <= len(bits) <= 1000.
bits[i] 总是0 或 1.
class Solution:
def isOneBitCharacter(self, bits: List[int]) -> bool:
i = 0
while i < len(bits)-1:
i += bits[i]+1
return i== len(bits)-1Tips
一次遍历，如果是1就是2字符，如果是0就是1字符，如果最后停止位置是-1，则是1字符
自除数 是指可以被它包含的每一位数除尽的数。
例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
还有，自除数不允许包含 0 。
给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
示例 1：
输入： 上边界left = 1, 下边界right = 22 输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
注意：
每个输入参数的边界满足 1 <= left <= right <= 10000。
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
ans = []
def helper(t):
s = str(t)
for i in s:
if int(i)==0 or t%int(i) >0:
return False
return True
for t in range(left, right+1):
if helper(t):
ans.append(t)
return ans 没啥说的你遍历就完了
给定两个整数 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 不是质数)
注意:
L, R 是 L <= R 且在 [1, 10^6] 中的整数。
R - L 的最大值为 10000。
通过次数18,120 提交次数25,872
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
primes= {2,3,5,7,11,13,17,19}
counter = 0
for i in range(left, right+1):
count1 = bin(i).count('1')
if count1 in primes:
counter+=1
return counter Tips
- 这里的优先边界提供了简单解法， 10^6的右边界可以被2^20覆盖，所以只需要枚举有限的质数即可
给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
示例: 输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] 输出: 2 解释: 这五个点如下图所示。组成的橙色三角形是最大的，面积为2。
注意:
3 <= points.length <= 50.
不存在重复的点。
-50 <= points[i][j] <= 50.
结果误差值在 10^-6 以内都认为是正确答案。
from itertools import combinations
class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
return max(abs((x0-x2)*(y1-y2)-(x1-x2)*(y0-y2)) for (x0,y0),(x1,y1),(x2,y2) in combinations(points,3))/2- Combinations(list, number)
- 面积公式
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
示例 1：
输入：n = 2 输出：[0,1,3,2] 解释： [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同 [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
示例 2：
输入：n = 1 输出：[0,1]
提示：
1 <= n <= 16
- 二进制编码方式：需要了解格雷编码的生成方式
看到这种编码的时候我也很好奇啊，这是闲的么设计这种无聊的编码逻辑，所以好奇害死猫，我google一下格雷编码有很多好处，例如编码变化有限，不会产生峰值电流，以及诸多好处，哈哈基本都不太看得懂。。。
class Solution:
def grayCode(self, n: int) -> List[int]:
res = []
for i in range(2**n):
res.append(i^(i>>1))
return res 二进制编码方式：最高位是二进制最高位，次高位是二进制看两位求异或，第三位是二进制2/3位求异或。为了产生一步的错位，用位运算向右移一位
- 找规律：如果你不想了解格雷编码的公式，下面的方法适合你
class Solution:
def grayCode(self, n: int) -> List[int]:
cur = [0,1]
base = 2
for i in range(1, n):
cur = cur + [i+base for i in cur[::-1]]
base<<1
return cur1位： [0, 1]
2位： [00, 01, 11, 10]
3位： [000, 001, 011, 010] | [110, 111, 101, 100]
n位的编码可以有n-1位的编码，正序第一位+0 拼接倒序第一位+1 得到