小编Ban*_*non的帖子

高效的字符串截断算法,顺序去除相等的前缀和后缀

每个测试的时间限制:5 秒
每个测试的内存限制:512 MB

给定一个s长度为n( n? 5000) 的字符串。您可以选择该字符串的任何适当的前缀(也是其后缀),并删除选定的前缀或相应的后缀。然后,您可以对结果字符串应用类似的操作,依此类推。应用此类操作的最佳序列后,最终字符串的最小长度是多少?

输入
每个测试的第一行包含一个s由小英文字母组成的字符串。

输出
输出单个整数 — 最终字符串的最小长度,在应用此类操作的最佳序列后可以实现。

例子 +-------+--------+----------------------------------+ | Input | Output | Explanation | +-------+--------+----------------------------------+ | caaca | 2 | caaca ? ca|aca ? aca ? ac|a ? ac | +-------+--------+----------------------------------+ | aabaa | 2 | aaba|a ? a|aba ? ab|a ? ab | +-------+--------+----------------------------------+ | abc | 3 | No operations are possible | +-------+--------+----------------------------------+

这是我到目前为止所做的:

  1. 在O(n^2)内计算给定字符串的所有子字符串的前缀函数

  2. 检查在O(n^3)内执行所有可能的运算组合的结果

我的解决方案通过了所有测试n …

c++ string algorithm optimization performance

12
推荐指数
1
解决办法
805
查看次数

为什么使用ListList <?超级E>是List <?扩展List <?超级E >>,但不是List <List <?超级E >>

我有一个通用接口interface ListList<E> extends List<List<E>>。由于某些原因,我无法转换ListList<? super T>List<List<? super T>>。有什么办法可以做到,为什么不起作用?

至此,我已经尝试了以下方法:

  1. 简单分配,通过这种方式,我设法分配ListList<? super T>List<? extends List<? super T>>(1),但是当我尝试分配ListList<? super T>List<List<? super T>>Incompatible types时,出现编译时错误(1.1)。
  2. 显式类型转换,由于相同的Incompatible types编译时错误(2),它不起作用。
  3. 强制转换为原始类型ListList,它可以正常工作(3),但我不喜欢原始类型。
  4. 将所有元素从添加ListList<? super T>到中List<? extends List<? super T>>,它可以正常工作(4),但是我需要一个更通用的解决方案,该解决方案不仅适用于ListList<E>,而且适用于任何通用类型。

这是我的代码:

ListList<? super T> var = new ArrayListList<>();
List<? extends List<? super T>> work = var; // (1)
List<List<? super T>> notWork = …
Run Code Online (Sandbox Code Playgroud)

java generics casting wildcard lower-bound

6
推荐指数
1
解决办法
139
查看次数

如何通过合同强制客户端代码初始化Kotlin中所有必需的构建器字段?

据说在2019年的JetBrains开放日,Kotlin团队研究了合同并试图实现上下文合同,该合同仅允许在某些情况下调用函数,例如,build仅在setName方法调用前被调用了一次的情况下才允许调用函数。是一段谈话录音。

我尝试使用当前可用的Kotlin功能模拟此类合同,以为创建null安全构建器data class Person(val name: String, val age: Int)

注意:当然,在这种情况下,使用命名参数而不是生成器模式要容易得多,但是命名参数不允许将未完全构建的对象解析为其他函数,并且在创建时很难使用它们由其他复杂对象等组成的复杂对象。

所以这是我的null安全构建器实现:

基于通用标志的构建器

sealed class Flag {
    object ON : Flag()
    object OFF : Flag()
}

class PersonBuilder<NAME : Flag, AGE : Flag> private constructor() {
    var _name: String? = null
    var _age: Int? = null

    companion object {
        operator fun invoke() = PersonBuilder<OFF, OFF>()
    }
}

val PersonBuilder<ON, *>.name get() = _name!!
val PersonBuilder<*, ON>.age get() = _age!!

fun <AGE …
Run Code Online (Sandbox Code Playgroud)

generics type-inference contract kotlin

5
推荐指数
1
解决办法
91
查看次数