响应式网站建设价格,学校网站建设有限公司,wordpress的登入页面,百度学术官网论文查重免费这两个问题的本质就是一个棵树#xff0c;然后根据n对树做剪枝。难点在于剪的时候边界条件有些坑#xff0c;get_lower_largest_digit_dic是这两个题目的共同点
题目一#xff1a; 小于n的最大数
算法题目#xff1a;小于n的最大数 问题描述#xff1a;给一个数组nums[5…这两个问题的本质就是一个棵树然后根据n对树做剪枝。难点在于剪的时候边界条件有些坑get_lower_largest_digit_dic是这两个题目的共同点
题目一 小于n的最大数
算法题目小于n的最大数 问题描述给一个数组nums[5,4,8,2],给一个n5416 让你从nums中选出一些元素使得组成的数字是小于n的最大数比如这个例子应该返回5288 这个题其实就是回溯一步但是讨论的情况有点绕细节可以看代码
class Solution:def get_num(self, candidates, num):max_str str(max(list(candidates)))num_str str(num)def get_lower_largest_digit_dic(candidates):dic{}prev Nonefor i in range(10):dic[str(i)] previf i in candidates:prev str(i)return diclower_largest_digit_dic get_lower_largest_digit_dic(candidates)i,l 0,len(num_str)res_str_arr [0 for i in range(l)]while(il):if int(num_str[i]) in candidates and il-1:# 第一阶段相等的一直往后填res_str_arr[i] num_str[i]i 1else:# 第二阶段遇到最后一个或者没有相等的也分为几种情况统一填为lower_largest_digit然后后面统一填最大digit lower_largest_digit_dic[num_str[i]]while digit None and i 0: #一直找不到一直回溯i - 1digit lower_largest_digit_dic[num_str[i]]# 按照while不成功的情况讨论下if i 0 and digit None and l 1:return Noneif i 0 and digit None and l 1:res_str_arr[0] 0else:res_str_arr[i] digitfor j in range(i1,l):res_str_arr[j] max_strreturn int(.join(res_str_arr))if __name__ __main__:s Solution()print(s.get_num({1,2,9,4}, 2533)) # 2499print(s.get_num({1,2,5,4}, 2543)) # 2542print(s.get_num({1,2,5,4}, 2541)) # 2525print(s.get_num({1,2,9,4}, 2111)) # 1999print(s.get_num({5,9}, 5555)) #999题目二 最大为 N 的数字组合
来自https://leetcode.com/problems/numbers-at-most-n-given-digit-set/
Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits [‘1’,‘3’,‘5’], we may write numbers such as ‘13’, ‘551’, and ‘1351315’.
Return the number of positive integers that can be generated that are less than or equal to a given integer n.
Example 1:
Input: digits [“1”,“3”,“5”,“7”], n 100 Output: 20 Explanation: The 20 numbers that can be written are: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77. Example 2:
Input: digits [“1”,“4”,“9”], n 1000000000 Output: 29523 Explanation: We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers, 81 four digit numbers, 243 five digit numbers, 729 six digit numbers, 2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers. In total, this is 29523 integers that can be written using the digits array. Example 3:
Input: digits [“7”], n 8 Output: 1
Constraints:
1 digits.length 9 digits[i].length 1 digits[i] is a digit from ‘1’ to ‘9’. All the values in digits are unique. digits is sorted in non-decreasing order. 1 n 109
其实和题目一思路很相似但是边界条件容易错
class Solution:def atMostNGivenDigitSet(self, digits: List[str], n: int) - int:def get_lt_digit_cnt_dic(digits_set):dic {}prev 0for i in range(0,10):stri str(i)dic[stri] previf stri in digits_set:prev 1return dicdigits_set set(digits)lt_digit_cnt_dic get_lt_digit_cnt_dic(digits_set)dl len(digits)nl len(str(n))factorial [1 for i in range(nl)]for i in range(1,nl):factorial[i] factorial[i-1]*dlres1 sum(factorial[i] for i in range(1,nl))res2,i 0,0strn str(n)while inl:lt_digit_cnt lt_digit_cnt_dic[strn[i]]res2 lt_digit_cnt * factorial[nl-(i1)]if (strn[i] not in digits_set):breaki1# 这个条件容易漏掉例如digits [3,4,8], n 4if i nl and strn[nl-1] in digits_set:res2 1# print(res1)return res1res2
