本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
Q1. 找到最近的人
解题思路
条件判断
示例代码
python
class Solution:
def findClosest(self, x: int, y: int, z: int) -> int:
a = abs(x - z)
b = abs(y - z)
if a == b:
return 0
elif a < b:
return 1
return 2Q2. 最小回文排列 I
解题思路
排序
示例代码
python
class Solution:
def smallestPalindrome(self, s: str) -> str:
cnt = Counter(s)
odd = ''
for k, v in cnt.items():
if v % 2:
odd = k
cnt[k] = v // 2
ans = ''
for k in sorted(cnt.keys()):
ans += k * cnt[k]
return ans + odd + ans[::-1]Q3. 最小回文排列 II
解题思路
数学，枚举第 k 个不同字典序的字符串，试填法，用组合数计算当前可能的字符串；剪枝，特判最值跳出
示例代码
python
from math import comb
comb = cache(comb)
class Solution:
def smallestPalindrome(self, s: str, k: int) -> str:
n = len(s) // 2
cnt = [0] * 26
ans = []
for c in s[: n]:
cnt[ord(c) - 97] += 1
def cal(cnt):
total = sum(cnt)
res = 1
for v in cnt:
res *= comb(total, v)
total -= v
if res > 10 ** 6:
return 10 ** 6
return res
for _ in range(n):
for i in range(26):
if cnt[i] == 0:
continue
cnt[i] -= 1
p = cal(cnt)
if k <= p:
ans.append(ascii_lowercase[i])
break
else:
k -= p
cnt[i] += 1
if len(ans) < n:
return ''
if len(s) % 2:
ans.append(s[n])
return ''.join(ans + ans[: n][::-1])Q4. 统计逐位非递减的整数
解题思路
数位 dp，进制转化一下，秒了
示例代码
python
class Solution:
def countNumbers(self, l: str, r: str, b: int) -> int:
def transfer(s: str):
x = int(s)
res = []
while x > 0:
x, r = divmod(x, b)
res.append(r)
return res[::-1]
@lru_cache(None)
def dfs(i: int, limit_low: bool, limit_high: bool, pre: int) -> int:
if i == len(high):
return 1
res = 0
lo = low[i] if limit_low else 0
hi = high[i] if limit_high else b - 1
for d in range(max(lo, pre), hi + 1):
res += dfs(i + 1, limit_low and d == lo, limit_high and d == hi, d)
res %= mod
return res
mod = 10 ** 9 + 7
low, high = transfer(l), transfer(r)
n = len(high)
diff = n - len(low)
low = [0] * diff + low
ans = dfs(0, True, True, 0)
dfs.cache_clear()
return ans