# Algorithms **Repository Path**: iambenben/Algorithms ## Basic Information - **Project Name**: Algorithms - **Description**: ACM算法习题库，作者参加ACM多年以来完成的算法题解。算法包含：字典树、线段树、深搜、广搜、图论、动态规划、递归、优先队列、排序、遗传算法、逆波兰表达式等。 - **Primary Language**: Java - **License**: GPL-3.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 3 - **Created**: 2024-01-24 - **Last Updated**: 2024-01-24 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # Algorithms ACM算法习题库，作者参加ACM多年以来完成的算法题解，平时闲暇也会写一些算法题锻炼编程思维，在此记录分享~ 项目包含：分治算法、字典树、线段树、深搜、广搜、BitMap、排列组合、图论、动态规划、递归、贪心算法、优先队列、 快速排序、归并排序、遗传算法、逆波兰表达式、并查集、图形打印等算法。 [![java](https://img.shields.io/badge/language-java-orange.svg)]() [![jdk](https://img.shields.io/badge/jdk-17-red.svg)]() [![License](http://img.shields.io/:license-apache-blue.svg)](http://www.apache.org/licenses/LICENSE-2.0.html) * 作者：YouYuan * 邮箱：xiyousuiyuan#163.com ## 十亿手机号排序去重-腾讯面试题 ### 题目 有一个保存了十亿条手机号的文件，JVM可用内存只有1G，请设计算法实现这10亿手机号的去重与排序，输出去重排序后的文件。 ### 解题分析思路 * 十亿条手机号的文件，在磁盘中占用的空间大约为10亿*11(byte)=11G，所以肯定要分批进行读取。 * 传统的数组循环去重或者利用Set集合去重，需要一次加载所有数据，一次性读取10亿数据使用String存储至少需要的JVM内存为10亿*(40+2*11)byte=57G，使用Long存储则需要7G内存，方案不可行。 * 使用前缀树的数据结构可以实现号码的储存与去重，对内存空间的利用率也高，手机号第一位均为1可以省去，存储11位手机号的前缀树高10层，需要的内存为第1位是10bit，第2位要100bit，第10位10的10次方bit，共需1.5G，可惜依然不满足1G的内存限制条件。 * 使用BitMap，利用电话号作为index映射到bitmap对应的位置，存储1个号码仅需要1bit，手机号第一位均为1可以省去，存储范围1000000000~9999999999共需要9999999999-1000000000(bit)=1.04G，还是不满足1G的内存限制条件，继续优化！ * 根据手机号的数据特性对BitMap进行优化：因为手机前3位为号段，只有有限的类型，可以将号码拆分为3位号段+8位号码的形式，BitMap只存储8位号码，号段使用Map映射，那么单个BitMap需要的内存为99999999-10000000(bit)=12M，创建50个号段，内存总花费12M*50=600M，完美！ * 使用BitMap存储数据消耗了600M内存，剩余400M内存可以用于读取数据，考虑到算法还有其他对象会占用空间，避免Java内存OOM使用300M用来读取数据比较合适，那么一次读取的数据量大概为300M/(40+11*2)=500万条，10亿数据分200次处理即可完成。 * 文件的读取与输出：使用缓冲流渐进式读取文件，避免爆内存，数据的输出只要遍历BitMap中的有值下标，与号段组装成完整手机号，使用缓冲流写入文件即可。 * 测试验证：运行时添加VM参数-Xms1G -Xmx1G对JVM使用的内存进行限制，确保算法满足题目1G内存的需求。 **知识点：Java中String对象占用内存的计算** ``` Java中一个空 String 所占空间为： 对象头（8 字节）+ 引用 (4 字节 ) + char 数组（16 字节）+ 1个 int（4字节）+ 1个long（8字节）= 40 字节。 String占用内存计算公式：40 + 2 * n，n为字符串长度。 ``` 完整解题源码：[跳转源码](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E9%9D%A2%E8%AF%95%E9%A2%98/%E5%8D%81%E4%BA%BF%E6%89%8B%E6%9C%BA%E5%8F%B7%E5%8E%BB%E9%87%8D.java) ## 求可翻转数组的最大子序列-美团面试题 ### 题目 给定一个序列数组，你有一次翻转该序列任意区间元素的机会(可以不翻转)，请找出该序列的最大累加和子序列。 例如给定数组 `[1,3,5,-10,10]` ， 翻转 `[-10,10]` 可得序列 `[1,3,5,10,-10]` ，最大累加和序列为`[1,3,5,10]`。 ### 解题思路 采用动态规划求解，序列最大累加和递推式： `dpMax[i] = Math.max(dpMax[i - 1] + arr[i], arr[i])` 记录当前最大累加和curMax，翻转后的最大累加和递推式： `dpReverse[i] = Math.max(arr[i] + curMax, arr[i] + dpReverse[i - 1])` 完整解题源码与思路：[跳转源码](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E6%89%BE%E6%9C%80%E5%A4%A7%E7%B4%AF%E5%8A%A0%E5%92%8C%E5%BA%8F%E5%88%97_%E5%8F%AF%E7%BF%BB%E8%BD%AC.java) ## 0-1背包问题-美团字节面试题 ### 题目 一个正在抢劫商店的小偷发现了n个商品，第i个商品价值v[i]美元，重w[i]磅，v[i]和w[i]都是整数。 这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅重的商品，W是一个整数．他应该拿哪些商品才能最大化价值呢？ ### 解题思路 我们称这个问题是0-1背包问题，因为对每个商品，小偷要么把它完整拿走，要么把它留下，他不能只拿走一个商品的一部分，或者把一个商品拿走多次，所以0-1背包问题不能使用贪心算法来求解（局部最优解不一定是全局最优解）。 先看看递归的解法： ```java /** * 计算背包能够装下的最大价值 递归解法，时间复杂度高 * 因为递归包含了大量中间结果的重复计算，只要数据集稍微大一点，计算复杂度呈指数级增加 * @param v 商品价值 * @param w 商品重量 * @param space 剩余空间 * @param current 当前位置 * @param cost 当前价值总值 */ private static int f(int[] v, int[] w, int space, int current, int cost) { if (space <= 0 || current >= v.length) { return cost; } int cost_1 = 0; int cost_2 = 0; if (space - w[current] >= 0) { //选择当前商品，空间减去当前重量，总价值加上当前价值，继续查看下一个商品 cost_1 = f(v, w, space - w[current], mark, current+1, cost+v[current]); } //不选择当前商品，空间和总价值不变，继续看下一个商品 cost_2 = f(v, w, space, mark, current+1, cost); // 返回挑选当前商品和不挑选当前商品能达到的总价值较大的那个 return cost_1 > cost_2 ? cost_1 : cost_2; } ``` 动态规划递推求解： 创建二维数组c用来递推保存最大总价值，设c[i,j]代表总容量为j的背包中装下的总共i种商品的最大总价值。 则0-1背包问题的目标是获得c[n,W]的最大值，其中n是可选商品的种类，W是背包总容量。 则0-1背包问题的最优子结构为： 1. 如果最优解包含第n种商品，则接下来需要解决子问题：背包剩余容量为W-w[n]，需要在前n-1种商品中作出选择并得出最优解。 2. 如果最优解不包含第n种商品，则接下来需要解决子问题：背包剩余容量为W，需要在前n-1种商品中作出选择并得出最优解。 综上所述，c[i,j]的递推式为： `c[i,j]=max{c[i-1,j]，c[i-1,j-w[i]]+v[i]}` 完整解题源码与思路：[跳转源码](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98.java) ## 字典序第K小的数 ### 题目 给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。注意：k和n可能很大 (1 <= k <= n <= 1000000000) 示例: 输入: n = 13, k = 2 输出: 10 题目链接：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order ### 解题思路 假如n=13，k=2，字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。 首先写出字典序生成的递归代码，因为n取值范围很大，使用递归处理大数据肯定超时，但是可以根据字典序排列规律来尝试优化解题方案。 在n=99时，递归输出的字典序列： ``` n=99时的字典序列： 1,10,11,12,13,14,15,16,17,18,19, 2,20,21,22,23,24,25,26,27,28,29, 3,30,31,32,33,34,35,36,37,38,39, 4,40,41,42,43,44,45,46,47,48,49, 5,50,51,52,53,54,55,56,57,58,59, 6,60,61,62,63,64,65,66,67,68,69, 7,70,71,72,73,74,75,76,77,78,79, 8,80,81,82,83,84,85,86,87,88,89, 9,90,91,92,93,94,95,96,97,98,99 ``` 可以总结出字典序数列的排列按照规律周期性重复，每个大层数字个数`len = (len * 10 + 1) 循环n的进位数次`，n=10则循环1次，n=100则循环2次，n=1000则循环3次，每层的个数分别位11，111，1111，以此类推。 完整解题源码与思路：[跳转源码](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E9%9D%A2%E8%AF%95%E9%A2%98/%E5%AD%97%E5%85%B8%E5%BA%8F%E7%9A%84%E7%AC%ACK%E5%B0%8F%E6%95%B0%E5%AD%97.java) ## 不使用加号实现整数加法-位运算 ### 题目 输入两个整数a和b，请输出a+b的结果，不能使用加号，包括调用的函数内也不能有加法运算。（-999999999 <= a,b <= 999999999） 示例： 输入 15 33 输出 48 输入： -999999999 999999999 输出 0 ### 解题思路 因为规定了完全不能使用加法运算，所以可用的运算方式只剩下位运算了，所以本题相当于使用位运算实现加法。 那么该如何实现呢？首先来看看位运算的运算规则： 1^1=0, 0^1=1, 0^0=0 根据异或的运算规则，可以使用异或运算来计算数字的相加结果。 1&1=1, 1&0=0, 0&0=0 根据与运算的规则，可以使用与运算来计算数字相加后的进位结果。 那么使用异或运算和与运算结合，就能够实现整数的加法了。 **计算过程如下：** ``` 例如3+5，二进制表示为 011 +101 3+5的二进制异或运算加法过程： 11 ^ 101 = 110(和) 11 & 101 = 001(进位数) 001 << 1 = 10(进位操作) 110 ^ 10 = 100(累加和) 110 & 10 = 10(计算进位数) 10 << 1 = 100(进位操作) 100 ^ 100 = 011(累加和) 100 & 100 = 100(计算进位数) 100 << 1 = 1000(进位操作) 011 ^ 1000 = 1000(累加和) 011 & 1000 = 0(没有进位了，计算结束) 计算出3+5的最终结果为1000(二进制)=8(十进制) ``` 另外需要注意，输入数字的范围是int范围，但是两个int相加之后可能超出int范围导致运算溢出，所以结果的保存要使用long类型。 拓展思考： 既然使用位运算实现了加法，那么如何使用位运算实现减法呢？ 完整解题源码与思路：[跳转源码](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E9%9D%A2%E8%AF%95%E9%A2%98/%E4%B8%8D%E4%BD%BF%E7%94%A8%E5%8A%A0%E5%8F%B7%E5%AE%9E%E7%8E%B0%E6%95%B4%E6%95%B0%E5%8A%A0%E6%B3%95.java)