阅读 81

漫画算法》读后笔记(三)

看完了《漫画算法—小灰的算法之旅》第一遍,觉得有些意犹未尽,因此第二次重温时,打算开始做一些笔记,这样可以加深自己对算法知识的理解,也能对没有看过这本书的朋友提供一些帮助。本文为了各位看官方便,由一篇该为四篇,这是第三篇———面试算法

前面学习的东西还是基础知识,而面试中的算法就是对基础知识的灵活运用,下面来看看这些问题?

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)+S1D = 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
复制代码

我兴致高昂的计算出答案的时候,再一看后面的内容,发现自己太单纯了!原来我解题的思路是通过公式硬算,和暴力枚举差不多是如出一辙,只不过我的方法更靠谱一些。而这道题还有更简单并且是我不知道的公式而已:

辗转相除法 也称为欧几里得算法,指两个整数ab(a>b),它们的最大公约数等于a除以b的余数cb之间的最大公约数

看上去好像比较绕,举个栗子:246060除以2412,然后2412的最大公约数等于12,那么2464的最大公约数就是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)
    }
复制代码

更相减损术 出自我国的《九章算术》,指两个整数ab(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

解题思路:

为了和原数接近,我们需要尽量保持高位不变,低位在最小的范围内变换顺序,这个范围也称之为逆序区域。

  1. 从后向前查看逆向区域,找到逆序区域的前一位,即数字置换的边界
  2. 让逆序区域的前一位和逆序区域中大于大于它的最小数字交换位置
  3. 把原来的逆序区域转为顺序状态

代码:

    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)2100次方

所以,我们得考虑优化一下了!推理过程的示意图太麻烦了,你们可以直接看公众号。我们推理的结果是自底向上求解,没有示意图就直接上代码了!

    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,唯独缺少11~100中的整数,如何找出这个缺失的整数?

解法1: 创建一个哈希表,以1100100个整数为key,然后遍历整个数组,每读到一个整数就删除这个key,最后剩下的key即是最后答案。

解法2: 将数组元素从小到大排序,然后遍历数组并检查相邻两个元素的连续性,如果发现相邻两个元素不连续,则断开的元素就是最终答案。

解法3: 计算1100的累加和,然后减去数组的每个元素,最后的得到的值就是最终答案。

问题扩展

一个无序数组有若干个正整数范围是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----个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正

传送门

关注下面的标签,发现更多相似文章
评论