793. 阶乘函数后 K 个零
难度困难 f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。
- 例如，
f(3) = 0，因为3! = 6的末尾没有 0 ；而f(11) = 2，因为11!= 39916800末端有 2 个 0 。
给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
1 class Solution {
2 public int preimageSizeFZF(int k) {
3 // 左边界
4 long l=0L,r=5000000000L;
5 while (l<r){
6 long mid=l+(r-l)/2;
7 if (zeroGet(mid)==k){
8 r=mid;
9 }else if (zeroGet(mid)>k){
10 r=mid;
11 }else{
12 l=mid+1;
13 }
14 }
15 long left=l;
16 // 右边界
17 l=0L;
18 r=5000000000L;
19 while (l<r){
20 long mid=l+(r-l)/2;
21 if (zeroGet(mid)==k){
22 l=mid+1;
23 }else if (zeroGet(mid)>k){
24 r=mid;
25 }else{
26 l=mid+1;
27 }
28 }
29 //System.out.println(l+" "+left);
30 return (int)(l-left);
31 }
32
33 public long zeroGet(long x){
34 long sum=0;
35 long mul=5;
36 while (mul<=x){
37 sum+=x/mul;
38 mul*=5;
39 }
40 return sum;
41 }
42 }
思路：二分查找左右边界。注意左右边界要用LONG。
剑指 Offer II 065. 最短的单词编码
难度中等单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：
words.length == indices.length- 助记字符串
s以'#'字符结尾 - 对于每个下标
indices[i]，s的一个从indices[i]开始、到下一个'#'字符结束（但不包括'#'）的 子字符串 恰好与words[i]相等
给定一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
1 class Solution {
2 static int ans;
3 static int count;
4 public int minimumLengthEncoding(String[] words) {
5 Trie trie = new Trie();
6 for (String word:words){
7 String t=reverse(word);
8 if (!trie.search(t)) trie.addWord(t);
9 }
10 ans=0;
11 count=0;
12 dfs(0,trie);
13 return ans+count;
14 }
15 public String reverse(String w){
16 StringBuilder sb=new StringBuilder();
17 for (int i=w.length()-1;i>=0;i--){
18 sb.append(w.charAt(i));
19 }
20 return sb.toString();
21 }
22 public void dfs(int len,Trie root){
23 if (root.isWord){
24 ans+=len;
25 count++;
26 return;
27 }
28 for (int i=0;i<26;i++){
29 if (root.child[i]!=null) dfs(len+1,root.child[i]);
30 }
31 }
32
33 public static void main(String[] args) {
34 String[] a={"t"};
35 System.out.println(new Solution().minimumLengthEncoding(a));
36 }
37 }
38
39 class Trie{
40 Trie[] child;
41 boolean isWord;
42 Trie(){
43 isWord=false;
44 child=new Trie[26];
45 }
46
47 public void addWord(String word){
48 Trie root=this;
49 for (int i=0;i<word.length();i++){
50 if (root.child[word.charAt(i)-'a']==null){
51 root.child[word.charAt(i)-'a']=new Trie();
52 }
53 root.isWord=false;
54 root=root.child[word.charAt(i)-'a'];
55 }
56 root.isWord=true;
57 }
58
59 public boolean search(String word){
60 Trie root=this;
61 for (int i=0;i<word.length();i++){
62 if (root.child[word.charAt(i)-'a']==null) return false;
63 else root=root.child[word.charAt(i)-'a'];
64 }
65 return true;
66 }
67 }
思路：倒序字典树，统计最长的单词以及数量。
标签：count,2022,offer,int,28,long,words,public,String From： https://www.cnblogs.com/benbicao/p/16632771.html