10.13 21. 1位重复数字
给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数的个数。
输入：20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
输入：100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
输入：1000
输出：262
最优解
public int numDupDigitsAtMostN(int N) {
return N - dp(N);
}
public int dp(int n) {
List<Integer> digits = new ArrayList<>();
while (n > 0) {
digits.add(n % 10);
n /= 10;
}
// k代表k的位数
// 设剩下的位置为i，剩下的数字为j，则不重复数字是在每一位依次填入与前几位不同的数字，
// 即选取剩下的j个数字填入剩下的i个位置，即有A(j, i)种可能，最后将其累加就是不重复数字个数
int k = digits.size();
int[] used = new int[10];
int total = 0;
// 求位数小于k的不重复数字的个数：因为最高位总是为0，
// 因此一开始剩下的数字j总是为9个（1-9），然后剩下的低位可选的数字总共有A(10-1,i)
for (int i = 1; i < k; i++) {
total += 9 * A(9, i - 1);
}
// 位数等于k
for (int i = k - 1; i >= 0; i--) {
int num = digits.get(i);
for (int j = i == k - 1 ? 1 : 0; j < num; j++) {
if (used[j] != 0) {
continue;
}
total += A(10 - (k - i), i);
}
if (++used[num] > 1) {
break;
}
if (i == 0) {
total += 1;
}
}
return total;
}
public int fact(int n) {
if (n == 1 || n == 0) {
return 1;
}
return n * fact(n - 1);
}
public int A(int m, int n) {
return fact(m) / fact(m - n);
}
总结
为什么要用反证法：可以用公式计算比较方便，排列组合。分情况讨论，一种是高位为0，一种是高位不为0.
10.14 22. 找不同
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 *t* 由字符串 *s* 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母
输入：s = "", t = "y"
输出："y"
思路
用collections.Count统计各个字幕出现的次数，找出多的那一个。
我的解
class Solution:
@classmethod
def findTheDifference(self, s: str, t: str) -> str:
from collections import Counter
counter_1 = Counter(t)
counter_1.subtract(s)
for k,v in counter_1.items():
if v == 1:
return k
10.14 23. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false
思路
双指针算法
最优解
class Solution:
@classmethod
def isSubsequence(self, s: str, t: str) -> bool:
len_s = len(s)
len_t = len(t)
i = j = 0
while i < len_s and j < len_t:
if s[i] == t[j]:
i += 1
j += 1
return i == len_s
总结
利用双指针来判断子序列，切忌用遍历。
10.15 24. 在排序数组中查找元素第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
思路
双指针，分别从前后逐个遍历。
我的解
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) == 0:
return [-1, -1]
if len(nums) == 1:
if nums[0] == target:
return [0,0]
i = 0
j = len(nums) - 1
res = [-1] * 2
while i < len(nums) and i != j:
if nums[i] == target:
res[0] = i
while nums[j] != target:
j -= 1
res[-1] = j
return res
else:
i += 1
if i == j and nums[i] == target:
return [i,j]
return res
优化
class Solution:
def searchRange(self, nums, target):
# find the index of the leftmost appearance of `target`. if it does not
# appear, return [-1, -1] early.
for i in range(len(nums)):
if nums[i] == target:
left_idx = i
break
else:
return [-1, -1]
# find the index of the rightmost appearance of `target` (by reverse
# iteration). it is guaranteed to appear.
for j in range(len(nums)-1, -1, -1):
if nums[j] == target:
right_idx = j
break
return [left_idx, right_idx]
最优解
class Solution:
# returns leftmost (or rightmost) index at which `target` should be inserted in sorted
# array `nums` via binary search.
def extreme_insertion_index(self, nums, target, left):
lo = 0
hi = len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > target or (left and target == nums[mid]):
hi = mid
else:
lo = mid+1
return lo
def searchRange(self, nums, target):
left_idx = self.extreme_insertion_index(nums, target, True)
# assert that `left_idx` is within the array bounds and that `target`
# is actually in `nums`.
if left_idx == len(nums) or nums[left_idx] != target:
return [-1, -1]
return [left_idx, self.extreme_insertion_index(nums, target, False)-1]
总结
因为题设排序数组，即可以使用二分法查找。
10.18 25. 超级丑数
编写一段程序来查找第 *n* 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
思路
见下一题思路
我的解
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
pointer_list = [0] * len(primes)
res = [0] * n
res[0] = 1
for i in range(1, len(res)):
res[i] = min(primes[j] * res[pointer_list[j]] for j in range(len(primes)))
for index, value in enumerate(primes):
if res[i] == value * res[pointer_list[index]]:
pointer_list[index] += 1
return res[-1]
10.18 26. 下一个丑数
编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
最优解
解法一：动态规划
此题丑数就是2，3，5的排列组合所能组成的公倍数由小到大排成的数组
class Solution:
@classmethod
def nthUglyNumber(self, n: int) -> int:
i2 = i3 = i5 = 0
dp = [0] * n
dp[0] = 1
for i in range(1, len(dp)):
dp[i] = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
if dp[i] == dp[i2] * 2:
i2 += 1
if dp[i] == dp[i3] * 3:
i3 += 1
if dp[i] == dp[i5] * 5:
i5 += 1
return dp[-1]
if __name__ == '__main__':
res = Solution.nthUglyNumber(10)
print(res)
解法二：堆算法
from heapq import heappop, heappush
class Ugly:
def __init__(self):
seen = {1, }
self.nums = nums = []
heap = []
heappush(heap, 1)
for _ in range(1690):
curr_ugly = heappop(heap)
nums.append(curr_ugly)
for i in [2, 3, 5]:
new_ugly = curr_ugly * i
if new_ugly not in seen:
seen.add(new_ugly)
heappush(heap, new_ugly)
class Solution:
u = Ugly()
def nthUglyNumber(self, n):
return self.u.nums[n - 1]
总结
丑数的定义要明确，是所给质因子公倍数的排序数组。