1470. 重新排列数组
难度简单给你一个数组 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. 单词之和
难度中等实现一个 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