This paper mainly supplements two small problems not mentioned before, one greedy algorithm problem, one LRU cache replacement strategy algorithm problem;

1. Leetcode455 — hand out cookies

Let’s say you’re a great parent and you want to give your kids some cookies. However, no more than one cookie can be given to each child.

For each child I, there is an appetite value g[I], which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie J has a size S [J]. If s[j] >= g[I], we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number.

Example 1: Input: g = [1,2,3], s = [1,1] Output: 1 Explanation: You have three children and two cookies. The appetites of the three children are: 1,2,3 respectively. Even though you have two little cookies, since they're both size 1, you can only satisfy a child with an appetite of 1. So you should print 1.Copy the code

The solution is shown below. Although the description of the problem looks troublesome, it is actually a typical greedy algorithm problem.

We first ranked the children’s greed, then the size of the cookies; If the maximum size of the biscuit can’t satisfy the most greedy child, then the children would have certainly can’t satisfy him, because you want cookies can hardly meet the maximum size, the rest of the biscuit certainly can not meet, this is will decrease index of an array of children, can go to meet a friend, if you can meet a friend, then the result 1, Decrement the array of cookies and the array of children respectively, to judge whether the next cookie can satisfy the next child, cycle until the array of cookies or the array of children is empty;

Public int findContentChildren(int[] g, int[] s) {array.sort (g); Arrays.sort(s); int gi = g.length - 1; int si = s.length - 1; int res = 0; while (gi >= 0 && si >= 0){ if (s[si] >= g[gi]){ res ++; si--; gi--; }else { gi--; } } return res; }Copy the code

2. Leetcode146 –LRU caching mechanism

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism.

Implement the LRUCache class:

LRUCache(int capacity) The LRU cache is initialized with a positive integer capacity. Int get(int key) Returns the value of the key if it exists in the cache, otherwise -1 is returned. Void put(int key, int value) If the keyword already exists, change its data value. If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.

The LRUCache class in the title description should be very familiar, LRU is the key content in the replacement strategy of cache and the replacement algorithm of virtual memory.

As shown below, we use LinkedHashMap, a class that has both a bidirectional list and a hash table, to save data in the order of insertion.

The LRUCache class we implement is mainly about get and PUT methods;

When the get method is called, return -1 if this key does not exist in the LinkedHashMap, otherwise refresh the key pair corresponding to this key as the latest accessed, the specific operation is to delete the original key pair, put again and save, LinkedHashMap will automatically save the newly inserted data last;

When the put method is called, if a key pair already exists in the LinkedHashMap, the original key pair is deleted, the latest key pair is put again, and the return value is returned. If not, check to see if the LinkedHashMap is full. If it is, delete the key pair of the header head, which is the least recently used one. This is also the design idea of LRU. Save the key-value pair into the LinkedHashMap after deleting it.

import java.util.LinkedHashMap; //leetcode 146 LRU cache class LRUCache {int capacity; int size; LinkedHashMap<Integer,Integer> linkedHashMap = new LinkedHashMap<>(); public LRUCache(int capacity) { this.capacity = capacity; this.size = 0; } public int get(int key) { if (! linkedHashMap.containsKey(key)){ return -1; } makeRecentUse(key); return linkedHashMap.get(key); } private void makeRecentUse(int key) { int value = linkedHashMap.get(key); linkedHashMap.remove(key); linkedHashMap.put(key,value); } public void put(int key, int value) { if (linkedHashMap.containsKey(key)){ linkedHashMap.remove(key); linkedHashMap.put(key,value); return; } if (linkedHashMap.size() == capacity){ Integer head = linkedHashMap.keySet().iterator().next(); linkedHashMap.remove(head); } linkedHashMap.put(key,value); }}Copy the code

Source:

Source: LeetCode link: leetcode-cn.com/problemset/…