1、判断联表是否有环
1.1 思路
类似于跑道赛跑，两个参赛者以不同的速度进行赛跑，因为跑道是环形的，所以速度快的总能再次追上速度慢的。所以在链表中，可以在头节点设置两个指针，一个一次移动一个位置，一个一次移动两个位置，那么如果链表有环，两个指针总能相遇。
1.2 代码实现
// node:链表的头节点public static boolean isCycle(Node node) {Node p1 = node;Node p2 = node;while (p2!= null && p2.next != null) {p1 = p1.next;p2 = p2.next.next;if (p1 == p2) {return true;}}return false;}public static class Node() {int data;Node next;Node(int data) {this.data = data;}}
1.3 复杂度
时间复杂度是O(n)，因为除了两个指针外没有用到任何额外的空间，所以空间复杂度是O(1)
1.4 问题扩展
- 如果链表有环，求出环的长度。
- 当两个指针第一次相遇时，说明都进入到环中，因为p2速度是p1的两倍，所以当p1走一圈时p2刚好走两圈，此时两个指针第二次相遇。
- 从第一次相遇开始计数循环数，到第二次相遇，循环次数即是一圈的长度，也就是环的长度。
- 如果链表有环，如何求出出入环点
2、最小栈的实现
实现一个栈，要求带有出栈（pop），入栈（push），取最小数（getMin）三个方法，保证这三个方法的复杂度都是O(1)。
2.1 思路
- 创建一个栈A的同时也创建一个额外的栈B，用来辅助栈A
- 当一个新元素进入栈A时，同时也让他进入栈B，这个元素就是栈A的最小值
- 以后每一个元素进入栈A时，都比较新元素跟当前栈A的最小值，如果新元素比原最小值还小，就让新元素也进入栈B。
- 此时的结构，栈B的栈顶为栈A的最小元素，第二个元素为栈A的第二小元素。。。以此类推
- 每当A出栈时，如果出栈的元素是最小元素，则让栈B的栈顶也出栈
- 这样就保证了栈B的栈顶永远是栈A的最小元素。
- 这个解法中，时间复杂度都是O(1),最坏空间复杂度是O(n)
2.2 代码
```java private StackmainStack = new Stack<>(); private Stack minStack = new Stack<>();
// element:入栈的元素 public void push(int element) { mainStack.push(element); // 如果辅助栈为空，或者新元素小于辅助栈的栈顶，那么新元素也压入辅助栈 if (minStack.isEmpty() || element <= minStack.peek()) { minStack.push(); } }
// 出栈 public Integer pop() { // 如果出栈元素跟辅助栈元素相等，那么辅助栈也将栈顶出栈 if (mainStack.peek().equals(minStack.peek())) { minStack.pop(); } return mainStack.pop(); }
// 获取最小元素 public Integer getMin() { if (minStack.empty()) { throw new Exception(“栈为空”)； } return minStack.peek(); }
<a name="V35LX"></a>## 3、如何求最大公约数写一段代码，写出两数的最大公约数，要尽量优化算法的性能。<a name="SOU3T"></a>### 3.1 辗转相除法（欧几里得算法）1. 定理：两个正整数a和b（a > b），它们的最大公约数等于a除以b的余数c与b之间的最大公约数1. 代码```javapublic static int getGreatestCommonDivisorV2(int a, int b) {int big = a > b ? a : b;int small = a > b ? b : a;int remainder = big % small;if (remainder == 0) {return small;}return getGreatestCommonDivisorV2(remainder,small);}
3.2 更相减损法
- 当两个整数较大时，做a%b取模运算的性能会比较低，所以使用更相减损法
- 定理：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小的数的最大公约数。
代码
public static int getGreatestCommonDivisorV2(int a, int b) {if (a == b) {return a;}int big = a > b ? a : b;int small = a > b ? b : a;return getGreatestCommonDivisorV2(big-small,small);}
3.3 两个算法结合的最终版
更相减损数如果两个数相差太大那么递归次数过大
- 代码
```java
public static int gcd(int a, int b){
if(a == b){
} if((a&1)==0 && (b&1)==0){return a;
} else if((a&1)==0 && (b&1)!=0){return gcd(a>>1, b>>1)<<1;
} else if((a&1)!=0 && (b&1)==0){return gcd(a>>1, b);
} else {return gcd(a, b>>1);
} }int big = a>b ? a:b;int small = a<b ? a:b;return gcd(big-small, small);
3. 在上述代码中，判断整数奇偶性的方式是让整数和1进行与运算，如果 (a&1)==0，则说明整数a是偶数；如果(a&1)!=0，则说明整数a是奇数。<a name="ghPPL"></a>## 4、如何判断一个数是否为2的整数幂实现一个方法，来判断一个正整数是否为2的整数次幂，要求性能尽可能高。<a name="hZRWi"></a>### 4.1 思路1. 2的整数次幂，例如2，4，8，16；转为二进制分别是10，100，1000，10000；然后分别减1，结果为1，11，111，1111；用100与11，或者1000与111做按位与运算，结果都为0。1. 结论：2的整数次幂n，与n-1进行按位与运算，结果为0，如果不为0则不是2的整数次幂。<a name="dJE1i"></a>### 4.2 代码```javapublic static boolean isPowerOf2(int num) {return (num&num-1) == 0;}
5、无序数组排序后的最大相邻差
有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值，要求空间复杂度和时间复杂度尽可能的低。
5.1 思路
5.2 代码
public static int getMaxSortedDistance(int[] array){// 1.得到数组的最大值和最小值int max = array[0];int min = array[0];for (int i=0; i < array.length; i++) {if (array[i] > max) {max = array[i];}if (array[i] < min) {min = array[i];}}int d = max - min;// 如果max和min相等，说明数组所有元素都相等if (d = 0) {return d;}// 2.初始化桶int bucketNum = array.length;Bucket[] buckets = new Bucket[bucketNum];for (int i=0; i<bucketNum; i++) {buckets[i] = new Bucket();}// 3.遍历原始数组，确定每个桶的最大最小值for (int i=0; i<array.length; i++) {// 确定数组元素所归属的桶下标int index = ((array[i] - min) * (bucketNum -1) / d);if (buckets[index].min == null || buckets[index].min > array[i]) {buckets[index].min = array[i];}if (buckets[index].max == null || buckets[index].max < array[i]) {buckets[index].max = array[i];}}// 4.遍历桶，找出最大差值int leftMax = buckets[0].max;int maxDistance = 0;for (int=1; i<buckets.length; i++) {if (buckets[i].min == null) {continue;}if (buckets[i].min - leftMax > maxDistance) {maxDistance = buckets[i].min - leftMax;}leftMax = buckets[i].max;}return maxDistance;}public static class Bucket {Integer min;Integer max;}
5.3 复杂度
这个方法不需要像标准桶排序那样给每一个桶内部进行排序，只需要记录桶内的最大和最小值即可，所 以时间复杂度稳定在O(n)。
6、如何用栈实现队列
6.1 思路
用两个栈来实现队列，栈A用来入队，栈B用来出队。比如栈A连续入栈N个元素，此时需要出队时，只需把栈A的元素按顺序出栈再入到栈B，那么栈B的栈顶就是第一个出队的，后续只要入队就加入栈A，出队就从栈B中出，如果栈B为空，再从栈A将元素倒入栈B。
6.2 代码
private Stack<Integer> StackA = new Stack<>();private Stack<Integer> StackB = new Stack<>();// 入队public static void enQueue(int data) {StackA.push(data);}// 出队public static Integer deQueue() {if (stackB.isEmpty()) {if (stackA.isEmpty()) {return null;}transfer();}return stackB.pop();}// 栈A的数据倒入栈Bpublic static void transfer() {while (!stackA.isEmpty) {stackB.push(stackB.pop());}}
6.3 复杂度
入队操作的时间复杂度显然是O(1) 。至于出队操作，如果涉及栈A和栈B的元素迁移，那么一 次出队的时间复杂度是O(n)；如果不用迁移，时间复杂度是O(1)。这里涉及一个新的概念，叫作均摊时间复杂度 。需要元素迁移的出队操作只有少数情况，并且不可能 连续出现，其后的大多数出队操作都不需要元素迁移。所以把时间均摊到每一次出队操作上面，其时间复杂度是O(1) 。
7、寻找全排列的下一个数(字典序算法)
给出一个正整数，找出这个正整数所有数字全排列的下一个数。说通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅 大于原数的新整数。让我们举几个例子。如果输入12345，则返回12354。 如果输入12354，则返回12435。
7.1 思路
最大的数：54321 顺序
最小的数：12345 逆序
比如1，2，3，5，4；为了与原数接近，应该尽量保持高位不变，低位在最小范围内变换顺序，至于变换顺序的范围大小，则取决于当前整数的逆序区域。从后往前找，前一个比后一个元素小就是逆序，第一个逆序区域是5，4；54已经是当前逆序的最大组合，所以再往前找一个位置，即354；首先需要从后面的区域中找到比3大的最小数，即4，与之交换变成453；倒数第三位已经确定，然后倒数两位仍为逆序，将之交换变为顺序即435；最后结果即12435。
步骤总结：
- 从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
- 让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
- 把原来的逆序区域转为顺序状态
7.2 代码
```java public static int[] findNearestNumber(int[] numbers){ // 1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。 int index = findTransferPoint(numbers); // 如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数字组成的整数 if (index = 0) {
} // 2.让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。 //复制并入参，避免直接修改入参 int[] numbersCopy = Arrays.copyOf(numbers, numbers.length); exchangeHead(numbersCopy, index-1); // 3.把原来的逆序区域转为顺序 reverse(numbersCopy, index); return numbersCopy; }return null;
// 查找逆序的边界 public static int findTransferPoint(int[] numbers) { for (int i=numbers.length-1; i>0; i—) { if (numbers[i] > numbers[i-1]) { return i; } } return 0; }
// 逆序区域边界值与逆序区域的刚好大于它的值交换 private static int[] exchangeHead(int[] numbers, int index) { int head = numbers[index]; for (int i=numbers.length-1; i>0; i—) { if (head < numbers[i]) { numbers[index] = numbers[i]; numbers[i] = head; break; } } return numbers; }
// 逆序变顺序 private static int[] reverse(int[] num, int index){ for (int i=index,j=num.length-1; i<j; i++,j—) { int temp = num[i]; num[i] = num[j]; num[j] = temp; } return num; }
<a name="JX5Qj"></a>### 7.3 复杂度该算法3个步骤每一步的时间复杂度都是O(n)，所以整体时间复杂度也是O(n)<a name="WgXFZ"></a>## 8、删掉k个数字后的最小值给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整 数尽可能小。应该如何选取被去掉的数字？<a name="k1akB"></a>### 8.1 思路给出一个整数541 270 936 ，要求删去1个数字，让剩下的整数尽可能小。此时，无论删除哪一个数字，最后的结果都是从9位整数变成8位整数。 既然同样是8位整数，显然应该优先把高位的数字降低，这样对新整数 的值影响最大。把原整数的所有数字从左到右进 行比较，如果发现某一位数字大于它右面的数字，那么在删除该数字 后，必然会使该数位的值降低 ，因为右面比它小的数字顶替了它的位 置。<br />代码解决方法：<br /><br /><br /><a name="r9SKj"></a>### 8.2 代码```java// num：原整数 k：删除数量public static String removeKDigits(String num, int k) {// 新整数的最终长度 = 原整数长度 - kint newLength = num.length() - k;// 创建一个栈，用来接收所有的数字char[] stack = new char(num.lemgth);int top = 0;for (int i=0; i<num.length();++i) {char c = num.charAt(i);// 当栈顶数字大于遍历到的当前数字时，栈顶数字出栈，相当于删除数字if (top > 0 && stack[top-1] > c && k > 0) {top -= 1;k -= 1;}stack[top++] = c;}// 找到栈中第一个非0数字的位置，以此构建新的整数字符串int offset = 0;while (offset < newLength && stack[offset] == '0') {offset++;}return offset == newLength? "0": new String(stack,offset, newLength - offset);}
9、如何实现两个大整数相加
给出两个很大的整数，要求实现程序求出两个整数之和。整数可能大到long类型装不下。
9.1 思路
9.2 代码
// bigNumberA：大整数A bigNumB：大整数Bpublic static String bigNumberSum(String bigNumberA,String bigNumberB) {// 1.把两个大整数用数组逆序存储，长度为较大整数的长度+1int maxLength = bigNumA.length() > bigNumB.length() ? bigNumA.length(): bigNumB.length();int[] arrayA = new int[maxLength + 1];for (int i=0; i<bigNumA.length();i++) {arrayA[i] = bigNumA.charAt(bigNumA.length()-1-i);}int[] arrayB = new int[maxLength + 1];for (int i=0; i<bigNumA.length();i++) {arrayB[i] = bigNumB.charAt(bigNumB.length()-1-i);}// 2.构建result数组，数组长度 = 较大整数长度 + 1int[] result = new int[maxLength + 1];// 3.遍历数组，按位相加for (i=0; i<result.length(); i++) {int temp = result[i];temp += arrayA[i];temp += arrayB[i];// 判断是否进位if (temp > 10) {temp = temp - 10;result[i+1] = 1;}rerult[i] = temp;}// 4.把reslut的数据再次逆序转为stringStringBuilder sb = new StringBuilder();boolean findFirst = false;for (int i=result.length-1; i>=0; i--) {if (!findFirst) {if (result[i] == 0) {continue;}findFirse = true;}sb.append(result[i]);}return sb.toString();}
9.3 复杂度
如果给出的大整数的最长位数是n，那么创建数组、按位计算、结果逆序的时间复杂度各自都是 O(n)，整体的时间复杂度也是O(n) 。
10、如何解决金矿问题
10.1 思路
- 动态规划：把复杂的问题简化成规模较小的子问题，再从简单的子问 题自底向上一步一步递推，最终得到复杂问题的最优解。
- 分析金矿的例子
- 首先，对于问题中的金矿来说，每一个金矿都存在着“挖”和“不挖”两种 选择。
- 如果最后一个金矿注定不被挖掘，显然，问题简化成了10个工人在前4个金矿中做出最优选择。
- 相应地，假设最后一个金矿一定会被挖掘，由于最后一个金矿消耗了3个工人，问题简化成了7个工人前4个金矿 中做出最优选择。
- 这两种简化情况，被称为全局问题的两个最优子结构 。
- 同样的道理，对于前4个金矿的选择，我们还可以做进一步简化。 首先针对10个工人4个金矿这个子结构，第4个金矿（300kg黄金/4人） 可以选择挖与不挖。根据第4个金矿的选择，问题又简化成了两种更小 的子结构。
- 10个工人在前3个金矿中做出最优选择。
- 6（10-4=6）个工人在前3个金矿中做出最优选择。
- 相应地，对于7个工人4个金矿这个子结构，第4个金矿同样可以选择挖 与不挖。根据第4个金矿的选择，问题也简化成了两种更小的子结构。
- 7个工人在前3个金矿中做出最优选择。
- 3（7-4=3）个工人在前3个金矿中做出最优选择。
- 就这样，问题一分为二，二分为四，一直把问题简化成在0个金矿或0个 工人时的最优选择，这个收益结果显然是0，也就是问题的边界 。
- 这就是动态规划的要点：确定全局最优解和最优子结构之间的关系，以及问题的边界。这个关系用数学 公式来表达的话，就叫作状态转移方程式 。
10.2 代码
```java /**- 获得金矿最优收益
- @param w 工人数量
- @param p 金矿开采所需的工人数量
- @param g 金矿储量
*/
public static int getBestGoldMiningV3(int w, int[] p, int[] g)
//创建当前结果
int[] results = new int[w+1];
//填充一维数组
for(int i=1; i<=g.length; i++){
for(int j=w; j>=1; j—){
} } //返回最后1个格子的值 return results[w]; }if(j>=p[i-1]){results[j] = Math.max(results[j],results[j-p[i-1]]+ g[i-1]);}
<a name="PF9pv"></a>## 11、 寻找缺失的整数在一个无序数组里有99个不重复的正整数，范围是1～100，唯独缺少1 个1～100中的整数。如何找出这个缺失的整数？<a name="b8Ezi"></a>### 11.1 思路1. 创建一个哈希表，以1到100这100个整数为Key。然后遍历整个数组，每读到一个整数，就定位到哈希表中对应的Key，然后删除这个Key。 由于数组中缺少1个整数，哈希表最终一定会有99个Key被删除，从而剩 下1个唯一的Key。这个剩下的Key就是那个缺失的整数。 假设数组长度是n，那么该解法的时间复杂度是O(n)，空间复杂度是 O(n)。1. 先把数组元素从小到大进行排序，然后遍历已经有序的数组，如果发现 某两个相邻元素并不连续，说明缺少的就是这两个元素之间的整数。假设数组长度是n，如果用时间复杂度为O(nlogn)的排序算法进行排序， 那么该解法的时间复杂度是O(nlogn)，空间复杂度是O(1)。1. 先算出1+2+3+…+100的和，然后依 次减去数组里的元素，最后得到的差值，就是那个缺失的整数。假设数组长度是n，那么该解法的时间复杂度是O(n)，空间复杂度是 O(1)。<a name="toXBg"></a>### 11.2 问题扩展1. 一个无序数组里有若干个正整数，范围是1～100，其中99个整数都出现 了偶数次 ，只有1个整数出现了奇数次 ，如何找到这个出现奇数次的整数？- 利用异或运算，在进行位运算时，相同位为0，不同位为1。例如一个无序数组{1，2，4，3，2，4，1}；利用异或运算（满足交换律和结合律），1 xor 2 xor 4 xor 3 xor 2 xor 4 xor1 = 1 xor 1 xor 2 xor 2 xor 4 xor 4 xor 3 = 0 xor 3 = 3。2. 假设一个无序数组里有若干个正整数，范围是1～100，其中有98个整数 出现了偶数次，只有2个 整数出现了奇数次，如何找到这2个出现奇数次的整数- - - 代码：```javapublic static int[] findLostNum(int[] array) {//用于存储2个出现奇数次的整数int result[] = new int[2];//第1次进行整体异或运算int xorResult = 0;for(int i=0;i<array.length;i++){xorResult^=array[i];}//如果进行异或运算的结果为0，则说明输入的数组不符合题目要求if(xorResult == 0){return null;}//确定2个整数的不同位，以此来做分组int separator = 1;while (0==(xorResult&separator)){separator<<=1;}//第2次分组进行异或运算for(int i=0;i<array.length;i++){if(0==(array[i]&separator)){result[0]^=array[i];}else {result[1]^=array[i];}}return result;}public static void main(String[] args) {int[] array = {4,1,2,2,5,1,4,3};int[] result = findLostNum(array);System.out.println(result[0] + "," + result[1]);}
若有收获，就点个赞吧
0 人点赞
