我知道我们可以通过中序和（后序或前序）遍历重建二叉树。
然而，我想知道从后序和前序遍历重建它是否也可行？
在经典的子集和问题中，存在一个集合 S 和一个目标 t，目标是找到 S 的一个子集，其和为 t。该变体具有伪多项式时间解。
在子集和问题的一个变体中，目标是找到 S 中所有和为 t 的子集。此变体没有伪多项式时间解；请参阅此处的答案：使用动态规划在 Python 上从子集和问题中获取所有子集。其中一条评论解释说，在最坏的情况下，当你有 N 个零，并且所需的和也为零时，你将需要输出所有 2^n - 1 个子集——因此不可能比 O(2^n) 更优。
如果我们不区分两个具有相同值的项目（例如，如果两个集合由一些具有相同值的项目组成，则它们被视为同一集合）——输出总和为 t 的所有不同子集的运行时复杂度是多少？
你好，我尝试解决下面这个问题已经 5 个小时了，但还是没找到答案。这个问题的标题是“线性排序”，所以我假设最优答案的时间复杂度应该是 O(n)。问题如下。
=======================================================
假设你有一个包含 n 个整数的数组，最初按升序排列。但是，数组中元素对之间最多进行了⌊√n/2⌋次任意交换。因此，最多有 √n 个元素可能偏离了正确的位置。你必须使用时间复杂度尽可能低的算法将此数组重新排序为升序。
=======================================================
目前我发现，如果能在 O(n) 的时间复杂度内找出哪些元素位置不对，那么排序本身也应该花费 O(n)。不过我现在也不知道该怎么办了 :(
算法线性排序(A):
n ← length(A)
misplacedIndices ← empty set
// Step 1: Identify indices of potentially misplaced elements
misplacedIndices.add(i) // Do this somehow(!!!!)
// sort indices in ascending order -> takes O(√n · log(√n))
misplacedIndices ← sorted(misplacedIndices)
// Step 2: Separate misplaced elements from correctly placed ones
misplacedList ← empty list
remainderList ← empty list
for i ← 0 to n - 1 do:
if i ∈ misplacedIndices then:
misplacedList.append(A[i])
else:
remainderList.append(A[i])
end for
// Sort the misplaced elements (only up to O(√n) elements)
sort(misplacedList) // Time complexity: O(√n · log√n)
// Step 3: Merge the two sorted lists (remainderList and misplacedList)
result ← empty list
i ← 0, j ← 0
while i < length(remainderList) and j < length(misplacedList) do:
if remainderList[i] ≤ misplacedList[j] then:
result.append(remainderList[i])
i ← i + 1
else:
result.append(misplacedList[j])
j ← j + 1
end while
// Append any remaining elements from either list
while i < length(remainderList) do:
result.append(remainderList[i])
i ← i + 1
end while
while j < length(misplacedList) do:
result.append(misplacedList[j])
j ← j + 1
end while
return result
检查维基百科页面上有关插入排序的伪代码：
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end while
请说明为什么文献中这样说：
The number of exchanges used by insertion sort is equal to the number of
inversions in the array, and the number of compares is at least equal to
the number of inversions and at most equal to the number of inversions
plus the array size minus 1.
一次相邻元素交换（即“当前选定元素”与已排序子数组中的元素（即从原始数组的左端开始））只会删除一次反转。
但是对于给定的元素列表，引入一次交换可以添加许多反转；假设列表：123，通过将元素3与元素交换1，会引入3反转。
所需的比较次数为三次：
i=1:<2,3>, i=2:<1,3>, <1,2>
此外，列表中反转的次数为三次：321
这个反转次数也是由给出的nC2，其中n是列表大小。
假设，对于大小为 的反向排序列表4: 4321，有六个反转：<4,3>,<4,2>,<4,1>,<3,2>,<3,1>,<2,1>，这也是 n 集的 2 子集的数量。在这两个问题中，由于不涉及排序，有 需要计算的组合数。
插入排序对反向排序列表的应用所涉及的步骤（比较+交换）<4321>如下：
1. i ← 1, j ← 1, A[0] > A[1]: swap A[1] and A[0], j ← 0: <3421>
2. i ← 2, j ← 2, A[1] > A[2]: swap A[2] and A[1], j ← 1: <3241>
j ← 1, A[0] > A[1]: swap A[1] and A[0], j ← 0: <2341>
3. i ← 3, j ← 3, A[2] > A[3]: swap A[3] and A[2], j ← 2: <2314>
j ← 2, A[1] > A[2]: swap A[2] and A[1], j ← 1: <2134>
j ← 1, A[0] > A[1]: swap A[1] and A[0], j ← 0: <1234>
但是，无法理解何时最大比较次数等于number of inversions + array size -1；至于大小为的反向排序数组的最坏情况n；反转次数等于nC2。
其余的比较从何而来，即'n-1'比较？
上面提到的文献指出这些'n-1'比较的来源是：
additional compare might happen for the value of `i` from `1` to `n-1` (when `a[i]` does not reach the left end of the array).
括号中的部分引起了混淆；其含义如下：(when a[i] does not reach the left end of the array).
这种情况可能意味着列表的情况，其中“第一个元素”(i=0)位于其最终位置，例如：1423。或者换句话说，它是否谈论all the possible比较，包括存在no反转的比较。
假设，对于1423，有两个反转，但需要进行额外的比较：<1,4>, <1,2>, <1,3>, <2,3>。但是，这些是四次比较，而不是三次（数组大小：4 减 1）。
也不清楚文献中使用的措辞，因为算法中没有明确显示这样的比较。
同一文献在此处列出了用于插入排序的 C++ 代码，但也没有明确显示任何此类比较。
新的代码生成工具仅接受一个输入 -n即输入数组的大小。然后，该工具应生成一个包含两种节点的简单决策树程序：
- 严格比较的决策节点
- 输出节点（叶）
决策节点使用 3 个运算符中的 1 个来比较输入数组中的两个元素 - <, =, >。不允许使用这些运算符的组合。也不允许使用额外的布尔运算符，例如 NOT、AND、OR。
输出节点指定从输入数组返回哪些元素。这些元素应全部具有相同的值，并且该值是整个输入数组的最小值。
到目前为止，我尝试使用基于堆栈的方法，该方法为长度为 2 的输入数组生成正确的代码，但对于每个更大的长度都会失败。输出如下所示：
if input[0] < input[1]:
return input[0]
else:
if input[0] == input[1]:
return input[0, 1]
else:
return input[1]
这是我的代码：
Node.kt
import ComparisonOperator.*
enum class ComparisonOperator {
LESS_THAN, EQUALS, GREATER_THAN
}
class Node (
val trueBranch: Node? = null,
val falseBranch: Node? = null,
val operator: ComparisonOperator = LESS_THAN,
val indices: IntArray = intArrayOf()
)
打印.kt
import TaskType.*
enum class TaskType {
PROCESS_NODE,
PROCESS_ELSE
}
data class StackEntry(val node: Node, val indent: Int, val taskType: TaskType)
fun generatePythonCode(root: Node): String {
val builder = StringBuilder()
val stack = ArrayDeque<StackEntry>()
stack.addLast(StackEntry(root, 0, PROCESS_NODE))
while (stack.isNotEmpty()) {
val entry = stack.removeLast()
val node = entry.node
val indent = entry.indent
val indentStr = " ".repeat(indent)
when (entry.taskType) {
PROCESS_NODE -> {
if (node.trueBranch == null) {
// Leaf node: output the return statement.
val indices = node.indices.joinToString(", ")
builder.append(indentStr).append("return input[").append(indices).append("]\n")
} else {
// Decision node: output an if statement.
val left = "input[${node.indices[0]}]"
val right = "input[${node.indices[1]}]"
val op = when (node.operator) {
ComparisonOperator.LESS_THAN -> "<"
ComparisonOperator.EQUALS -> "=="
ComparisonOperator.GREATER_THAN -> ">"
}
builder.append(indentStr).append("if ").append(left).append(" $op ").append(right).append(":\n")
// Push the false branch as an else task (it will add the "else:" line).
stack.addLast(StackEntry(node.falseBranch!!, indent, PROCESS_ELSE))
// Then push the true branch for processing with increased indent.
stack.addLast(StackEntry(node.trueBranch, indent + 1, PROCESS_NODE))
}
}
PROCESS_ELSE -> {
// For an else task, output the "else:" line and then process the node.
builder.append(indentStr).append("else:\n")
stack.addLast(StackEntry(node, indent + 1, PROCESS_NODE))
}
}
}
return builder.toString().trimEnd()
}
代码生成
import ComparisonOperator.*
enum class FrameType {
EQUALITY,
MERGE
}
// Each frame holds the current candidate groups (each a List<Int>).
// When the number of candidate groups is 1, a leaf (output) node is produced.
// Otherwise, two candidate groups are extracted and processed.
data class Frame(
val candidates: List<List<Int>>,
val type: FrameType,
var step: Int = 0,
var group1: List<Int>? = null,
var group2: List<Int>? = null,
var rest: List<List<Int>> = emptyList(),
// For a MERGE frame, we need:
// branchTrue: result for candidate list [group1] + rest.
// branchEquality (i.e. the nested equality decision) will be built from two subbranches.
// For an EQUALITY frame, we only need branchTrue and branchFalse.
var branchTrue: Node? = null,
var branchFalse: Node? = null,
// Temporary field to hold a generated child result.
var tempResult: Node? = null
)
// The function generateMinProgram builds the decision tree (as Node objects) that, when interpreted,
// returns the indices of all occurrences of the minimum element from the input array.
// It uses a brute-force backtracking strategy based on a stack.
fun generateMinProgram(n: Int): Node {
// Assume n >= 2. Initially, each candidate group is a single index.
val initialCandidates = (0 until n).map { listOf(it) }
val stack = ArrayDeque<Frame>()
// The outermost decision is always a MERGE.
stack.add(Frame(candidates = initialCandidates, type = FrameType.MERGE))
// The iterative DFS: process the frames until the root decision is built.
var result: Node? = null
while (stack.isNotEmpty()) {
val current = stack.last()
// If the candidate list has only one candidate group, create a leaf (output) node.
if (current.candidates.size == 1) {
// This candidate group represents the indices that are equal to the minimum.
result = Node(
trueBranch = null,
falseBranch = null,
// For output nodes the operator value is not used.
operator = LESS_THAN,
indices = current.candidates.first().toIntArray()
)
stack.removeLast()
if (stack.isNotEmpty()) {
// Propagate the result to the parent frame.
stack.last().tempResult = result
} else {
// No parent exists; this would happen if n==1 (but we assume n>=2).
return result
}
continue
}
// Otherwise, there is at least a decision to be made.
when (current.type) {
FrameType.MERGE -> {
// MERGE frame has three main phases.
when (current.step) {
0 -> {
// Initialize: pick the first two candidate groups.
current.group1 = current.candidates[0]
current.group2 = current.candidates[1]
current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
// Process the "true" branch for the primary decision:
// if input[group1[0]] < input[group2[0]] then the winner is group1.
val trueCandidates = listOf(current.group1!!) + current.rest
// New frame for processing the "true" branch.
stack.add(Frame(candidates = trueCandidates, type = FrameType.MERGE))
current.step = 1
}
1 -> {
// Coming back from the "true" branch.
current.branchTrue = current.tempResult
current.tempResult = null
// Next, process the nested equality decision.
// Create a new EQUALITY frame.
// For equality: if input[group1[0]] == input[group2[0]], then we merge group1 and group2.
// The candidate list becomes [group1 U group2] + rest.
val merged = current.group1!! + current.group2!!
val eqCandidates = listOf(merged) + current.rest
stack.add(Frame(candidates = eqCandidates, type = FrameType.EQUALITY))
current.step = 2
}
2 -> {
// Returning from the equality branch's "true" part (for the equality decision).
// In a MERGE frame, we now go to process the "false" branch of the nested equality:
current.branchTrue = current.branchTrue // holds nothing new; we now reuse the equality structure.
// For the "false" branch of the equality decision (i.e. when input[group1[0]] is not equal to input[group2[0]])
// we take group2 as the winner. Candidate list becomes [group2] + rest.
val falseCandidates = listOf(current.group2!!) + current.rest
stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
current.step = 3
}
3 -> {
// Coming back from the equality frame "false" branch.
current.branchFalse = current.tempResult
current.tempResult = null
// Build the nested equality decision node.
// This node has operator EQUALS and compares the same indices from group1 and group2.
val eqNode = Node(
trueBranch = current.tempResult ?: run {
// The true branch result is already stored in branch from the equality frame "true",
// which was set when processing the equality frame. In this MERGE frame, we expect the equality
// decision to have been constructed by processing the two equality branches.
// Here we use current.branchTrue that was computed in step 2.
current.branchTrue
},
falseBranch = current.branchFalse,
operator = EQUALS,
indices = intArrayOf(current.group1!![0], current.group2!![0])
)
// Build the primary decision node.
val mergeNode = Node(
trueBranch = current.branchTrue,
falseBranch = eqNode,
operator = LESS_THAN,
indices = intArrayOf(current.group1!![0], current.group2!![0])
)
stack.removeLast() // Done with current MERGE frame.
if (stack.isNotEmpty()) {
stack.last().tempResult = mergeNode
} else {
return mergeNode
}
}
}
}
FrameType.EQUALITY -> {
// EQUALITY frame has two phases.
when (current.step) {
0 -> {
// In an EQUALITY frame the comparison is always on the two groups that formed the candidate list.
// Since we always pass a candidate list with at least one candidate, if there are at least two,
// then we perform a decision test.
current.group1 = current.candidates[0]
current.group2 = current.candidates[0] // In an equality frame candidate list is built from either merged groups or single group2.
// For an EQUALITY frame, if there is more than one candidate group then we consider the first two.
// However, in our usages we've built the candidate list so that its size should be 1.
// To support a generic approach we check:
if (current.candidates.size >= 2) {
current.group2 = current.candidates[1]
current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
} else {
// If candidate list size is 1, then we are at a leaf even in an equality frame.
val leaf = Node(
trueBranch = null,
falseBranch = null,
operator = EQUALS,
indices = current.candidates.first().toIntArray()
)
stack.removeLast()
if (stack.isNotEmpty()) {
stack.last().tempResult = leaf
} else {
return leaf
}
continue
}
// Process the "true" branch of the equality decision:
// If input[group1[0]] == input[group2[0]], then the result candidate list remains as-is.
// (In our usage, for the equality branch, candidate list is already merged.)
val trueCandidates = current.candidates
stack.add(Frame(candidates = trueCandidates, type = FrameType.EQUALITY))
current.step = 1
}
1 -> {
// Return from the "true" branch.
current.branchTrue = current.tempResult
current.tempResult = null
// Process the "false" branch:
// In our usage, the "false" branch for an EQUALITY decision comes from a candidate list built for group2.
// We expect that candidate list to have a single candidate group.
val falseCandidates = if (current.candidates.size >= 2) {
// Use the second candidate alone alongside any remaining candidates.
listOf(current.candidates[1]) + current.rest
} else {
current.candidates
}
stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
current.step = 2
}
2 -> {
// Return from the "false" branch.
current.branchFalse = current.tempResult
current.tempResult = null
// Build the equality decision node.
val eqNode = Node(
trueBranch = current.branchTrue,
falseBranch = current.branchFalse,
operator = EQUALS,
indices = intArrayOf(current.candidates[0][0], if (current.candidates.size >= 2) current.candidates[1][0] else current.candidates[0][0])
)
stack.removeLast()
if (stack.isNotEmpty()) {
stack.last().tempResult = eqNode
} else {
return eqNode
}
}
}
}
}
}
// Should never reach here.
return result!!
}
主页.kt
fun main() {
val root = generateMinProgram(2)
val code = generatePythonCode(root)
println(code)
}
我不会要求你修复我的代码。相反，我正在寻找一种高级算法及其数据结构的描述。也许回溯解决方案就足够了？
这也是一个 XY 问题，因为我真正需要的是对这个问题的答案：我们如何推导出数组“最小值查找”中最小严格决策节点的公式？该问题的浏览量不多，因此我尝试通过强制执行代码生成步骤来找出公式。
我正在研究一个优化问题，即找到一个最大化某个目标函数的区域，我使用一组像素坐标来跟踪该区域，并且每一步我都会在边界处添加或删除一个像素，以查看目标函数是否增加。我希望该区域是连通的，是否有任何数据结构可以快速决定删除一个像素是否会使该区域断开连接？这里我们假设一个像素与其四个邻居相连。
还有一个类似的问题：如果我希望该区域始终是单连通的，该怎么办？单连通的意思是没有洞，而添加一个像素可能会产生一个洞。
我正在寻找具有以下几个属性的寻路算法：
- 速度非常必要，一旦选定目标，就需要快速制定次优路径，然后在运动过程中进行改进。这让我觉得我需要一个“随时算法”
- 环境中还有其他参与者，因此不断变化。这让我想到基于D* 或 D* Lite的算法，这样可以快速替换路径。
这两个要求让我想到了Anytime D*，除了我的最后一个要求外，它似乎可以正常工作：
- 返回的路径必须快速跟随，并且直接。由Field D*生成的路径就是很好的例子。
有没有一种算法可以结合这两种算法（Anytime D* 和 Field D*）的各个方面？如果没有，是否可以将 Anytime D* 的改进纳入 Field D* 中？还是我遗漏了什么，而我已经拥有了我需要的东西？
我晚上晚些时候会写这篇文章，所以几个小时内我都无法回复任何内容。我希望我有足够的背景信息。
感谢您的所有帮助！
是否存在一种算法，可以有效地将 uint32 转换为不同的 uint32，并在给定可变的随机种子时产生 1：1 的映射？
我对此的初步方向是一种算法，其中种子以某种方式表达数字中要重新排列的位（这样 0000 0101 就变成了 0100 1000，种子为 [0->6, 2->3]），但我不确定如何生成一种有效地进行混洗的方法。
一些限制：
- 生成从种子进行改组的算法不需要非常快
- 实际上，对 uint32 执行 shuffle 应该很快
- 对于给定的种子，输出中不应有重复（唯一的 uint32 产生唯一的 uint32）
我正在一个在线平台上解决一个测试，问题陈述与此类似。
Stuart 必须从一个地方到另一个地方（A->B），他每次可以跳 1 步、2 步或 3 步。A 和 B 之间可以有 n 个阻挡器。
我们需要找出他能做到这一点的方法数量。
我觉得这类似于经典的爬楼梯问题，但区别不大，在爬楼梯问题中，你最终必须到达第 n 级台阶，而在这个特定问题中，你必须走下楼梯，这样可能就是第 n+1 级台阶。我说得对吗？
所以我写的代码是这样的：
function countWays(n) {
if (n < 0) return 0;
if (n === 0) return 1;
if (n === 1) return 2; //If you have one stop-over, there's two ways to reach. One is take one jump and then one more. Second is take two jumps at once and reach the destination
return countWays(n-1) + countWays(n-2) + countWays(n-3);
}
console.log(countWays(4))这没有被接受。所以我想知道这有什么问题。我是否也应该添加基本情况n==2？
if (n === 2) return 4
但这仍然没有任何好处，因为n = 3它会返回6，而从视觉上我可以看到，如果有 3 个中途停留，就会有 7 种方式。
我想问的另一个问题是，
在经典的楼梯案例中，基准情况n === 0是 1。这里还是一样吗？这让我有点困惑，因为当没有更多的台阶可以爬的时候，结果怎么会是 1。另一方面，当n === 1你仍然有一条路可以到达目的地时。
此外，f(3)逻辑和直觉表明应该是：
number of ways to reach first stopover + f(2)
而且number of ways to reach first stopover只有一种方式可以做到这一点（跳一次）。
但是，我不能输入if(n == 1) return 1基本情况，因为这样不正确。假设只有一个中途停留点 (n = 1)，实际上有两种到达方式：
- 跳 2 步
- 跳 1 步，然后再跳 1 步。
这也造成了一些混乱。
在Sedgewick & et al.的算法第4版第296页中，作者写道：
截止值 M 的最佳值取决于系统，但在大多数情况下，5 到 15 之间的任何值都可能效果良好。
但是我不明白截止值依赖于系统是什么意思，因为算法的性能的衡量标准是它执行的操作数，而不是与计算机处理器的速度无关？