目录
7 临时补充
3 布隆过滤器
总结：布隆过滤器的提示点：
1、黑名单问题；2、要求内存空间极为苛刻；3、单样本的大小可能很大；4、允许有失误率（可能要自己问）
5 哈夫曼（霍夫曼）编码问题
Huffman Tree：给定n个权值作为n个叶子结点，构造一颗二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树（也就是非叶子节点的权值和最小）。
具体应用：
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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> priorityQueue = new PriorityQueue<>(); //将数组中所有的元素放入最小堆中 for (int i = 0; i < arr.length; i++) { priorityQueue.add(arr[i]); } //所需要花费的金钱 int sum = 0; //存储堆顶元素之和 int cur = 0; while (priorityQueue.size() > 1){ cur = priorityQueue.poll()+priorityQueue.poll(); sum+= cur; priorityQueue.add(cur); } return sum; }
6 贪心
例1：贪心堆
输入：参数1，正数数组costs；参数2，正数数组profits；参数3，正数k；参数4，正数m
costs[i]表示i号项目的花费；profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)；k表示你不能并行、只能串行的最多做k个项目；m表示你初始的资金
说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目
输出：你最后获得的最大钱数
在这道题目中可以用一个最小堆和最大堆来解决问题，在最小堆中按照花费排序，弹出小于启动资金的
这个代码好像没找到
例2：一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数组，里面 是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行 的宣讲的场次最多。返回这个最多的宣讲场次
这里正确的贪心方法应该是按照结束时间的早晚进行排序，先去结束时间早的再去结束时间晚的
//定义安排的类 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; }
7 岛问题
出处：LeetCode200岛屿数量。博客上https://www.cnblogs.com/youngao/p/11457061.html有记录，但是代码不好，这里给出左程云的思路：利用一个感染函数，将遍历的过的感染这和博客中的算法思路感觉是很类似的
public static int countIslands(int[][] m) { if (m == null || m[0] == null) { return 0; } int N = m.length; int M = m[0].length; //保存岛屿数量 int res = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (m[i][j] == 1) { res++; //从该点出发，将四周进行感染 infect(m, i, j, N, M); } } } return res; } public static void infect(int[][] m, int i, int j, int N, int M) { if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) { return; } //将感染后置为2 m[i][j] = 2; infect(m, i + 1, j, N, M); infect(m, i - 1, j, N, M); infect(m, i, j + 1, N, M); infect(m, i, j - 1, N, M); }
还有一种是利用多CPU和并查集实现的方法，这里只给出思路
8 递归与回溯
例1：打印一个字符串的全部子序列，包括空字符串
在每一个位置都可以选择要还是不要，并且沿着这条路继续下去
public static void printAllSubsquence(char[] str,int i,String res){ if (i == str.length){ //当前遍历的位置到达字符数组结尾时便打印结果字符串 System.out.println(res); return; } //不要第i个位置的字符 printAllSubsquence(str,i+1,res); //要第i个位置的字符 printAllSubsquence(str,i+1,res+String.valueOf(str[i])); }
例2：给你一个数组arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或者false。
这里为了简单分析，假设数组中全为正数，则数组如下，递归分析如下图所示，一开始记录位置f(0,0)标示从0位置开始向后寻找，在寻找之前和为0。
public static boolean isSum(int[] arr,int i,int sum,int aim){ //当遍历到数组最后位置时要判断是否相等返回，因为一开始0不代表算上自身位置的和所以i应该一直到arr.length而不是arr.length-1 if (i == arr.length){ return sum == aim; } //两种情况，要当前数字和不要当前数字 return isSum(arr,i+1,sum,aim)||isSum(arr,i+1,sum+arr[i],aim); }
分析上述代码，arr、aim是确定的，可变的是i和sum，如：F(3,5)当这个位置确定了以后和前面是怎么来到F(3,5)位置无关，因此可以用动态规划进行优化，i与sum是两个变量因此需要一个二维表维护
根据下面的代码分析出最后一行的结尾，确定只有当sum==aim时才为true
if (i == arr.length){ return sum == aim; }
对任意位置有：
isSum(arr,i+1,sum,aim)||isSum(arr,i+1,sum+arr[i],aim);
需要下面一行的sum位置和sum移动arr[i]即a的位置，根据这些条件可以从下至上递推至(0,0)位置的值为true或false
7 临时补充
1 在LeetCode上有，题号未知
给定一个N行3列二维数组，每一行表示有一座大楼，一共有N座大楼。所有大楼的底部都坐落在X轴上，每一行的三个值(a,b,c)代表每座大楼的从(a,0)点开始，到(b,0)点结束，高度为c。
输入的数据可以保证a<b,且a，b，c均为正数。大楼之间可以有重合。请输出整体的轮廓线。
例子：给定一个二维数组
[
[1, 3, 3],
[2, 4, 4],
[5, 6, 1]
]
输出为轮廓线
[
[1, 2, 3],
[2, 4, 4],
[5, 6, 1]
]
解题分析：
示例分析如下图
稍微复杂一点的例子
轮廓线的产生是因为有高度的变化，即只要有了高度信息那么便可以产生轮廓，采用TreeMap结构进行排序查找。TreeMap本身是有序的，底层采用红黑树实现
//节点中保存上或下，位置，高度信息 public static class Node { public boolean isUp; public int posi; public int h; public Node(boolean bORe, int position, int height) { isUp = bORe; posi = position; h = height; } } //自己定义的一个比较器 public static class NodeComparator implements Comparator<Node> { @Override public int compare(Node o1, Node o2) { //当位置不同时，位置小的在前 if (o1.posi != o2.posi) { return o1.posi - o2.posi; } //当位置相同时，约定上的排在前面，这个排序策略没有严格要求，排在后面也可 if (o1.isUp != o2.isUp) { return o1.isUp ? -1 : 1; } return 0; } } public static List<List<Integer>> buildingOutline(int[][] buildings) { //声明信息数组，一座大楼会被拆成两条信息 Node[] nodes = new Node[buildings.length * 2]; //生成信息数组 for (int i = 0; i < buildings.length; i++) { //存放大楼上的信息 nodes[i * 2] = new Node(true, buildings[i][0], buildings[i][2]); //存放大楼下的信息 nodes[i * 2 + 1] = new Node(false, buildings[i][1], buildings[i][2]); } //先按照位置排序 Arrays.sort(nodes, new NodeComparator()); //key高度，value出现的次数 TreeMap<Integer, Integer> htMap = new TreeMap<>(); //收集每个位置对应的高度信息key位置，value：高度 TreeMap<Integer, Integer> pmMap = new TreeMap<>(); for (int i = 0; i < nodes.length; i++) { if (nodes[i].isUp) { if (!htMap.containsKey(nodes[i].h)) { htMap.put(nodes[i].h, 1); } else { htMap.put(nodes[i].h, htMap.get(nodes[i].h) + 1); } } else { if (htMap.containsKey(nodes[i].h)) { //如果是下，并且频率为1再出现的时候就直接删除了 if (htMap.get(nodes[i].h) == 1) { htMap.remove(nodes[i].h); } else { htMap.put(nodes[i].h, htMap.get(nodes[i].h) - 1); } } } //存放当前位置对应的最大高度信息 if (htMap.isEmpty()) { pmMap.put(nodes[i].posi, 0); } else { pmMap.put(nodes[i].posi, htMap.lastKey()); } } List<List<Integer>> res = new ArrayList<>(); int start = 0; int height = 0;//之前的高度 for (Entry<Integer, Integer> entry : pmMap.entrySet()) { //在遍历的过程中，位置信息是从小到大的 int curPosition = entry.getKey(); int curMaxHeight = entry.getValue(); if (height != curMaxHeight) { //若之前的高度不为0则生成轮廓线 if (height != 0) { List<Integer> newRecord = new ArrayList<Integer>(); newRecord.add(start);//开始位置 newRecord.add(curPosition);//结束位置 newRecord.add(height);//高度 //添加记录 res.add(newRecord); } //若为0，轮廓线开始的位置 start = curPosition; //轮廓线开始的高度 height = curMaxHeight; } } return res; }
2
给定一个字符串str， str表示一个公式， 公式里可能有整数、 加减乘除符号和左右括号， 返回公式的计算结果。
【举例】
str="48*((70-65)-43)+8*1"， 返回-1816。
str="3+1*4"， 返回7。 str="3+(1*4)"， 返回7。
【说明】
1． 可以认为给定的字符串一定是正确的公式， 即不需要对str做公式有效性检查。
2． 如果是负数， 就需要用括号括起来， 比如"4*(-3)"。 但如果负数作为公式的开头或括号部分的开头， 则可以没有括号， 比如"-3*4"和"(-3*4)"都是合法的。
3． 不用考虑计算过程中会发生溢出的情况
public static int getValue(String str) { return value(str.toCharArray(), 0)[0]; } //递归过程，返回值为数组，长度为2arr[0]代表计算结果，arr[1]代表计算到的位置 //i表示当前计算的位置 public static int[] value(char[] str, int i) { //用一个双向链表进行收集，即分析中的栈 LinkedList<String> que = new LinkedList<String>(); int pre = 0; int[] bra = null; while (i < str.length && str[i] != ')') { if (str[i] >= '0' && str[i] <= '9') { //当一直遇到数字时转换成可以计算的类型 pre = pre * 10 + str[i++] - '0'; } else if (str[i] != '(') { //遇到的不是数字且不是左括号即遇到了加减乘除 addNum(que, pre); que.addLast(String.valueOf(str[i++])); pre = 0; } else {//遇到了左括号，进入递归 bra = value(str, i + 1); pre = bra[0]; i = bra[1] + 1;//跳过左括号的位置 } } addNum(que, pre); return new int[] { getNum(que), i }; } public static void addNum(LinkedList<String> que, int num) { if (!que.isEmpty()) { int cur = 0; String top = que.pollLast(); if (top.equals("+") || top.equals("-")) { que.addLast(top); } else { cur = Integer.valueOf(que.pollLast()); num = top.equals("*") ? (cur * num) : (cur / num); } } que.addLast(String.valueOf(num)); } public static int getNum(LinkedList<String> que) { int res = 0; boolean add = true; String cur = null; int num = 0; while (!que.isEmpty()) { cur = que.pollFirst(); if (cur.equals("+")) { add = true; } else if (cur.equals("-")) { add = false; } else { num = Integer.valueOf(cur); res += add ? num : (-num); } } return res; }
3 跳表
功能类似于红黑树，其key是有序的，O(logN)
主要是利用层数来实现的，层数与key值的大小无关而是利用随机函数生成的，该函数只产生两个值0 1，且是等概率的，当产生1时停止。如：1 一层；0 1两层；0001四层。在产生的所有层数中，最大的层数为系统最小。在移动中，遇到比待插入大的向下移动，比待插入小的向右移动
如下图，假设8为三层，先从系统最小的顶层开始，右侧是19，比19小因此向下来到4层，右侧为5,8比5大因此向右移动。重复以上规律最终插入位置如下。
利用上的规律可以跳过许多没必要检索的数据
0