秋招突击——7/22——复习{堆——前K个高频元素}——新作{回溯——单次搜索、分割回文串。链表——环形链表II，合并两个有序链表}

引言

• 又是充满挑战性的一天，继续完成我们的任务吧！继续往下刷，一场面试三个构成：八股、项目和算法，都得抓住！加油
• 今天复习一下堆，然后把回溯剩下的题目全部做完，然后的继续往下做链表！

复习

堆

• 对顶堆——数据流的中位数
  • front是大顶堆，back是小顶堆

堆——前K个高频元素

• 题目链接
• 第一次练习链接
• 第二次练习链接
• 虽然已经做了两次，但是一点都想不起来应该怎么做！

个人实现

• 这道题可以通过设置不同的数据结构实现，通过key-value改变记录每一个数字出现的频率，然后通过PriorityQueue来实现根据频率进行排序，这样效率就快很多！那么怎么实现自定义排序就很重要！

class Solution {class Item implements Comparable<Item>{int val;int freq;Item(int value,int frequency){val = value;freq = frequency;}// override the compareTo function@Overridepublic int compareTo(Item o){return Integer.compare( this.freq,o.freq);}}public int[] topKFrequent(int[] nums, int k) {// define map to store the key-value item ,priorityqueue to sort the itemPriorityQueue<Item> pq = new PriorityQueue<>(Comparator.reverseOrder());Map<Integer,Item> map = new HashMap<>();// traverse all the elementsfor(int x :nums){if(map.containsKey(x)){Item temp = map.get(x);temp.freq = temp.freq + 1;System.out.println(map.get(x).freq);}else{Item temp = new Item(x,1);map.put(x,temp);pq.add(temp);}}// traverse the front k elementsint[] res = new int[k];//System.out.println(pq.peek().val);for(int i = 0;i < k;i ++)res[i] = pq.poll().val;return res;}
}

问题

• 如何重写对象compare方法
  • 要实现Comparable接口
  • compareTo方法是接受当前类型的变量，进行的比较
  • compareTo方法，返回的是一个int类型的变量
  • 实现comparable接口，需要实现compareTo方法

class Item implements Comparable<Item> {int val;int freq;Item(int value, int frequency) {val = value;freq = frequency;}// override the compareTo function@Overridepublic int compareTo(Item o) {return Integer.compare(o.freq, this.freq); // descending order}
}

• 致命问题！！PriorityQueue并不会自动重新排序！需要每次更新都要插入和删除对应的元素，不然会出问题！

复习实现二

• 这里不知道自己着了什么魔，这个题目为啥要想的那么复杂，不就是先统计频率，然后再根据频率进行排序吗？为什么要想那么多！

class Solution {class Item implements Comparable<Item>{int val;int freq;Item(int value,int frequency){val = value;freq = frequency;}// override the compareTo function@Overridepublic int compareTo(Item o){return Integer.compare( this.freq,o.freq);}}public int[] topKFrequent(int[] nums, int k) {// define map to store the key-value item ,priorityqueue to sort the itemPriorityQueue<Item> pq = new PriorityQueue<>(Comparator.reverseOrder());Map<Integer,Item> map = new HashMap<>();// traverse all the elementsfor(int x :nums){if(map.containsKey(x)){Item temp = map.get(x);temp.freq = temp.freq + 1;}else{map.put(x,new Item(x,1));}}// traverse the values int the for(Item x:map.values()){pq.add(x);}// traverse the front k elementsint[] res = new int[k];//System.out.println(pq.peek().val);for(int i = 0;i < k;i ++)res[i] = pq.poll().val;return res;}
}

问题

• 这里Map的相关方法使用起来还是带有试验的性质，很多方法当时写了就错了，编译器提醒没有这种方法，才知道应该换！这里再复习一遍！
• 加入元素：
  • put(K key,V value)
  • 如果存在旧值，会将其替换
  • 注意，没有set方法，那是list才有的
• 获取对应的value
  • get(Object key)
  • 如果不含有对应的key，就返回null
• 删除对应的元素
  • remove(Object key)
• 判定是否含有对应的元素
  • containsKey（Obejct key）
  • 是containsKey，contains是Set的方法
• 判定是否为空
  • isEmpty
  • 不是Empty，每次都写错
• 获取所有value
  • values
  • 这里是返回所有的values，不是valueset
• 获取所有的key
  • keySet
  • 不是keys

参考实现

使用计数排序

• 将所有出现的频次记录在对应的数组中，然后根据索引进行遍历，减少遍历的时间！

这里就不记录了，如果感兴趣，就自己去看！

限定堆使用的大小

• 如果直接将所有的元素加入到堆中进行排序，需要消耗很多时间，这里只要前K个元素，所以只需要维护一个大小为K的堆就行了！

class Solution {class Item implements Comparable<Item>{int val;int freq;Item(int value,int frequency){val = value;freq = frequency;}// override the compareTo function@Overridepublic int compareTo(Item o){return Integer.compare( this.freq,o.freq);}}public int[] topKFrequent(int[] nums, int k) {// define map to store the key-value item ,priorityqueue to sort the itemPriorityQueue<Item> pq = new PriorityQueue<>();Map<Integer,Item> map = new HashMap<>();// traverse all the elementsfor(int x :nums){if(map.containsKey(x)){Item temp = map.get(x);temp.freq = temp.freq + 1;}else{map.put(x,new Item(x,1));}}// traverse the values int the for(Item x:map.values()){if(pq.size() < k)pq.add(x);else{if(pq.peek().freq < x.freq){pq.poll();pq.add(x);}}}// traverse the front k elementsint[] res = new int[k];//System.out.println(pq.peek().val);for(int i = 0;i < k;i ++)res[i] = pq.poll().val;return res;}
}

新作

单词搜索

题目链接

注意

• 整个二维矩阵的大小可能是一个单元格，仅仅只有一个字母，可能是边界情况需要特殊处理。
• 目标单词的长度是遍历的深度，也就是遍历树的高度，然后上下左右是四个方向，是每一层遍历的宽度。

个人实现

• 这道题是典型的回溯，回溯的要素设定如下
  • idx 界限值是 单词的长度
  • 每一层遍历的宽度是上下左右四个方向
  • 需要维护一个exist数组，标记每一个元素的访问情况。

class Solution {// define the global string to store the mid situationStringBuilder str = new StringBuilder();// exist matrix to store the attendenceboolean[][] exist ;//boolean res = false;int[][] step = {{1,0},{0,1},{-1,0},{0,-1}};boolean dfs(char[][] board,String word,int idx,int x,int y){if(idx == word.length()){return true;}for(int i = 0;i < 4;i ++){int xNext = x + step[i][0];int yNext = y + step[i][1];if(xNext >= 0 && xNext < board.length ){if(yNext >= 0 && yNext < board[0].length){if(!exist[xNext][yNext] && board[xNext][yNext] == word.charAt(idx)){exist[xNext][yNext] = true;if(dfs(board,word,idx + 1,xNext,yNext)) return true;exist[xNext][yNext] = false;}}}}return false;}public boolean exist(char[][] board, String word) {//define row and col of the matrixint row = board.length;int col = board[0].length;exist = new boolean[row][col];// traverse the board to find the first charfor(int i = 0;i < board.length;i ++){for(int j = 0;j < board[0].length;j ++){if(board[i][j] == word.charAt(0)){//System.out.println("first " + board[i][j]);exist[i][j] = true;if(dfs(board,word,1,i,j)) return true;exist[i][j] = false;}}}return false;}
}

代码量真多，不过还是在规定时间内完成了！

参考实现

这里可以将融合到原来的数组中，通过修改特殊的字符，然后判定当前位置是否已经访问过！

分割回文串

题目链接

注意

• 回文串，逆序和顺序都是一样的
• 仅由小写字母构成，不用担心字母大小写变换
• 长度是1到16，可能有边界情况需要特殊考虑！

个人实现

• 这道题是一个组合体，找到所有的组合，然后在判断一下，是否是回文就行了。
• 总结一下回溯的几个要素
  • 树的深度：总的元素数量
  • 节点的宽度：每一个节点放或者不放两种情况。

错误！！这里审错题目了！是分割字符串，应该然后分割之后每一个字串都是回文

• 修改一下回溯的几个要素
  • 树的深度：分割的位置，总的元素数减一，每一个元素都有一个分割点
  • 节点的宽度：是否在当前点进行分割

class Solution {List<String> list = new ArrayList();List<List<String>> res = new ArrayList<>();boolean judge(String str){str = str.trim();StringBuilder sb = new StringBuilder(str);sb.reverse();return str.equals(sb.toString());}void dfs(StringBuilder s,int idx,int len){if(idx == len ){if(judge(s.toString())){list.add(s.toString());res.add(new ArrayList(list));list.remove(list.size() - 1);}return;}// cutint subIdx = len - s.length();String temp = s.substring(0,idx - subIdx);//System.out.print("idx:" + idx + "  temp:" + s.substring(0,idx - subIdx));if(judge(temp)){list.add(temp);//System.out.println("  subtemp:" + s.substring(idx - subIdx));dfs(new StringBuilder(s.substring(idx - subIdx)),idx + 1,len);list.remove(list.size() - 1);}// not cutdfs(s,idx + 1,len);}public List<List<String>> partition(String s) {dfs(new StringBuilder(s),1,s.length());return res;}
}

问题

• StringBuilder获取子串是substring，没有大写，而且也没有简称，不是subString，不是subStr ，都不是！！是substring

  • substring(strat_idx）:从start_idx到末尾
  • substring(start_idx,end_idx):从start_idx到end_idx这段子串 ,不包括end_idx,相当于在end_idx前面一个字符做的分割点

• String去除空格

  • str.trim()去除前后空格
  • str.replace（" “,”"）;
  • 正则表达式replaceAll(“\s+”, “”)

• 我这里回溯的角度可能有问题，导致时间上有很多耗费！

参考实现

暴力搜索 + 迭代优化

暴力搜索

• 这里举得是区间长度，也就是区间起点，然后列举区间的终点，不同于我们列举每一个分割点！
• 迭代深度
  • 每一区间的起点的位置
• 单次迭代的宽度
  *

迭代优化

• 利用了回文字符串的中间子串也一定是回文字符串的特性，具体如下图！

for(int j = 0;j < n;j ++){for(int i = 0;i <= j;i ++){if(i == j)	f[i][j] = true;else if(s[i] == s[j]){if(i + 1 > j -1 || f[i + 1][j - 1])	f[i][j] = true;}}
}

具体实现代码

class Solution {boolean[][] f;List<String> list = new ArrayList();List<List<String>> res = new ArrayList<>();void dfs(String s,int idx){int m = s.length();if(idx == m){res.add(new ArrayList(list));return ;}for(int i = idx ;i < m; i++){if(f[idx][i]){//System.out.println("idx:" + idx + " i" + i + " substr:"+s.substring(idx,i+1));list.add(s.substring(idx,i + 1));dfs(s,i+1);list.remove(list.size() - 1);}}}public List<List<String>> partition(String s) {int m = s.length();f = new boolean[m][m];for(int j = 0;j < m;j ++){for(int  i = 0;i <= j;i ++){if(i == j)  f[i][j] = true;else if(s.charAt(i) == s.charAt(j)){if(i + 1 > j - 1 || f[i + 1][j - 1])    f[i][j] = true;}}}dfs(s,0);return res;}
}

确实更快，那个回文推导的得稍微记一下！

环形链表II

• 题目连接
  
  
  注意
• pos表示-1或者有效索引
• 不用担心数字越界
• 空间复杂度要求是O（1）

个人实现

• 这个明显是用快慢指针，首先判定是否有环，然后在有环的情况下，判定出对应环的起始点！
• 难点在第二步，不过感觉这个环的起始点，之前好像做过。感觉快慢节点在有环的情况下，应该有特殊情况！

这里还是不知道怎么推导出来的，这题挂了！

如果不强制要求空间复杂度的话，只需要一次遍历就能实现！

这里就不写了，没什么意思！

参考实现

• 这里推导的比较绕，我看了很多遍，总结起来就是一句话
  • 快慢指针相遇的地方，和链表的头节点分别同时触发一个速度为1的节点遍历，相遇点就是入点

先套一个快慢指针的模板

while(f != null){f = f.next;s = s.next;if(f == null)	return false;f = f.next;if(f == s)	return true;
}

最终实现代码

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null)   return null;ListNode s = head;ListNode f = head.next;// judge whether contains circlewhile(f != null){f = f.next;s = s.next;if(f == null)   return null;f = f.next;if(f == s){s = head;f = f.next;while(s != f)   {s = s.next;f = f.next;}return s;}}return null;}
}

两个有序链表

• 题目链接
  
  
• 第一次练习连接

个人实现

• 这个题目第二次做了，而且是个简单题，直接遍历就行了

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head1 = list1;ListNode head2 = list2;ListNode dummy = new ListNode();ListNode temp = dummy;while(head1 != null && head2 != null){if(head1.val < head2.val){temp.next = head1;head1 = head1.next;temp = temp.next;}else{temp.next = head2;head2 = head2.next;temp = temp.next;}}temp.next = (head1 == null ? head2:head1);return dummy.next;}
}

题目很简单，但是让我想到了某一次字节的面试，面试官觉得我代码写的太差了，那道题是一个大数加法，使用链表表示的，我最后写的太差了！毕竟我已经换了三道题，感觉完蛋了！

总结

• 今天状态不得行，刷到了第三题，我就厌烦的不行，不过还是得调整一下！
• 真的是，每天刷题，刷的恶心，恶心的不行！后续还是得加油！
• 又搞到好晚，我要睡了！
• 明天面试百度，加油！