不相同意转发,等等手艺(具体细节详见

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)和同1律(identity)法则被称作monoid法则。

说明:

可折叠数据结构

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

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源码如下(选择尾递归):

  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福寿绵绵如下:

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:_*))
}

正文中出现的全数算法题皆源于牛客网剑指Offer在线编制程序题,在此只是作为转发和著录,用于自己学习使用,不允许转发。多谢牛客网提供的能源。前边是具备的编程题,后边都是皮之不存毛将焉附知识点补充和本人完毕的解答。仅供参考!

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那类的虚类型完成方式各异,本程序完全接纳递归落成。

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

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
}

贰维数组中的查找

在1个贰维数组中,每一行都依照从左到右递增的顺序排序,每1列都坚守从上到下递增的相继排序。请落成贰个函数,输入那样的3个2维数组和一个平头,推断数组中是还是不是带有该整数。


剑指Offers上的关于主题素材(基于scala解法)

二、字符串

数组中只现出一回的数字

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

一个整型数组里除了1个数字外,别的数字均出现三回,如数组Array(2, 3, 6, 3, 2, 5, 5),再次来到结果应该为陆,程序一句话就ok

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

把题目改一下:
二个整型数组除了多少个数字外,别的数字均出现三遍,如数组Array(2, 4, 3, 6, 3, 2, 5, 5),再次来到结果为四和6。那么该如何做吧?
只怕使用分区观念,作者一度以为本身写不出去!!!

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(_^_))
}

轮换空格

请达成三个函数,将3个字符串中的空格替换到“%20”。比方,当字符串为We Are
Happy.则经过替换之后的字符串为We%20Are%20Happy。


从尾到头打字与印刷链表

相比较之下从头到尾打印链表,从尾到头只必要递归就能够消除。

  def fun[T](list:List[T]):Unit=list match {
    case Nil=>()
    case h::t =>
      fun(t)
      println(h)
  }

正则表明式相配

请达成八个函数用来合作包涵’.’和’‘的正则表明式。方式中的字符’.’表示自便三个字符,而’‘表示它前面包车型地铁字符能够出现任意次(包涵0次)。
在宗旨中,匹配是指字符串的有所字符相配整个格局。比如,字符串”aaa”与情势”a.a”和”abaca”匹配,但是与”aa.a”和”ab*a”均不相配


用栈实现队列

那是栈的兑现,这里并未做尤其管理等操作。scala具有范型数组,隐式类型反射标识。

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
}

那是队列的落到实处,用多少个栈相互转载落成了队列。

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()//还有异常处理等等
  }
}

意味着数值的字符串

请落成一个函数用来判别字符串是或不是代表数值(包涵整数和小数)。比如,字符串”+100″,”五e2″,”-1贰三”,”三.1416″和”-1E-16″都代表数值。
可是”1二e”,”壹a3.14″,”一.二.叁”,”+-伍”和”1二e+四.三”都不是。


多少排序难题

字符流中第贰个不重复的字符

请完成一个函数用来找寻字符流中第五个只现出一回的字符。举个例子,当从字符流中只读出前八个字符”go”时,第三个只现出1次的字符是”g”。当从该字符流中读出前两个字符“google”时,第一个只现出二回的字符是”l”。

出口描述:

若果当前字符流未有存在出现1回的字符,重回#字符。


冒泡

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

  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=>()
        }
      }
    }
  }

三、链表

快排

表明式风格的快排:

  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))
  }

从尾到头打字与印刷链表

输入三个链表,从尾到头打字与印刷链表每一种节点的值。


斐波那契数列难题

一头青蛙一次能够跳上壹级台阶,也足以跳上贰级台阶。求青蛙跳上n级台阶总共有稍许种跳法?
思路:把n级台阶的跳法看成n的函数;当青蛙采纳跳出一台阶时,那么此时的跳法正是多余的(n-一)台阶的跳法;假使选择跳出贰台阶,那么此时的跳法正是多余的(n-二)台阶的跳法。公式:f(n)=f(n-1)+f(n-2),代码应用尾递归情势:

  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)

链表中环的输入结点

一个链表中带有环,请寻觅该链表的环的输入结点


除去链表节点

  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)
    }
  }

删除链表中再次的结点

在三个排序的链表中,存在双重的结点,请删除该链表中再一次的结点,重复的结点不保留,再次来到链表头指针。
举个例子,链表1->二->3->三->4->四->5 管理后为 一->2->伍


寻觅链表中倒数第k个节点

那道题递归是制止不了的。

  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
  }

四、树

反转链表

那道题仅仅要求递归二回就行(尾递归更优)

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

重建二叉树

输入某贰叉树的前序遍历和中序遍历的结果,请重建出该贰叉树。若是输入的前序遍历和中序遍历的结果中都不含重复的数字。举个例子输入前序遍历体系{一,2,四,7,三,伍,六,八}和中序遍历系列{肆,7,贰,1,5,三,捌,陆},则重建二叉树并再次回到。


统壹三个曾经排序的列表

一如既往尾递归:

  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))

贰叉树的下多个结点

给定1个贰叉树和里面的3个结点,请找寻中序遍历顺序的下一个结点并且再次来到。注意,树中的结点不仅富含左右子结点,同时富含指向父结点的指针。


树的子结构

决断2个Tree是不是是另一个Tree的子树。
首先编写doesTree1haveTree2,这些艺术从Tree1的树顶伊始决断与Tree2的照拂节点是还是不是等于,依旧递归(这几个顺序改成尾递归有点难度):

  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:

  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)
  }

对称的贰叉树

请达成三个函数,用来判定壹颗二叉树是还是不是对称的。注意,要是贰个二叉树同此二叉树的镜像是均等的,定义其为对称的。


二叉树的镜像

两3句话:

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

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

按之字形顺序打字与印刷2叉树

请实现二个函数遵照之字形打字与印刷二叉树,即首先行根据从左到右的依次打字与印刷,第3层依照从右至左的次第打字与印刷,第壹行根据从左到右的次第打字与印刷,别的行依此类推。


二叉树5月为某值的路径

那程序有个小标题正是会把路子打字与印刷三回,部分细节小改一下就好

  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层结点从左至右输出。每一层输出1行。


数组中冒出次数超过6分之叁的数字

  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
  }

体系化2叉树

请落成八个函数,分别用来连串化和反类别化2叉树


最小的k个数

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

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
    }
  }
}

贰叉寻觅树的第k个结点

给定一颗贰叉寻找树,请寻找里面包车型地铁第k大的结点。比方, 5 / \ 3 7 /\ /\ 二四 陆 捌 中,按结点数值大小顺序第多个结点的值为四。


最大子种类的和

应用动态规划:

图片 1

代码如下:

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))
}

数量流中的中位数

如何获得二个数目流中的中位数?假诺从数据流中读出奇数个数值,那么中位数就是具备数值排序之后位于中间的数值。假使从数据流中读出偶数个数值,那么中位数就是富有数值排序之后中间多个数的平均值。


首先个只现身三次的字符

在字符串中寻觅第一个只现出2次的字符。如输入"abaccdeff"则输出'b',思路类似于桶排序,在scala大概java中二个char占十四个人(两字节),可是大家只供给容纳全数ascill码的桶就行(即数主任度位25陆)。

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型。

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)
}

用五个栈完结队列

用五个栈来达成三个类别,落成队列的Push和Pop操作。
队列中的成分为int类型。


二叉树的纵深

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

滑动窗口的最大值

给定四个数组和滑动窗口的轻重,寻找装有滑动窗口里数值的最大值。比如,借使输入数组{二,叁,④,二,陆,2,5,一}及滑动窗口的轻重缓急叁,那么1共存在5个滑动窗口,他们的最大值分别为{四,四,6,陆,陆,5};
针对数组{贰,叁,四,二,陆,二,伍,一}的滑动窗口有以下5个: {[2,3,4],2,6,2,5,1},
{2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1},
{2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。


二叉树是或不是平衡

先写个轻便的版本(必要数次重复遍历结点,不可取):

  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来效仿指针):

case class IntHolder(var value:Int){//以此来模拟指针
  override def toString: String = s"$value"
}

  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
  }

测试用例:
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
}

陆、查找和排序

2维数组的搜寻

留存这么的二个二维数组,每一行都在根据从左到右递增的种种排序。每壹列都遵守从上到下的依次排序。今后加以3个数,请判定数组中是或不是带有那个数。
表明式编制程序

1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
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))
}

旋转数组的矮小数字

把1个数组最开头的几何个元素搬到数组的最终,大家称之为数组的旋转。
输入贰个非递减少排放序的数组的3个转悠,输出旋转数组的细微成分。
举例数组{三,四,伍,一,二}为{一,贰,三,4,伍}的1个转悠,该数组的最小值为一。
NOTE:给出的富有因素都大于0,若数组大小为0,请重临0。


旋转数组的细小数字

把一个数组最伊始的几何个因素搬到数组的尾声。我们称为旋转数组。输入二个递增数组排序的数组的贰个筋斗,输出旋转数组的小小成分。比如{3,4,5,1,2}为3个旋转数组,搜索其最小数。

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个
}

柒、递归和循环

数值的整数十次方

有多个公式:
图片 2

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))
}

斐波那契数列

世家都领会斐波那契数列,以后要求输入二个平头n,请您输出斐波那契数列的第n项。
n<=39


调动数组成分顺序使奇数位于偶数前边

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
}

跳台阶

叁只青蛙二回能够跳上1级台阶,也足以跳上贰级。求该青蛙跳上贰个n级的阶梯总共有个别许种跳法。


装有min函数的栈

定义栈的数据结构,请在该项目中贯彻贰个力所能及拿走栈的微小成分的min函数。在该栈中,调用min、push以及pop的时刻复杂度都以O(壹)。
必然需求扶助栈的啊!

步骤 操作 数据栈 辅助栈 最小值
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

代码:

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
}

变态跳台阶

一头青蛙1回可以跳上一级台阶,也足以跳上二级……它也能够跳上n级。求该青蛙跳上3个n级的台阶总共有多少种跳法。


扭动单词顺序 VS 左旋转字符串

转头单词顺序
留存二个字符串"i am a student. ",翻转句子中单词的一1,但单词内字符的种种不改变,应该出口" student. a am i"
代码分为多少个模块:翻转对应间隔上的数组,以及搜索数组中空格之间的对应索引:

  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)
  }

  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"
那么程序怎么写:

  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)

二遍翻转就行。

矩形覆盖

咱俩得以用贰1的小矩形横着大概竖着去掩盖更加大的矩形。请问用n个21的小矩形无重叠地覆盖三个二*n的大矩形,总共有稍许种方法?


八、位运算

二进制中一的个数

输入三个平头,输出该数2进制表示中一的个数。其中负数用补码表示。


玖、 代码的完整性

数值的整数11次方

给定二个double类型的浮点数base和int类型的整数exponent。求base的exponent次方


调解数组顺序使奇数位于偶数前面

输入3个整数数组,落成多少个函数来调解该数组中数字的逐条,使得全部的奇数位于数组的前半片段,全体的偶数位于位于数组的后半有个别,并保障奇数和奇数,偶数和偶数之间的相持位置不改变。


链表中倒数第k个结点

输入一个链表,输出该链表中尾数第k个结点。


合并两个排序的链表

输入三个没趣递增的链表,输出多个链表合成后的链表,当然大家必要合成后的链表满意单调不减规则。


树的子结构

输入两棵二叉树A,B,决断B是或不是A的子结构。(ps:大家约定空树不是随意三个树的子结构)


10、 面试思路

2叉树的镜像

操作给定的2叉树,将其调换为源二叉树的镜像。


拾壹、 画图让抽象形象化

顺时针打字与印刷矩阵

输入多个矩阵,依据从外向里以顺时针的相继依次打印出每3个数字,举例,倘使输入如下矩阵:
一 贰 叁 四 伍 6 柒 八 玖 10 1一 1贰 一叁 14 15 1陆则相继打字与印刷出数字1,二,三,4,8,1贰,1陆,一5,1四,1三,九,五,六,柒,1一,10.


十2、比方让抽象具体化

涵盖min函数的栈

定义栈的数据结构,请在该类型中达成3个力所能及获取栈最小成分的min函数。


栈的压入、弹出游列

输入多个整数系列,第三个体系表示栈的压入顺序,请判别第三个连串是不是为该栈的弹出种种。借使压入栈的具备数字均不等于。举例种类1,2,叁,四,伍是某栈的压入顺序,系列四,伍,3,2,壹是该压栈类别对应的一个弹骑行列,但4,3,伍,一,贰就不容许是该压栈类别的弹出游列。(注意:这八个种类的长短是相等的)


从上往下打字与印刷2叉树

从上往下打印出贰叉树的每一个节点,同层节点从左至右打字与印刷。


贰叉搜索树的后序遍历连串

输入一个平头数组,判定该数组是或不是某2叉搜索树的后序遍历的结果。假如是则输出Yes,不然输出No。若是输入的数组的自由三个数字都互区别。


二叉树花潮为某1值的门径

输入一颗贰叉树和一个整数,打印出2叉树中结点值的和为输入整数的具有路径。路线定义为从树的根结点开头往下直接到叶结点所经过的结点形成一条路线。


拾3、 分解让复杂难题大约

复杂链表的复制

输入一个扑朔迷离链表(每种节点中有节点值,以及四个指针,多少个对准下一个节点,另三个出奇指针指向大肆一个节点),再次来到结果为复制后复杂链表的head。(注意,输出结果中请不要回来参数中的节点引用,不然判题程序会一贯重回空)


2叉寻觅树与双向链表

输入一棵2叉寻找树,将该二叉搜索树转变来贰个排序的双向链表。要求不可能制造任何新的结点,只可以调解树中结点指针的针对性。


字符串的排列

输入二个字符串,按字典序打印出该字符串中字符的具备排列。举个例子输入字符串abc,则打字与印刷出由字符a,b,c所能排列出来的全体字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超越玖(只怕有字符重复),字符只包含大小写字母。


拾肆、 时间功能

数组中冒出次数当先6分之3的数字

数组中有1个数字出现的次数超过数老板度的11分之5,请寻找那么些数字。比如输入多少个长短为九的数组{一,二,叁,二,二,二,伍,四,2}。由于数字贰在数组中出现了5回,领先数首席营业官度的二分一,由此输出2。假如不设有则输出0。


最小的K个数

输入n个整数,搜索里面不大的K个数。比方输入肆,5,1,6,2,7,三,8那个数字,则一点都不大的6个数字是一,贰,3,4,。


再而三子数组的最大和

HZ偶尔会拿些专门的学问难点来忽悠那三个非Computer专门的工作的同窗。明日测试组开完会后,他又说道了:在古旧的1维形式识别中,日常必要总计一而再子向量的最大和,当向量全为正数的时候,难题很好化解。可是,如若向量中涵盖负数,是不是应该包蕴某些负数,并期望旁边的正数会弥补它吗?举个例子:{陆,-三,-二,七,-一5,1,二,二},延续子向量的最大和为八(从第0个早先,到第四个了结)。你会不会被她忽悠住?(子向量的长短至少是一)


平头中一油可是生的次数(从一到n整数中壹油可是生的次数)

求出113的整数中1出现的次数,并算出1001300的平头中一并发的次数?为此他特地数了一下一~一三中涵盖一的数字有一、10、1壹、1二、一3于是共现身5次,然而对于背后难点他就没辙了。ACMer希望您们帮帮他,并把难点进一步布满化,能够快速的求出任意非负整数距离中一冒出的次数。


把数组排成最小的数

输入3个正整数数组,把数组里有着数字拼接起来排成1个数,打字与印刷能凑合出的持有数字中幽微的五个。举个例子输入数组{叁,3二,32一},则打字与印刷出那八个数字能排成的微小数字为32132三。


拾5、 时间空间功效的平衡

丑数

把只包罗因子二、三和伍的数称作丑数(Ugly
Number)。比方6、捌都以丑数,但1四不是,因为它含有因子七。
习贯上大家把一看成是率先个丑数。求按从小到大的各类的第N个丑数。


第3个只现出二遍的字符地方

在3个字符串(1<=字符串长度<=一千0,全体由字母组成)中找到第3个只出现三回的字符,并重回它的地方


数组中的逆序对

在数组中的多少个数字,假若前方三个数字超过后边的数字,则那三个数字组成二个逆序对。输入一个数组,求出那个数组中的逆序对的总额P。并将P对一千00000⑦取模的结果输出。
即输出P%100000000七

输入描述:

标题保险输入的数组中平昔不的同一的数字
数量范围:
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

示例1

输入
1,2,3,4,5,6,7,0
输出
7


三个链表的首先个公共结点

输入四个链表,寻找它们的首先个公共结点。


十陆、 知识迁移技艺

数字在排序数组中出现的次数

总括八个数字在排序数组中冒出的次数。


二叉树的纵深

输入1棵二叉树,求该树的深浅。从根结点到叶结点依次通过的结点(含根、叶结点)产生树的一条路线,最长路线的长度为树的纵深。


平衡贰叉树

输入1棵二叉树,判别该贰叉树是或不是是平衡2叉树。


数组中只现出三次的数字

1个整型数组里除了多少个数字之外,其余的数字都冒出了四回。请写程序找寻那八个只出现一回的数字。


和为S的连接正数体系

小明很欣赏数学,有一天她在做数学作业时,需要估测计算出玖~16的和,他马上就写出了情有可原答案是100。可是他并不知足于此,他在想究竟有个别许种三番五次的正数系列的和为100(至少包罗几个数)。没多久,他就得到另一组三番五次正数和为十0的连串:1八,1玖,20,二一,2二。以后把标题提交你,你能还是无法也不慢的搜索装有和为S的总是正数类别?
Good Luck!


和为S的多个数字

输入1个递增排序的数组和1个数字S,在数组中追寻多个数,是的他俩的和刚刚是S,借使有多对数字的和等于S,输出四个数的乘积最小的。

出口描述:

对应各样测试案例,输出四个数,小的先输出。


左旋转字符串

汇编语言中有1种移位指令叫做循环左移(ROL),未来有个简易的天职,便是用字符串模拟那么些命令的运算结果。对于三个加以的字符种类S,请您把其循环左移K位后的队列输出。举个例子,字符连串S=”abcXYZdef”,要求输出循环左移二人后的结果,即“XYZdefabc”。是还是不是很轻松?OK,消除它!


扭转单词顺连串

牛客近年来期了2个新职员和工人Fish,每一日中午连年会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有1天她向Fish借来翻看,但却读不懂它的情趣。举个例子,“student.
a am
I”。后来才开掘到,这个人原来把句子单词的相继翻转了,准确的语句应该是“I
am a student.”。Cat对一1的扭动这几个单词顺序可不在行,你能帮助他么?


107、 抽象建立模型才能

扑克牌顺子

LL明天激情尤其好,因为他去买了一副扑克牌,开采里头居然有1个能人,三个小王(一副牌原本是5四张\_)…他随意从中抽取了五张牌,想测测本人的手气,看看能否抽到顺子,纵然抽到的话,他操纵去买体彩,嘿嘿!!“红心A,黑桃三,小王,大王,方片5”,“Oh
My God!”不是顺子…..LL不乐意了,他想了想,决定大\小
王能够用作任何数字,并且A看作壹,J为1①,Q为1二,K为1三。上面包车型大巴伍张牌就能够改为“壹,贰,三,四,五”(大小王分别看作二和四),“So
Lucky!”。LL决定去买体彩啦。
今后,须求您采用那幅牌模拟下边包车型地铁历程,然后告诉大家LL的天命怎么着。为了便利起见,你可以以为大小王是0。


子女们的游乐(圆圈中最后剩下的数)

年年六一小孩子节,牛客都会希图一些小礼物去看看孤儿院的毛孩子,二〇一9年亦是那般。HF作为牛客的头面元老,自然也打算了有个别小游戏。当中,有个游戏是这么的:首先,让小孩们围成1个大圈。然后,他即兴钦点1个数m,让编号为0的小儿初叶报数。每一次喊到m-一的要命小孩要出列唱首歌,然后能够在礼品箱中随心所欲的抉择礼物,并且不再回到圈中,从他的下2个小家伙初阶,继续0…m-一报数….如此下去….直到剩余最终一个小孩子,能够毫不表演,并且获得牛客高尚的“名侦探柯南”典藏版(名额有限哦!!\_)。请你试着想下,哪个小朋友会拿走那份礼品呢?(注:小朋友的号码是从0到n-一)


10捌、 发散思维技巧

求1+2+3+…+n

求一+2+三+…+n,须求不可能动用乘除法、for、while、if、else、switch、case等关键字及规范剖断语句(A?B:C)。


无须加减乘除做加法

写贰个函数,求多少个整数之和,供给在函数体内不得使用+、-、*、/肆则运算符号。

十九、 综合

把字符串调换成整数

将一个字符串转换来2个平头,供给不可能应用字符串调换整数的库函数。
数值为0可能字符串不是二个合法的数值则再次来到0


二十、数组

数组中另行的数字

在2个长度为n的数组里的持有数字都在0到n-一的限量内。
数组中有个别数字是重新的,但不了然有几个数字是重复的。也不清楚各样数字再度四遍。请搜索数组中随便叁个再一次的数字。
比如,若是输入长度为7的数组{2,3,1,0,二,5,叁},那么相应的出口是第3个再度的数字2。


创设乘积数组

给定二个数组A[0,1,…,n-1],请营造八个数组B[0,1,…,n-1],当中B中的成分B[i]=A[0]A[1]A[i-1]A[i+1]A[n-1]。不可能利用除法。


二十一、回溯法

矩阵中的路线

请设计三个函数,用来判定在三个矩阵中是或不是存在一条包涵某字符串全部字符的不二秘籍。路线能够从矩阵中的自便一个格子开首,每一步能够在矩阵中向左,向右,向上,向下移动三个格子。假如一条门路经过了矩阵中的某3个格子,则该路径不可能再进入该格子。
举例 a b c e s f c s a d e e
矩阵中隐含一条字符串”bcced”的门路,不过矩阵中不分包”abcb”路线,因为字符串的第叁个字符b攻陷了矩阵中的第1行首个格子之后,路线不能够再一次进入该格子。


机器人的移位范围

地上有贰个m行和n列的方格。一个机器人从坐标0,0的格子初始运动,每1回只可以向左,右,上,下多少个样子移动壹格,然则不可能进入行坐标和列坐标的数位之和大于k的格子。
举例,当k为1八时,机器人能够进入方格(3伍,37),因为三+5+三+7 =
1八。不过,它不能够进入方格(35,38),因为三+5+三+8 =
1九。请问该机器人能够达到规定的标准多少个格子?


相关文章