首页 > 其他分享 >2022-8-29 每日一题-简单模拟-剑指offer-字典树

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

时间:2022-08-29 12:24:25浏览次数:82  
标签:2022 val offer int 29 trie MapSum key public

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

相关文章

  • "蔚来杯"2022牛客暑期多校训练营10 E.Reviewer Assignment
    E.eviewerAssignment题目大意有m篇论文和n个审稿人,给出每个审稿人能审论文的集合,要求给没个审稿人安排一篇论文。令f(i)表示被至少i个审稿人审过的论文数量,要求求出一种......
  • 2022第三届“网鼎杯”网络安全大赛-青龙组 部分WriteUp
    MISC签到题八道网络安全选择题,百度都能搜索到答案,这里如果只知道部分题目答案,可以通过枚举测试fuzz答案,获得flagflag:flag{a236b34b-8040-4ea5-9e1c-97169aa3f43a}REre693......
  • Ps 2022在M1 mac上导出 PNG 格式发生未知错误如何解决?
    Photoshop2022formac在M1上导出PNG时,会提示“发生了未知错误”,即使点击“导出”按钮,导出的图片也是一个空白文件。小编教给大家Ps2021在M1mac上导出PNG格式发......
  • 2022年3月 第一次[脱碳经营EXPO参展
      我司参加了于2022年3月16日至3月18日在东京BigSite举行的第一届脱碳经营EXPO春季展,并借此次能源行业集中亮相的机会展示了由EMS,SmartOM,磷酸铁锂电池,PCS模块,DCDC模块......
  • 2022-08-28 第六小组 高佳誉 学习笔记
    VUE重点定义MVVM设计模式指令思维导图知识点1.定义第三方开发的,基于MVVM设计模式的,渐进式的,纯前端js框架渐进式的:可以逐步在项目中使用vue的部分功能,可以轻松......
  • 周六总结(8-29)
    先说总结:上周抓不到做事节奏、失去编程兴趣,周末可以做的都不想做,只想堕落一天这个周六因为去了老哥家做客,所以在周一早上写总结,这周末其实就是周六去做客、周日一直在家玩......
  • 2022-08-29-Linux C 中connect函数用法及注意事项
    LinuxC中connect函数用法详细介绍及注意事项:C语言connect()函数的函数功能:简单来讲就是:我客户端,自身socket用于和服务端的socket建立socket连线。用于向目的IP和目......
  • 2022 HDU多校5
    PandaemoniumAsphodelos:TheFirstCircle(Savage)(数据结构)Problem有一行长度为\(n\)个格子,一开始每个格子的颜色都是\(0\),并且权值都也是\(0\),现在有\(q\)次操作,每......
  • 2022.8.28 whk 记录
    PrefacePollard-Rho学了800万年模板过不了,AC300没戏了,等AC400叭(高中生活真的好累,一点学OI的时间都没了。只能趁周末水题。Content[CF766E]Mahmoudandaxor......
  • 2022年7月7日周记
    1、本周做了什么:本周我开始学习Python,本周我对Python语言进行了初步的学习,我学习了Python的简介,Python的基本环境。本周我学习了2个小时,因为是初学,没有在代码上花费太多的......