scala写算法-List、Stream、以及剑指Offer里局地难题基于scala解法语言

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法则。

1、C#的值类型

可折叠数据结构

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

有多少个特性:

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:_*))
  }
}
  • 存储在栈里 
  • 据悉值类型的变量直接包含值(值类型存储实际值)。
    将一个值类型变量赋给另一个值类型变量时,将复制包罗的值。
    那与引用类型变量的赋值不一样,引用类型变量的赋值只复制对目的的引用,而不复制对象自我。
  • 抱有的值类型均隐式派生自 System.ValueType。
  • 与引用类型分化,不可能从值类型派生出新的种类。
    但与引用类型相同的是,结构也足以已毕接口。
  • 与引用类型不一致,值类型不可以包罗 null 值。 可是,能够为 null 的品种
    成效允许值类型分配给 null。
  • 每种值类型均有一个隐式的默许构造函数来初始化该项目标默许值。

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
}

 

剑指Offers上的关于难点(基于scala解法)

值类型分为两类:
struct( 结构
)、 enum(枚举 )

数组中只出现四次的数字

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

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

把难题改一下:
一个整型数组除了七个数字外,其余数字均出现五次,如数组Array(2, 4, 3, 6, 3, 2, 5, 5),重回结果为4和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(_^_))
}

struct( 结构 )分为以下几类:

从尾到头打印链表

对照从头到尾打印链表,从尾到头只要求递归即可解决。

  def fun[T](list:List[T]):Unit=list match {
    case Nil=>()
    case h::t =>
      fun(t)
      println(h)
  }
  • Numeric(数值)类型

    • 整型

    • 浮点型

    • decimal

  • bool

  • 用户定义的结构。

用栈达成队列

那是栈的达成,这里并从未做老大处理等操作。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()//还有异常处理等等
  }
}

下表列出了 C# 中置放类型中可用的值类型:

若干排序难题

类型 描述 范围 默认值
bool 布尔值 True 或 False False
byte 8 位无符号整数 0 到 255 0
char 16 位 Unicode 字符 U +0000 到 U +ffff ‘\0’
decimal 128 位精确的十进制值,28-29 有效位数 (-7.9 x 1028 到 7.9 x 1028) / 100 到 28 0.0M
double 64 位双精度浮点型 (+/-)5.0 x 10-324 到 (+/-)1.7 x 10308 0.0D
float 32 位单精度浮点型 -3.4 x 1038 到 + 3.4 x 1038 0.0F
int 32 位有符号整数类型 -2,147,483,648 到 2,147,483,647 0
long 64 位有符号整数类型 -923,372,036,854,775,808 到 9,223,372,036,854,775,807 0L
sbyte 8 位有符号整数类型 -128 到 127 0
short 16 位有符号整数类型 -32,768 到 32,767 0
uint 32 位无符号整数类型 0 到 4,294,967,295 0
ulong 64 位无符号整数类型 0 到 18,446,744,073,709,551,615 0
ushort 16 位无符号整数类型 0 到 65,535 0
冒泡

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

实在是简不难单类型,所有的概括类型(C# 语言的组成部分)均为 .NET
Framework 系统项目标别名。 例如,int 是 System.Int32
的别名。可应用文字开首化简单类型。 例如,“A”是 char 类型的文字,而 2001
是 int
类型的文字。如需得到一个品种或一个变量在一定平台上的纯正尺寸,能够使用
sizeof 方法。表明式 sizeof(type)
暴发以字节为单位存储对象或项目的囤积尺寸。上面举例获取其它机器上 int
类型的仓储尺寸:

快排

表明式风格的快排:

  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 namespace DataTypeApplication
 2 {
 3    class Program
 4    {
 5       static void Main(string[] args)
 6       {
 7          Console.WriteLine("Size of int: {0}", sizeof(int));
 8          Console.ReadLine();
 9       }
10    }
11 }

斐波那契数列难题

一只青蛙一回可以跳上1级台阶,也得以跳上2级台阶。求青蛙跳上n级台阶总共有多少种跳法?
思路:把n级台阶的跳法看成n的函数;当青蛙选择跳出1台阶时,那么此时的跳法就是多余的(n-1)台阶的跳法;如若选用跳出2台阶,那么此时的跳法就是多余的(n-2)台阶的跳法。公式: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)
    }
  }
Size of int: 4

找出链表中尾数第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))
  }//尾递归

 

统一四个已经排序的列表

依旧尾递归:

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

2、 C# 的 struct

树的子结构

认清一个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)
  }

struct(结构)平日作为一小组相关变量的器皿,在 C#
中它使得一个纯粹变量可以储存各类数据类型的连带数据。struct
关键字用于创建结构体,可以根据如下的措施宣示 Person结构:

二叉树的镜像

两三句话:

  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 struct Person
2 {
3    public string name;
4    public int age;
5    public string sex;
6 };  

二叉树中和为某值的门路

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

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

上边的顺序演示了组织的用法:

数组中冒出次数大多数的数字

  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
  }
using System;

namespace MyStruct
{
    struct Person
    {
        public string name;
        public int age;
        public string sex;
    }

    class Program
    {
        static void Main(string[] args)
        {
            Person person1;
            person1.name = "张三";
            person1.age = 18;
            person1.sex = "男";

            Person person2;
            person2.name = "李四";
            person2.age = 20;
            person2.sex = "男";

            //输出 person1 的信息
            Console.WriteLine("person1 姓名:{0}", person1.name);
            Console.WriteLine("person1 性别:{0}", person1.sex);
            Console.WriteLine("person1 年龄:{0}", person1.age);

            //输出 person2 的信息
            Console.WriteLine("person2 姓名:{0}", person2.name);
            Console.WriteLine("person2 性别:{0}", person2.sex);
            Console.WriteLine("person2 年龄:{0}", person2.age);

            Console.Read();
        }
    }
}

最小的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
    }
  }
}

 

最大子种类的和

行使动态规划:

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

当上边的代码被编译和进行时,它会发出下列结果:

先是个只现出一次的字符

在字符串中找出第三个只出现四次的字符。如输入"abaccdeff"则输出'b',思路类似于桶排序,在scala或者java中一个char占16位(两字节),可是大家只须要容纳所有ascill码的桶就行(即数高管度位256)。

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
}
person1 姓名:张三
person1 性别:男
person1 年龄:18
person2 姓名:李四
person3 性别:男
person4 年龄:20

多少个链表的首先个公共结点

多少个链表有重合部分,那么这两条链表相比像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)
}

 

二叉树的深度

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

协会与类具有众多一样的语法,但社团比类受到的限制越来越多:

二叉树是还是不是平衡

先写个简易的版本(必要多次重复遍历结点,不可取):

  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
}
  • 社团可含蓄艺术、字段、索引、属性、运算符方法和事件。
  • 协会不可以宣称默许构造函数(没有参数的构造函数)或终结器。
  • 社团可以注脚具有参数的构造函数。
  • 一个布局不可以持续自另一个布局或类,并且它不可能为类的基类。
  • 社团可已毕一个或三个接口。
  • 结构成员不可以指定为 abstract、virtual 或 protected。
  • 与类分裂,无需使用 new 运算符即可对结构进行实例化。
  • 要是不应用 New
    操作符,只有在富有的字段都被起首化之后,字段才被赋值,对象才被利用。

二维数组的探寻

留存这么的一个二维数组,每一行都在听从从左到右递增的各种排序。每一列都听从从上到下的逐条排序。现在加以一个数,请判断数组中是不是带有那些数。
注明式编程

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

多提一下:可将社团类型强制转换为接口类型,那将导致“装箱”操作,以将社团包装在托管堆上的引用类型对象内。
当将值类型传递到接受 Object
作为输入参数的形式时,将爆发装箱操作。详细的会在后头装箱和注销装箱表明。

旋转数组的蝇头数字

把一个数组最发轫的几何个元素搬到数组的尾声。大家称为旋转数组。输入一个递增数组排序的数组的一个转悠,输出旋转数组的细微元素。比如{3,4,5,1,2}为一个转悠数组,找出其最小数。

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

C# 的 enum 

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

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
}

枚举类型(也号称枚举)为定义一组能够赋给变量的命名整数常量提供了一种有效的点子。
例如,如果您必须定义一个变量,该变量的值表示一周中的一天。
该变量只好存储三个有意义的值。
若要定义这个值,可以应用枚举类型。枚举类型是选用 enum 关键字申明的:

装有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

代码:

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
}
enum Days { Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday };
enum Months : byte { Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec }; 

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

反过来单词顺序
留存一个字符串"i am a student. ",翻转句子中单词的逐一,但单词内字符的逐一不变,应该出口" 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)

一次翻转就行。

 

默许景况下,枚举中每个元素的基本功项目是 int。
可以运用冒号指定另一种整数值类型,如前方的以身作则所示。准许使用的种类有
byte、sbyte、short、ushort、int、uint、long 或 ulong。

 

平常状态下,最好是在命名空间内直接定义枚举,以便该命名空间中的所有类都可以平等有益地走访它。
可是,仍能将枚举嵌套在类或结构中。
默许景况下,第二个枚举数的值为 0,后边每个枚举数的值依次递增 1。
例如,上边的枚举,Sat 是 0,Sun 是 1,Mon 是 2 等。

enum Days {Sat, Sun, Mon, Tue, Wed, Thu, Fri};

 

 

如上面的示范所示枚举数可用初叶值来重写默许值。

enum Days {Sat=1, Sun, Mon, Tue, Wed, Thu, Fri};

 在此枚举中,强制因素连串从 1 而不是 0 开始。 不过,一般提出如此使用。注,枚举数的称呼中无法包涵空白。

 

假定变量
meetingDay 的品类为 Days,则只可以将 Days
定义的某部值赋给它(无需显式强制转换)。 假诺会议日期变更,能够将 Days
中的新值赋给 meetingDay:

Days meetingDay = Days.Monday;
//...
meetingDay = Days.Friday;

 可以将随意整数值赋给 meetingDay。 例如,代码行 meetingDay = (Days)
42 不会暴发错误。 但也不应当那样做,因为默许约定的是枚举变量只容纳枚举定义的值之一。 将任意值赋给枚举类型的变量很有可能会促成错误。
 
下边的实例演示了枚举变量的用法:

using System;

namespace MyEnum
{
    class Program
    {
        enum Days { Sun, Mon, tue, Wed, thu, Fri, Sat };
        static void Main(string[] args)
        {
            int WeekdayStart = (int)Days.Mon;
            int WeekdayEnd = (int)Days.Fri;
            Console.WriteLine("Monday: {0}", WeekdayStart);
            Console.WriteLine("Friday: {0}", WeekdayEnd);

            Console.Read();
        }
    }
}

 

当下边的代码被编译和实施时,它会发生下列结果:

Monday: 1
Friday: 5

品种源码下载:https://pan.baidu.com/s/1miOPAdU


 

C#基础,目录

上一篇:4、C#基础 – C# 的
常见概念简述

下一篇:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图