阅读 25

LeetCode之Circular Permutation in Binary Representation(Kotlin)

问题:


方法: 这题可以通过循环码生成去做,但是需要了解循环码生成理论。本解法没有使用其他多余知识,只是利用染色法记录是否经过,然后通过位操作异或去改变某一位并加入list,且跳过已经添加的元素,最后输出list即可。

class CircularPermutationInBinaryRepresentation {
    fun circularPermutation(n: Int, start: Int): List<Int> {
        val vis = BooleanArray((1).shl(n)) { // 2^n
            false
        }
        val ans = mutableListOf<Int>()
        ans.add(start)
        vis[start] = true
        var cur = start
        for (i in 0 until (1).shl(n)) { // 2^n
            for (j in 0 until n) {
                val t = cur.xor((1).shl(j))
                if (!vis[t]) {
                    cur = t
                    vis[t] = true
                    ans.add(cur)
                    break
                }
            }
        }
        return ans
    }
}

fun main(args: Array<String>) {
    val circularPermutationInBinaryRepresentation = CircularPermutationInBinaryRepresentation()
    CommonUtils.printArray(circularPermutationInBinaryRepresentation.circularPermutation(3, 2).toTypedArray())
}
复制代码

有问题随时沟通

具体代码实现可以参考Github