电子书网站搭建教程,小程序开发教程视频,深圳工程建设服务网,建设银行软件官方网站下载文章目录 1. 只出现一次的数字算法原理#xff1a;代码#xff1a; 2. 随机链表的复制算法原理#xff1a;代码#xff1a; 3. 宝石与石头算法原理#xff1a;代码#xff1a; 4. 坏键盘打字算法原理#xff1a;代码#xff1a; 5. 前K个高频单词算法原理#xff1a;代… 文章目录 1. 只出现一次的数字算法原理代码 2. 随机链表的复制算法原理代码 3. 宝石与石头算法原理代码 4. 坏键盘打字算法原理代码 5. 前K个高频单词算法原理代码 1. 只出现一次的数字 原题链接 算法原理
这里这需要使用一个哈希表 把所有的元素放入到哈希表中因为哈希表中不能放入重复的元素
代码
class Solution {public int singleNumber(int[] nums) {HashSetInteger set new HashSet();for(int x : nums) {if(!set.contains(x)) {set.add(x);}else {set.remove(x);}}for(int x : nums) {if(set.contains(x)) {return x;}}return -1;}
}2. 随机链表的复制 原题链接 算法原理
我们刚看到题一定很懵但是我们可以画图来看一下什么叫做复制链表 两个链表的结构完全一样但是值不一样 所以我们现在就是看如何让第二个链表和第一个链表展现出来一样的东西
这个时候我们需要一个哈希表来把新节点和老节点放入进去 这样我们在new 新的节点的时候就可以通过一一对应的关系把老节点对应的关系展现出来 这个时候 map.get(cur).next map.get(cur.next) map.get(cur).random map.get(cur.random)
代码
public Node copyRandomList(Node head) {HashMapNode,Node map new HashMap();Node cur head;while (cur ! null) {Node node new Node(cur.val);map.put(cur,node);cur cur.next;}cur head;while (cur ! null) {map.get(cur).next map.get(cur.next);map.get(cur).random map.get(cur.random);cur cur.next;}return map.get(head);}3. 宝石与石头 原题链接 算法原理
先把宝石放到哈希表中 再遍历石头如果哈希表中有这个字母 计数器 最后返回计数器的值
代码
public int numJewelsInStones(String jewels, String stones) {int count 0;HashSetCharacter set new HashSet();for (char ch : jewels.toCharArray()) {set.add(ch);}for (char ch : stones.toCharArray()) {if (set.contains(ch)) {count;}}return count;}4. 坏键盘打字 原题链接 算法原理
要求的输出只输出大写并且只输出一次 这个时候我们先把输入的那一行字母放入到哈希表中 然后再new 一个哈希表 经过对比之后再把坏键盘的字母放入到哈希表中 这样第二个哈希表中的就是要求的值
代码 public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNextLine()) {String str1 in.nextLine();String str2 in.nextLine();func(str1,str2);}}private static void func(String str1,String str2) {HashSetCharacter set new HashSet();for (char ch : str2.toUpperCase().toCharArray()) {set.add(ch);//把可以输出的键都放入了哈希表}HashSetCharacter set2 new HashSet();for (char ch : str1.toUpperCase().toCharArray()) {if (!set.contains(ch) !set2.contains(ch)) {System.out.print(ch);set2.add(ch);}}}5. 前K个高频单词 原题链接 算法原理
先统计单词出现的次数建立小根堆,指定比较的方式遍历map 调整优先级队列
注意在建立小根堆的时候需要考虑到前三个单词次数一样的情况下需要用大根堆来排序
代码
public ListString topKFrequent(String[] words, int k) {//1.统计每个单词出现的次数MapString,Integer map new HashMap();for (String word : words) {if (map.get(word) null) {map.put(word,1);}else {int val map.get(word);map.put(word,val1);}}//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() - o2.getValue();}});//3.遍历map 调整优先级队列for (Map.EntryString,Integer entry : map.entrySet()) {if (minHeap.size() k) {minHeap.offer(entry);}else {Map.EntryString,Integer top minHeap.peek();//如果当前频率相同if (top.getValue().equals(entry.getValue())){//字母顺序小的进来if (top.getKey().compareTo(entry.getKey()) 0) {minHeap.poll();minHeap.offer(entry);}}else {if (top.getValue().compareTo(entry.getValue()) 0) {minHeap.poll();minHeap.offer(entry);}}}}ListString ret new ArrayList();for (int i 0; i k; i) {Map.EntryString,Integer top minHeap.poll();ret.add(top.getKey());}Collections.reverse(ret);return ret;}
