网站域名缴费,wordpress搭建数据库,2018年公司做网站注意事项,八戒网站做推广【java数据结构】HashMapOJ练习题 一、只出现一次的数字二 、随机链表的复制三 、宝石与石头四、坏键盘打字五、前K个高频单词 博客最后附有整篇博客的全部代码#xff01;#xff01;#xff01; 一、只出现一次的数字
只出现一次的数字 思路#xff1a;
先遍历一遍数组… 【java数据结构】HashMapOJ练习题 一、只出现一次的数字二 、随机链表的复制三 、宝石与石头四、坏键盘打字五、前K个高频单词 博客最后附有整篇博客的全部代码 一、只出现一次的数字
只出现一次的数字 思路
先遍历一遍数组将所有元素全部存到HashMap集合中再遍历一遍数组获取每个值对应的values值判断是否等于1
代码 public int singleNumber(int[] nums) {HashMapInteger,Integer hashMapnew HashMap();for(int i0;inums.length;i){if(hashMap.containsKey(nums[i])){hashMap.put(nums[i],hashMap.get(nums[i])1);}else{hashMap.put(nums[i],1);}}for(int i0;inums.length;i){if(hashMap.containsKey(nums[i])){if(hashMap.get(nums[i])1){return nums[i];}}}return -1;}二 、随机链表的复制
随机链表的复制 思路
定义HashMap来存储新老节点的映射关系再遍历一遍然后通过老节点的map.get().next和map.get().random获得新节点的next和random最后再通过老节点的map.get(cur.next)和map.get(cur.random)映射出应赋值给新节点的next和random的值 map.get(cur).next map.get(cur.next); map.get(cur).random map.get(cur.random); 代码 public Node copyRandomList(Node head) {Node cur head;HashMapNode, Node map new HashMap();while (cur ! null) {Node newNode new Node(cur.val);map.put(cur,newNode);cur cur.next;}curhead;while (cur ! null) {map.get(cur).next map.get(cur.next);map.get(cur).random map.get(cur.random);curcur.next;}return map.get(head);}三 、宝石与石头
宝石与石头 思路
现将字符串转化为字符数组将石头的每个字符存储进HashMap中然后遍历宝石如果HashMap中存在宝石通过map.get()获取values值进行count最后返回count。
代码 public int numJewelsInStones(String jewels, String stones) {char[] jewelChars jewels.toCharArray();//宝石char[] stonesChars stones.toCharArray();//石头int count 0;HashMapCharacter,Integer mapnew HashMap();for(int i 0; i stonesChars.length; i){if(map.containsKey(stonesChars[i])){map.put(stonesChars[i],map.get(stonesChars[i])1);}else{map.put(stonesChars[i],1);}}for(int i 0; ijewelChars.length; i){if(map.containsKey(jewelChars[i])){countmap.get(jewelChars[i]);}}return count;}四、坏键盘打字
坏键盘打字 思路
将所有的字符串全部进行大写转化将输出的字存储进HashMap的map1集合中遍历打印的字并且只要求输出一遍我们将出现过的字符可以重新放到一个HashMap的map2集合中判断map1和map2两个如果都不包含则进行打印。
代码 public static void main(String[] args) {Scanner sc new Scanner(System.in);String str1 sc.nextLine();String str2sc.nextLine();faultyKeyboard(str1,str2);}public static void faultyKeyboard(String str1,String str2){String str3str1.toUpperCase();String str4str2.toUpperCase();char[] str5str3.toCharArray();char[] str6str4.toCharArray();HashMapCharacter,Integer map1new HashMap();HashMapCharacter,Integer map2new HashMap();for (int i 0; i str6.length; i) {if(map1.containsKey(str6[i])){map1.put(str6[i],map1.get(str6[i])1);}else{map1.put(str6[i],1);}}for(int i0;istr5.length;i){if(!map1.containsKey(str5[i])!map2.containsKey(str5[i])){map2.put(str5[i],1);System.out.print(str5[i]);}}}五、前K个高频单词
前K个高频单词 思路
将每个单词存储进HashMap的map集合建立小根堆在未建立好K大小的小根堆的时候这个时候如果遇到频率相同的单词需要j建立成大根堆遍历map先建立好k个大小的小跟堆堆顶元素小于入堆元素则插入入堆元素堆顶元素等于入堆元素则判断单词大小小的入堆
代码 public ListString topKFrequent(String[] words, int k) {HashMapString, Integer map new HashMap();for (String word : words) {map.put(word, map.getOrDefault(word, 0) 1);}//2. 建立小根堆PriorityQueueMap.EntryString,Integer minHeap new PriorityQueue(new ComparatorMap.EntryString, Integer() {Overridepublic int compare(Map.EntryString, Integer o1, Map.EntryString, Integer o2) {if(o1.getValue().compareTo(o2.getValue()) 0) {return o2.getKey().compareTo(o1.getKey());}return o1.getValue().compareTo(o2.getValue());}});//3.遍历mapfor(Map.EntryString,Integer entry : map.entrySet()) {if(minHeap.size() k) {minHeap.offer(entry);}else {Map.EntryString,Integer top minHeap.peek();if(top.getValue().compareTo(entry.getValue()) 0) {minHeap.poll();minHeap.offer(entry);}else if(top.getValue().compareTo(entry.getValue()) 0) {if(top.getKey().compareTo(entry.getKey()) 0) {minHeap.poll();minHeap.offer(entry);}}}}ArrayListString list new ArrayList();for (int i 0; i k; i) {Map.EntryString,Integer tmp minHeap.poll();list.add(tmp.getKey());}Collections.reverse(list);return list;}此篇博客的全部代码
