当前位置: 首页 > news >正文

受欢迎的做pc端网站广州网站推广排名

受欢迎的做pc端网站,广州网站推广排名,可以做用户画像的网站,网站只做五周这两个问题的本质就是一个棵树,然后根据n对树做剪枝。难点在于剪的时候边界条件有些坑,get_lower_largest_digit_dic是这两个题目的共同点 题目一: 小于n的最大数 算法题目:小于n的最大数 问题描述:给一个数组nums[5…

这两个问题的本质就是一个棵树,然后根据n对树做剪枝。难点在于剪的时候边界条件有些坑,get_lower_largest_digit_dic是这两个题目的共同点

题目一: 小于n的最大数

算法题目:小于n的最大数
问题描述:给一个数组nums=[5,4,8,2],给一个n=5416, 让你从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(i<l):if int(num_str[i]) in candidates and i<l-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] = '0'else:res_str_arr[i] = digitfor j in range(i+1,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 i<nl:lt_digit_cnt = lt_digit_cnt_dic[strn[i]]res2 += lt_digit_cnt * factorial[nl-(i+1)]if (strn[i] not in digits_set):breaki+=1# 这个条件容易漏掉,例如digits =["3","4","8"], n = 4if i == nl and strn[nl-1] in digits_set:res2 += 1# print(res1)return res1+res2
http://www.dt0577.cn/news/20834.html

相关文章:

  • 遂宁做网站网络推广的方法有哪些
  • wap网站开发和自适应阿里巴巴数据分析官网
  • 网站建设团队介绍哪些网站可以seo
  • 泰安千橙网站建设优化熊掌号色盲测试图片
  • wordpress 分类目录排序长春百度网站优化
  • 网页设计与网站建设实验报告德国搜索引擎
  • 学校网站的平台用途及建设规划网站搜索引擎推广
  • 免费wap网站建设开发网站需要多少钱
  • 免费搭建手机网站十大免费无代码开发软件
  • 织梦 网站无法显示该页面电商
  • 做网站推广都有哪些行业阿里云域名查询和注册
  • 开发大型网站的最主流语言汨罗网站seo
  • 专业建站lhznkj百度收录时间
  • 织梦模板更新网站磁力帝
  • 舟山网站建设seo工具
  • 做it软件的网站企业网站推广建议
  • 如何用文档做网站天津seo顾问
  • 做全网营销型网站建设近期国际新闻
  • 北京建设委网站网站搭建软件
  • 怎么看网站banner尺寸做网站的步骤
  • 线上推广公司排名seo网站推广排名
  • 广州网站设计网站制作营销技巧培训ppt
  • html语言做的网站和asp的区别bt种子磁力搜索
  • 动态网站登录加注册怎么做郑州官网网络营销外包
  • 视频网站怎么做压力测试海淀区seo搜索引擎
  • 网站建设基础ppt互联网广告营销方案
  • 独立商城系统网站建设国际新闻最新消息10条
  • wordpress 文章在数据库seo包年优化平台
  • 内涵吧网站免费搭建网站
  • 哪个网站有上门做指甲鼓楼网页seo搜索引擎优化