面试复习之基础数据结构与算法第二篇
一、堆
1.Priority Queue是堆数据结构的代表
Priority Queue，优先级队列，正常入队，按照优先级出队。
2.Priority Queue的两种实现机制：
Heap：二叉堆(大顶堆、小顶堆)，二项堆，斐波那契小顶堆，值小的始终排在前面，堆顶是最小值大顶堆，值大的始终排在前面，堆顶是最大值Binary Search Tree
3.Heap不同实现的算法复杂度
4.返回数据流中第K大元素？
思路1：记录前K大元素，每次对记录的元素排序
N个元素，每个元素计算一次，复杂度是O(N)K个元素快速排序，复杂度是O(K * log K)算法的复杂度是O(N * K * log K)
思路2：利用优先级队列，小顶堆，最小元素(即第K大元素)始终在堆顶
/*** N个元素，每个元素计算一次，复杂度是O(N)* K个元素快速排序及堆顶比较，复杂度是O(log2 k)* 算法的复杂度是O(N * log2 K)*/class KthLargest {private PriorityQueue<Integer> priorityQueue;private int k;public KthLargest(int k, int[] nums) {//利用小顶堆(Java默认实现)priorityQueue = new PriorityQueue<>(k);this.k = k;//遍历数组把num加入for (int num : nums) {add(num);}}public int add(int num) {if (priorityQueue.size() < k){//加入元素到小顶堆priorityQueue.offer(num);}else if(priorityQueue.peek() < num){//如果小顶堆的堆顶元素值 < numpriorityQueue.poll();priorityQueue.offer(num);}else{//返回第k大元素，即小顶堆的堆顶return priorityQueue.peek();}}
5.计算滑动窗口中最大值？
思路1：优先级队列，大顶堆，最大元素始终在堆顶
维护Max Heap，时间复杂度是O(log k)查询堆顶，时间复杂度是O(1)算法复杂度是O(N * log K)
思路2：双端队列
/*** 输入* nums [1,3,-1,-3,5,3,6]* k = 3* 输出(每次计算连续的k个元素最大值)* [3,3,5,5,6]** 特征分析，每次滑动后，可以放弃左侧已经计算过的部分* N个元素入队，时间复杂度是O(N)* 保持队列左侧永远是最大值* 新元素入队维护，时间复杂度是O(N)* 算法复杂度是O(N * log K)*/public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length == 0) {return new int[0];}//保存数组元素的下标Deque<Integer> window = new ArrayDeque<>();//计算结果int[] result = new int[nums.length - k + 1];for(int i = 0; i < nums.length; i++) {//从k开始，window.peek()查询队首元素//删除队列中小于窗口左边下标的元素if(i >= k && window.peek() <= i - k) {//移除队首元素window.remove();}//新入队元素nums[i]//从队列右侧开始，删除小于nums[i]的元素while(!window.isEmpty() && nums[window.peekLast()] < nums[i]){window.removeLast();}window.add(i);//队列左侧是最大值，加入结果if(i >= k - 1){result[i - k + 1] = nums[window.peek()];}}return result;}
二、哈希表
1.哈希表、哈希函数、哈希碰撞。
哈希表、哈希函数解决的问题是方便查找查询的复杂度是O(1)哈希碰撞99%情况会存在碰撞拉链法解决冲突，即数组元素退化为一个链表的数据结构存储
2.不同语言的内置实现：
3.映射(Map)，元素的Key值不允许重复
HashMap哈希表的实现无序插入、删除、查询的平均复杂度是O(1)TreeMap二叉搜索树的实现有序查询的复杂度是O(log N)
4.集合(Set)，元素不允许重复
HashSet哈希表的实现无序插入、删除、查询的平均复杂度是O(1)TreeSet二叉搜索树的实现有序查询的复杂度是O(log N)
5.有效的字母异位词？
思路1：数组排序，对不同字符串的排序结果做比较，相同即可。
/*** 时间复杂度是O(N * log N)*/public boolean isAnagram(String a, String b) {if (a.length() != b.length()) {return false;}char[] c1 = a.toCharArray();char[] c2 = b.toCharArray();Arrays.sort(c1);Arrays.sort(c2);return String.copyValueOf(c1).equals(String.copyValueOf(c2));}
思路2：Map计数
/*** 时间复杂度是O(N)*/public boolean isAnagram(String a, String b) {if (a.length() != b.length()) {return false;}char[] c1 = a.toCharArray();char[] c2 = b.toCharArray();//a.length() == b.length()int length = a.length();Map<Character, Integer> map1 = new HashMap<>();Map<Character, Integer> map2 = new HashMap<>();for (int i = 0; i < length; i++) {if (map1.get(c1[i]) == null) {map1.put(c1[i], 0);} else {map1.put(c1[i], map1.get(c1[i]) + 1);}if (map2.get(c2[i]) == null) {map2.put(c2[i], 0);} else {map2.put(c2[i], map2.get(c2[i]) + 1);}}return map1.equals(map2);}
6.数组中两数之和等于目标值？
/*** 输入* nums = [2,7,11,15]* target = 9* 输出* 因为nums[0] + nums[1] = 9* 因此输出数组下标[0,1]*/
思路1：暴力求解，两层循环
/*** 时间复杂度是O(N^2)*/public int[] twoSum(int[] nums, int target) {if (nums == null) {return new int[]{};}int[] result = new int[2];for(int i = 0; i < nums.length-1; i++){for(int j = i+1; j < nums.length-1; j++){if(nums[i] + nums[j] == 9){result[0] = i;result[1] = j;return result;}}}return result;}
思路2：Set，一次循环 + 一次查找
/*** 时间复杂度是O(2N)*/public int[] twoSum(int[] nums, int target) {if (nums == null) {return new int[]{};}int[] result = new int[2];HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length-1; i++) {set.add(nums[i]);}int temp;for (int i = 0; i<nums.length-1; i++){temp = target - nums[i];if(set.contains(temp)){result[0] = i;//找到result[1]即可;return result;}}return result;}
思路3：Map，key用来记录nums[i]的值，value用来记录对应的下标。
/*** 时间复杂度是O(2N)*/public int[] twoSum(int[] nums, int target) {if (nums == null) {return new int[]{};}int[] result = new int[2];Map<Integer,Integer> map = new HashMap<>();for (int i = 0; i < nums.length-1; i++) {map.put(nums[i], i);}for (int i = 0; i < nums.length-1; i++) {int temp = target - nums[i];if(map.containsKey(temp) && map.get(temp) != i){result[0] = i;result[1] = map.get(temp);}}return result;}
7.数组中三数之和等于目标值？
/*** 输入* nums = [-1,0,1,2,-1,-4]* target = 0** 输出数组元素* [-1,0,1]、[-1,2,-1]*/
思路1：暴力求解，三层循环
/*** 时间复杂度是O(N^3)*/
思路2：Set，两次循环 + 一次查找
/*** 使用Map/Set消除一层循环* 时间复杂度是O(N^2)，空间复杂度是O(N)*/public List<Integer[]> threeSum(int[] arr) {if(arr ==null || arr.length == 0){return new ArrayList();}List<Integer[]> resultList = new ArrayList();Arrays.sort(arr);for(int i=0; i<arr.length-1; i++){//重复的过滤掉if(i>0 && arr[i] == arr[i-1]){continue;}Map<Integer,Integer> targetMap = new HashMap<>();for(int j=i+1; j<arr.length; j++){if(targetMap.containsKey(arr[j])){if(targetMap.get(arr[j]) == 0){resultList.add(new Integer[]{arr[i], arr[j], -arr[i] - arr[j]});targetMap.put(arr[j],1);}}else{targetMap.put(-arr[i] - arr[j],0);}}}return resultList;}
思路3：Sort + Find
/*** 时间复杂度是O(N^2)*/public List<Integer[]> threeSum(int[] arr) {if (arr == null || arr.length < 3) {return new ArrayList<>();}Arrays.sort(arr);List<Integer[]> resultList = new ArrayList<>();for(int i=0; i<arr.length-2; i++){if(i>0 && arr[i]==arr[i-1]){continue;}int left = i+1;int right = arr.length-1;while(left < right){int s = arr[i] + arr[left] + arr[right];if(s < 0){left += 1;}else if(s > 0){right -= 1;}else{resultList.add(new Integer[]{i, left, right});while(left < right && arr[left] == arr[left+1]){left += 1;}while(left < right && arr[right] == arr[right-1]){right -= 1;}left += 1;right -= 1;}}}return resultList;}