看完了《漫画算法—小灰的算法之旅》第一遍，觉得有些意犹未尽，因此第二次重温时，打算开始做一些笔记，这样可以加深自己对算法知识的理解，也能对没有看过这本书的朋友提供一些帮助。本文为了各位看官方便，由一篇该为四篇，这是第三篇———面试算法
前面学习的东西还是基础知识，而面试中的算法就是对基础知识的灵活运用，下面来看看这些问题？
1.判断链表是否有环？
有一个单向链表，链表中有可能出现“环”，如下图。问题：如何用代码判断该链表是否有环？如何用代码求出环的长度以及入环点？
经过观察发现，链表的每一个元素都是不重复的，这样我们就可以通过穷举遍历、哈希表缓存来实现，但这些都不是最优的方案，我们直接使用快慢指针来判断链表是否有环，代码如下：
/**
* <p>文件描述：面试算法代码<p>
* <p>@author 烤鱼<p>
* <p>@date 2019/11/4 0004 <p>
* <p>@update 2019/11/4 0004<p>
* <p>版本号：1<p>
*
*/
data class Node(var data:Int,var next:Node? = null)
object InterViewCode {
// 链表是否有环
fun isCycle(head:Node):Boolean{
var p1:Node? = head
var p2:Node? = head
while (p1 != null && p2?.next != null){
p1 = p1.next
p2 = p2.next?.next
if(p1 == p2){
return true
}
}
return false
}
}
测试代码：
fun testLinkedCycle(){
val node1 = Node(5)
node1.next = Node(3)
node1.next?.next = Node(7)
node1.next?.next?.next = Node(2)
node1.next?.next?.next?.next = Node(6)
node1.next?.next?.next?.next?.next = node1.next
println("链表是否有环：${InterViewCode.isCycle(node1)}")
}
测试结果：
链表是否有环：true
其实回头来分析原理很简单，就好比龟兔赛跑，之前兔子一直在前面跑，如果赛道是环形的话，那么当兔子跑完第一圈以后，一定会看到乌龟；如果兔子一直跑完也没有看到乌龟，那么他们的赛道一定是非环形的。这个具体看看代码就明白了，代码中兔子的速度设置为乌龟的两倍，当然你也可以设置三倍。
接下来我们需要考虑第二个问题：如何求出环的长度？ 分析一下：
通过上面的龟兔赛跑的龟兔见面，证明了
赛道链表是闭环，如果龟兔第二次见面的话，证明这个过程兔子又跑完了一个整圈了，我们计算这个过程兔子跑的长度就是环的长度了！计算一下：
// 获取链表环的长度
fun getCycleOfLength(head:Node):Int{
var p1:Node? = head
var p2:Node? = head
var count = 0
var length = 0
while (p1 != null && p2?.next != null){
p1 = p1.next
p2 = p2.next?.next
if(p1 == p2){
count++
}
if (count ==1){
length+=1
}
if(count == 2){
return length
}
}
return 0
}
测试一下：
fun testLinkedCycle(){
val node1 = Node(5)
node1.next = Node(3)
node1.next?.next = Node(7)
node1.next?.next?.next = Node(2)
node1.next?.next?.next?.next = Node(6)
node1.next?.next?.next?.next?.next = node1.next
println("链表是否有环：${InterViewCode.isCycle(node1)}")
println("链表环的长度：${InterViewCode.getCycleOfLength(node1)}")
}
测试结果：
链表是否有环：true
链表环的长度：4
回头来分析一下：
兔子的速度比乌龟快
1倍，即乌龟走一步兔子走两步，速度差为1步，当龟兔再次相遇时，兔子老兄已经比乌龟老弟多跑了一圈了，这里可以推理出一个公式：
环长 = 速度差*前进次数
回头再来看代码，这样就容易理解是怎么一回事了！然后我们再来看看最后一个问题：求入环点是多少？
从上图推算得知，当龟兔第一次相遇时：
- 乌龟跑的奔跑的距离是
D+s1- 此时兔子奔跑的距离是
D+(S1+S2)+S1- 根据兔子速度是乌龟的两倍得出：
2*(D+S1) =D+(S1+S2)+S1即D=S2
经过上面的分析，我们尝试在第一次相遇以后，将兔子以速度太快罚到起点重新跑，这个时候兔子心里有委屈，于是和乌龟速度保持同步，然后我们验证一下它们再次相遇的点是不是起点？是的话，就证明我们上面的推论正确。代码如下：
// 获取链表环的起点
fun getCycleOfStart(head:Node):Int{
var p1:Node? = head
var p2:Node? = head
var count = 0
while (p1 != null && p2?.next != null){
// 这是乌龟 速度始终保持
p1 = p1.next
// 这是兔子 速度在相遇前和相遇后有变化
// 相遇以后慢慢跑，和乌龟速度同步
p2 = if(count == 1){
p2.next
}else{
// 还在首圈冲刺阶段，开足马力
p2.next?.next
}
if(p1 == p2){
count++
if(count == 1){
// 从头开始
p1 = head
}else{
return p1?.data?:0
}
}
}
return 0
}
测试代码：
fun testLinkedCycle(){
val node1 = Node(5)
node1.next = Node(3)
node1.next?.next = Node(7)
node1.next?.next?.next = Node(2)
node1.next?.next?.next?.next = Node(6)
node1.next?.next?.next?.next?.next = node1.next
println("链表是否有环：${InterViewCode.isCycle(node1)}")
println("链表环的长度：${InterViewCode.getCycleOfLength(node1)}")
println("链表环的入环点：${InterViewCode.getCycleOfStart(node1)}")
}
测试结果：
链表是否有环：true
链表环的长度：4
链表环的入环点：3
OK ,龟兔赛跑结束了，不分输赢，哈哈！
2.一场关于栈的面试
实现一个栈，该栈带有出栈（
pop）、入栈（push）、取最小元素（getMin）三个方法，要保证三个方法的时间复杂度都是（O(1)）解题思路:加一个备胎
实现代码：
/**
* <p>文件描述：自定义栈<p>
* <p>@author 烤鱼<p>
* <p>@date 2019/11/4 0004 <p>
* <p>@update 2019/11/4 0004<p>
* <p>版本号：1<p>
*
*/
class CustomStack {
private val mainStack = Stack<Int>()
private var minStack = Stack<Int>()
// 入栈
fun push(element:Int){
mainStack.push(element)
if(minStack.empty() || element <= minStack.peek()){
minStack.push(element)
}
}
// 出栈
fun pop():Int{
if(mainStack.peek() == minStack.peek()){
minStack.pop()
}
return mainStack.pop()
}
// 获取栈最小元素
fun getMin():Int{
if(mainStack.empty()){
throw Exception("Stack is empty")
}
return minStack.peek()
}
}
测试效果：
fun testMinStack(){
val stack = CustomStack()
stack.push(5)
stack.push(7)
stack.push(8)
stack.push(3)
stack.push(1)
println(stack.getMin())
stack.pop()
stack.pop()
stack.pop()
println(stack.getMin())
}
测试结果：
1
5
3.如何求出最大公约数
写一段代码，求出两个整数的最大公约数，要尽量优化算法的性能。
看到这道题的时候，我记起了小学五年级学的质数与最大公约数的概念，于是很快的写出了自己的答案：
// 获取最大公约数
fun getGreatCommonDivisor(a:Int,b:Int,c:Int = 1):Int{
val max = kotlin.math.max(a, b)
val min = min(a,b)
if(max % min == 0){
return min
}
var common = c
var total = min
for (i in 2..min){
if(i >= total)break
if(isPrime(i)){
if(min % i == 0 && max % i == 0){
common *= i
total /= common
return getGreatCommonDivisor(max,total,common)
}
}
}
return common
}
// 是否是素数
private fun isPrime(data:Int):Boolean {
if(data<4){
return true
}
if(data%2 == 0){
return false
}
val sqrt = sqrt(data.toDouble())
for (i in 3..sqrt.toInt() step 2){
if(data%i == 0){
return false
}
}
return true;
}
测试代码：
fun getMax(){
val result = InterViewCode.getGreatCommonDivisor(240,600)
println(result)
}
测试结果：
120
我兴致高昂的计算出答案的时候，再一看后面的内容，发现自己太单纯了！原来我解题的思路是通过公式硬算，和暴力枚举差不多是如出一辙，只不过我的方法更靠谱一些。而这道题还有更简单并且是我不知道的公式而已：
辗转相除法 也称为欧几里得算法，指两个整数
a和b(a>b)，它们的最大公约数等于a除以b的余数c和b之间的最大公约数看上去好像比较绕，举个栗子：
24和60，60除以24余12,然后24和12的最大公约数等于12，那么24和64的最大公约数就是12。**注意：**当两个整数较大时，做
a % b取模运算的性能会比较差。
// 辗转相除法
fun getGreatCommonDivisor2(a:Int,b:Int):Int{
val max = kotlin.math.max(a, b)
val min = min(a,b)
if(max%min == 0){
return min
}
return getGreatCommonDivisor2(max%min,min)
}
更相减损术 出自我国的《九章算术》，指两个整数
a和b(a>b)，它们的最大公约数等于a-b的差值c和较小数b的最大公约数注意： 这里还是有个问题，虽然没有取模运算性能差的问题，但是运算效率低，毕竟相减没有相除快！
// 更相减损术
fun getGreatCommonDivisor3(a:Int,b:Int):Int{
if(a == b)return a
val max = kotlin.math.max(a, b)
val min = min(a,b)
if(max % min == 0){
return min
}
return getGreatCommonDivisor2(max - min,min)
}
移位运算 公式推理过程就不再分析了，咱们直接看代码：
// 位移运算
fun getGreatCommonDivisor4(a:Int,b:Int):Int{
if(a == b)return a
if((a and 1) == 0 && (b and 1) == 0 ){
return getGreatCommonDivisor4(a.shr(1),b.shr(1)).shl(1)
}else if((a and 1) == 0 && (b and 1) != 0){
return getGreatCommonDivisor4(a.shr(1),b)
}else if((a and 1) != 0 && (b and 1) == 0){
return getGreatCommonDivisor4(a,b.shr(1))
}else{
val max = kotlin.math.max(a, b)
val min = min(a,b)
return getGreatCommonDivisor4(max-min,min)
}
}
测试代码：
// 求最大公约数
fun getMax(){
// 默认方法
println(InterViewCode.getGreatCommonDivisor(240,600))
// 辗转相除法
println(InterViewCode.getGreatCommonDivisor2(240,600))
// 更相减损术
println(InterViewCode.getGreatCommonDivisor3(240,600))
// 位移运算
println(InterViewCode.getGreatCommonDivisor4(240,600))
}
测试结果：
120
120
120
120
说实话，如果遇到这样的面试题，我肯定不知道怎么答？毕竟哪些公式不是逻辑思维，而是前人推理无数次之后直接拿出来的结论，很少人会记得清楚这些公式。所以，我觉得知道这些就好，不一定需要死记硬背。
4.如何判断一个数是否为2的整数次冥？
实现一个方法，来判断一个正整数是否是
2的整数次冥，要求性能尽可能高。推理过程就不说了，反正我深深相信位运算太强大了！
// 求是否是2的整数次冥
fun isPowerOf(num: Int): Boolean {
return num and num - 1 == 0
}
5.无序数组排序后的最大相邻差
有一个无序整数型数组，如何求出改数组排序后任意两个相邻元素的最大差值？要求时间和空间复杂度最优。
解题思路是通过计数排序或者桶排序来排序的同时，顺便把相邻元素的最大差值一并求出来。
// 求无序数组最大相邻差
fun getMaxSortedDistance(array: IntArray):Int{
var max = array[0]
var min = array[0]
// 计算数列的最大值和最小值以及差值
for (i in array){
if(i>max){
max = i
}
if(i < min){
min = i
}
}
val d = max-min
if(d == 0)return 0
// 初始化桶
val bucketNum = array.size
val bucketList = Array(bucketNum) { _ ->
return@Array Bucket()
}
// 遍历原始数组 确定桶的大小
for (i in array){
// 确定数组元素所归属的桶下标
val index = (i-min)*(bucketNum-1)/d
if(bucketList[index].min == 0 || bucketList[index].min > i){
bucketList[index].min = i
}
if(bucketList[index].max == 0 || bucketList[index].max<i){
bucketList[index].max = i
}
}
// 遍历桶，找到最大值
var leftMax = bucketList[0].max
var result = 0
for (i in 1 until bucketNum){
if(bucketList[i].min == 0)continue
if(bucketList[i].min - leftMax > result){
result = bucketList[i].min - leftMax
}
leftMax = bucketList[i].max
}
return result
}
测试代码：
// 求最大差
fun getMaxDistance(){
println("最大相邻差：${InterViewCode.getMaxSortedDistance(intArrayOf(2,6,3,4,5,10,9))}")
}
测试结果：
最大相邻差：3
6.如何用栈实现队列
用栈来模拟一个队列，要求实现两个基本的操作：入队、出队
老规矩，用两个栈来实现，其中一个栈作为备胎：
/**
* <p>文件描述：用栈实现自定义队列<p>
* <p>@author 烤鱼<p>
* <p>@date 2019/11/4 0004 <p>
* <p>@update 2019/11/4 0004<p>
* <p>版本号：1<p>
*
*/
class CustomQueue {
private val stackA = Stack<Int>()
private val stackB = Stack<Int>()
fun push(element:Int){
stackA.push(element)
}
fun pop():Int{
if(stackB.isEmpty()){
if(stackA.empty()){
throw Exception("Queue is empty!")
}
transfer()
}
return stackB.pop()
}
private fun transfer(){
while (stackA.isNotEmpty()){
stackB.push(stackA.pop())
}
}
}
测试代码：
fun testCustomQueue(){
val customQueue = CustomQueue()
customQueue.push(1)
customQueue.push(2)
customQueue.push(3)
println(customQueue.pop())
println(customQueue.pop())
customQueue.push(4)
println(customQueue.pop())
println(customQueue.pop())
}
测试结果：
1
2
3
4
7.寻找全排列的下一个数（字典序算法）
给出一个正整数,找出这个正整数所有数字全排列的下一个数字。如：
如果输入12345，返回12354
如果输入12354，返回12435
如果输入12435，返回12453
解题思路：
为了和原数接近，我们需要尽量保持高位不变，低位在最小的范围内变换顺序，这个范围也称之为逆序区域。
- 从后向前查看逆向区域，找到逆序区域的前一位，即数字置换的边界
- 让逆序区域的前一位和逆序区域中大于大于它的最小数字交换位置
- 把原来的逆序区域转为顺序状态
代码：
fun findNearestNumber(num:Int):Int{
// 从后向前查看逆向区域，找到逆序区域的前一位，即数字置换的边界
val array = numToArray(num)
val index = findTransFerPoint(array)
// 如果数字置换边界是0 ，说明整个数组已经逆序，无法得到更大的相同数组组成的整数
if(index == 0){
return num
}
// 让逆序区域的前一位和逆序区域中大于大于它的最小数字交换位置
exchange(array,index)
// 把原来的逆序区转为顺序状态
reverse(array,index)
return arrayToNum(array)
}
private fun reverse(array: IntArray, index: Int) {
var j = index
for (i in array.size-1 downTo 1){
if(j<=i)break
val tmp = array[j]
array[j] = array[i]
array[i] = tmp
j++
}
}
private fun exchange(array: IntArray, index: Int) {
val head = array[index-1]
for (i in array.size-1 downTo 1){
if(head < array[i]){
array[index-1] = array[i]
array[i] = head
break
}
}
}
private fun findTransFerPoint(array: IntArray):Int{
for (i in array.size-1 downTo 1){
if(array[i]>array[i-1]){
return i
}
}
return 0
}
// 整数转整数数组
private fun numToArray(num: Int):IntArray{
val b = num.toString()
val result = IntArray(b.length)
val c = b.split(Pattern.compile("/*"))
for (i in c.indices) {
if(c[i].isNotEmpty()){
result[i] = Integer.valueOf(c[i])
}
}
return result
}
// 整数组转整数
private fun arrayToNum(array: IntArray):Int{
val result = StringBuilder()
for (i in array){
result.append(i)
}
return result.toString().toInt()
}
测试代码：
// 测试字典序算法
fun testLexicographicalOrder(){
var value = 12345
for (i in 0 until 10){
value = InterViewCode.findNearestNumber(value)
println(value)
}
}
测试结果：
12354
12453
12543
13542
14532
15432
25431
35421
45321
54321
8.一道关于数字的题目
给出一个整数，从该整数中去掉
k个数字，要求剩下的数字形式的新整数尽可能小。解题思路：
通过局部最优解，得到全局最优解，即贪心算法。
作者的最佳答案：
// 删除数字 K
fun removeKDigits(num:String,k:Int):String{
var count = k;
// 创建一个栈接收所有的数字
val stack = CharArray(num.length)
var top = 0
// 当栈定数字大于遍历到当前数字时，栈顶数字出栈（相当于删除数字）
for (i in num){
while (top >0 && stack[top-1] >i && count >0){
top --
count--
}
stack[top++] = i
}
// 找到栈中第一个非零数字的位置，以此构建新的整数字符串
var offset = 0
while (offset < num.length-k && stack[offset] == '0'){
offset++
}
return if(offset == num.length-k) "0" else String(stack,offset,num.length-k-offset)
}
我的答案：
// 删除数字 K
fun removeKDigits(num:String,k:Int):String{
var count = k;
// 创建一个栈接收所有的数字
val stack = CharArray(num.length)
var top = 0
// 当栈定数字大于遍历到当前数字时，栈顶数字出栈（相当于删除数字）
for (i in num){
while (top >0 && stack[top-1] >i && count >0){
top --
count--
}
stack[top++] = i
}
// 找到栈中第一个非零数字的位置，以此构建新的整数字符串
var offset = 0
while (offset < num.length-k && stack[offset] == '0'){
offset++
}
return if(offset == num.length-k) "0" else String(stack,offset,num.length-k-offset)
}
// 删除数字 K
fun removeKDigits2(num:String,k:Int):String{
return when (k) {
0 -> num
num.length -> "0"
else -> removeKDigits(numToArray(num.toInt()),k).toString()
}
}
// 删除数字 K 具体过程
private fun removeKDigits(num:IntArray, k:Int):Int{
var top = num[0]
var count = k
for (i in 1 until num.size){
if(top>num[i] && num[i] != -1){
num[i-1] = -1
count--
if(count == 0)break
}
top = num[i]
}
if(count >0){
return removeKDigits(num,count)
}
val sb = StringBuilder()
var isOffset = false
for (i in num){
if(isOffset && i != -1){
sb.append(i)
}else{
if(i >= 1){
sb.append(i)
isOffset = true
}
}
}
if(sb.isEmpty())return 0
return sb.toString().toInt()
}
测试代码：
// 测试删除K个数字的方法
fun testRemoveKDigits(){
var value = InterViewCode.removeKDigits("1593212",2)
println(value)
value = InterViewCode.removeKDigits2("1593212",2)
println(value)
value = InterViewCode.removeKDigits("30200",1)
println(value)
value = InterViewCode.removeKDigits2("30200",1)
println(value)
value = InterViewCode.removeKDigits("10",2)
println(value)
value = InterViewCode.removeKDigits("10",2)
println(value)
value = InterViewCode.removeKDigits2("541270936",2)
println(value)
value = InterViewCode.removeKDigits("541270936",2)
println(value)
}
测试结果：
13212
15212
0
0
0
0
1270936
1270936
9.如何实现大整数相加？
给出两个很大的整数（假设有
100位），要求实现两个整数的和。解题思路：
实现代码：
fun bigNumSum(a:String,b:String):String{
if(a.isEmpty())return "0"
if(b.isEmpty())return "0"
val numA = a.split(Pattern.compile("/*")).toTypedArray()
val numB = b.split(Pattern.compile("/*")).toTypedArray()
numA.reverse()
numB.reverse()
val max = Math.max(numA.size,numB.size)
var spaceNumber = 0
val sb = StringBuilder()
for (i in 1..max){
val x = if(numA.size <= i) 0 else numA[i].toInt()
val y = if(numB.size <= i) 0 else numB[i].toInt()
val num = x+y+spaceNumber
spaceNumber = if(num>10){
1
} else if(num == 0){
spaceNumber == 0
continue
}else{
0
}
sb.append(num%10)
}
if(spaceNumber == 1){
sb.append(1)
}
return sb.reverse().toString()
}
测试代码：
// 测试大型整数相加
fun testBigNumSum(){
println(InterViewCode.bigNumSum("256","378"))
println(InterViewCode.bigNumSum("425896556879442311568","104253689514247"))
}
10.如何求解金矿问题
很久很久以前，有一位国王拥有五座金控，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同，例如有的金矿储量是
500KG黄金，需要三个人挖掘......如果参与挖矿的工人总数是
10人，每座金矿要么全挖，要么不挖，不能派出一半的人挖去一半的金矿。要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
这道题考的是动态规划，关键点在于全局最优解和最优子结构之间的关系，以及问题的边界。在数学上面有一个专门的术语——状态转移方程式
F(n,w) = 0(n=0或w=0)n代表金矿数量w代表工人数量
推理过程也很简单，直接看图：
图1
图2
依次类推，七人的时候继续利用类似图
1的原理继续拆分找到七人最优子结构，最后经过递归就可以得到我们预期的答案了。动态规划(
dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。——摘自百度百科
不理解的话，就看看下面的代码吧！
// 动态规划之金矿问题 递归方案
fun getBestGoldMining(w:Int,n:Int,p:IntArray,g:IntArray):Int{
if(w== 0 || n == 0)return 0
// 当人数无法再进行拆分，即问题边界
if(w<p[n-1]){
return getBestGoldMining(w,n-1,p,g)
}
// 返回当前两个选择的最优解
return Math.max(
// 最后一个金矿放弃，即不挖最后一个金矿
getBestGoldMining(w,n-1,p,g),
// 最后一个金矿挖了
getBestGoldMining(w-p[n-1],n-1,p,g)+g[n-1])
}
测试代码：
fun getBestGoldMining(){
// 10 人 5矿 [400KG/5人,500KG/5人,200KG/3人,300KG/4人,350KG/3人]
var value = InterViewCode.getBestGoldMining(10,5, intArrayOf(5,5,3,4,3), intArrayOf(400,500,200,300,350))
println(value)
}
测试结果：
900
当然，这里还没有完，假设我们有100个金矿的话，这个时间复杂度是多少呢？
O(2^100)即2的100次方
所以，我们得考虑优化一下了！推理过程的示意图太麻烦了，你们可以直接看公众号。我们推理的结果是自底向上求解，没有示意图就直接上代码了！
fun getBestGoldMining2(w:Int,p:IntArray,g:IntArray):Int{
// 创建表格
val resultTable = Array(g.size+1){
IntArray(w+1){
0
}
}
// 填充表格
for (i in 1.. g.size){
for (j in 1..w){
if(j<p[i-1]){
resultTable[i][j] = resultTable[i-1][j]
}else{
resultTable[i][j] = Math.max(resultTable[i-1][j],resultTable[i-1][j-p[i-1]]+g[i-1])
}
}
}
return resultTable[g.size][w]
}
测试代码：
fun getBestGoldMining(){
// 10 人 5矿 [400KG/5人,500KG/5人,200KG/3人,300KG/4人,350KG/3人]
var value = InterViewCode.getBestGoldMining(10,5, intArrayOf(5,5,3,4,3), intArrayOf(400,500,200,300,350))
println(value)
value = InterViewCode.getBestGoldMining2(10,intArrayOf(5,5,3,4,3), intArrayOf(400,500,200,300,350))
println(value)
}
测试结果：
900
900
上面的二维数组Kotlin写起来比较复杂，看起来也不容易理解，因此我们再修改一下代码:
// 动态规划之金矿问题 数组方案
// p 工人需求数组
// g 金矿储量数组
fun getBestGoldMining3(w:Int,p:IntArray,g:IntArray):Int{
// 创建数组
val result = IntArray(w+1)
for (i in 1..g.size){
for (j in w downTo 1){
if(j >= p[i-1]){
result[j] = Math.max(result[j],result[j-p[i-1]]+g[i-1])
}
}
}
return result[w]
}
测试代码：
// 测试动态规划
fun getBestGoldMining(){
// 10 人 5矿 [400KG/5人,500KG/5人,200KG/3人,300KG/4人,350KG/3人]
var value = InterViewCode.getBestGoldMining(10,5, intArrayOf(5,5,3,4,3), intArrayOf(400,500,200,300,350))
println(value)
value = InterViewCode.getBestGoldMining2(10,intArrayOf(5,5,3,4,3), intArrayOf(400,500,200,300,350))
println(value)
value = InterViewCode.getBestGoldMining3(10,intArrayOf(5,5,3,4,3), intArrayOf(400,500,200,300,350))
println(value)
}
测试结果：
900
900
900
11.寻找缺失的整数
在一个无序数组里有
99个不重复的正整数，范围是1~100,唯独缺少1个1~100中的整数，如何找出这个缺失的整数？
解法1：
创建一个哈希表，以1到100这100个整数为key，然后遍历整个数组，每读到一个整数就删除这个key，最后剩下的key即是最后答案。
解法2： 将数组元素从小到大排序，然后遍历数组并检查相邻两个元素的连续性，如果发现相邻两个元素不连续，则断开的元素就是最终答案。
解法3：
计算1到100的累加和，然后减去数组的每个元素，最后的得到的值就是最终答案。
问题扩展
一个无序数组有若干个正整数范围是
1~100,其中一个数字出现了奇数次，其余数字出现了偶数次，如何找出这个出现奇数次的数字？
解法：
通过将无序数组进行遍历，依次进行异或(XOR)运算，最后结果就是最终答案
问题再扩展
一个无序数组有若干个正整数范围是
1~100,其中两个数字出现了奇数次，其余数字出现了偶数次，如何找出这个出现奇数次的数字？
解法：
一个整数，可以利用异或运算得到答案，那么如果是两个整数呢？答案是依然可以。我们先使用上面的解法，得到一个所有元素异或的结果，然后根据最后一位是1来进行分治，比如最后一位是1的位置是倒数第一位，那么就根据最后一位来进行分治，最后一位是1在一组，其它元素在另一组，然后再根据上面的方法进行处理，最后就得到了我们想要的那两个整数了。
示例如下：
// 寻找整数
fun findLostNum(array: IntArray):IntArray{
val result = IntArray(2){
return@IntArray 0
}
var value = 0
// 整体异或运算
for (i in array){
value = value xor i
}
// 参数有误
if(value == 0)return result
var separator = 1
while (0 == separator and value){
separator = separator.shl(1)
}
// 分治法
for (i in array){
if(0 == i and separator){
result[0] = result[0] xor i
}else{
result[1] = result[1] xor i
}
}
return result
}
测试代码：
// 寻找整数
fun findLostNum(){
var result = InterViewCode.findLostNum(intArrayOf(4,1,2,2,7,1,4,3))
println(result.contentToString())
}
测试结果：
[3, 7]
后记
1----本文由苏灿烤鱼整理编写,转载请注明
2----如果有什么想要交流的,欢迎留言。也可以加微信:Vicent_0310
3----个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正
