hangscer

scala写算法-List、Stream、以及剑指Offer里部分题目基于scala解法

2017/05/26

Stream(immutable)

Stream是惰性列表。实现细节涉及到lazy懒惰求值传名参数等等技术(具体细节详见维基百科-求值策略)。
StreamList是scala中严格求值非严格求值两个代表性不可变函数式数据结构。
考虑字符串拼接的表达式"foo"+"bar"的到"foobar",空串""就是这个操作的单位元(identity,数学中又称幺元),也就是说s+""或者""+s的值就是s。如果将三个字符串相加s+t+r,由于操作是可结合的(associative),所以说((s+t)+r)(s+(t+r))的结果一样。
在函数式编程里,把这类代数称为monoid。结合律(associativity)和同一律(identity)法则被称为monoid法则。

可折叠数据结构

比如ListStreamTreeVector等等这类都是可折叠数据结构。monoid与折叠操作有着紧密联系。
比如words=List("aa","bb","cc"),运用折叠方法如下:

1
2
words.foldRight("")((a,b)=>a+b) == ((""+"aa")+"bb")+"cc"
words.foldLeft("")((a,b)=>a+b) == "aa"+("bb"+("cc"+""))

首先实现Stream.fold方法,然后用fold去实现map filter flatMap等等高阶函数(大可不必仅使用fold去编写其它函数,就像尺规作图没有刻度一样。这样写仅仅为了好玩,没有银弹No Silver Bullet)。至于mapflatMap是什么?函子(Functor)是对map的泛化,Monad是对flatMap的泛化(相关概念参见Fp in Scala)。
fold源码如下(采用尾递归):

1
2
3
4
5
6
7
8
def fold[B](z: =>B)(f:(A,B)=>B):B={
@tailrec
def loop(stream: Stream[A])(result: =>B)(f:(A,B)=>B):B=stream match {
case Empty =>result
case Cons(h,t) =>loop(t())(f(h(),result))(f)
}
loop(self)(z)(f)
}

Stream实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
trait Stream[+A] {self=>
import Stream.{cons,empty}
def fold[B](z: =>B)(f:(A,B)=>B):B={
@tailrec
def loop(stream: Stream[A])(result: =>B)(f:(A,B)=>B):B=stream match {
case Empty =>result
case Cons(h,t) =>loop(t())(f(h(),result))(f)
}
loop(self)(z)(f)
}
def toList=fold(Nil:List[A])((a,b)=> ::(a,b)).invert
def exits(p:A=>Boolean)=fold(false)((a,b)=>p(a)||b)
def forall(p:A=>Boolean)=fold(true)((a,b)=>p(a)&&b)
def invert=fold(Empty:Stream[A])((a,b)=>cons(a,b))
def map[B](f:A=>B)=fold(Empty:Stream[B])((a,b)=> cons(f(a),b)).invert
def ++[B>:A](stream:Stream[B])=invert.fold(stream)((a,b)=>{cons(a,b)})
def flatMap[B>:A](f:A=>Stream[B])=fold(Empty:Stream[B])((a,b)=>{f(a)++b}).invert
def filter(p:A=>Boolean)=fold(Empty:Stream[A])((a,b)=>p(a) match {
case true =>cons(a,b)
case false =>b
}).invert
def take(n:Int)=fold((n,empty[A]))((a,b)=> b._1 match {
case r if r >0=>(r-1,cons(a,b._2))
case 0=>(0,b._2)
})._2.invert
def drop(n:Int)=fold((n,empty[A]))((a,b)=>b._1 match {
case r if r>0 =>(r-1,b._2)
case 0 => (0,cons(a,b._2))
})._2
}
case class Cons[+A](h:()=>A,t:()=>Stream[A]) extends Stream[A]
case object Empty extends Stream[Nothing]
object Stream{
def cons[A](hd: =>A,tl: =>Stream[A]) :Stream[A]={
lazy val head=hd
lazy val tail=tl
Cons(()=>head,()=>tail)
}
def empty[A]:Stream[A]=Empty
def apply[A](xs:A*):Stream[A]=
if(xs.isEmpty)
empty
else
cons(xs.head,apply(xs.tail:_*))
}

List(immutable)

scala中的List实现方式类似于c语言中的链表数据结构,但是不同于链表,List是不可变的。就像字符串操作a=b+c,字符串a加上字符串b的到新的字符串c,同理,不可变的List,al=bl++cl,listbl与listcl相连接的到新的listal,而blcl本身不变。相比抽象数据结构ADT,我更愿意把List称作代数数据结构。其不变性与函数式数据结构中的数据共享有关(通过复制与共享实现了不变性)。
至于exists forall takeWhile take filter map foldRight等函数均采用尾递归方式,无需考虑爆栈问题。与官方库基于CanBuildFrom这类的虚类型实现方式不同,本程序完全采用递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
trait List[+A]{self=>
def tail=self match {
case Nil => Nil
case _::t=>t
}
def init:List[A]=self match {
case Nil=> Nil
case h::Nil => Nil
case h::t=> ::(h,t.init)
}
def print={
def loop(list: List[A]):String=list match {
case Nil=>"Nil"
case h::t=>s"$h :: ${loop(t)}"
}
loop(self)
}
override def toString= print
def setHead[B>:A](newHead:B)= ::(newHead,self.tail)
def drop(n:Int):List[A]=n match {
case 0=>self
case _ if n>0 => self match {
case _::t=> t.drop(n-1)
}
case _ if n<0 =>Nil
}
def dropWhile(p:A=>Boolean):List[A]=self match {
case Nil=>Nil
case h::t=>p(h) match {
case true => t.dropWhile(p)
case false=> self
}
}
def ++[B>:A](list: List[B]):List[B]=self match {
case Nil=>list
case h::t=> ::(h,t++list)
}
def foldRight[B](z:B)(f:(A,B)=>B)={
@tailrec
def loop(list: List[A])(z:B)(f:(A,B)=>B):B=list match {
case Nil => z
case h::t => loop(t)(f(h,z))(f)
}
loop(self)(z)(f)
}
def invert=foldRight(Nil:List[A])(::(_,_))
def length=foldRight(0)((_,b)=>b+1)
def flatMap[B>:A](f:B=>List[B]):List[B]=self match {
case Nil=> Nil
case h::t=> f(h)++t.flatMap(f)
}
def map[B](f:A=>B)={
@tailrec
def loop(list: List[A])(result:List[B])(f:A=>B):List[B]=list match {
case Nil=>result
case h::t => loop(t)(::(f(h),result))(f)
}
loop(self)(Nil:List[B])(f).invert
}
def filter(p:A=>Boolean):List[A]={
@tailrec
def loop(list: List[A])(result:List[A])(p:A=>Boolean):List[A]=list match {
case Nil => result
case h::t => p(h) match {
case true =>loop(t)(::(h,result))(p)
case false=>loop(t)(result)(p)
}
}
loop(self)(Nil)(p).invert
}
def take(n:Int):List[A]={
@tailrec
def loop(list: List[A])(result:List[A])(n:Int):List[A]=list match {
case Nil=> result
case h::t => n match {
case 0 =>result
case _ if n>0 =>loop(t)(::(h,result))(n-1)
}
}
loop(self)(Nil)(n).invert
}
def takeWhile(p:A=>Boolean):List[A]={
@tailrec
def loop(list: List[A])(result:List[A])(p:A=>Boolean):List[A]=list match {
case Nil=>result
case h::t=>p(h) match {
case true => loop(t)(::(h,result))(p)
case false => result
}
}
loop(self)(Nil)(p).invert
}
def forall(p:A=>Boolean):Boolean={
@tailrec
def loop(list: List[A])(result:Boolean)(p:A=>Boolean):Boolean=list match {
case Nil => result
case h::t => p(h) match {
case true => loop(t)(result)(p)
case false=>false
}
}
loop(self)(true)(p)
}
def exists(p:A=>Boolean):Boolean={
@tailrec
def loop(list: List[A])(result:Boolean)(p:A=>Boolean):Boolean=list match {
case Nil => result
case h::t => p(h) match {
case true=>true
case false=>loop(t)(result)(p)
}
}
loop(self)(false)(p)
}
}
case class ::[+A](h:A,t:List[A]) extends List[A]
case object Nil extends List[Nothing]
object List{
def empty[A]:List[A]=Nil
def apply[A](xs:A*):List[A]={
if(xs.isEmpty) empty[A]
else ::(xs.head,apply(xs.tail:_*))
}
}

Tree

1
2
3
4
5
6
7
8
9
10
trait Tree[+A] {
}
case object EmptyNode extends Tree[Nothing]{
override def toString: String = "Nil"
}
case class Node[+A](value:A,left:Tree[A],right:Tree[A]) extends Tree[A]
object Tree{
def node[A](value:A,left:Tree[A]=EmptyNode,right:Tree[A]=EmptyNode)=Node(value,left,right)
def empty[A]:Tree[A]=EmptyNode
}

剑指Offers上的有关题目(基于scala解法)

数组中只出现一次的数字

0 0 0 ^ 0 = 0
0 1 0 ^ 1 = 1
1 1 1 ^ 1 = 0

一个整型数组里除了一个数字外,其它数字均出现两次,如数组Array(2, 3, 6, 3, 2, 5, 5),返回结果应该为6,程序一句话就ok😂

1
2
val array=Array(2, 3, 6, 3, 2, 5, 5)
println(array.reduce(_^_))

把题目改一下:
一个整型数组除了两个数字外,其它数字均出现两次,如数组Array(2, 4, 3, 6, 3, 2, 5, 5),返回结果为4和6。那么该怎么做呢?
还是采用分区思想,我一度以为自己写不出来!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
object Main extends App {
def findFisrtBitofOne(n:Int):Int={
Stream.from(0).find(i=>IsBitofOne(n,i)==1).get
}
def IsBitofOne(n:Int,index:Int)= (n>>index)&(1) //index 从零开始 ; n的第index位是1吗?
// IsBitofOne(Integer.valueOf("1010",2).toInt,0)
val array=Array(2,4,3,6,3,2,5,5)
val inDex=findFisrtBitofOne(array.reduce(_^_))
val array1=array.filter(i=>IsBitofOne(i,inDex)==1)
val array2=array.filter(i=>IsBitofOne(i,inDex)==0)
println(array1.reduce(_^_))
println(array2.reduce(_^_))
}

从尾到头打印链表

相比从头到尾打印链表,从尾到头只需要递归即可解决。

1
2
3
4
5
6
def fun[T](list:List[T]):Unit=list match {
case Nil=>()
case h::t =>
fun(t)
println(h)
}

用栈实现队列

这是栈的实现,这里并没有做异常处理等操作。scala具有范型数组,隐式类型反射标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Stack[T](implicit classTag: ClassTag[T]){
@volatile private[this] var _size=0
val elems=new Array[T](100)
def push(x:T)={
elems(_size)=x
_size+=1
}
def pop():T={
_size-=1
elems(_size)
}
def size=_size
def isEmpty= size==0
}

这是队列的实现,用两个栈互相中转实现了队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Queue[T](implicit classTag: ClassTag[T]){
val a=new Stack[T]
val b=new Stack[T]
def appendTail(x:T)={
a.push(x)
}
def deleteHead():T={
while(!a.isEmpty){
b.push(a.pop())
}
b.pop()//还有异常处理等等
}
}

若干排序问题

冒泡

C语言风格的冒泡排序(指令式风格):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sort(array: Array[Int])={
var temp=0
for(i<- 0 until array.length-1){
for(j<- 0 until array.length-i-1){
array(j)>array(j+1) match {
case true =>
temp=array(j)
array(j)=array(j+1)
array(j+1)=temp
case false=>()
}
}
}
}
快排

声明式风格的快排:

1
2
3
4
def qsort(list:List[Int]):List[Int]=list match {
case Nil=> Nil
case h::t => qsort(t.filter(_<=h)) ++ List(h) ++ qsort(t.filter(_>h))
}

斐波那契数列问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求青蛙跳上n级台阶总共有多少种跳法?
思路:把n级台阶的跳法看成n的函数;当青蛙选择跳出1台阶时,那么此时的跳法就是剩下的(n-1)台阶的跳法;如果选择跳出2台阶,那么此时的跳法就是剩下的(n-2)台阶的跳法。公式:f(n)=f(n-1)+f(n-2),代码采用尾递归形式:

1
2
3
4
5
def loop(step:Int,res1:Int,res2:Int):Int=step match {
case 1 => res1
case _ if step>1=>loop(step-1,res2,res1+res2)
}
loop(5,1,2)

删除链表节点

1
2
3
4
5
6
7
def deleteListNode(list:List[Int],x:Int):List[Int]=list match {
case Nil=> Nil
case h::t => h==x match {
case true =>t//在c语言中,需要free指针
case false=> h::deleteListNode(t,x)
}
}

找出链表中倒数第k个节点

这道题递归是避免不了的。

1
2
3
4
5
6
7
8
def fun(list: List[Int],k:Int):Int=list match {
case Nil=>0
case h::t =>
val now=1+fun(t,k)
if(now==k)
println(s"we found it:$h")
now
}

反转链表

这道题仅仅需要递归一遍就行(尾递归更优)

1
2
3
4
def fun(list:List[Int],result:List[Int]):List[Int]=list match {
case Nil => result
case h::t => fun(t,::(h,result))
}//尾递归

合并两个已经排序的列表

依然尾递归:

1
2
3
4
5
6
7
8
9
10
def fun(list1:List[Int],list2:List[Int],result:List[Int]):List[Int]=(list1,list2) match {
case (_,Nil)=>result.reverse++list1
case (Nil,_)=>result.reverse++list2
case (h1::t1,h2::t2)=>h1>h2 match {
case true =>fun(list1,t2,h2::result)
case false=>fun(t1,list2,h1::result)
}
}
//测试:
println(fun(List(1,3,5,7),List(2,3,6,8),Nil))

树的子结构

判断一个Tree是否是另一个Tree的子树。
首先编写doesTree1haveTree2,这个方法从Tree1的树顶开始判断与Tree2的对应节点是否相等,依然递归(这个程序改成尾递归有点难度):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def doesTree1HaveTree2[A](tree1:Tree[A],tree2: Tree[A]):Boolean=(tree1,tree2) match {
case (EmptyNode,EmptyNode)=>true
case (EmptyNode,_) =>false
case (_,EmptyNode) =>true
case (Node(value1,left1,right1),Node(value2,left2,right2))=>
value1==value2 && doesTree1HaveTree2(left1,left2) && doesTree1HaveTree2(right1,right2)
}
//测试:
val tree1=node(1,
node(2,
node(4),
node(5)),
node(3))
val tree2=node(1,node(2),node(3))
println(Tree.doesTree1HaveTree2(tree1,tree2))

判断Tree1是否包含Tree2:

1
2
3
4
5
6
7
def doesTree1containsTree2[A](tree1: Tree[A],tree2:Tree[A]):Boolean=(tree1,tree2) match {
case (EmptyNode,EmptyNode)=>true
case (_,EmptyNode)=>true
case (EmptyNode,_)=>false
case (Node(value1,left1,right1),_)=>
doesTree1HaveTree2(tree1,tree2) || doesTree1containsTree2(left1,tree2) || doesTree1containsTree2(right1,tree2)
}

二叉树的镜像

两三句话😎:

1
2
3
4
def invert:Tree[A]=self match {
case EmptyNode=>EmptyNode
case Node(value,left,right)=>Node(value,left.invert,right.invert)
}

self是scala中的自身类型,类似于this,在Tree中有定义。

二叉树中和为某值的路径

这程序有个小问题就是会把路径打印两次,部分细节小改一下就好

1
2
3
4
5
6
7
8
9
10
11
12
13
def fun(tree1:Tree[Int],result:Int,targetSum:Int,path:Stack[Int]):Unit={
if(result==targetSum) {
println("we found it")
path.elems.foreach(i=>print(s" $i"))
}
if(tree1==EmptyNode)
return
val Node(value,left,right)=tree1
path.push(value)
fun(left,result+value,targetSum,path)
fun(right,result+value,targetSum,path)
path.pop()
}

数组中出现次数超过一半的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def fun[T](array:Array[T])={
var n=array(0)
var times=1
for(i<- 1 until array.length){
if(array(i)!=n)
times-=1
if(times==0){
n=array(i)
times=1
}
if(array(i)==n)
times+=1
}
n
}

最小的k个数

这题需要使用优先队列(小根堆)(适合海量数据)Heap.insertHeap.deleteMin函数实现了上滤与下滤过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
object Main extends App {
import Comapre.intCompare
val heap=new Heap[Int]()
val k=2
val array=Array(0,4,5,1,6,2,7,3,8) //0 index舍弃
1 until array.length foreach (i=>{
while(heap.size==k)
heap.deleteMin()
heap.insert(array(i))
})
heap.print // 7 8
}
class Heap[T](implicit classTag: ClassTag[T]){ //从 1 开始
private[this] val elems=new Array[T](100)
var size=0
def insert(x:T)(implicit com:Comapre[T])={
def loop(i:Int):Int={
if(com.compare(elems(i/2),x)<=0) //如果父节点比待插入的数据小 则返回当前节点
return i
elems(i)=elems(i/2)
loop(i/2)
}
elems(loop(size+1))=x
size+=1
}
def deleteMin()(implicit com:Comapre[T]):T={
def loop(i:Int):Int={
if(i>size)
return i/2
val left=elems(i*2)
val right=elems(i*2+1)
if(com.compare(left,right)<0){
elems(i)=left
loop(2*i)
}else{
elems(i)=right
loop(2*i+1)
}
}
val result=elems(1)
val last=elems(size)
elems(loop(1))=last
size-=1
return result
}
def print=1 to size foreach(i=>println(elems(i)))
}
trait Comapre[T]{
def compare(x:T,y:T):Int
}
object Comapre{
implicit val intCompare:Comapre[Int]=new Comapre[Int] {
override def compare(x: Int, y: Int): Int =x-y match {
case r if r>0 => 1
case 0 => 0
case r if r<0 => -1
}
}
}

最大子序列的和

运用动态规划:


代码如下:

1
2
3
4
5
6
7
8
9
10
11
object Main extends App {
val array=Array(1,-2,3,10,-4,7,2,-5)
def fun(i:Int):Int={
if(i==0)
return array(i)
if(fun(i-1)<0)
return array(i)
return fun(i-1)+array(i)
}
println(fun(array.length-2))
}

第一个只出现一次的字符

在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"则输出'b',思路类似于桶排序,在scala或者java中一个char占16位(两字节),但是我们只需要容纳整个ascill码的桶就行(即数组长度位256)。

1
2
3
4
5
6
7
object Main extends App {
val str="abaccdeff"
val array=new Array[Int](256)
str.map(_.toInt).foreach(i=> array(i)+=1)
val r=array.zipWithIndex.find{case (i,_)=>i==1}.get._2.toChar
println(r)//b
}

两个链表的第一个公共结点

两个链表有重合部分,那么这两条链表比较像Y型,而不是X型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
object Main extends App {
val orgin=List(6,7,8,9)
val list1=1::2::3::orgin
val list2= 4::5::orgin
def fun(listA: List[Int],listB:List[Int]):List[Int]={
if(listA eq listB)
return listA
fun(listA.tail,listB.tail)
}
val lenthg1=list1.length
val length2=list2.length
val r=if(lenthg1>length2)
fun(list1.drop(lenthg1-length2),list2) //把长的部分给扔了,"削平"
else
fun(list1,list2.drop(length2-lenthg1)) //把长的部分给扔了,"削平"
println(r)
}

二叉树的深度

1
2
3
4
5
def height[A](tree:Tree[A]):Int=tree match {
case EmptyNode=> 0
case Node(_,left,right)=>
1+Math.max(height(left),height(right))
}

二叉树是否平衡

先写个简单的版本(需要多次重复遍历结点,不可取🙅):

1
2
3
4
5
6
7
def isBalanaced[A](tree:Tree[A]):Boolean=tree match {
case EmptyNode=>true
case Node(_,left,right)=>
if(Math.abs(height(left)-height(right))>1)
return false
isBalanaced(left) && isBalanaced(right) //如果左右高度差大于1的话 直接返回false
}

高效改进版(需要使用IntHolder来模拟指针):

1
2
3
case class IntHolder(var value:Int){//以此来模拟指针
override def toString: String = s"$value"
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isBalanaced[A](tree:Tree[A],h:IntHolder):Boolean=tree match {
case EmptyNode=>
h.value=0
true
case Node(_,left,right)=>
val left_height=IntHolder(0)
val right_height=IntHolder(0)
if(isBalanaced(left,left_height) && isBalanaced(right,right_height)){
if(Math.abs(left_height.value-right_height.value)<=1){
h.value = Math.max(left_height.value,right_height.value)+1
return true
}
}
return false
}
1
2
3
4
5
6
7
8
9
10
11
测试用例:
object Main extends App {
val tree=node(1,
node(2,
node(4),
node(5,
node(7))),
node(3,empty,node(6)))
val r=Tree.isBalanaced(tree,IntHolder(0))
println(r)//true
}

二维数组的查找

存在这样的一个二维数组,每一行都在按照从左到右递增的顺序排序。每一列都按照从上到下的顺序排序。现在给定一个数,请判断数组中是否包含这个数。
声明式编程

1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
object Main extends App {
val array_rows=4 //其实是4行
val array_cols=4 //其实是4列
val array=Array(
Array(1,2,8,9),
Array(2,4,9,12),
Array(4,7,10,13),
Array(6,8,11,15))
def fun(row_index:Int,col_index:Int,target:Int):Option[(Int,Int)]={
if(row_index==array_rows || col_index== -1) //出界了
return None
if(array(row_index)(col_index) == target)
return Some((row_index,col_index))
if(array(row_index)(col_index)>target) //说明这个数所在列 都大于target 此列略过
return fun(row_index,col_index-1,target)
if(array(row_index)(col_index)<target) //说明这个数所在行都比target小,target不可能在此行
return fun(row_index+1,col_index,target)
return None
}
println(fun(0,3,7))
}

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾。我们称之为旋转数组。输入一个递增数组排序的数组的一个旋转,输出旋转数组的最小元素。比如{3,4,5,1,2}为一个旋转数组,找出其最小数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
object Main extends App {
val intArray=Array(3,4,5,1,2)
def fun(left:Int,right:Int):Option[Int]={
val mid=(left+right)/2
if(right-left ==1)
return Some(right)
if(intArray(left) < intArray(mid)) //说明中间数仍然在第一个自增数组里
return fun(mid,right)
if(intArray(right)>intArray(mid)) //说明了中间数把后递增数组小
return fun(left,mid)
return None
}
println(fun(0,intArray.length-1))//Some(3) 第4个
}

数值的整数次方

有一个公式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
object Main extends App {
def fun(base: Int,exp:Int):Int={
if(exp==0)
return 1
if(exp==1)
return base
var result=fun(base,exp/2) //因为 (exp-1)/2与exp/2的结果是一样的
result=result*result
if((exp&1)==1)
result=result*base
return result
}
println(fun(2,2))
}

调整数组元素顺序使奇数位于偶数前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object Main extends App {
val array=Array(1 to 10:_*)
def exchange(left:Int,right:Int)={
val temp=array(left)
array(left)=array(right)
array(right)=temp
}
def fun(left:Int,right:Int):Unit={//奇数在前 偶数在后
if(left==right)
return
if(array(right)%2==0)//右为偶数的话
fun(left,right-1)
if(array(left)%2==0) //左为偶数的话 交换
exchange(left,right)
if(array(left)%2==1) //左为奇数的话
fun(left+1,right)
}
fun(0,array.length-1)
array.foreach(println)//ok
}

具有min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push以及pop的时间复杂度都是O(1)。
肯定需要辅助栈的啦!

步骤 操作 数据栈 辅助栈 最小值
1 压入3 3 3 3
2 压入4 3,4 3,3 3
3 压入2 3,4,2 3,3,2 2
4 压入1 3,4,2,1 3,3,2,1 1
5 弹出 3,4,2 3,3,2 2
6 弹出 3,4 3,3 3
7 压入 3,4,0 3,3,0 0

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class StackWithMin{
type T=Int
val dataStack=new Stack[T]()
val minStack=new Stack[T]()
def push(x:T)={
if(dataStack.isEmpty&&minStack.isEmpty){
dataStack.push(x)
minStack.push(x)
}else{
if(x>minStack.peak)
minStack.push(minStack.peak)
else
minStack.push(x)
dataStack.push(x)
}
}
def pop()={
minStack.pop()
dataStack.pop()
}
def min=minStack.peak
}
class Stack[T]( implicit classTag: ClassTag[T]){
val arr_data=new Array[T](100)
@volatile var length=0
def push(x:T)={
arr_data(length)=x
length+=1
}
def pop()={
length-=1
arr_data(length)
}
def peak= arr_data(length-1)
def isEmpty=length==0
}

翻转单词顺序 VS 左旋转字符串

翻转单词顺序
存在一个字符串"i am a student. ",翻转句子中单词的顺序,但单词内字符的顺序不变,应该输出" student. a am i"
代码分为两个模块:翻转对应区间上的数组,以及找出数组中空格之间的对应索引:

1
2
3
4
5
6
7
8
9
10
11
def exchange(array: Array[Char],left:Int,right:Int)={
val temp=array(left)
array(left)=array(right)
array(right)=temp
}
def reverse(array: Array[Char],left:Int,right:Int):Unit={
if(left==right || left>right)
return
exchange(array,left,right)
reverse(array,left+1,right-1)
}
1
2
3
4
5
6
7
8
9
10
11
12
val charArray="i am a student. ".toCharArray
reverse(charArray,0,charArray.length-1)
var l=0
var r=0
for(index<- 0 until charArray.length-1){
if(charArray(index)==' '){
r=index
reverse(charArray,l,r)
l=r
}
}
println(charArray.mkString(""))

左旋转字符串
还记得旋转数组吗?
输入"abcdef"和2,得到"cedfab"
那么程序怎么写:

1
2
3
4
5
val charArray="abcdef".toCharArray
reverse(charArray,0,charArray.length-1)
reverse(charArray,0,charArray.length-1-2)
reverse(charArray,charArray.length-2,charArray.length-1)
print(charArray.mkString)

三次翻转就行。