仓颉编程语言白皮书

随着万物互联以及智能时代的到来，软件的形态将发生巨大的变化。一方面，移动应用和移动互联网领域仍然强力驱动人机交互、设备协同、智能化、安全性等方向的创新，另一方面人工智能也同样驱动软件朝智能化、端边云协同等方向演进。新技术、新场景下应用软件的开发对编程语言提出了新的诉求和挑战。

仓颉编程语言作为一款面向全场景应用开发的现代编程语言，通过现代语言特性的集成、全方位的编译优化和运行时实现、以及开箱即用的 IDE 工具链支持，为开发者打造友好开发体验和卓越程序性能。其具体特性表现为：

• 高效编程：面向应用开发，我们希望语言能够易学易用，降低开发者入门门槛和开发过程中的心智负担，支持各种常见的开发范式和编程模式，让开发者简洁高效地表达各种业务逻辑。仓颉是一门多范式编程语言，支持函数式、命令式和面向对象等多种范式，包括值类型、类和接口、泛型、代数数据类型、模式匹配、以及高阶函数等特性。此外，仓颉还支持类型推断，能够减轻开发者类型标注的负担；通过一系列简明高效的语法，能够减少冗余书写、提升开发效率；语言内置的各种语法糖和宏（macro）的能力，支持开发者基于仓颉快速开发领域专用语言（DSL），构建领域抽象。

• 安全可靠：作为现代编程语言，仓颉追求编码即安全，通过静态类型系统和自动内存管理，确保程序的类型安全和 null safety 等内存安全；同时，仓颉还提供各种运行时检查，包括数组下标越界检查、类型转换检查、数值计算溢出检查、以及字符串编码合法性检查等，能够及时发现程序运行中的错误；此外，还通过代码扫描工具、混淆工具以及消毒器，进一步提供跨语言互操作安全和代码资产保护等支持。

• 轻松并发：并发和异步编程能够有效提高处理器利用率，并在交互式应用中确保程序的响应速度，是应用开发中必不可少的能力。仓颉语言实现了轻量化用户态线程和并发对象库，让高效并发变得轻松。仓颉语言采用用户态线程模型，每个仓颉线程都是极其轻量级的执行实体，拥有独立的执行上下文但共享内存。对开发者来说，用户态线程的使用和传统的系统线程的使用方式保持一致，没有带来额外负担；而从运行态视角看，线程的管理由运行时完成，不依赖操作系统的线程管理，因此线程的创建、调度和销毁等操作更加高效，且资源占用比系统线程更少。为了避免数据竞争，仓颉语言提供了并发对象库，并发对象的方法是线程安全的，因此在多线程中调用这些方法和串行编程没有区别，应用逻辑的开发者无需额外关心并发管理。对于一些核心库，仓颉还提供了无锁或者细粒度锁的算法实现，能够进一步减少线程的阻塞，提升并发度。

• 卓越性能：仓颉编译器及运行时从全栈对编译进行优化，包括编译器前端基于 CHIR（Cangjie HighLevel IR）高层编译优化（比如语义感知的循环优化、语义感知的后端协同优化等），基于后端的编译优化（比如：SLP 向量化、Intrinsic 优化、InlineCache、过程间指针优化、Barrier 优化等），基于运行时的优化（比如轻量锁、分布式标记、并发 Tracing 优化等），一系列的优化让仓颉充分发挥处理器能力，为应用提供卓越的性能支持。另外仓颉语言对运行时进行原生的轻量化设计，通过对运行时模块化分层设计，定义仓颉公共对象模型和运行时公共基础组件，基于公共对象模型，实现运行时的内存管理、回栈、异常处理、跨语言调用等基础能力，大幅减少多个能力间的冗余对象设计，精简运行时体积。同时通过包的按需加载技术，减少仓颉应用启动的冗余包内存开销，因此对于资源敏感设备，占用资源更少，支持更友好。

除此之外，仓颉还支持面向应用开发的一系列工具链，包括语言服务（高亮、联想）、调试（跨语言调试、线程级可视化调试）、静态检查、性能分析、包管理、文档生成、Mock 工具、测试框架、覆盖率工具、Fuzz 工具以及智能辅助编程工具，进一步提升软件开发体验以及效率。以下我们将围绕上述几个方面介绍仓颉语言的主要特性，让读者能够快速了解仓颉语言的定位和主要技术特色。

高效编程

仓颉支持面向对象、函数式、命令式等多种编程范式的融合，既支持面向对象编程范式的模块化和灵活性，又支持函数式编程范式的简洁性和高抽象级表达，使得开发者能够根据业务需求，选择最合适的表达方式，简洁高效地开发业务代码。

除此以外，仓颉还借鉴了现代语言中的各种优秀语言特性，包括各种声明式语法和语法糖，除了能让通用场景的编程更加简洁，还可以针对特定场景快速设计领域特定语言（DSL），以提升领域易用性。

仓颉是一个典型的多范式编程语言，对过程式编程、面向对象编程和函数式编程都提供了良好的支持，包括值类型、类和接口、泛型、代数数据类型和模式匹配，以及函数作为一等公民等特性支持。

多范式

仓颉是一个典型的多范式编程语言，对过程式编程、面向对象编程和函数式编程都提供了良好的支持，包括值类型、类和接口、泛型、代数数据类型和模式匹配，以及函数作为一等公民等特性支持。

类和接口

仓颉支持使用传统的类（class）和接口（interface）来实现面向对象范式编程。仓颉语言只允许单继承，每个类只能有一个父类，但可以实现多个接口。每个类都是 Object 的子类（直接子类或者间接子类）。此外，所有的仓颉类型（包括 Object）都隐式地实现 Any 接口。

仓颉提供 open 修饰符，来控制一个类能不能被继承，或者一个对象成员函数能不能被子类重写（override）。

在下面的例子中，类 B 继承了类 A，且同时实现了接口 I1 和 I2。为了让 A 能够被继承，它的声明需要被 open 修饰。类 A 中的函数 f 也被 open 修饰，因此可以在 B 中被重写。对函数 f 的调用会根据对象具体的类型来决定执行哪个版本，即动态派遣。

public open class A {
    let x: Int = 1
    var y: Int = 2

    public open func f(): Unit {
        println("function f in A")
    }

    public func g(): Unit {
        println("function g in A")
    }
}

public interface I1 {
    func h1(): Unit
}

public interface I2 {
    func h2(): Unit
}

public class B <: A & I1 & I2 {
    public override func f(): Unit {
        println("function f in B")
    }

    public func h1(): Unit {
        println("function h1 in B")
    }

    public func h2(): Unit {
        println("function h2 in B")
    }
}

main() {
    let o1: I1 = B()
    let o2: A = A()
    let o3: A = B()


    o1.h1() // "function h1 in B"
    o2.f()  // "function f in A"
    o3.f()  // 动态派遣，"function f in B"
    o3.g()  // "function g in A"  
}

interface I1 {
    func f(x: Int): Unit
}


interface I2 {
    func g(x: Int): Int
}


interface I3 <: I1 & I2 {
    func h(): Unit
}

函数作为一等公民

仓颉中函数可以作为普通表达式使用，可以作为参数传递，作为函数返回值，被保存在其他数据结构中，或者赋值给一个变量使用。

func f(x: Int) {
    return x
}

let a = f
let square = {x: Int => x * x} // lambda 表达式
// 函数嵌套定义，以及函数作为返回值
func g(x: Int) {
    func h(){
        return f(square(x))
    }
    return h
}

func h(f: ()->Int) {
    f()
}

let b = h(g(100))

class C{
    var x = 100
    func resetX(n: Int){
        x = n
        return x
    }
}

main(){
    let o = C()
    let f = o.resetX  // 成员函数作为一等公民
    f(200)
    print(o.x) // 200
}

代数数据类型和模式匹配

代数数据类型是一种复合类型，指由其它数据类型组合而成的类型。两类常见的代数类型是积类型（如 struct、tuple 等）与和类型（如 tagged union）。

在此我们着重介绍仓颉的和类型 enum，以及对应的模式匹配能力。

在下面的例子中，enum 类型 BinaryTree 具有两个构造器，Node 和 Empty。其中 Empty 不带参数，对应于只有一个空节点的二叉树，而 Node 需要三个参数来构造出一个具有一个值和左右子树的二叉树。

enum BinaryTree {
    | Node(value: Int, left: BinaryTree, right: BinaryTree)
    | Empty
}

func sumBinaryTree(bt: BinaryTree) {
    match (bt) {
        case Node(v, l, r) =>
            v + sumBinaryTree(l) + sumBinaryTree(r)
        case Empty => 0
    }
}

• 常量模式：可以使用多种字面量值进行判等比较，如整数、字符串等。
• 绑定模式：可以将指定位置的成员绑定到新的变量，多用于解构 enum 或 tuple。上面的 sumBinaryTree 例子中就用到了绑定模式，将 Node 节点中实际的参数与三个新声明的变量 v、l 和 r 分别绑定。
• 类型模式：可以用于匹配是否目标类型，多用于向下转型。
• tuple 模式：用于比较或者解构 tuple。
• 通配符模式：用于匹配任何值。

未来仓颉还计划引入更加丰富的模式，如序列（sequence）模式、record 模式等。

// 常量模式-字符串字面量
func f1(x: String) {
    match (x) {
        case "abc" => ()
        case "def" => ()
        case _ => () // 通配符模式
    }
}

// tuple 模式
func f2(x: (Int, Int)) {
    match (x) {
        case (_, 0) => 0  // 通配符模式和常量模式
        case (i, j) => i / j // 绑定模式，将 x 的元素绑定到 i 和 j 两个变量
    }
}

// 类型模式
func f3(x: ParentClass) {
    match (x) {
        case y: ChildClass1 => ...
        case y: ChildClass2 => ...
        case _ => ...
    }
}

泛型

在现代软件开发中，泛型编程已成为提高代码质量、复用性和灵活性的关键技术。泛型作为一种参数化多态技术，允许开发者在定义类型或函数时使用类型作为参数，从而创建可适用于多种数据类型的通用代码结构。泛型带来的好处包括：

• 代码复用：能够定义可操作多种类型的通用算法和数据结构，减少代码冗余。
• 类型安全：支持更多的编译时的类型检查，避免了运行时类型错误，增强了程序的稳定性。
• 性能提升：由于避免了不必要的类型转换，泛型还可以提高程序执行效率。

仓颉支持泛型编程，诸如函数、struct、class、interface、extend 都可以引入泛型变元以实现功能的泛型化。数组类型在仓颉中就是典型的泛型类型应用，其语法表示为 Array<T>，其中 T 表示了元素的类型，可以被实例化为任何一个具体的类型，例如 Array<Int> 或 Array<String>，甚至可以是嵌套数组 Array<Array<Int>>，从而可以轻易地构造各种不同元素类型的数组。

除了类型外，我们还可以定义泛型函数。例如我们可以为使用泛型函数来实现任意两个同类型数组的 concat 操作。如下代码所示，我们定义了一个泛型函数 concat，并且它支持任意两个 Array<T> 类型的数组参数，经过处理后返回了一个拼接后的新数组。这样定义的 concat 函数可以应用在 Array<Int>、Array<String>、Array<Array<Int>> 以及其它任意类型的数组上，实现了功能的通用化。

func concat<T>(lhs: Array<T>, rhs: Array<T>): Array<T> {
    let defaultValue = if (lhs.size > 0) {
        lhs[0]
    } else if (rhs.size > 0) {
        rhs[0]
    } else {
        return []
    }
    let newArr = Array<T>(lhs.size + rhs.size, item: defaultValue)
    // 使用数组切片进行整段拷贝
    newArr[0..lhs.size] = lhs
    newArr[lhs.size..lhs.size+rhs.size] = rhs
    return newArr
}

func lookup<T>(element: T, arr: Array<T>): Bool where T <: Equatable<T> {
    for (e in arr){
        if (element == e){
            return true
        }
    }
    return false
}

如下示例所示，Apple 是 Fruit 的子类，但是变量 a 和变量 b 之间是不能互相赋值的，Array<Fruit> 和 Array<Apple> 之间没有子类型关系。

open class Fruit {}
class Apple <: Fruit {}

main() {
    var a: Array<Fruit> = []
    var b: Array<Apple> = []
    a = b // 编译报错
    b = a // 编译报错
}

类型扩展

仓颉支持类型扩展特性，允许我们在不改变原有类型定义代码的情况下，为类型增加成员函数等功能。具体来说，

仓颉的类型扩展可以对已有的类型做如下几类扩展：

• 添加函数
• 添加属性
• 添加操作符重载
• 实现接口

下面的例子中，我们为 String 类型增加了 printSize 成员函数，因此在下面的代码中就可以像调用其他预定义的成员函数一样来调用 printSize。

extend String {
    func printSize() {
        print(this.size)
    }
}

main() {
    "123".printSize()
}

在下面的例子中，我们可以定义一个新接口 Integer，然后用 extend 给已有的整数类型实现 Integer 接口，这样已有的整数类型就自然成为了 Integer 的子类型。其中 sealed 修饰符表示该接口只能在当前包中被实现（或扩展）。

sealed interface Integer {}

extend Int8 <: Integer {}
extend Int16 <: Integer {}
extend Int32 <: Integer {}
extend Int64 <: Integer {}

let a: Integer = 123 // ok

类型推断

类型推断是指由编译器根据程序上下文自动推断变量或表达式的类型，而无需开发者显式写出。

仓颉作为现代编程语言，对类型推断也提供了良好的支持。

在仓颉中变量的定义可以根据初始化表达式的类型来推断其类型。除了变量以外，仓颉还额外支持了函数定义返回值类型的推断。在仓颉中，函数体的最后一个表达式会被视为这个函数的返回值。像变量一样，当函数定义省略了返回类型，函数就会通过返回值来推断返回类型。

var foo = 123 // foo 是 'Int64'
var bar = 'hello' // bar 是 'String'

func add(a: Int, b: Int) { // add 返回 Int
  a + b
}

func map<T, R>(f: (T)->R): (Array<T>)->Array<R> {
    ...
}

map({ i => i.toString() })([1, 2, 3]) // 支持推断泛型柯里化函数
// 推断结果为map<Int, String>({ i => i.toString() })([1, 2, 3])

其他现代特性及语法糖

函数重载

仓颉允许在同一作用域内定义多个同名函数。编译器根据参数的个数和类型，来决定函数调用实际执行的是哪个函数。例如，下面的绝对值函数，为每种数值类型都提供了对应的实现，但这些实现都具有相同的函数名 abs，从而让函数调用更加简单。

func abs(x: Int64): Int64 { ... }
func abs(x: Int32): Int32 { ... }
func abs(x: Int16): Int16 { ... }
...

命名参数

命名参数是指在调用函数时，提供实参表达式的同时，还需要同时提供对应形参的名字。使用命名参数可以提升程序的可读性，减少参数的顺序依赖性，让程序更加易于扩展和维护。

在仓颉中，函数定义时通过在形参名后添加 ! 来定义命名参数。当形参被定义为命名参数后，调用这个函数时就必须在实参值前指定参数名，如下面的例子所示：

func dateOf(year!: Int, month!: Int, dayOfMonth!: Int) {...}
dateOf(year: 2024, month: 6, dayOfMonth: 21)

参数默认值

仓颉的函数定义中，可以为特定形参提供默认值。函数调用时，如果选择使用该默认值做实参，则可以省略该参数。

这个特性可以减少很多函数重载或者引入建造者模式的需求，降低代码复杂度。

func dateOf(
    year!: Int64, 
    month!: Int64, 
    dayOfMonth!: Int64, 
    timeZone!: TimeZone = TimeZone.Local
) {...}

dateOf(year: 2024, month: 6, dayOfMonth: 21) 
dateOf(year: 2024, month: 6, dayOfMonth: 21, timeZone: TimeZone.UTC) 

尾随 lambda（trailing lambda）

仓颉支持尾随 lambda 语法糖，从而更易于 DSL 中实现特定语法。具体来说，很多语言中都内置提供了如下经典的条件判断或者循环代码块：

if (x > 0) {
    x = -x
}

while (x > 0) {
    x--
}

尾随 lambda 则能够让 DSL 开发者定制出类似的代码块语法，而无需在宿主语言中内置。例如，在仓颉中，我们支持下面这种方式的函数调用：

func unless(condition: Bool, f: ()->Unit) {
    if(!condition) {
        f()
    }
}

let a = f(...)
unless(a > 0) {
    print("no greater than 0")
}

这里对 unless 函数的调用看上去像是一种特殊的 if 表达式，这种语法效果是通过尾随 lambda 语法实现 —— 如果函数的最后一个形参是函数类型，那么实际调用这个函数时，我们可以提供一个 lambda 表达式作为实参，并且把它写在函数调用括号的外面。尤其当这个 lambda 表达式为无参函数时，我们允许省略 lambda 表达式中的双箭头 =>，将其表示为代码块的形式，从而进一步减少对应 DSL 中的语法噪音。因此，在上面的例子中，unless 调用的第二个实参就变成了这样的 lambda 表达式：

{ print("no greater than 0") }

如果函数定义只有一个参数，并且该参数是函数类型，我们使用尾随 lambda 调用该函数时还可以进一步省略函数调用的括号，从而让代码看上去更简洁自然。

func runLater(fn:()->Unit) {
    sleep(5 * Duration.Second)
    fn()
}

runLater() { // ok
    println("I am later")
}

runLater { // 可以进一步省略括号
    println("I am later")
}

管道（Pipeline）操作符

仓颉中引入管道（Pipeline）操作符，来简化嵌套函数调用的语法，更直观的表达数据流向。下面的例子中，给出了嵌套函数调用和与之等效的基于管道操作符 |> 的表达式。后者更加直观的反映了数据的流向：|> 左侧的表达式的值被作为参数传递给右侧的函数。

func double(a: Int) {
    a * 2
}

func increment(a: Int) {
    a + 1
}

main() {
println(double(increment(double(double(5))))) // 42

5 |> double |> double |> increment |> double |> println // 42
}

操作符重载

仓颉中定义了一系列使用特殊符号表示的操作符，其中大多数操作符都允许被重载，从而可以作用在开发者自己定义的类型上，为自定义类型的操作提供更加简洁直观的语法表达。

在仓颉中只需要定义操作符重载函数就能实现操作符重载。在下面的例子中，我们首先定义一个类型 Point 表示二维平面中的点，然后我们通过重载+操作符，来定义两个点上的加法操作。

struct Point {
    let x: Int
    let y: Int

    init(x: Int, y: Int) {...}

    operator func +(rhs: Point): Point {
        return Point(
            this.x + rhs.x,
            this.y + rhs.y
        )
    }
}

let a: Point = ...
let b: Point = ...
let c = a + b

属性（property）

在面向对象范式中，我们常常会将成员变量设计为 private 的，而将成员变量的访问封装成 getter 和 setter 两种 public 方法。

这样可以隐藏数据访问的细节，从而更容易实现访问控制、数据监控、跟踪调试、数据绑定等业务策略。

仓颉中直接提供了属性这一种特殊的语法，它使用起来就像成员变量一样可以访问和赋值，但内部提供了 getter 和 setter 来实现更丰富的数据操作。对成员变量的访问和赋值会被编译器翻译为对相应 getter 和 setter 成员函数的调用。

具体来说，prop 用于声明只读属性，只读属性只具有 getter 的能力，必须提供 get 实现；mut prop 用于声明可变属性。可变属性同时具备 getter 和 setter 的能力，必须提供 get 和 set 实现。

如下示例所示，开发者希望对 Point 类型的各数据成员的访问进行记录，则可以在内部声明 private 修饰的成员变量，通过声明对应的属性来对外暴露访问能力，并在访问的时候使用日志系统 Logger 记录它们的访问信息。对使用者来说，使用对象 p 的属性与访问它的成员变量一样，但内部却实现了记录的功能。

注意这里 x 和 y 是只读的，只有 get 实现，而 color 则是可变的，用 mut prop 修饰，同时具有get 和 set 实现。

class Point {
    private let _x: Int
    private let _y: Int
    private var _color: String

    init(x: Int, y: Int, color: String) {
        _x = x
        _y = y
        _color = color
    }

    prop x: Int {
        get() {
            println('level: Debug, "access x"')
            return _x
        }
    }

    prop y: Int {
        get() {
            println('level: Debug, "access y"')
            return _y
        }
    }

    mut prop color: String {
        get() {
            println('level: Debug, "access color"')
            return _color
        }

        set(c) {
            println('level: Debug, "reset color to ${c}"')
            _color = c
        }
    }
}

main() {
    let p = Point(0, 0, "red")
    let x = p.x // "access x"
    let y = p.y // "access y"
    p.color = "green" // "reset color to green"
}

安全可靠

编程语言的设计和实现，以及相应工具支持，对于程序质量和安全性有重要影响。

仓颉通过静态类型系统、动静态检查、自动内存管理、以及工具链来提升程序的安全性。

静态类型和垃圾收集

仓颉是静态类型语言，程序中所有变量和表达式的类型都是在编译期确定的，并且在程序运行过程中不会发生改变。相比动态类型系统，静态类型系统对开发者有更多的约束，但能够在编译期尽量早的发现程序中的错误，提高程序的安全性，同时也让程序的行为更加容易预测，为编译优化提供了更多信息，使能更多的编译优化，提升程序的性能。

垃圾收集（GC）是一种自动内存管理机制，它能够自动识别和回收不再需要使用的对象，将开发者从手工释放内存中解放出来，不仅可以提高开发效率，还能有效避免各种常见内存错误，提升程序的安全性。常用的垃圾收集技术包括 tracing 和引用计数（reference counting，即 RC）。仓颉采用 tracing GC 技术，通过在运行时跟踪对象之间的引用关系，来识别活动对象和垃圾对象。

空引用安全

空引用是指引用类型的值可以为 null。代码存在空引用会引发各种各样潜在的风险，空引用被图灵奖得主 Tony Hoare 称为“价值十亿美元的错误”。

在许多编程语言中，空引用都是最常见的陷阱之一，开发者很容易在未确保非空的情况下访问引用类型的成员，从而引发错误或异常。因为语言类型系统并未给非空引用类型提供任何保障。

空引用安全就是旨在消除代码空引用危险。

仓颉是实现了空引用安全的语言之一。在仓颉中，没有提供 null 值，换句话说，仓颉的引用类型永远是非空的。从而在类型上杜绝了空引用的发生。

值得注意的是，表示一个空值在语义中是十分有用的。在仓颉中，对于任意类型T，都可以有对应的可选类型 Option<T>。具有 Option<T>类型的变量要么对应一个实际的具有 T 类型的值 v，因此取值为 Some(v)，要么具有空值，取值为 None。

可选类型（Option<T>）是一种 enum 类型，是一个经典的代数数据类型，表示有值或空值两种状态。

enum Option<T> {
    Some(T) | None
}

var a: Option<Int> = Some(123)
a = None

基于可选类型使用的广泛性，仓颉还为可选类型提供了丰富的语法糖支持。例如可以使用 ?T 来代替 Option<T>，也提供了可选链操作符（?.）来简化成员访问，以及空合并操作符（??）来合并有效值。

var a: ?Int = None
a?.toString() // None
a ?? 123 // 123
a = Some(321)
a?.toString() // Some("321")
a ?? 123 // 321

值类型

值类型是一种具有传递即复制的语义行为的类型，具有值类型的变量，其中保存的是数据自身，而不是指向数据的引用。由于值类型的这种特性，开发者选择性地使用值类型可以使得程序显著减少修改语义，从而让程序变得更可预测、更可靠。

例如最典型的并发安全问题就是在程序不同的线程中传递了同一个可变对象，此时访问这个对象的字段将会造成不可预测的 data race 问题。如果这个对象具备值语义，那么在传递的过程中我们就可以保证它经过了完整的复制，让每个线程对该值的访问都是彼此独立的，从而保证了并发安全。

仓颉原生支持了值类型，除了常见的 Int 类型以外，仓颉也可以使用 struct 来实现用户自定义的值类型。

如下面的例子，Point 正是一个值类型，因此在经过赋值后，a 和 b 已经是两个彼此独立的变量，对 a 的修改不会影响到 b。

struct Point {
    var x: Int
    var y: Int
    init(x: Int, y: Int) { ... }
    ...
}

var a = Point(0, 0)
var b = a
a.x = 1
print(b.x) // 0

不可变优先

不可变（Immutable）指的是在变量赋值或对象创建结束之后，使用者就不能再改变它的值或状态。不可变意味着只读不写，因此不可变对象天然地具备线程安全的特性，即如无其它特殊限制的话可以在任何线程上自由调用。此外，相较于可变对象，不可变对象的访问没有副作用，因此在一些场合下也会让程序更易于了解，而且提供较高的安全性。

不可变通常可以分为两种，一种是不可变变量，不可变变量是指经初始化后其值就不可被修改的变量；另一种是不可变类型，不可变类型是指在构造完成后实际数据对象的内容无法被改变。

在仓颉中，let 定义的变量是不可变变量，而像 String、enum 等类型是不可变类型，这些都是不可变思想在仓颉中的应用。更多地使用不可变特性可以让程序更安全，也更利于理解和维护。

函数参数不可变

在仓颉中，所有函数形参都是不可变的，这意味着我们无法对形参赋值，如果形参是值类型，也无法修改形参的成员。

struct Point {
    var x: Int
    var y: Int
    init(x: Int, y: Int) { ... }
    ...
}


func f(a: Point) {  
    a = Point(0, 0) 
    a.x = 2 
}

模式匹配引入的新变量不可变

在仓颉中，模式匹配支持变量绑定模式，我们可以将目标值解析到新绑定的变量中，但这个变量仍然是不可变的。这意味着我们无法对绑定的变量赋值，如果变量是值类型，也无法修改变量的成员。

func f(a: ?Point) {
    match (a) {
        case Some(b) => 
            b = Point(0, 0) 
            b.x = 2 
        case None => ()
    }
}

闭包捕获可变变量不允许逃逸

在仓颉中，闭包指的自包含的函数或 lambda，闭包可以从定义它的静态作用域中捕获变量，即使对闭包调用不在定义的作用域，仍可以访问其捕获的变量。

仓颉中允许闭包捕获可变变量，但不允许该闭包继续逃逸，这避免了对可变变量修改可能导致的意外行为。

func f() {
    let a = 1
    var b = 2
    func g() {
        print(a) 
        print(b) 
    }
    return g 
}

初识仓颉语言

仓颉编程语言是一种面向全场景应用开发的通用编程语言，可以兼顾开发效率和运行性能，并提供良好的编程体验，主要具有如下特点：

语法简明高效

仓颉编程语言提供了一系列简明高效的语法，旨在减少冗余书写、提升开发效率，例如插值字符串、主构造函数、Flow 表达式、match 和重导出等语法，让开发者可以用较少编码表达相关逻辑。

main() {
    let lang = "cangjie"
    "hello, ${lang}!" |> println // 插值字符串和 pipeline 表达式

    // Lamda 表达式
    let applyFunc = {
        v: Int64, f: (Int64) -> Int64 => f(v)
    }

    let double = {x: Int64 => x * 2}
    let square = {x: Int64 => x * x}

    // composition 表达式
    let doubleAfterSquare = square ~> double 

    applyFunc(5) {it => it + 3} |> println  // 尾随 lambda
    doubleAfterSquare(3) |> println   
}

多范式编程

仓颉编程语言支持函数式、命令式和面向对象等多范式编程，融合了高阶函数、代数数据类型、模式匹配、泛型等函数式语言的先进特性，还有封装、接口、继承、子类型多态等支持模块化开发的面向对象语言特性，以及值类型、全局函数等简洁高效的命令式语言特性。开发者可以根据开发偏好或应用场景，选用不同的编程范式。

• 含匹配值的 match 表达式：

main() {
    let x = 0
    match (x) {
        case 1 => let r1 = "x = 1"
                  print(r1)
        case 0 => let r2 = "x = 0" // Matched.
                  print(r2)
        case _ => let r3 = "x != 1 and x != 0"
                  print(r3)
    }
}

• 没有匹配值的 match 表达式：

main() {
    let x = -1
    match {
        case x > 0 => print("x > 0")
        case x < 0 => print("x < 0") // Matched.
        case _ => print("x = 0")
    }
}

类型安全

仓颉编程语言是静态强类型语言，通过编译时类型检查尽早识别程序错误，降低运行时风险，也便于代码维护。同时，仓颉编译器提供了强大的类型推断能力，可以减少类型标注工作，提高开发效率。

内存安全

仓颉编程语言支持自动内存管理，并在运行时进行数组下标越界检查、溢出检查等，确保运行时内存安全。

@OverflowThrowing
main() {
let res: Int8 = Int8(100) + Int8(29)
// 100 + 29 在数学上等于 129，在 Int8 的表示范围上发生了上溢出，程序抛出异常
res |> println
}

高效并发

仓颉编程语言提供了用户态轻量化线程（原生协程），以及简单易用的并发编程机制，保证并发场景的高效开发和运行。

import std.sync.*
import std.time.*

main() {
spawn { =>
    println("New thread before sleeping")
    sleep(100 * Duration.millisecond) // sleep for 100ms.
    println("New thread after sleeping")
}
println("Main thread")
}

兼容语言生态

仓颉编程语言支持和 C 等主流编程语言的互操作，并采用便捷的声明式编程范式，可实现对其他语言库的高效复用和生态兼容。

// declare the function by `foreign` keyword, and omit `@C`
foreign func rand(): Int32
foreign func printf(fmt: CString, ...): Int32

main() {
// call this function by `unsafe` block
let r = unsafe { rand() }
println("random number ${r}")
unsafe {
    var fmt = LibC.mallocCString("Hello, No.%d\n")
    printf(fmt, 1)
    LibC.free(fmt)
}
}

领域易扩展

仓颉编程语言提供了基于词法宏的元编程能力，支持在编译时变换代码，此外，还提供了尾随 lambda、属性、操作符重载、部分关键字可省略等特性，开发者可由此深度定制程序的语法和语义，有利于内嵌式领域专用语言（Embedded Domain Specific Languages，EDSL）的构建。

通常 Memoize 的使用需要开发者手动实现存储和提取的功能。通过宏，可以自动化这一过程。宏的效果如下：

@Memoize[true]
func fib(n: Int64): Int64 {
    if (n == 0 || n == 1) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}

main() {
    let start = DateTime.now()
    let f35 = fib(35)
    let end = DateTime.now()
    println("fib(35): ${f35}")
    println("execution time: ${(end - start).toMicroseconds()} us")
}

助力 UI 开发

UI 开发是构建端侧应用的重要环节，基于仓颉编程语言的元编程和尾随 lambda 等特性，可以搭建声明式 UI 开发框架，提升 UI 开发效率和体验。

内置库功能丰富

仓颉编程语言提供了功能丰富的内置库，涉及数据结构、常用算法、数学计算、正则匹配、系统交互、文件操作、网络通信、数据库访问、日志打印、解压缩、编解码、加解密和序列化等功能。

扩展

import std.collection.*

main() {

    let arr = [1, 2, 3, 4, 5] 
    arr.forEach { it => println(it) }
    arr.forEach { i, it => println("${i}: -> ${it}") }
    arr.map { it => it * 2 } |> println
    arr.filter { it => it % 2 == 0 } |> println
    arr.every { it => it % 2 == 0 } |> println
    arr.some { it => it % 2 == 0 } |> println
    arr.reduce(10) { prev, next => prev + next } |> println
    "Hello".toArray().forEach { it => println(Rune(it)) }
    times(5) { i => unless(i % 2 != 0) { println(i) } }
}

/**
 * 为Array类扩展一系列函数，以支持各种数组操作
 */
extend<T> Array<T> {
    /**
     * 遍历数组并执行给定的操作
     *
     * @param f 一个接受数组元素并返回Unit的操作函数
     */
    public func forEach(f: (T) -> Unit): Unit {
        for (i in 0..this.size) {
            f(this[i])
        }
    }

    /**
     * 遍历数组并执行给定的操作，操作函数接收元素的索引和值
     *
     * @param f 一个接受索引和数组元素并返回Unit的操作函数
     */
    public func forEach(f: (Int, T) -> Unit): Unit {
        for (i in 0..this.size) {
            f(i, this[i])
        }
    }

    /**
     * 映射数组中的每个元素到新数组
     *
     * @param f 一个接受数组元素并返回新值的映射函数
     * @return 一个新的数组，包含映射后的元素
     */
    public func map(f: (T) -> T): Array<T> {
        var list = ArrayList<T>()
        for (i in 0..this.size) {
            f(this[i]) |> list.add
        }
        list.toArray()
    }

    /**
     * 过滤数组中的元素，只保留满足条件的元素
     *
     * @param f 一个接受数组元素并返回Bool的过滤函数
     * @return 一个新的数组，包含满足过滤条件的元素
     */
    public func filter(f: (T) -> Bool): Array<T> {
        var list = ArrayList<T>()
        for (i in 0..this.size) {
            if (f(this[i])) {
                this[i] |> list.add
            }
        }
        list.toArray()
    }

    /**
     * 检查数组中的所有元素是否满足条件
     *
     * @param f 一个接受数组元素并返回Bool的检查函数
     * @return 如果所有元素都满足条件则返回true，否则返回false
     */
    public func every(f: (T) -> Bool): Bool {
        for (i in 0..this.size) {
            if (!f(this[i])) {
                return false
            }
        }
        true
    }

    /**
     * 检查数组中是否存在满足条件的元素
     *
     * @param f 一个接受数组元素并返回Bool的检查函数
     * @return 如果存在满足条件的元素则返回true，否则返回false
     */
    public func some(f: (T) -> Bool): Bool {
        for (i in 0..this.size) {
            if (f(this[i])) {
                return true
            }
        }
        false
    }

    /**
     * 对数组中的元素执行归约操作
     *
     * @param f 一个接受两个数组元素并返回一个元素的归约函数
     * @return 归约操作的结果
     */
    public func reduce(f: (T, T) -> T): T {
        var result = this[0]
        for (i in 1..this.size) {
            result = f(result, this[i])
        }
        result
    }

    /**
     * 对数组中的元素执行归约操作，初始值为给定的值
     *
     * @param v 归约操作的初始值
     * @param f 一个接受两个数组元素并返回一个元素的归约函数
     * @return 归约操作的结果
     */
    public func reduce(v: T, f: (T, T) -> T): T {
        var result = v
        for (i in 0..this.size) {
            result = f(result, this[i])
        }
        result
    }
}

func times(n: Int64, f: (Int64) -> Unit): Unit {
    for (i in 0..n) { f(i) }
}

func unless(p: Bool, f: () -> Unit): Unit {
    if (!p) { f() }
}

函数式编程

main(){
    // First-Class Functions
    let applyFunc = {
        val: Int64, fn: (Int64) -> Int64 => fn(val)
    }

    // Higher-Order Functions
    let double = {x: Int64 => x * 2}
    let square = {x: Int64 => x * x}

    // Function Composition
    let compse = {
        f: (Int64) -> Int64, g: (Int64) -> Int64 => {
            x: Int64 => g(f(x))
        }
    }
    let doubleAfterSquare = square ~> double // compse(square, double)

    applyFunc(5) {it => it + 3} |> println
    doubleAfterSquare(3) |> println  
}

枚举类型

import std.math.*

// 枚举类型
enum Shape {
    | Circle(Float64)
    | Rectangle(Float64, Float64)
    | Square(Float64)

    // Pattern Matching
    public static func area(shape: Shape): Unit {
        let s = match (shape) {
            case Circle(radius) => radius * radius * Float64.PI
            case Rectangle(width, height) => width * height
            case Square(side) => side * side
        }
        "Area: ${s}" |> println
    }

    public static func perimeter(shape: Shape): Unit {
        let c = match (shape) {
            case Circle(radius) => radius * 2.0 * Float64.PI
            case Rectangle(width, height) => (width + height) * 2.0
            case Square(side) => side * 4.0
        }
        "Perimeter: ${c}" |> println
    }
}

main() {
    let circle = Circle(5.0)
    circle |> Shape.area
    circle |> Shape.perimeter

    let rectangle = Rectangle(4.0, 6.0)
    rectangle |> Shape.area
    rectangle |> Shape.perimeter

    let square = Square(7.0)
    square |> Shape.area
    square |> Shape.perimeter
}

运算符重载

import std.collection.*

main() {
    let a = List([1, 2, 3, 4, 5])
    a[-3] = 12
    a[-2] |> println
    a |> println
    "size: ${a.size}" |> println
}

class List<T> <: ToString where T <: ToString {
    public List(let v: ArrayList<T>) {}

    public init(a: Array<T>) {
        this.v = ArrayList<T>(a)
    }

    operator func [](idx: Int64): T {
        match {
            case idx > this.size => return this.v[this.size]
            case idx < 0 && -idx <= this.size => return this.v[this.size + idx]
            case -idx > this.size => return this.v[0]
            case _ => return this.v[idx]
        }
    }

    operator func [](idx: Int64, value!: T): Unit {
        match {
            case idx > this.size => this.v.add(value)
            case idx < 0 && -idx <= this.size => this.v[this.size + idx] = value
            case -idx > this.size => this.v[0] = value
            case _ => this.v[idx] = value
        }
    }

    public func toString(): String {
        return this.v.toString()
    }

    prop size: Int64 {
        get() {
            this.v.size
        }
    }
}

接口、类及继承

import std.math.*

public interface HasArea {
    func getArea(): Float64
    prop area: Float64 {
        get() {
            getArea()
        }
    }
}

public interface HasPerimeter {
    func getPerimeter(): Float64
    prop perimeter: Float64 {
        get() {
            getPerimeter()
        }
    }
}

class Circle <: HasArea & HasPerimeter {
    public Circle(let radius: Float64) {}

    public func getArea(): Float64 {
        radius * radius * Float64.PI
    }

    public func getPerimeter(): Float64 {
        radius * 2.0 * Float64.PI
    }
}

open class Rectangle <: HasArea & HasPerimeter {
    public Rectangle(let width: Float64, let height: Float64) {}

    public func getArea(): Float64 {
        width * height
    }

    public func getPerimeter(): Float64 {
        (width + height) * 2.0
    }
}

class Square <: Rectangle {
    public Square(let side: Float64) {
        super(side, side)
    }
}

func printArea(shape: HasArea) {
    "Area: ${shape.getArea()}" |> println
}

func printPerimeter(shape: HasPerimeter) {
    "Perimeter: ${shape.getPerimeter()}" |> println
}

main() {
    let circle = Circle(5.0)
    let rectangle = Rectangle(4.0, 6.0)
    let square = Square(7.0)

    circle |> printArea
    circle |> printPerimeter
    
    rectangle |> printArea
    rectangle |> printPerimeter
    
    square.area |> println
    square.perimeter |> println
}

序列化、反序列化

import encoding.json.*
import serialization.serialization.*

class Person <: Serializable<Person> {
    var name: String = ""
    var age: Int64 = 0
    var loc: Option<Location> = Option<Location>.None

    public func serialize(): DataModel {
        return DataModelStruct()
            .add(field<String>("name", name))
            .add(field<Int64>("age", age))
            .add(field<Option<Location>>("loc", loc))
    }

    public static func deserialize(dm: DataModel): Person {
        var dms = match (dm) {
            case data: DataModelStruct => data
            case _ => throw Exception("this data is not DataModelStruct")
        }
        var result = Person()
        result.name = String.deserialize(dms.get("name"))
        result.age = Int64.deserialize(dms.get("age"))
        result.loc = Option<Location>.deserialize(dms.get("loc"))
        return result
    }
}

class Location <: Serializable<Location>{
    var country: String = ""
    var province: String = ""

    public func serialize(): DataModel {
        return DataModelStruct()
            .add(field<String>("country", country))
            .add(field<String>("province", province))
    }

    public static func deserialize(dm: DataModel): Location {
        var dms = match (dm) {
            case data: DataModelStruct => data
            case _ => throw Exception("this data is not DataModelStruct")
        }
        var result = Location()
        result.country = String.deserialize(dms.get("country"))
        result.province = String.deserialize(dms.get("province"))
        return result
    }
}

main() {
    var js = ##"{
    "name": "A",
    "age": 30,
    "loc": {
        "country": "China",
        "province": "Beijing"
    }
}"##
    var jv = JsonValue.fromStr(js)
    var dm = DataModel.fromJson(jv)
    var A = Person.deserialize(dm)
    println("name == ${A.name}")
    println("age == ${A.age}")
    println("country == ${A.loc.getOrThrow().country}")
    println("province == ${A.loc.getOrThrow().province}")
    println("====================") 
    dm = A.serialize()
    var jo = dm.toJson().asObject()
    println(jo.toJsonString())
    0
}

JSON 构建及解析

import encoding.json.*
import std.collection.*

main() {
    "\n使用 JsonObject 构建json:\n" |> println
    let date = JsonObject()
    let map = HashMap<String, JsonValue>([
        ("name", JsonString("Alice")), 
        ("age", JsonInt(32))
    ])
    date.puts(map).put("date", JsonString("2024-10-27"))
    date.toJsonString() |> println
    "\n-----------------------------" |> println
    "\n从字符串解析Json:\n" |> println
    let json = ##"{
        "name": "Tom", 
        "age": 30,
        "city": "Shanghai"
    }"##
    let re = JsonValue.fromStr(json)
    re.toJsonString() |> println
}

extend JsonObject {
    public func puts(map: HashMap<String, JsonValue>): JsonObject {
        for ((k, v) in map) {
            this.put(k, v)
        }
        this
    }
}

找单独的数

问题描述

在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。

要求:

1. 设计一个算法，使其时间复杂度为 O(n)，其中 n 是班级的人数。
2. 尽量减少额外空间的使用，以体现你的算法优化能力。

测试样例

样例1：

输入：cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出：4
解释：拿到数字 4 的同学是唯一一个没有配对的。

样例2：

输入：cards = [0, 1, 0, 1, 2]
输出：2
解释：拿到数字 2 的同学是唯一一个没有配对的。

解题思路

1. 初始化一个变量 result = 0。
2. 遍历数组 cards，对于每个元素 card，执行异或操作 result ^= card。异或操作具有交换律和结合律，因此可以保证最终 result 的值为那个单独的数字。
3. 返回 result。

代码实现

Cangjie

func solution(cards: Array<Int64>): Int64{
    var result = 0
    for (card in cards) {
        result ^= card
    }
    result
}

main(){
    println(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4)
    println(solution([0, 1, 0, 1, 2]) == 2)   
}

Rust

fn solution(cards: Vec<i32>) -> i32 {
    let mut result = 0;
    for card in cards {
        result ^= card;
    }
    result
}

fn main() {
   println!("{}", solution(vec![1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4);
   println!("{}", solution(vec![0, 1, 0, 1, 2]) == 2);
}

Python

def solution(cards):
    result = 0
    for card in cards:
        result ^= card
    return result

print(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4)
print(solution([0, 1, 0, 1, 2]) == 2)

JavaScript

function solution(cards) {
    let result = 0;
    for (let card of cards) {
        result ^= card
    }
    return result
}

console.log(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4);
console.log(solution([0, 1, 0, 1, 2]) == 2);

复杂度分析

1. 时间复杂度：O(n)，其中 n 是班级的人数。遍历数组一次，异或操作的时间复杂度为 O(1)。
2. 空间复杂度：O(1), 只使用了常数级别的额外空间。

徒步旅行中的补给问题

问题描述

小R正在计划一次从地点A到地点B的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小R每天必须消耗1份食物。 幸运的是，小R在路途中每天都会经过一个补给站，可以购买食物进行补充。 然而，每个补给站的食物每份的价格可能不同，并且小R最多只能同时携带 K 份食物。

要求：

现在，小R希望在保证每天都有食物的前提下，以最小的花费完成这次徒步旅行。你能帮助小R计算出最低的花费是多少吗？

测试样例

样例1：

输入：n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]
输出：9

样例2：

输入：n = 6 ,k = 3 ,data = [4, 1, 5, 2, 1, 3]
输出：9

样例3：

输入：n = 4 ,k = 1 ,data = [3, 2, 4, 1]
输出：10

解题思路

1. 遍历数组 data，对于每个元素，将其添加到 ready 数组中。
2. 如果 ready 数组的长度大于 k，则删除 ready 数组中的第一个元素。
3. 计算当前 ready 数组中的最小值，并将其加到 min_money 中。
4. 返回 min_money。

代码实现

Cangjie

import std.collection.*

func solution(n: Int64, k: Int64, data: Array<Int64>) {
    var min_money = 0
    var ready = ArrayList<Int64>()
    for (i in data) {
        ready.add(i)
        if (ready.size > k) { ready.remove(at: 0) }
        let min_value = ready.iterator().min().getOrThrow()
        min_money += min_value
    }
    min_money
}

main() {
    println(solution(5, 2, [1, 2, 3, 3, 2]) == 9)
    println(solution(6, 3, [4, 1, 5, 2, 1, 3]) == 9)
    println(solution(4, 1, [3, 2, 4, 1]) == 10)
}

Rust

fn solution(n: usize, k: usize, data: Vec<i32>) -> i32 {
    let mut min_money = 0;
    let mut ready = Vec::new();
    for &i in &data {
        ready.push(i);
        if ready.len() > k {
            ready.remove(0);
        }
        let min_value = *ready.iter().min().unwrap();
        min_money += min_value;
    }
    min_money
}

fn main() {
   println!("{}", solution(5, 2, vec![1, 2, 3, 3, 2]) == 9);
   println!("{}", solution(6, 3, vec![4, 1, 5, 2, 1, 3]) == 9);
   println!("{}", solution(4, 1, vec![3, 2, 4, 1]) == 10);
}

Python

def solution(n, k, data):
    min_money = 0
    ready = []
    for i in data:
        ready.append(i)
        if len(ready) > k:
            ready.pop(0)
        min_value = min(ready)
        min_money += min_value
    return min_money

print(solution(5, 2, [1, 2, 3, 3, 2]) == 9)
print(solution(6, 3, [4, 1, 5, 2, 1, 3]) == 9)
print(solution(4, 1, [3, 2, 4, 1]) == 10)

JavaScript

function solution(n, k, data) {
    let min_money = 0;
    let ready = [];
    for (let i of data) {
        ready.push(i);
        if (ready.length > k) {
            ready.shift();
        }
        let min_value = Math.min(...ready);
        min_money += min_value;
    }
    return min_money;
}
console.log(solution(5, 2, [1, 2, 3, 3, 2]) == 9);
console.log(solution(6, 3, [4, 1, 5, 2, 1, 3]) == 9);
console.log(solution(4, 1, [3, 2, 4, 1]) == 10);

复杂度分析

1. 时间复杂度：O(n)，其中 n 是数组 data 的长度。遍历数组 data 的时间复杂度为 O(n)，对于每个元素，删除和添加操作的时间复杂度均为 O(k)，因此总的时间复杂度为 O(n+k)。
2. 空间复杂度：O(k)，其中 k 是数组 data 的长度。需要使用一个长度为 k 的数组 ready 来存储当前已经购买的食物价格。

数字字符串格式化

问题描述

小M在工作时遇到了一个问题，他需要将用户输入的不带千分位逗号的数字字符串转换为带千分位逗号的格式，并且保留小数部分。 小M还发现，有时候输入的数字字符串前面会有无用的 0，这些也需要精简掉。请你帮助小M编写程序，完成这个任务。

测试样例

样例1：

输入：s = "1294512.12412"
输出：'1,294,512.12412'

样例2：

输入：s = "0000123456789.99"
输出：'123,456,789.99'

样例3：

输入：s = "987654321"
输出：'987,654,321'

解题思路

1. 首先去掉字符串前面的无用的 0，可以使用 trimStart("0") 方法。
2. 将字符串按照小数点进行分割，得到整数部分和小数部分。
3. 将整数部分按照每三位进行分割，并在分割后的部分之间添加逗号。
4. 将整数部分和小数部分拼接起来，得到最终的结果。

代码实现

Cangjie

RuneArray

func solution(s: String) {
    let strArray = s.trimStart("0").split(".")
    let integer_part = strArray[0]
    var fractional_part = ""
    if (strArray.size > 1) {
        fractional_part = strArray[1]
    }
    var result = ""
    let rs = integer_part.toRuneArray()
    let product = rs.size / 3
    let surplus = rs.size % 3
    if( surplus != 0) {result = "${String(rs[..surplus])},"}
    for (i in 0..product - 1) {
        result += "${String(rs.slice(surplus + 3 * i, 3))},"
    }
    result += "${String(rs[rs.size - 3..])}"
    if (fractional_part != "") {result = "${result}.${fractional_part}"}
    result
}

main() {
    println(solution("1294512.12412") == '1,294,512.12412')
    println(solution("0000123456789.99") == '123,456,789.99')
    println(solution("987654321") == '987,654,321')
}

Iterator

import std.collection.*

func solution(s: String) {
    let strArray = s.trimStart("0").split(".")
    let integer_part = strArray[0]
    var fractional_part = ""
    if (strArray.size > 1) {
        fractional_part = strArray[1]
    }
    var result = ""
    let rs = integer_part.toRuneArray()
    let product = rs.size / 3
    let surplus = rs.size % 3
    //  The same as above...
    let it = rs.iterator()
    let takeString = {n => String(n |> it.take |> collectArray)}
    if (surplus != 0) { result = "${takeString(surplus)},"}
    for (_ in 0..product - 1) { result += "${takeString(3)},"}
    result += "${takeString(3)}"
    //  The same as above...
    if (fractional_part != "") {result = "${result}.${fractional_part}"}
    result
}

main() {
    println(solution("1294512.12412") == '1,294,512.12412')
    println(solution("0000123456789.99") == '123,456,789.99')
    println(solution("987654321") == '987,654,321')
}

ArrayList

import std.collection.*

func solution(s: String) {
    let strArray = s.trimStart("0").split(".")
    let integer_part = strArray[0]
    var fractional_part = ""
    if (strArray.size > 1) {
        fractional_part = strArray[1]
    }
    // The same as above...
    var result = ''
    var list = ArrayList(integer_part.toRuneArray())  
    while(list.size > 3 ){
        result = ",${String(list[list.size-3..])}" + result
        list = list[..list.size-3]
    }
    result = "${String(list)}${result}"
    // The same as above ...
    if (fractional_part != "") {
        result = "${result}.${fractional_part}"
    }
    result
}

main() {
    println(solution("1294512.12412") == '1,294,512.12412')
    println(solution("0000123456789.99") == '123,456,789.99')
    println(solution("987654321") == '987,654,321')
}

LinkedList

import std.collection.*

func solution(s: String) {
    let strArray = s.trimStart("0").split(".")
    let integer_part = strArray[0]
    var fractional_part = ""
    if (strArray.size > 1) { fractional_part = strArray[1] }
    //  The same code as before ...
    var offest = 0
    var result = ""
    let link = LinkedList(integer_part.toRuneArray())
    let iter = link.lastNode.getOrThrow() |> link.backward
    for (i in 0..link.size) {
        result = "${iter.next().getOrThrow()}${result}"
        if (i == link.size - 1) { break }
        offest ++
        if (offest == 3) {
            result = ",${result}"
            offest = 0
        }
    }
    // The same code as before ...
    if (fractional_part != "") {
        result = "${result}.${fractional_part}"
    }
    result
}

main() {
    println(solution("1294512.12412") == '1,294,512.12412')
    println(solution("0000123456789.99") == '123,456,789.99')
    println(solution("987654321") == '987,654,321')
}

Rust

fn solution(s: &str) -> String {
    let s = s.trim_start_matches('0');
    let parts: Vec<&str> = s.split('.').collect();
    let integer_part = parts[0];
    let fractional_part = parts.get(1).unwrap_or(&"").to_string();
    let mut result = String::new();
    let mut integer_part = integer_part.to_string();
    while integer_part.len() > 3 {
        result = format!(",{}", &integer_part[integer_part.len() - 3..]) + &result;
        integer_part = integer_part[..integer_part.len() - 3].to_string();
    }
    result = integer_part + &result;
    if !fractional_part.is_empty() {
        result += &format!(".{}", fractional_part);
    }
    result
}

 fn main() {
    println!("{}", solution("1294512.12412") == "1,294,512.12412");
    println!("{}", solution("0000123456789.99") == "123,456,789.99");
    println!("{}", solution("987654321") == "987,654,321");
 }

Python

def solution(s: str) -> str:
    s = s.lstrip('0')
    if '.' in s:
        integer_part, fractional_part = s.split('.')
    else:
        integer_part, fractional_part = s, ''
    if integer_part:
        integer_part = ''.join(reversed(integer_part))
        integer_part = ','.join(integer_part[i:i+3]
                                for i in range(0, len(integer_part), 3))
        integer_part = ''.join(reversed(integer_part))
    if fractional_part:
        return f"{integer_part}.{fractional_part}"
    else:
        return integer_part

print(solution("1294512.12412") == '1,294,512.12412')
print(solution("0000123456789.99") == '123,456,789.99')
print(solution("987654321") == '987,654,321')

JavaScript

function solution(s) {
    s = s.replace(/^0+/, '');
    let parts = s.split('.');
    let integer_part = parts[0];
    let fractional_part = parts[1] || '';
    let result = '';
    while (integer_part.length > 3) {
        result = ',' + integer_part.slice(-3) + result;
        integer_part = integer_part.slice(0, integer_part.length - 3);
    }
    result = integer_part + result;
    if (fractional_part) {
        result += '.' + fractional_part;
    }
    return result;
}

console.log(solution("1294512.12412") === '1,294,512.12412');
console.log(solution("0000123456789.99") === '123,456,789.99');
console.log(solution("987654321") === '987,654,321');

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。
• 空间复杂度：O(n)，其中 n 是字符串的长度。

数字分组求偶数和

问题描述

小M面对一组从 1 到 9 的数字，这些数字被分成多个小组，并从每个小组中选择一个数字组成一个新的数。目标是使得这个新数的各位数字之和为偶数。任务是计算出有多少种不同的分组和选择方法可以达到这一目标。

要求:

numbers: 一个由多个整数字符串组成的列表，每个字符串可以视为一个数字组。小M需要从每个数字组中选择一个数字。

例如: 对于 [123, 456, 789]，14 个符合条件的数为: 147 149 158 167 169 248 257 259 268 347 349 358 367 369。

测试样例

样例1：

输入：numbers = [123, 456, 789]
输出：14

样例2：

输入：numbers = [111, 222, 333]
输出：0

样例3：

输入：numbers = [123, 456, 789, 111, 222, 333]
输出：14

解题思路

1. 初始化一个变量 count，用于存储所有数字的和。初始值为 0。
2. 遍历数组中的每个数字，将其转换为字符串，并逐个字符地遍历。
3. 对于每个字符，将其转换为数字，并加到 count 中。
4. 最后，返回 count 的值。

代码实现

Cangjie

func solution(numbers: Array<Int64>) {
    var count = 0
    func backtrack(index: Int64, current_sum: Int64): Unit {
        if (index == numbers.size) {
            if (current_sum % 2 == 0) {
                count++
            }
            return;
        }
        let group = numbers[index].toString().toRuneArray()
        for (digit in group) {
            let selectedDigit = Int64(UInt32(digit) - 48)
            backtrack(index + 1, current_sum + selectedDigit)
        }
    }
    backtrack(0, 0)
    count
}

main() {
    println(solution([123, 456, 789]) == 14)
    println(solution([123456789]) == 4)
    println(solution([14329, 7568]) == 10)
}

Rust

fn solution(numbers: Vec<i32>) -> i32 {
    let mut count = 0;
    fn backtrack(index: usize, 
        current_sum: i32, 
        numbers: &Vec<i32>, 
        count: &mut i32) {
        if index == numbers.len() {
            if current_sum % 2 == 0 { *count += 1 }
            return;
        }
        let group = numbers[index].to_string();
        for digit in group.chars() {
            let digit = digit.to_digit(10).unwrap() as i32;
            backtrack(index + 1,
                current_sum + digit, 
                numbers, 
                count);
        }
    }
    backtrack(0, 0, &numbers, &mut count);
    count
}

 fn main() {
    println!("{}", solution(vec![123, 456, 789]) == 14);
    println!("{}", solution(vec![123456789]) == 4);
    println!("{}", solution(vec![14329, 7568]) == 10);
 }

Python

def solution(numbers):
    count = 0

    # back tracking function
    def backtrack(index, currentSum):
        if index == len(numbers):
            if currentSum % 2 == 0:
                nonlocal count
                count += 1
            return

        group = str(numbers[index])
        for digit in group:
            digit = int(digit)
            backtrack(index + 1, currentSum + digit)
    
    backtrack(0, 0)
    return count

print(solution([123, 456, 789]) == 14)
print(solution([123456789]) == 4)
print(solution([14329, 7568]) == 10)

JavaScript

function solution(numbers) {
    let count = 0;
    function backtrack(index, currentSum) {
        if (index === numbers.length) {
            if (currentSum % 2 === 0) {
                count++;
            }
            return;
        }
        const group = numbers[index].toString();
        for (const digit of group) {
            const selectedDigit = parseInt(digit);
            backtrack(index + 1, currentSum + selectedDigit);
        }
    }
    backtrack(0, 0);
    return count;
}

console.log(solution([123, 456, 789]) === 14);
console.log(solution([123456789]) === 4);
console.log(solution([14329, 7568]) === 10);

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

寻找最大葫芦

问题描述

在一场经典的德州扑克游戏中，有一种牌型叫做 葫芦。葫芦由五张牌组成， 其中包括三张相同牌面值的牌 a 和另外两张相同牌面值的牌 b。如果两个人同时拥有葫芦，我们会优先比较牌 a 的大小， 若牌 a 相同则再比较牌 b 的大小。

在这个问题中，我们对葫芦增加了一个限制：组成葫芦的五张牌牌面值之和不能超过给定的最大值 max。牌面值的大小规则为：A > K > Q > J > 10 > 9 > ... > 2，其中 A 的牌面值为1，K 为 13，依此类推。

要求：

给定一组牌，你需要找到符合规则的最大的葫芦组合，并输出其中三张相同的牌面和两张相同的牌面。如果找不到符合条件的葫芦，则输出 0, 0

测试样例

样例1:

输入: n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]
输出: [8, 5]

样例2:

输入: n = 9, max = 37, array = [9, 9, 9, 9, 6, 6, 6, 6, 13]
输出: [6, 9]

样例3:

输入: n = 9, max = 40, array = [1, 11, 13, 12, 7, 8, 11, 5, 6]
输出: [0, 0]

解题思路

• 首先，我们需要统计每张牌出现的次数，然后遍历所有可能的牌面值组合，找到符合条件的最大的葫芦组合。
• 遍历所有可能的牌面值组合，对于每种牌面值，我们需要判断该牌面值是否可以组成葫芦，以及组合后的牌面值之和是否小于等于给定的最大值。
• 如果可以组成葫芦，则更新最大葫芦组合。
• 最后，返回最大葫芦组合。

代码实现

Cangjie

import std.collection.*

func solution(n: Int64, max: Int64, array: Array<Int64>) {
    let rankOrder = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
    var cnts = HashMap<Int64,Int64>(13, {i => (rankOrder[i], 0)})
    for (num in array) { cnts[num] ++ }
    for (a in rankOrder) {
        if (cnts[a] >= 3) {
            for (b in rankOrder) {
                if (b == a) { continue }
                if (cnts[b] >= 2) {
                    let total = 3 * a + 2 * b;
                    if (total <= max) { return [a, b] }
                }
            } 
        }
    }
    [0, 0]
}

main() {
    println(solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1]) == [8, 5])
    println(solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13]) == [6, 9]);
    println(solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6]) == [0, 0]);
}

Rust

use std::collections::HashMap;

fn solution(_n: usize, max: i32, array: &[i32]) -> Vec<i32> {
    let rank_order = vec![1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2];
    let mut cnts = HashMap::new();
    for &num in array { *cnts.entry(num).or_insert(0) += 1 }
    for &a in &rank_order {
        if *cnts.get(&a).unwrap_or(&0) >= 3 {
            for &b in &rank_order {
                if b == a { continue }
                if *cnts.get(&b).unwrap_or(&0) >= 2 {
                    let total = 3 * a + 2 * b;
                    if total <= max { return vec![a, b] }
                }
            }
        }
    }
    vec![0, 0]
}

fn main() {
   println!("{:?}", solution(9, 34, &[6, 6, 6, 8, 8, 8, 5, 5, 1]) == vec![8, 5]);
   println!("{:?}", solution(9, 37, &[9, 9, 9, 9, 6, 6, 6, 6, 13]) == vec![6, 9]);
   println!("{:?}", solution(9, 40, &[1, 11, 13, 12, 7, 8, 11, 5, 6]) == vec![0, 0]);
}

Python

from collections import Counter

def solution(n, max, array):
    rank_order = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
    cnts = Counter(array)
    for a in rank_order:
        if cnts.get(a, 0) >= 3:
            for b in rank_order:
                if b == a:
                    continue
                if cnts.get(b, 0) >= 2:
                    total = 3 * a + 2 * b
                    if total <= max:
                        return [a, b]
    return [0, 0]

print(solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1]) == [8, 5])
print(solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13]) == [6, 9])
print(solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6]) == [0, 0])

JavaScript

function solution(n, max, array) {
    const rankOrder = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2];
    const cnts = array.reduce((acc, val) => {
        acc[val] = (acc[val] || 0) + 1;
        return acc;
    }, {});

    for (let a of rankOrder) {
        if (cnts[a] >= 3) {
            for (let b of rankOrder) {
                if (b === a) continue;
                if (cnts[b] >= 2) {
                    const total = 3 * a + 2 * b;
                    if (total <= max) {
                        return [a, b];
                    }
                }
            }
        }
    }
    return [0, 0];
}

console.log(JSON.stringify(solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1])) === JSON.stringify([8, 5]));
console.log(JSON.stringify(solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13])) === JSON.stringify([6, 9]));
console.log(JSON.stringify(solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6])) === JSON.stringify([0, 0]));

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是牌的数量。我们需要遍历所有可能的牌面值组合，对于每种牌面值，我们需要遍历所有可能的牌面值组合。
• 空间复杂度：O(n)，其中 n 是牌的数量。我们需要使用一个哈希表来统计每张牌出现的次数。

小E的怪物挑战

问题描述

小E在一个游戏中遇到了 n 个按顺序出现的怪物。每个怪物都有其特定的血量h[i]和攻击力a[i]。小E的初始血量为 H， 攻击力为 A。

游戏规则如下：

1. 小E可以击败血量和攻击力都小于她当前属性的怪物
2. 对于每只怪物，小E可以选择与它战斗或者跳过这只怪物
3. 为了保持战斗节奏，要求击败的怪物序列中，后一个怪物的血量和攻击力都必须严格大于前一个怪物

小E想知道，她最多能击败多少怪物。

1. 输入

   • n：怪物的数量
   • H：小E的血量
   • A：小E的攻击力
   • h[i]：第i个怪物的血量
   • a[i]：第i个怪物的攻击力

2. 输出

   • 返回小E最多能击败的怪物数量

3. 约束条件

   • 1 < n < 100
   • 1 < H, A, h[i], a[i] < 1000

测试样例

样例1:

• 输入：n = 3, H = 4, A = 5, h = [1, 2, 3], a = [3, 2, 1]
• 输出：1

样例2:

• 输入：n = 5, H = 10, A = 10, h = [6, 9, 12, 4, 7], a = [8, 9, 10, 2, 5]
• 输出：2

样例3:

• 输入：n = 4, H = 20, A = 25, h = [10, 15, 18, 22], a = [12, 18, 20, 26]
• 输出：3

样例4:

• 输入：n = 4, H = 20, A = 25, h = [22, 18, 15, 10], a = [26, 20, 18, 12]
• 输出：1

解题思路

1. 初始化：创建一个动态规划数组 dp，其中 dp[i] 表示以第 i 个怪物结尾的最长严格递增子序列的长度。
2. 状态转移：对于每个怪物 i，遍历之前的所有怪物 j，如果怪物 j 的血量和攻击力都小于怪物 i，则更新 dp[i]。
3. 结果：最终结果是 dp 数组中的最大值。

代码实现

Cangjie

func solution(
    n: Int64,
    H: Int64,
    A: Int64,
    h: Array<Int64>,
    a: Array<Int64>
) {
    var cnt = 0;
    let dp = Array<Int64>(n, repeat: 0);
    for (i in 0..n) {
        if (H > h[i] && A > a[i]) {
            dp[i] = 1
            for (j in 0..i) {
                if (h[j] < h[i] && a[j] < a[i]) {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
            cnt = max(dp[i], cnt)
        }
    }
    cnt
}

main(){
    println(solution(3, 4, 5, [1, 2, 3], [3, 2, 1]) == 1);
    println(solution(5, 10, 10, [6, 9, 12, 4, 7], [8, 9, 10, 2, 5]) == 2);
    println(solution(4, 20, 25, [10, 15, 18, 22], [12, 18, 20, 26]) == 3);
}

Rust

fn solution(
    n: i32, 
    h: i32, 
    a: i32, 
    heights: Vec<i32>, 
    ages: Vec<i32>
) -> i32 {
    let mut cnt = 0;
    let mut dp = vec![0; n as usize];
    for i in 0..n {
        if h > heights[i as usize] && a > ages[i as usize] {
            dp[i as usize] = 1;
            for j in 0..i {
                if heights[j as usize] < heights[i as usize] 
                    && ages[j as usize] < ages[i as usize] {
                    dp[i as usize] = dp[i as usize].max(dp[j as usize] + 1);
                }
            }
            cnt = cnt.max(dp[i as usize]);
        }
    }
    cnt
}

fn main() {
   println!("{}", solution(3, 4, 5, vec![1, 2, 3], vec![3, 2, 1]) == 1);
   println!("{}", solution(5, 10, 10, vec![6, 9, 12, 4, 7], vec![8, 9, 10, 2, 5]) == 2);
   println!("{}", solution(4, 20, 25, vec![10, 15, 18, 22], vec![12, 18, 20, 26]) == 3);
}

Python

def solution(n: int, H: int, A: int, h: list, a: list) -> int:
    cnt = 0
    dp = {}
    for i in range(n):
        if H > h[i] and A > a[i]:
            dp[i] = 1
            for j in range(i):
                if h[j] < h[i] and a[j] < a[i]:
                    dp[i] = max(dp[i], dp[j]+1)

            cnt = max(dp[i], cnt)

    return cnt

print(solution(3, 4, 5, [1, 2, 3], [3, 2, 1]) == 1)
print(solution(5, 10, 10, [6, 9, 12, 4, 7], [8, 9, 10, 2, 5]) == 2)
print(solution(4, 20, 25, [10, 15, 18, 22], [12, 18, 20, 26]) == 3)

JavaScript

function solution(n, H, A, h, a) {
    let cnt = 0;
    let dp = {};
    for (let i = 0; i < n; i++) {
        if (H > h[i] && A > a[i]) {
            dp[i] = 1;
            for (let j = 0; j < i; j++) {
                if (h[j] < h[i] && a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            cnt = Math.max(dp[i], cnt);
        }
    }
    return cnt;
}

console.log(solution(3, 4, 5, [1, 2, 3], [3, 2, 1]) === 1);
console.log(solution(5, 10, 10, [6, 9, 12, 4, 7], [8, 9, 10, 2, 5]) === 2);
console.log(solution(4, 20, 25, [10, 15, 18, 22], [12, 18, 20, 26]) === 3);

复杂度分析

• 时间复杂度：O(n^2)，其中 n 为数组的长度。
• 空间复杂度：O(n)，其中 n为数组的长度。

创意标题匹配问题

问题描述

在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的 bidword 对创意中的通配符（通配符是用成对 {} 括起来的字符串，可以包含 0 个或者多个字符）进行替换，用来提升广告投放体验。例如：“{末日血战} 上线送 SSR 英雄，三天集齐无敌阵容！”，会被替换成 “帝国时代游戏下载上线送 SSR 英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和n个标题，判断这句标题是否从该创意替换生成的。

测试样例

样例 1：

输入：n = 4, template = "ad{xyz}cdc{y}f{x}e", titles = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
输出："True,False,False,True"

样例 2：

输入：n = 3, template = "a{bdc}efg", titles = ["abcdefg", "abefg", "efg"]
输出："True,True,False"

样例 3：

输入：n = 5, template = "{abc}xyz{def}", titles = ["xyzdef", "abcdef", "abxyzdef", "xyz", "abxyz"]
输出："True,False,True,True,True"

解题思路

1. 首先使用正则表达式将模板中的通配符替换为 .*，用来匹配任意字符。
2. 遍历标题列表，对每个标题使用正则表达式进行匹配。
3. 如果匹配成功，并且匹配的结束位置是标题的末尾，则说明该标题是由模板替换生成的，将结果设为 True，否则设为 False。
4. 将所有结果拼接成一个字符串，以逗号分隔，作为最终输出。

代码实现

Cangjie

import std.regex.*

func solution(n: Int64, template: String, titles: Array<String>){
    let pattern = Regex("{.*?}").matcher(template).replaceAll(".*")
    let results = Array<String>(n, repeat: "False")
    for (i in 0..n) {
        let matchData = Regex(pattern).matches(titles[i])
        ifSome(matchData){ _ => results[i] = "True" }
    }
    String.join(results, delimiter: ",")
}

main() {
    let testTitles1 = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
    let testTitles2 = [
        "CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj",
        "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", 
        "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"
    ]
    let testTitles3 = ["abcdefg", "abefg", "efg"]

    println(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1) == "True,False,False,True" )
    println(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2) == 
        "False,False,False,False,False,True" )
    println(solution(3, "a{bdc}efg", testTitles3) == "True,True,False" )
}

Rust

 extern crate regex;
 use regex::Regex;

fn solution(_n: usize, template_: &str, titles: Vec<&str>) -> String {
    let regex_template = Regex::new(r"\{.*?\}").unwrap()
        .replace_all(template_, ".*?") + "$";
    let re = Regex::new(&regex_template).unwrap();
    let mut results = Vec::new();
    for title in titles {
        let match_result = re.is_match(title);
        if match_result { results.push("True") }
        else { results.push("False") }
    }
    results.join(",")
}

 fn main() {
   let test_titles1 = vec![
        "adcdcefdfeffe", "adcdcefdfeff", 
        "dcdcefdfeffe", "adcdcfe"
    ];
    let test_titles2 = vec![
        "CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj",
        "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj",
        "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx",
    ];
    let test_titles3 = vec!["abcdefg", "abefg", "efg"];

    println!("{}", solution(4, "ad{xyz}cdc{y}f{x}e", test_titles1) ==
        "True,False,False,True");
    println!("{}", solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", 
        test_titles2) == "False,False,False,False,False,True"
    );
    println!("{}", solution(3, "a{bdc}efg", test_titles3) ==
        "True,True,False");
 }

python

import re
def solution(n, template_, titles):
    pattern = re.sub(r'\{.*?\}', '.*?', template_)
    regex = re.compile(pattern)
    results = []
    for title in titles:
        if regex.fullmatch(title):
            results.append("True")
        else:
            results.append("False")
    return ",".join(results)

testTitles1 = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
testTitles2 = [
    "CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", 
    "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", 
    "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"
]
testTitles3 = ["abcdefg", "abefg", "efg"]

print(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1) == "True,False,False,True" )
print(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2) == 
    "False,False,False,False,False,True" )
print(solution(3, "a{bdc}efg", testTitles3) == "True,True,False" )

JavaScript

function solution(n, template_, titles) {
    let pattern = template_.replace(/{.*?}/g, '.*?');
    let regex = new RegExp(`^${pattern}$`);
    let results = [];
    for (let title of titles) {
        if (regex.test(title)) {
            results.push("True");
        } else {
            results.push("False");
        }
    }
    return results.join(",");
}

const testTitles1 = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"];
const testTitles2 = [
    "CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", 
    "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", 
    "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"
];
const testTitles3 = ["abcdefg", "abefg", "efg"];

console.log(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1) === 
    "True,False,False,True");
console.log(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2) === 
    "False,False,False,False,False,True");
console.log(solution(3, "a{bdc}efg", testTitles3) === "True,True,False");

复杂度分析

• 时间复杂度：O(n)，其中 n 是标题的数量。对于每个标题，我们需要进行一次正则表达式匹配，时间复杂度为 O(m)，其中 m 是标题的长度。因此总时间复杂度为 O(nm)。
• 空间复杂度：O(n)，其中 n 是标题的数量。我们需要一个列表来存储每个标题的匹配结果，列表的大小为 n。

找出整型数组占比超过一半的数

题目描述

小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

测试样例

样例1：

输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出：3

样例2：

输入：array = [5, 5, 5, 1, 2, 5, 5]
输出：5

样例3：

输入：array = [9, 9, 9, 9, 8, 9, 8, 8]
输出：9

解题思路

1. 初始化哈希表：创建一个空的字典来存储每个数字及其出现次数。
   
2. 遍历数组：对于数组中的每个数字，更新哈希表中该数字的出现次数。
   
3. 查找目标数字：遍历哈希表，找到出现次数超过数组长度一半的数字。
   
4. 返回结果：返回找到的数字。

代码实现

Cangjie

import std.collection.*

func solution(array: Array<Int64>) {
    let size = array.size
    var map = HashMap<Int64, Int64>(size, {i => (array[i], 0)})
    for(num in array) { map[num]++ }
    for((num, count) in map ) {
        if( count > size / 2) { return num }
    }
    0
}

main() {
    println(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)
}

• 摩尔投票算法 (Boyer–Moore majority vote)

import std.collection.*

// Boyer–Moore majority vote
func solution(array: Array<Int64>) {
    var (candidate, count) = (0, 0)
    let map = HashMap<Int64, Int64>(array.size, {i => (array[i], 0)})
    for (num in array) {
        match {
            case count == 0 => (candidate, count) = (num, 1)
            case candidate == num => count++
            case _ => count--
        }
        map[num]++
    }
    if (map[candidate] > array.size / 2) { candidate }
    else { 0 }
}

main() {
    println(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)
}

Rust

 use std::collections::HashMap;

fn solution(array: Vec<i64>) -> i64 {
    let size = array.len();
    let mut map = HashMap::new();
    for num in array {
        *map.entry(num).or_insert(0) += 1;
    }
    for (num, count) in map {
        if count > size / 2 {
            return num;
        }
    }
    0
}

 fn main() {
    println!("{}", solution(vec![1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3);
 }

Python

def solution(array):
    size = len(array)
    map = {}
    for num in array:
        map[num] = map.get(num, 0) + 1
    for num, count in map.items():
        if count > size / 2:
            return num
    return 0

print(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)

JavaScript

function solution(array) {
    const size = array.length;
    const map = {};
    for (let num of array) {
        map[num] = (map[num] || 0) + 1;
    }
    for (let [num, count] of Object.entries(map)) {
        if (count > size / 2) {
            return num;
        }
    }
    return 0;
}

console.log(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3);

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组一次来统计每个数字的出现次数。
  
• 空间复杂度：O(n)，其中 n 是数组的长度。需要使用哈希表来存储每个数字及其出现次数。

观光景点组合得分问题

问题描述

小R正在研究一组观光景点，每个景点都有一个评分，保存在数组 values 中，其中 values[i] 表示第 i 个观光景点的评分。同时，景点之间的距离由它们的下标差 j - i 表示。一对景点 (i < j) 的观光组合得分为 values[i] + values[j] + i - j，也就是两者评分之和减去它们之间的距离。

小R想知道，在哪种情况下能够获得观光景点组合的最高得分。

约束条件:

• 2 <= values.length
• 1 <= values[i] <= 1000

测试样例

样例1：

输入：values = [8, 3, 5, 5, 6]
输出：11

样例2：

输入：values = [10, 4, 8, 7]
输出：16

样例3：

输入：values = [1, 2, 3, 4, 5]
输出：8

解题思路

1. 将每个景点的得分视为 values[i] + i，我们称之为 score_i。
2. 将每个景点的得分视为 values[j] - j，我们称之为 score_j。
3. 我们的目标是：最大化 score_i + score_j，其中 i < j。

代码实现

Cangjie

func solution(values: Array<Int64>) {
    var max_score = 0
    // let score_i = values[i] + i
    var max_value = values[0] + 0
    for (j in 1..values.size) {
        let score_j = values[j] - j
        max_score = max(max_score, max_value + score_j)
        max_value = max(max_value, values[j] + j)
    }
    max_score
}

main() {
    println(solution([8, 3, 5, 5, 6]) == 11)
    println(solution([10, 4, 8, 7]) == 16)
    println(solution([1, 2, 3, 4, 5]) == 8)
}

Rust

fn solution(values: Vec<i32>) -> i32 {
    let mut max_score = 0;
    let mut max_value = values[0] + 0;
    for j in 1..values.len() {
        let score_j = values[j] - j as i32;
        max_score = max_score.max(max_value + score_j);
        max_value = max_value.max(values[j] + j as i32);
    }
    max_score
}

 fn main() {
    println!("{}", solution(vec![8, 3, 5, 5, 6]) == 11);
    println!("{}", solution(vec![10, 4, 8, 7]) == 16);
    println!("{}", solution(vec![1, 2, 3, 4, 5]) == 8);
 }

Python

def solution(values):
    max_score = 0
    # 第一个景点的得分是 values[0] + 0
    max_value = values[0] + 0
    for j in range(1, len(values)):
        score_j = values[j] - j
        max_score = max(max_score, max_value + score_j)
        max_value = max(max_value, values[j] + j)
    return max_score

print(solution([8, 3, 5, 5, 6]) == 11)
print(solution([10, 4, 8, 7]) == 16)
print(solution([1, 2, 3, 4, 5]) == 8)

JavaScript

function solution(values) {
    let max_score = 0;
    let max_value = values[0] + 0;   
    for (let j = 1; j < values.length; ++j) {
        let score_j = values[j] - j;
        max_score = Math.max(max_score, max_value + score_j);
        max_value = Math.max(max_value, values[j] + j);
    }
    return max_score;
}

console.log(solution([8, 3, 5, 5, 6]) === 11 );
console.log(solution([10, 4, 8, 7]) === 16 );
console.log(solution([1, 2, 3, 4, 5]) === 8 );

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 values 的长度。我们只需要遍历一次数组。
• 空间复杂度：O(1)，我们只需要常数级别的额外空间。

mdbook code block

代码段cangjie可以直接运行仓颉代码

main() {
println("你好，仓颉!")
}

使用cangjie, no_run 隐藏运行图标

class List<T> {
    var elem: Option<T> = None
    var tail: Option<List<T>> = None
}

func sumInt(a: List<Int64>) {  }

rust 代码

 fn main() {
println!("Hello, world!");
 }

JavaScript 代码

console.log("Hello Javascript!")

Python 代码

print("Hello Python!")