Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

* Method 1: Greedy

* what we are greedy for: we are greedy for a smaller lexicographical order.

```Java

class Solution {

public String removeDuplicateLetters(String s) {

if(s.length() == 0) return "";

char[] arr = s.toCharArray();

int[] count = new int[26];

for(char c : arr){

count[c - 'a']++;

}

int pos = 0;

// Greedy for the smallest lexicographical order until we meet a letter exist the last time.

// We assume it is c.

for(int i = 0; i < arr.length; i++){

if(arr[i] < arr[pos]) pos = i; // always greedy for the smallest lexicographical order for current letter.

if(--count[arr[i] - 'a'] == 0) break; // once we meet a letter exists the last time, we need to break.

}

// remove all c in current string and make it as the beginning of the result.

String next = s.substring(pos + 1).replace(arr[pos] + "", "");

return arr[pos] + removeDuplicateLetters(next);

}

}

```

* Method 2: Deque

* The idea of deque is very same as previous one.

```Java

class Solution {

public String removeDuplicateLetters(String s) {

int[] count = new int[26];

char[] arr = s.toCharArray();

for(char c: arr) count[c - 'a']++;

boolean[] visited = new boolean[26];

// Deque increasing.

Deque<Character> dq = new LinkedList<>();

for(char c : arr){

count[c - 'a']--; // remove the frequency of current letter.

if(visited[c - 'a']) continue; // means current character has already in the dq.

// !dq.isEmpty(): Means current dq is not empty

// dq.peekLast() > c: the end character in the dq has larger lexicographical order than c.

// count[dq.peekLast() - 'a'] > 0: if end letter is at the last time appearence, it means we cannot remove it.

while(!dq.isEmpty() && dq.peekLast() > c && count[dq.peekLast() - 'a'] > 0){

visited[dq.pollLast() - 'a'] = false;

}

visited[c - 'a'] = true;

dq.offer(c);

}

StringBuilder sb = new StringBuilder();

while(!dq.isEmpty()){

sb.append(dq.poll());

}

return sb.toString();

}

}

```

### Reference

1.[Java solution using Stack with comments](https://leetcode.com/problems/remove-duplicate-letters/discuss/76769/Java-solution-using-Stack-with-comments)

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up:

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

* Method 1: Use axtra space to get O(1).

```Java

/**

class Solution {

private Random random;

private HashMap<Integer, Integer> map;

/** @param head The linked list's head.

public Solution(ListNode head) {

this.map = new HashMap<>();

this.random = new Random();

ListNode cur = head;

int count = 0;

while(cur != null){

map.put(count++, cur.val);

cur = cur.next;

}

}

/** Returns a random node's value. */

public int getRandom() {

int rand = random.nextInt(map.size());

return map.get(rand);

}

}

/**

```

* Method 2: Reservoir Sampling

```Java

/**

class Solution {

private ListNode head;

private Random random;

/** @param head The linked list's head.

public Solution(ListNode head) {

this.head = head;

this.random = new Random();

}

/** Returns a random node's value. */

public int getRandom() {

ListNode cur = head.next;

int count = 1;

ListNode hold = head;

while(cur != null){

count++;

int rand = random.nextInt(count) + 1;

if(rand == count) hold = cur;

cur = cur.next;

}

return hold.val;

}

}

/**

```

There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?

Answer this question, and write an algorithm for the general case.

General case:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

Note:

1. A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.

2. After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.

3. Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

* Method 1: Information Theory

* For a single pig(bit), we can figure out how many states can be representated.

* Example: minutesToTest 60 mins, minutesToDie 15mins

* states to resent die: [15, 30, 45, 60] + live = 5

* The question changed to: how many bits required to resent the value of buckets.

```Java

class Solution {

public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {

//how many states can be represented by a pig within the test.

int statesToPresent = minutesToTest / minutesToDie + 1;

return (int)Math.ceil(Math.log(buckets) / Math.log(statesToPresent));

}

}

```

### Reference

1. [leetcode 458. Poor Pigs 可怜的猪 + 猪试毒需要最少的数量 + 发现规律](https://blog.csdn.net/JackZhang_123/article/details/78775716)

You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.

Design a log storage system to implement the following functions:

void Put(int id, string timestamp): Given a log's unique id and timestamp, store the log in your storage system.

int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", granularity = "Day", it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.

Note:

1. There will be at most 300 operations of Put or Retrieve.

2. Year ranges from [2000,2017]. Hour ranges from [00,23].

3. Output for Retrieve has no order required.

* Method 1: Map

```Java

class LogSystem {

private Map<String, Integer> map;

private static final Map<String, Integer> g;

private static final String token = "00";

static{

g = new HashMap<>();

g.put("Year", 4);

g.put("Month", 7);

g.put("Day", 10);

g.put("Hour", 13);

g.put("Minute", 16);

g.put("Second", 19);

}

public LogSystem() {

this.map = new HashMap<>();

}

public void put(int id, String timestamp) {

map.put(timestamp, id);

}

public List<Integer> retrieve(String s, String e, String gra) {

int index = g.get(gra);

String ssub = s.substring(0, index);

String esub = e.substring(0, index);

List<Integer> result = new ArrayList<>();

for(String k : map.keySet()){

String ksub = k.substring(0, index);

if(ksub.compareTo(ssub) >= 0 && ksub.compareTo(esub) <= 0)

result.add(map.get(k));

}

return result;

}

}

/**

```