未命名分组 - 集合-哈希-堆 - 《数据结构 · Leetcode · SQL · 刷题笔记》

451. 根据字符出现频率排序

思路：首先肯定需要统计一下里面各个字符出现的频率。诗一个数组来存放这个有序的频率。数组的下标代表着相应的频率。而上面放的应该是一个容器，说明对应的这个频率里面有那些字符是这个频率的。最后诗一个sb来进行一个拼接。

class Solution {
    public String frequencySort(String s) {
        HashMap<Character,Integer> map = new HashMap<>();
        for (char c:s.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        List<Character>[] frequency = new ArrayList[s.length()+1];
        for (char c:map.keySet()){
            int f = map.get(c);
            if(frequency[f]==null){
                frequency[f] = new ArrayList<>();
            }
            frequency[f].add(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = frequency.length-1; i >=0; i--) {
            if(frequency[i] == null){
                continue;
            }
            for (char c:frequency[i]){
                for (int j=0;j<i;j++){
                    sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}

378. 有序矩阵中第K小的元素

遍历数组里面的数，放入一个K大小的堆里面。遍历之后就可以获得这个数。


class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer integer, Integer t1) {
                return t1-integer;
            }
        });

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(heap.size()<k){
                    heap.add(matrix[i][j]);
                }else {
                    if(heap.peek()>matrix[i][j]){
                        heap.poll();
                        heap.add(matrix[i][j]);
                    }
                }
            }
        }
        return heap.peek();
    }
}

215. 数组中的第K个最大元素

思路一：
把数组排序一下，找到从后面往前面数，找到相应的位置上的数字。

思路二：
使用一个堆来记录一下里面k个数字，使用小顶堆来记录。那么堆顶部的就是需要求的数字。同时我们可以优化一下，如果k大于len/2 可以转换使用另外一半的大顶堆。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);

        for (int i:nums) {
            if(queue.size()<k){
                queue.add(i);
            }else if(queue.peek()<i){
                queue.poll();
                queue.add(i);
            }
        }
        return queue.peek();
    }
}

349. 两个数组的交集

思路：将第一个遍历一下放到Set里面，第二个我们同时也遍历一下。有效的结果放到ArrayList里面。遇到重复的话，就将Set里面的数据删除。

class Solution {
   public int[] intersection(int[] nums1, int[] nums2) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int i=0;i<nums1.length;i++){
            set.add(nums1[i]);
        }
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<nums2.length;i++){
            if(set.contains(nums2[i])){
                list.add(nums2[i]);
                set.remove(nums2[i]);
            }
        }
        int res[] = new int[list.size()];

        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return  res;

    }
}

350. 两个数组的交集 II

思路：
使用一个哈希表来记录一下出现的次数，遇到了一次就将频率-1；

class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int num:nums1){
            if(!map.containsKey(num)){
                map.put(num,1);
            }else {
                map.put(num,map.get(num)+1);
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        for(int num:nums2){
            if(map.containsKey(num)){
                list.add(num);
                map.put(num,map.get(num)-1);
                if(map.get(num) == 0){
                    map.remove(num);
                }
            }
        }
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return  res;


    }
}

347. 前 K 个高频元素

思路：使用一个哈希表来记录一下每个数字出现的频率。使用优先队列（小根堆）来维护K个数值，假如假如的元素的频率比小根堆的堆顶还要大的话，弹出堆顶。加入新的数值。

class Solution {
     public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> hashmap = new HashMap<>();
        for(int num:nums){
            if(hashmap.containsKey(num)){
                hashmap.put(num,hashmap.get(num)+1);
            }else {
                hashmap.put(num,1);
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer integer, Integer t1) {
                return hashmap.get(integer) - hashmap.get(t1);
            }
        });
        for(int key:hashmap.keySet()){
            if(pq.size()<k){
                pq.add(key);
            }else if(hashmap.get(key)> hashmap.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }

        LinkedList<Integer> res = new LinkedList<>();
        while (!pq.isEmpty()){
            res.add(pq.remove());
        }
        return res;

    }
}

哈希

560. 和为K的子数组

最简单的方法是暴力，固定一个i 从i开始遍历。遇到相等的就count++。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;

        for(int i=0;i<nums.length;i++){
            int sum = 0;
            for(int j=i;j<nums.length;j++){
                sum+=nums[j];
                if(sum ==k){
                    count++;

                }

            }
        }
        return count;
    }
}

之后的想法是我们诗一个dp的数组来记录一下前缀和。就是所dp[i] = [0…i)的数字的和。
知道了这个之后，可以用哈希表进行一个加速。就像twosum里面的。查询map里面有没有 k-dp[i]的数值。另一方面，需要记录一下map里面的频率。

使用Map储存结果，将搜索的复杂度减小为O(n)

在有了第一步结果后，我们将问题转化为：

给定一个数组，是否存在两个数的差等于target，如果存在，请问有多少种情况

这种情况下，就非常类似于数组中两数求和1. 两数之和，我们将遍历的结果加到set中，使用常数时间进行查找，但是第一题只要求找到一个结果即可，所以用Set(Set本质上就是Map)。但是在本文中，当我们查找dp[i]-k时，对应的dp[j]可能不唯一，这也对应了本问题的多种答案，所以，我们使用Map去存储，key是dp[i]，value是dp[j]有多少种选择。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;

        int[] dp = new int[nums.length+1];

        for(int i=1;i<=nums.length;i++){
            dp[i] = dp[i-1]+nums[i-1];
        }
        HashMap<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<dp.length;i++){
            if(map.containsKey(dp[i]-k)){
                count+=map.get(dp[i]-k);
            }
            map.put(dp[i],map.getOrDefault(dp[i],0)+1);
        }
        return count;
    }
}

974. 和可被 K 整除的子数组

这道题说的是我们有一个数组，寻找到里面和能被K整除的连续子序列。
首先想到的的是前缀和的思路。前缀和就是记录一下[0…i]的和，例如dp[2] = [0….2]的数的和。

我们再看，题目的要求其实需要我们求 P[j]-P[i-1] %K 0 的组合。对阵式子做一点变化，其实我们求的是P[j] %K == P[i-1] %K 的数量。求得P[j] % k的数值，结果就要增加到现在为止的等于 P[j] % k 的值。
**

    public int subarraysDivByK(int[] A, int K) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int sum = 0;
        int res = 0;

        for(int i:A){
            sum+=i;
            sum = (sum%K+K)%K;
            int same = map.getOrDefault(sum,0);
            res+=same;
            map.put(sum,same+1);
        }
        return res;

    }