一、优先队列

PriorityQueue

特点：

• 正常入
• 按照优先级出

实现机制：

1. Heap (Binary, Binomial, Fibonacci）
2. Binary Search Tree

例如小顶堆： 入队，需保持最小元素在堆顶；出队，直接返回堆顶元素

不同实现机制的优先队列，及其基本操作的时间复杂度如下

实战题目

1. 第K大的元素

class KthLargest {
    final PriorityQueue<Integer> prq;
    final int k;
    public KthLargest(int k, int[] nums) {
        this.k=k;
        prq=new PriorityQueue<>(k);
        for(int n:nums){
            add(n);
        }
    }

    public int add(int val) {
        if(prq.size()<k){
            prq.offer(val);
        }
        else if(val > prq.peek()){
            prq.poll();//无需
            prq.offer(val);
        }
        return prq.peek();
    }
}

1. 滑动窗口
   思路：
2. 维护一个优先队列（大顶堆），根元素最大。窗口每次滑动调整堆内元素，将堆顶元素放入结果数组。维护堆顶元素最大复杂度LogK，返回最大值复杂度O(1)，总体复杂度O(N·logK)
3. 因为窗口大小固定，且只返回最大值，所以无需优先队列，用队列即可。维护一个deque(双端队列)。首先前k元素进入队列，后面随窗口滑动维护队列。窗口向右滑动时若比队列最大元素小则正常进入，若比最大元素大则移除前面全部元素再入队，始终保持最大元素在最左边。时间复杂度O(N·1)

   class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums: return []
        window,res=[],[]
        for i,x in enumerate(nums):
            if i >= k and window[0]<= i-k:
                window.pop(0)
            while window and nums[window[-1]] <= x:
                window.pop()
            window.append(i)
            if i >= k-1:
                res.append(nums[window[0]])
        return res
   

二、映射Map & 集合Set

HashTable & Hash Function & Collisions

什么是Hash函数：

Hash函数能够实现O(1)复杂度的元素查找，实现元素（值）和其存放位置（键）的快速映射

使用ASCII码进行映射的示意图所下所示：

Hash函数的碰撞：不同元素经过相同的哈希函数作用得到了相同的“键”，如果不加处理则映射关系就会失效

几种处理思路 ：

1. “拉链法”，在冲突的键处放链表，将相同键的值链接起来
2. 左移
3. 右移

List vs Map vs Set（抽象数据结构）

• List：线性表，元素可重复，数组或链表，查找耗时O(N)，插入O(1);
• Map：映射关系，“键——值”的对应关系，键唯一;
• Set：集合，可认为是List去重版，但实现机制一般是哈希表或二叉树，查找O(1)或O(logN);

  HashMap，HashSet，TreeMap，TreeSet

  哈希方式实现的Map和Set，查找复杂度均为O(1)，
  Tree方式实现的Map和Set，查找复杂度均为O(LogN) 哈希方式优势在于查找的时间复杂度，Tree方式优势在于元素排列是有序的。 根据实际情况选用不同方式

不同语言HashMap 最佳实践（使用形式）

• Python
• dict
• hashmap = {key: value}
• C++
• std::unordered_map
• std::map
• Java
• HashMap
• TreeMap
• C#
• Dictionary
• Hashtable
• StringDictionary
• SortedDictionary

不同语言HashSet 最佳实践（使用形式）

• Python
• hashset = {value1, value2}
• C++
• std::unordered_set
• std::set
• Java
• HashSet
• TreeSet
• C#
• HashSet
• SortedSet

实战题目

1. 有效异位词 所谓异位词，指的是单词组成字母相同，但字母移位了的字符串。给定两个字符串，返回true或false

   • 思路一：字符串内字符按字母顺序排序，最后比较字符串是否相同。使用快排最快时间复杂度：O(NlogN)

     def IsAnagram(self,s,t):
     return sorted(s)==sorted(t)
     

   • 思路二：哈希函数权值比较。
   • 思路三：数各字符出现次数，每遇到一个字符，其出现次数+1。时间复杂度O(N)
     • 用编程语言自带的map

       def isAnagram1(self,s,t):
       dic1, dic2 = {}, {}
       for item in s:
        dic1[item] = dic1.get(item, 0) + 1
       for item in t:
        dic2[item] = dic2.get( item, 0) + 1 
       return dic1 == dic2
       

     • 或自己用一个26位长度的数组记录

       def isAnagram2(self,S,t):
       dic1, dic2 = [0]*26, [0]*26
       for item in s:
        dic1[ord(item)-ord('a')] += 1
       for item in t:
        dic2 [ord(item)-ord('a')] += 1
       return dic1 == dic2
       

2. 两数之和 输入一个数字数组nums和一个目标target，若数组中存在两数x，y满足x+y==target，返回true，否则返回false

   • 思路一：暴力求解，双重循环配对求和，时间复杂度O(N²)
   • 思路二：将所有元素放入一个集合，先在外层循环每一个元素x，内层在Set里面查找target-x，找到了即返回对应下标

     class Solution {
     public:
     vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); ++i) {
            int t = target - nums[i];
            if (m.count(t) && m[t] != i) {
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
     }
     };
     

3. 三数之和 顾名思义，若存在x+y+z==target，则返回true

   • 思路一：三重循环，暴力求解。时间复杂度O(N³)
   • 思路二：三重循环基础上改进，在前两重循环的基础上不再遍历z而是直接在Set里面查找target-(x+y)，时间复杂度O(N²·1)，空间复杂度O(N)（Set额外空间）

     def threeSum(self, nums):
     if len(nums) < 3:
        return []
     nums.sort( )
     res = set( )
     for i, v in enumerate(nums[:-2]):
        if i >= 1 and V == nums[i-1]:
            continue
        d={}
        for X in nums [i+1:] :
            if x not in d:
                d[-v-x] = 1
            else:
                res.add((v, -v-x, x))
     return map(list,res)
     

   • 思路三：循环+双指针法。先对数组排序，在一重循环遍历x的基础上，用一首一尾两个双指针两头逼近，查找y+z=target-x的情况。（升序排列情况下，若y+z < target-x，左指针右移，若y+z > target-x，则右指针左移，逆序排列反之）

     def threeSum(self, nums):
     res =[]
     nums. sort()
     for i in xrange( len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        1, r = i+1, len(nums)-1
        while 1 < r:
            s = nums[i] + nums[U] + nums [r]
            if s<0: l+=1
            elif s>0:r-=1
            else:
                res . append( (nums[i], nums[U], nums[r]))
                while L < r and nums[l] == nums [l+1]:
                l+=1
                while L < r and nums[r] == nums [r-1]:
                    r -= 1
                l += 1; r -= 1
     return map(list,res)
     

4. 四数之和

5. 群体异位词给定一个字符串数组，找出数组中互为异位词的字符串并放到一个字数组中，最后返回所有异位词组合

   • 思路一：使用set的方式存储异位词组，同一个key可有多个value。同时使用字符串内部排序的方式判断是否互为异位词。最后将set转化为array返回即可

     var groupAnagrams = function(strs) {
     const map = new Map();
     for (let str of strs) {
        let array = Array.from(str);
        array.sort();
        let key = array.toString();
        let list = map.get(key) ? map.get(key) : new Array();
        list.push(str);
        map.set(key, list);
     }
     return Array.from(map.values());
     };