Today, we introduce a general method to solve the problems of common greedy strategy or dictionary sorting.

The first one, leetcode medium difficulty

First of all, I'll give you a simple problem of dictionary order. I won't use the optimal solution to solve this problem here. This is the middle difficulty problem of leetcode. The optimal solution still needs to be considered again. As the beginning of this article, it's just to introduce the greedy solution I want to introduce. Please don't spray!!

Seeing this problem, I just want to use violence to solve it, so as to better understand this solution.

Give me my answer first. It's very violent, but it's very understandable.

public List<Integer> lexicalOrder(int n) {
        List<String> list = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            list.add(i + "");
        }
        Collections.sort(list,(o1,o2)->{
            return o1.compareTo(o2);
        });
        List<Integer> iList = new ArrayList<>();
        list.stream().forEach((str)->{
            iList.add(Integer.parseInt(str));
        });
        return iList;
    }

This solution is very simple. It uses the sorting of the Collections.sort() method, and then rewrites the Comparator class. Here is the lambda expression, which makes the code more concise.

You can go to leetcode to have a look, do it yourself, and have plenty of food and clothing.

So, the information I want to give through this topic is: usually related to string sort, dictionary order, number sort and so on, we can use this idea to solve the problem.

No, let's look at other topics.

The second one, leetcode medium difficulty

This is a common topk problem, and the optimal solution is not the answer I give, just to illustrate this solution.

My solution: use priority queue to maintain a small top heap with the size of k. each time the elements of the heap reach k, the top elements of the heap will pop up first, so that the heap always maintains the maximum value of k, and finally the elements with the height of k can reach the top.

Now let's look at my answer (Note: my answer is definitely not the optimal solution, just to illustrate this method)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Queue<Obj> queue = new PriorityQueue<>(k,(o1,o2)->{
            return o2.num - o1.num;
        });

        HashMap<Integer,Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++){
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
        }

        for(int key : map.keySet()){
            queue.offer(new Obj(key,map.get(key)));
        }

        int[] ans = new int[k];
        int i = 0;
        while(i < k){
            ans[i] = queue.poll().target;
            i++;
        }

        return ans;

    }

    class Obj {
        public int target;
        public int num;

        public Obj(int target, int num){
            this.target = target;
            this.num = num;
        }
    }
}

This approach does not maintain the largest heap of k.

class Solution {
  public List<Integer> topKFrequent(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap();
    for (int n: nums) {
      map.put(n, map.getOrDefault(n, 0) + 1);
    }

    PriorityQueue<Integer> heap =
            new PriorityQueue<Integer>((n1, n2) -> map.get(n1) - map.get(n2));


    for (int n: map.keySet()) {
      heap.add(n);
      if (heap.size() > k)
        heap.poll();
    }
    
    List<Integer> top_k = new LinkedList();
    while (!heap.isEmpty())
      top_k.add(heap.poll());
    Collections.reverse(top_k);
    return top_k;
  }
}

This method maintains the largest heap of k.

The comparison shows that the core idea is to maintain the largest heap of k or not

Queue<Obj> queue = new PriorityQueue<>(k,(o1,o2)->{
            return o2.num - o1.num;
        });

And this code

PriorityQueue<Integer> heap =
            new PriorityQueue<Integer>((n1, n2) -> map.get(n1) - map.get(n2));

Compare the

Collections.sort(list,(o1,o2)->{
            return o1.compareTo(o2);
        });

It uses the inner class: Comparator, and then builds the collation that conforms to the meaning of the question.

The third, more complicated

This topic can better understand what is to build a ranking rule that conforms to the meaning of the topic.

Because many topics require you to sort by more than one field, maybe two fields, or three fields, you need to "build".

How to solve this problem: sort and insert

• Sorting rules: sort in descending order of first H height and ascending order of number of K
• Traverse the sorted array and insert it into the position of K according to K

Core idea: the tall man stands first, the short man inserts into the K position, there must be K tall men in front, and the short man inserts into the front again to meet the requirements of K.

Let's look at the solution

public int[][] reconstructQueue(int[][] people) {
        // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
        // Another insertion process
        // [7,0]
        // [7,0], [7,1]
        // [7,0], [6,1], [7,1]
        // [5,0], [7,0], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            //In position i, the number of inserts: i[1] is the first number of [7,0], [7,1], [6,1], [5,0], [5,2], [4,4], indicating that there are several higher than me.
            list.add(i[1], i);
        }

        return list.toArray(new int[list.size()][2]);
    }

You will find that the core code is just as complicated as the first and second questions.

Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

What does this mean: o1 and o2 are a bit array similar to [7,0]. When the first number is equal, then compare the size of the second number of the one-dimensional array. Of course, compare the first number first.

This is an example of multiple field comparison. Is it the same as the previous idea.

summary

At last, we find that we can use Java Comparator to solve the sorting problems, such as array sorting, number sorting, string sorting and priority queue sorting.

Say so much, just thinking, don't kowtow to the best solution!!!