/**
* <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)breakif(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){
returntrue
}
if(data%2 == 0){
returnfalse
}
val sqrt = sqrt(data.toDouble())
for (i in 3..sqrt.toInt() step 2){
if(data%i == 0){
returnfalse
}
}
returntrue;
}
复制代码
测试代码：
fun getMax(){
val result = InterViewCode.getGreatCommonDivisor(240,600)
println(result)
}
复制代码
// 辗转相除法
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)
}
复制代码
// 更相减损术
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)
}elseif((a and 1) == 0 && (b and 1) != 0){
return getGreatCommonDivisor4(a.shr(1),b)
}elseif((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)
}
}
复制代码
// 求是否是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)continueif(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)
}
}
复制代码
// 删除数字 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++
}
returnif(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++
}
returnif(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 = falsefor (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
} elseif(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"))
}
复制代码
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)
}
复制代码
// 寻找整数
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())
}
复制代码
