2022-8-29 每日一题-简单模拟-剑指offer-字典树

标签：2022 val offer int 29 trie MapSum key public

1470. 重新排列数组

难度简单112收藏分享切换为英文接收动态反馈

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

 1 class Solution {
 2     public int[] shuffle(int[] nums, int n) {
 3         int[] a=new int[2*n];
 4         for (int i=0;i<2*n;i++){
 5             if (i%2==0) a[i]=nums[i/2];
 6             else a[i]=nums[n+i/2];
 7         }
 8         return a;
 9     }
10 }

思路：模拟。

 

剑指 Offer II 066. 单词之和

难度中等22收藏分享切换为英文接收动态反馈

实现一个 MapSum 类，支持两个方法，insert 和 sum：

• MapSum() 初始化 MapSum 对象
• void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
• int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

 1 class MapSum {
 2     Trie root;
 3     static int ans;
 4     /** Initialize your data structure here. */
 5     public MapSum() {
 6         root=new Trie();
 7     }
 8 
 9     public void insert(String key, int val) {
10         root.addWord(key,val);
11     }
12 
13     public int sum(String prefix) {
14         Trie trie=root.search(prefix);
15         if (trie==null) return 0;
16         ans=0;
17         dfs(trie);
18         return ans;
19     }
20     
21     public void dfs(Trie trie){
22         if (trie.isWord) ans+=trie.value;
23         for (int i=0;i<26;i++){
24             if (trie.child[i]!=null) dfs(trie.child[i]);
25         }
26     }
27 }
28 
29 
30 class Trie{
31     Trie[] child;
32     int value;
33     boolean isWord;
34     Trie(){
35         isWord=false;
36         child=new Trie[26];
37         value=0;
38     }
39 
40     public void addWord(String word,int value){
41         Trie root=this;
42         for (int i=0;i<word.length();i++){
43             if (root.child[word.charAt(i)-'a']==null){
44                 root.child[word.charAt(i)-'a']=new Trie();
45             }
46             root=root.child[word.charAt(i)-'a'];
47         }
48         root.isWord=true;
49         root.value=value;
50     }
51 
52     public Trie search(String word){
53         Trie root=this;
54         for (int i=0;i<word.length();i++){
55             if (root.child[word.charAt(i)-'a']==null) return null;
56             else root=root.child[word.charAt(i)-'a'];
57         }
58         return root;
59     }
60 }
61 /**
62  * Your MapSum object will be instantiated and called as such:
63  * MapSum obj = new MapSum();
64  * obj.insert(key,val);
65  * int param_2 = obj.sum(prefix);
66  */

思路：字典树存储，加个value，计算sum的时候先找到前缀再dfs。

标签：2022,val,offer,int,29,trie,MapSum,key,public
From： https://www.cnblogs.com/benbicao/p/16635537.html