trie

The prefix tree is understood by the figure above, in which nodes are represented by circles, and characters such as "abc" are added to the whole tree as paths instead of nodes. At the same time, each character is added from the beginning node, so it can be seen that "abc" and "bce" are two branches, while the first half of "abc" and "abd" are one branch, and finally two branches are formed .
Extended functions: 1. The added characters can be added to the node in the form of path to store the information whether the end of the string is the same as the previous path, so that the "be" can be added, but the number of strings that do not form a new branch at last can be used for the statistics of how much string information is added as a whole. (extended string plus several times)
2. Query the arrival prefix, and in the process of adding, it reaches the node several times.

public static class TrieNode{
	public int path;
	public int end;
	public TrieNode[] nexts;

	public TrieNode(){
		path = 0;
		end = 0;
		//To simplify, 26 letters are used as 26 paths
		nexts = new TrieNode[26];
	}
}

public static class Trie{
	private TrieNode root;

	public Trie(){
		//The new header is the whole header node
		root = new TrieNode();
	}

	public void insert(String word){
		if(word == null){
			return;
		}
		char[] chs = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for(int i =0;i<chs.length;i++){
			//Use the difference of asker code to express the first path
			index = chs[i] - 'a';
			//Judge whether the starting position of this road exists. If it does not exist, create a new one. At the same time, open the following roads in turn.
			if(node.nexts[index] == null){
				nofr.nexts[index] = new TrieNode();
			}
			node = node.nexts[index];
			node.path++;
		}
		node.end++;
	}
	
	public void delete(String word){
		if(search(word) != 0){
			char[] chs = word.toCharArray();
			TrieNode node = root;
			int index = 0;
			for(int i = 0;i<chs.length;i++){
				index = chs[i] - 'a';
				//The path information of a node is reduced by one to zero, which means that the next strings are all strings to be deleted, so the following strings are set to null directly
				if(--node.nexts[index].path == 0){
					node.nexts[index] = null;
					return;
				}
				node = node.nexts[index];
			}
			node.end--;
		}
	}

	public int search(String word){
		if(word == null){
			return ;
		}
		char[] chs = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for(int i = 0;i<chs.length;i++){
			index = chs[i] - 'a';
			if(node.nexts[index] == null){
				return 0;
			}
			node = node.nexts[index];
		}
		return node.end;
	}

	public int prefixNumber(String pre){
		if(pre == null){
			return 0;
		}
		char[] chs = pre.toCharArray();
		TrieNode node = root;
		int index = 0;
		for(int i = 0;i<chs.length;i++){
			index = chs[i] - 'a';
			if(node.nexts[index] == null){
				return 0;
			}
			node = node.nexts[index];
		}
		return node.path;
	}
}

Given an array strs of string type, a splicing method is found to make the string formed after all strings are put together have the lowest dictionary order

The two strings are combined and then sorted, instead of just comparing the two strings and sorting directly and finally integrating. Greedy algorithms can be used.
If you need to prove that your order is unique, you need to prove that the entire order is transitive. (a > b, b > C, then a > C) if the current string is already the smallest, then you need to prove that if you change any two small strings in the string, then it is smaller than the current string.
After the greedy strategy is put forward, if we want to prove that the greedy strategy is correct, we will pay a lot of experience. It is better to use the logarithm directly, without proving the greedy strategy.

public static class MyComparator implements Comparator<String> {
	@override
	public int compare(String a,String b){
		return(a+b).compareTo(b+a);
	}
}

public static String lowestString(String[] strs){
	if(strs == null || strs.length == 0){
		return " ";
	}
	Arrays.sort(strs,new MyComparator());
	String res = " ";
	for(int i = 0;i<strs.length;i++){
		res += strs[i];
	}
	return res;
}

When a gold bar is cut into two parts, it costs the same amount of copper as the length. For example, a gold bar with a length of 20, no matter how long it is cut into two halves, will cost 20 copper plates. A group of people want to divide the whole gold bar, how to divide the most economical copper bar? For example, given the array {10,20,30}, it represents a total of three people. The length of the whole gold bar is 10 + 20 + 30 = 60. The gold bar is divided into 10, 20 and 30 parts. If you first divide the length of 60 bars into 10 and 50, then spend 60 to divide the length of 50 bars into 20 and 30, and spend 50 to spend 110 copper plates in total. But if you first divide the length of 60 bars into 30 and 30, spend 60 and then divide the length of 30 bars into 10 and 20, spend 30 and spend 90 coppers in total. Enter an array to return the minimum cost of segmentation.

For this problem, the input array is the number of copies and values to be cut. To return the minimum cost, according to the Huffman coding idea, the total length is the total node, and the sum of different nodes is the following sub nodes. Through the combination of the lower sub nodes, a tree with the minimum cost is formed.
Create a new small root heap, and then take out the root node and the other smallest one, and combine the root node with the other smallest value. At this time, return the combined value to the small root heap, re form the small root heap, and operate recursively until the whole array element is combined. The middle process is the process of minimizing the cost of segmentation, and the final added value is the minimum cost.

public class int lessMoney(int [] arr){
	PriorityQueue<Integer> pQ = new PriorityQueue<>();
	for(int i = 0;i< arr.length;i++){
		pQ.add(arr[i]);
	}
	int sum = 0;
	int cur = 0;
	while(pQ.size()>1){
		cur = pQ.poll() +pQ.poll();
		sum +=cur;
		pQ.add(cur);
	}
	return sum;
}

## Two arrays, one for cost and one for profit. The i-th bit of the two arrays represents the situation of each item. The money back is the price plus the profit. Start with a start-up fund. If the cost is less than the start-up fund, you can start projects, but you can only do one project at a time, and you can only do K projects at most. After the completion of the funds into start-up funds plus project profits. Ask for the final amount of money.

1. take cost The cost array forms a small root heap. As long as the head cost of the small root heap is lower than the startup fund, the head in the small root heap will be taken out in turn and put into the large root heap. According to the high income, the high income is in the head. After taking it out, the remaining items in the small root heap are items that cannot be done at present, and the items stored in the large root heap are items that can be done at present, and are sorted according to the profit.

```java
public static int findMaximizedCapital(int k,int W,int[] Profits,int[] Capital){
	Node[] nodes = new Node[Profits.length];
	for(int i = 0;i<Profits.length;i++){
		nodes[i] = new Node(Profits[i],Capital[i]);
	}
	//MinCostComparator and the following Max are both inheritance comparators. They compare the cost in Node to realize the large root heap and the small root heap
	PriorityQueue<Node> minCastQ = new PriorityQueue<>(new MinCostComparator());
	PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
	for(int i = 0;i<nodes.length;i++){
		minCostQ.add(nodes[i]);
	}
	for(int i = 0;i<k;i++){
		while(!minCostQ.isEmpty() &&minCostQ.peek().c<=W){
			maxProfitQ.add(minCostQ.poll());
		}
		if(maxProfitQ.isEmpty()){
			return W;
		}
		W += maxProfitQ.poll().p;
	}
	return W;
}

Some projects need to occupy a conference room for propaganda, and the conference room can not accommodate the propaganda of two projects at the same time. Give you the start time and end time of each project (give you an array, which is a specific project). You can arrange the schedule of the lecture, and ask the conference room to give the most lectures. Return to the most lectures.

The end time is used for judgment and sorting according to the end time of the project. The end time of the current project can exclude other projects that cannot be started. The next selected project is the project with the earliest end time and the start time less than the last end time after the end.

public static class Program{
	public int start;
	public int end;
	public Program(int start,int end){
		this.start = start;
		this.end = end;
	}
}

public static class ProgramComparator implements Comparator<Program>{
	@Override
	public int compare(Program o1,Program o2){
		return o1.end-o2.end;
	}
}

public static int bestArrange(Program[] programs,int start){
	Arrays.sort(programs,new ProgramComparator());
	int result = 0;
	for(int i = 0;i< programs.length;i++){
		if(start<=programs[i].start){
			result++;
			start = programs[i].end;
		}
	}
	return result;
}