最近因为考试耽搁了几天刷题，首先介绍下面这道题，这是有关图的问题：
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.Each transformed word must exist in the word list. Note that beginWord is not a transformed word.Note:
Return 0 if there is no such transformation sequence.All words have the same length.All words contain only lowercase alphabetic characters.You may assume no duplicates in the word list.You may assume beginWord and endWord are non-empty and are not the same.Example 1:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] Output: 5 Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.
Example 2:
Input: beginWord = “hit” endWord = “cog” wordList = [“hot”,“dot”,“dog”,“lot”,“log”] Output: 0 Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
下面是我的代码：
public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (wordList.size() == 0) return 0; LinkedList<String> queue = new LinkedList(); // 这个用来存适合的串 LinkedList<Integer> levels = new LinkedList<>(); // 这个用来存层数 levels.offer(1); //初始时设置层数为1 queue.offer(beginWord); //初始把最开始的串放进去 while (!queue.isEmpty()) { String peak = queue.poll(); Integer level = levels.poll(); if (peak.equals(endWord)) return level; for (int i = 0; i < peak.length(); i++) { char[] p = peak.toCharArray(); // 这个串的每一个位置换一个字母，如果得到了wordlist，就继续放入队列中 for (char ch = 'a'; ch <= 'z'; ch++) { p[i] = ch; String xp = String.valueOf(p); if (wordList.contains(xp)) { queue.offer(xp); levels.offer(level + 1); // 记录层数 wordList.remove(xp); //并且去掉wordlist中的那个 } } } } return 0; }额！！很遗憾！ 提交后： 先说一下思路：这个是个BFS类的问题，我们从beginword开始，每次换一个字母看看是否换完之后，是否在wordlist中，如果在里面，就继续放入队列中，并把wordlist中的去掉，防止闭环，并且记录层数，达到BFS的目的，直到换完得到endword，此时，返回层数，得到最短路径。理论上来说，这是没问题的！！！但是超时了！！！，我正在想还有什么优化的方法。
------------------------------分割线-------------这是一年后---------------------------------------------------------
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { if(endWord.equals(beginWord)) return 0; HashMap<String,Integer> map = new HashMap<>(); for(String word: wordList) map.put(word, 1); if(!map.containsKey(endWord)) return 0; Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); int cur = 1, nexts = 0; int step = 0; boolean mark = false; while(!queue.isEmpty()){ String u = queue.poll(); cur--; if(u.equals(endWord)){ mark = true; break; } char[] ch = u.toCharArray(); for(int i = 0; i<ch.length; i++){ char t = ch[i]; for(int j = 0; j<26; j++){ ch[i] = (char)(j+97); if(ch[i] == t) continue; String rr = new String(ch); if(map.containsKey(rr)){ map.remove(rr); queue.offer(rr); nexts++; } } ch[i] = t; } if(cur == 0){ step++; cur = nexts; nexts = 0; } } if(!mark) return 0; return step+1; } }我还是AC了，也还是用的BFS
下面是一个优先队列的问题：
Given a non-empty array of integers, return the k most frequent elements. Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.这里不只是TreeMap进行改装，也是能实现的，对TreeMap的值进行倒排，然后输出。这个问题知道其原理，但是我在用java实现的时候，出现几处无法修复的错，可能是现阶段还是不能熟练使用优先队列。对于347，还是会二刷。
下面再来一个hard级别的优先队列题目：题目传送门 ，当然这道题不一定要用优先队列求解，还有其它的办法。
题目描述如下： 通过这道题目，我主要是学会了如何自定义优先队列，也就是如何指定优先队列的排序规则，比如说是大堆，小堆，或者你指定某个属性进行排序，这题中，我指定的其实就是ListNode中的val进行排序。
class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode head = new ListNode(-1); head.next = null; ListNode dup = head; PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { //指定从小到大进行排 return o1.val - o2.val; } }); for(int i = 0; i<lists.length; i++){ if(lists[i] != null) priorityQueue.offer(lists[i]); } while(!priorityQueue.isEmpty()){ ListNode node = priorityQueue.poll(); if(node.next != null) priorityQueue.offer(node.next); dup.next = node; dup = dup.next; } return head.next; } }首先把所有的链表中首节点放入优先队列中，然后出列第一个节点，放入链表中，根据排序规则，第一个节点应该是val最小的，第一个节点出来后，把第一个节点的next节点继续放入优先队列中，重新进行建堆，最后队列为空，表示过程结束了。链表采用尾插法插入建立。 这个时间应该是一般般，只超过76.42% 的提交。应该有更好的优化方法，后面学习过程中再想想怎么优化。
----------------------------------------------------------------------.2020-12.1----------------------------------------------------------------- 补充一道打卡题： 用暴力没有AC，后来评论区看到有人用堆，惭愧😓，没有想到这么好的解法：
class Solution { public String reorganizeString(String S) { int len = S.length(); if(len == 0) return ""; int[] count = new int[26]; char[] ch = S.toCharArray(); for(char c: ch) count[c-'a'] ++; PriorityQueue<Character> priorityQueue = new PriorityQueue<>((a, b)->count[b-'a']-count[a-'a']); for(char c: ch){ if(!priorityQueue.contains(c)){ priorityQueue.offer(c); } } Character before = priorityQueue.poll(); count[before-'a']--; if(count[before-'a'] > 0) priorityQueue.offer(before); String res = ""+before; while(!priorityQueue.isEmpty()){ Character c = priorityQueue.poll(); if(c == before && priorityQueue.isEmpty()) return ""; else if(c == before){ Character d = priorityQueue.poll(); res += d; count[d-'a']--; if(count[d-'a'] > 0) priorityQueue.offer(d); priorityQueue.offer(c); before = d; }else{ res += c; count[c-'a']--; if(count[c-'a'] > 0) priorityQueue.offer(c); before = c; } } return res; } }按照字母频率从大到小构建堆，频率第一大的和第二大的两两合并，先消耗完它们，按照频率从大到小依次消耗，用到了贪心的思想
