介绍前缀树
何为前缀树?如何生成前缀树?
例子:
一个字符串类型的数组arr1,另一个字符串类型的数组arr2。
public static class TireNode{
public int pass;
public int end;
// public HashMap<Char,TireNode> next;
// public TreeMap<Char,TireNode> next;
public TireNode[] nexts;
public TireNode(){
pass = 0;
end = 0;
nexts = new TireNode[26];
}
}
public static class Tire{
private TireNode root;
public Tire(){
root = new TireNode();
}
//加入一个字符串
public void insert(String word){
if (word == null){
return;
}
char[] chs = word.toCharArray();
TireNode node = root;
node.pass++;
int index = 0;
for (int i = 0; i < chs.length; i++) {//从左向右遍历字符
index = chs[i] - 'a';// 由字符对应走向哪条路
if (node.nexts[index] == null){
node.nexts[index] = new TireNode();
}
node = node.nexts[index];
node.pass++;
}
node.end++;
}
//word这个词之前加入过几次
public int search(String word){
if (word == null){
return 0;
}
char[] chs = word.toCharArray();
TireNode 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;
}
//所有加入的字符串中，有几个是一pre为前缀的
public int prefixNumber(String pre){
if (pre == null){
return 0;
}
char[] chs = pre.toCharArray();
TireNode 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.pass;
}
//删除一个节点 沿途p--，最后e--
public void delete(String word){
if (search(word) != 0){
char[] chs = word.toCharArray();
TireNode node = root;
node.pass--;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (--node.nexts[index].pass == 0){
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.end--;
}
}
}
在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。
也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优-?-> 整体最优
一些项目要占用一一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
给你每-个项目开始的时间和结束的时间(给你- -个数组，里面是一一个个具体
的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
返回这个最多的宣讲场次。
public class BestArrange {
public static class Program{
public int star;
public int end;
public Program(int star,int end){
this.star = star;
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 bastArrange(Program[] programs,int timePoint){
Arrays.sort(programs,new ProgramComparator());
int res = 0;
//依次遍历所有的会议
for (int i = 0; i < programs.length; i++) {
if (timePoint > programs[i].star){
res++;
timePoint = programs[i].end;
}
}
return res;
}
}
}
贪心算法的在笔试时的解题套路
1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
2，脑补出贪心策略A、贪心策略B、贪心策略C…
3，用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
4，不要去纠结贪心策略的证明
public class lowstString {
public static void main(String[] args) {
}
public static class MtComparator implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
return (o1+o2).compareTo(o2+o1);
}
}
public static String lowstString(String[] strings){
if (strings == null || strings.length == 0){
return "";
}
Arrays.sort(strings,new MtComparator());
String res = "";
for (int i = 0; i < strings.length; i++) {
res += strings[i];
}
return res;
}
}
贪心策略在实现时，经常使用到的技巧:
1，根据某标准建立一个比较器来排序
2，根据某标准建立一个比较器来组成堆.
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。
一群人想整分整块金条，怎么分最省铜板?
例如,给定数组{10, 20, 30}，代表一共三个人，整块金条长度为10+20+30=60。金条要分成10, 20, 30三个部分。如果先把长度 60的金条分成10和50，花费60;再把长度50的金条分成20和30，花费50;一共花费110铜板。但是如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20,花费30;一共花费90铜板。
输入一个数组，返回分割的最小代价。
public static 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;
}
输入:
正数数组costs – costs[i]表示i号项目的花费
正数数组profits – profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
正数k – k表示你只能串行的最多做k个项目
正数m – m表示你初始的资金
说明:
你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出:
你最后获得的最大钱数。
public class IPo {
public static class Node{
public int p;
public int c;
public Node(int p, int c) {
this.p = p;
this.c = c;
}
}
public static class MinCostComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return o1.c-o2.c;
}
}
public static class MaxProfitComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return o2.p - o1.p;
}
}
public static int fingMaximizedCapital(int k ,int w, int[] Profits,int[] Capital){
PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MinCostComparator());
for (int i = 0; i < Profits.length; i++) {
maxProfitQ.add(new Node(Profits[i], Capital[i]));
}
for (int i = 0; i < k; i++) {
while (!maxProfitQ.isEmpty() && minCostQ.peek().c <= w){
maxProfitQ.add(minCostQ.poll());
}
if (maxProfitQ.isEmpty()){
return w;
}
w += maxProfitQ.poll().p;
}
return w;
}
}
一个数据流中， 随时可以取得中位数
public class Nqueens {
public static int num1(int n){
if (n < 1){
return 0;
}
int[] record = new int[n];
return process1(0,record,n);
}
private static int process1(int i, int[] record, int n) {
if (i == n){
return 1;
}
int res = 0;
for (int j = 0; j < n; j++) {
if (isValid(record,i,j)){
record[i] = j;
res += process1(i+1,record,n);
}
}
return res;
}
public static boolean isValid(int[] record,int i, int j){
for (int k = 0; k < i; k++) {
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i-k)){
return false;
}
}
return true;
}
}
位运算
public static int num2(int n){
if (n < 1|| n > 32){
return 0;
}
int limit = n == 32? -1:(1<<n)-1;
return process2(limit,0,0,0);
}
// colLim 列的限制，1的位置不能放皇后，0的位置可以
// leftDiaLim 左斜线的限制，1的位置不能放皇后，θ的位置可以
// rightDiaLim 右斜线的限制，1的位置不能放皇后，θ的位置可以
private static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
if (colLim == limit){
return 1;
}
int pos = 0;
int mostRightOne = 0;
pos = limit & (~(colLim | leftDiaLim | rightDiaLim));//可以填皇后的位置
int res = 0;
while (pos != 0){
mostRightOne = pos & (~pos+1);
pos = pos -mostRightOne;
res += process2(limit,colLim|mostRightOne,
(leftDiaLim | mostRightOne) <<1,
(rightDiaLim | mostRightOne)>>>1);
}
return res;
}