int s_dynamic(int n,int k) {
int maxj = n-k;
int *arr = new int[maxj+1];
for (int i = 0; i <= maxj; ++i)
arr[i] = 1;
for (int i = 1; i <= k; ++i)
for(int j = 1; j <= maxj; ++j)
arr[j] += i*arr[j-1];
return arr[maxj];
}
这是我尝试使用动态编程确定斯特林数字.
它的定义如下:
S(n,k)= S(n-1,k-1)+ k S(n-1,k),如果1 <k <n
如果k = 1 ou k = n,则S(n,k)= 1
好像对不对吧？除了我运行我的单元测试...
partitioningTest ..\src\Test.cpp:44 3025 == s_dynamic(9,3) expected: 3025 but was: 4414
谁能看到我做错了什么？
谢谢!
BTW,这是递归解决方案:
int …最近我需要实现非递归 DFS 作为更复杂算法的一部分，准确地说是 Tarjan 算法。递归实现非常优雅，但不适用于大图。当我实现迭代版本时，我对它最终变得多么不优雅感到震惊，我想知道我是否做错了什么。
迭代 DFS 有两种基本方法。首先，您可以一次将一个节点的所有子节点压入堆栈（这似乎更为常见）。或者你可以只推一个。我将专注于第一个，因为这似乎每个人都是这样做的。
我在这个算法上遇到了各种问题，最终我意识到要高效地完成它，我不需要 1 个，不是 2 个，而是 3 个布尔标志（我不一定意味着您需要三个显式布尔变量，您可能会间接存储信息通过变量的特殊值，通常是整数，但您需要以一种或另一种方式访问这 3 条信息。这三个标志是：1）已访问。这是为了防止孩子被非常冗余地推入堆栈。2）完成。防止同一节点的冗余处理。3) 升序/降序。指示子项是否已被推入堆栈。伪代码如下所示：
while(S)
if S.peek().done == True
S.pop()
continue
S.peek().visited = True
if S.peek().descending == True
S.peek().descending = False
for c in S.peek().children
if c.visited == False
S.push(c)
doDescendingStuff()
else
w = S.pop()
w.done = True
doAscendingStuff()
一些注意事项：1）从技术上讲，您不需要升/降，因为您可以只查看孩子是否都完成了。但它在密集图中效率很低。
2），主要问题：访问/完成的事情似乎没有必要。这就是为什么（我认为）你需要它。在访问堆栈之前，您无法标记访问过的事物。如果这样做，您可能会以错误的顺序处理事情。例如，假设 A 链接到 B 和 C，B 链接到 D，D 链接到 C。然后从 A，您将 B 和 C 压入堆栈。从 B 将 D 压入堆栈……然后呢？如果在将它们压入堆栈时标记已访问的事物，则不会在此处将 C 压入堆栈。但这是错误的，应该从 D 访问 C，而不是从图中的 A 访问（假设 …
git log -p .
仅在当前目录中,但不在子目录中
当量
svn log --diff --depth files .
可能吗？
我正在努力解决这个问题,我想以非递归的方式解决这个问题.我的算法似乎没有逻辑错误,73%的测试用例通过了.但它无法处理大数据,报告称"超出时间限制".我很感激,如果有人能给我一些提示,如何在非递归中做到这一点,并避免时间限制超过,提前谢谢!
问题链接
我相信在LeetCode中也有类似的一个.
http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/
问题描述:
给定二叉树,从根找到最大路径总和.路径可以在树中的任何节点处结束,并且其中包含至少一个节点.
例:
鉴于以下二叉树:
1
/ \
2 3
返回4.(1-> 3)
法官
超出时限
总运行时间:1030毫秒
输入 输入数据
{-790,-726,970,696,-266,-545,830,-866,669,-488,-122,260,116,521,-866,-480,-573,-926,88,733,#,#,483,-935,-285,-258,892,180,279 ,-935,675,2,596,5,50,830,-607,-212,663,25,-840,#,#, - 333754,#817842,-220,-269,9,-862,-78,-473,643,536 - 142,773,485,262,360,702,-661,244,-96,#519566,-893,-599,126,-314,160,358,159,#,#, - 237,-522,-327,310,-506,462,-705,868,-782,300,-945,-3,139, - 193,-205,-92,795,-99,-983,-658,-114,-706,987,292,#,234,-406,-993,-863,859,875,383,-729,-748,-258,329,431,-188,-375 ,-696,-856,825,-154,-398,-917,-70,105,819,-264,993,207,21,-102,50,569,-824,-604,895,-564,-361,110,-965,-11,557,#,202213 ,-141,759,214,207,135,329,15,#,#,244#,334628509627,-737,-33,-339,-985,349,267,-505,-527,882,-352,-357,-630,782,-215,-555,132, - 835,-421,751,0,-792,-575,-615,-690,718,248,882,-606,-53,157,750,862,#,940,160,47,-347,-101,-947,739,894,#, - 658,-90,-277 ,-925,997,862,-481,-83,708,706,686,-542,485,517,-922,978,-464,-923,710,-691,168,-607,-888,-439,499,794,-601,435,-114,-337,422,#, - 855,-859,163 ,-224 ,902,#,577,#, - 386,272,-9 ......
预期
6678
我的代码 C++
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL; …鉴于此算法,我想知道是否存在迭代版本.另外,我想知道迭代版本是否更快.
这种伪蟒...
该算法返回对树的根的引用
make_tree(array a)
if len(a) == 0
return None;
node = pick a random point from the array
calculate distances of the point against the others
calculate median of such distances
node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances)
node.right = make_tree(subset, such the distance is greater or equal to the median)
return node
我遇到了一个不断困扰我的 Rustlings 练习：
pub fn factorial(num: u64) -> u64 {
// Complete this function to return factorial of num
// Do not use:
// - return
// For extra fun don't use:
// - imperative style loops (for, while)
// - additional variables
// For the most fun don't use:
// - recursion
// Execute `rustlings hint iterators4` for hints.
}
解决方案的提示告诉我...
在命令式语言中，您可能会编写一个 for 循环来迭代将值乘以可变变量。或者，您可以使用递归和匹配子句编写更具功能性的代码。但是你也可以使用范围和迭代器来解决这个问题。
我试过这种方法，但我遗漏了一些东西：
if num > 1 {
(2..=num).map(|n| n * ( n - 1 ) ??? …任何人都可以指出在不使用递归的情况下在二叉树(不是平衡的树或BST)中获取节点深度的方法吗？理想情况下在Java/C/C#
该节点表示为:
class Node
{
Node Left;
Node Right;
string Value;
int Depth;
}
使用带有FIFO列表的Level Order是我的第一个想法,但是当我发现水平发生变化时,我很难过,特别是对于不平衡的树.
我读过书，遇到了无法解决的问题。我查了很久的资料。我绞尽脑汁试图理解它。
因此，我得到一个长度为 N (int) 的数组，通过使用非递归合并排序算法对其进行排序。我学习了长度为 2^n 的数组的合并排序算法。但我完全不明白它对于长度为 N 的数组是如何工作的。
有人可以解释一下它是如何工作的吗？
我试图将这个递归函数转换为非递归函数.这是来自二叉搜索树的搜索函数.我知道这是很自然,使之递归的,但学习的目的,我想使其非递归.我怎么能这样做？提前致谢!
bool Search(BstNode* root, string data) {
if (root == NULL) return false;
else if (root->data == data) return true;
else if (data <= root->data) return Search(root->left, data);
else return Search(root->right, data);
}
我正在使用 Lavaan 运行非递归模型。然而，发生了两件事我不太明白。首先，拟合优度指数和一些标准误差为“NA”。第二，不同方向的两个变量之间的两个系数不一致（非递归部分：ResidentialMobility--作者）：一个为正，另一个为负（至少应该是同一个方向；否则如何解释？）。有人可以帮我吗？如果您希望我进一步澄清，请告诉我。谢谢！
model01<-'ResidentialMobility~a*Coun
SavingMotherPercentage~e*Affect
SavingMotherPercentage~f*Author
SavingMotherPercentage~g*Recipro
Affect~b*ResidentialMobility
Author~c*ResidentialMobility
Recipro~d*ResidentialMobility
ResidentialMobility~h*Affect
ResidentialMobility~i*Author
ResidentialMobility~j*Recipro
Affect~~Author+Recipro+ResidentialMobility
Author~~Recipro+ResidentialMobility
Recipro~~ResidentialMobility
Coun~SavingMotherPercentage
ab:=a*b
ac:=a*c
ad:=a*d
be:=b*e
cf:=c*f
dg:=d*g
'
fit <- cfa(model01, estimator = "MLR", data = data01, missing = "FIML")
summary(fit, standardized = TRUE, fit.measures = TRUE)
输出：
lavaan (0.5-21) 在 93 次迭代后正常收敛
Used Total
Number of observations 502 506
Number of missing patterns 4
Estimator ML Robust
Minimum Function Test Statistic NA NA
Degrees of freedom -2 -2
Minimum Function Value 0.0005232772506
Scaling …如何在不使用堆栈的情况下非递归地遍历O(n)中的线程二叉树(只允许为临时变量使用常量额外空间,因此我们不能将访问标志添加到树中的每个节点).我花了很多时间思考它,但除非我们要遍历具有树数据的内存位置,否则我似乎并不可行.假设我们使用多个数组表示来实现指针,然后我们可以遍历O(n)中的树,是否有人有其他想法？
注意这不是功课,只是为了节省一些键盘敲击的能量来写关于作业的评论!