小编Dan*_*iel的帖子

我有很多大的(大约5000 x 5000)矩阵,我需要在Matlab中反转.我实际上需要逆,所以我不能使用mldivide,这对于解决一个b的Ax = b要快得多.

我的矩阵来自一个问题,这意味着他们有一些不错的属性.首先,他们的决定因素是1,所以他们肯定是可逆的.但它们不是可对角化的,或者我会尝试对它们进行对角化,将它们反转,然后将它们放回去.他们的条目都是实数(实际上是理性的).

我正在使用Matlab来获取这些矩阵,对于这些东西,我需要对它们的反转进行处理,所以我更喜欢一种方法来加速Matlab.但是,如果有另一种语言,我可以使用它会更快,那么请让我知道.我不知道很多其他语言(一点点但只有C和一点点但是Java),所以如果它在其他语言中真的很复杂,那么我可能无法使用它.请继续并建议,以防万一.

我一直在接受这些艰难的面试问题.这个真让我感到困惑.

您将获得一个poly获取并返回的函数int.它实际上是一个非负整数系数的多项式,但你不知道系数是什么.

您必须编写一个函数,使用尽可能少的调用来确定系数poly.

我的想法是使用递归知道我可以得到最后一个系数poly(0).所以我想,以取代poly用(poly - poly(0))/x,但我不知道如何做到这一点的代码,因为我只能打电话poly.任何人都知道如何做到这一点？

从正数的数组A开始.从索引i开始,你可以移动索引i + x获取任何x <= A [i].目标是找到到达阵列末尾所需的最小移动次数.

这是一个例子:

{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 

如果你总是在每一步中尽可能地走,那么这就是你得到的:

0 , 2 , 3 , 5 , 7

这需要4个动作.但是你可以通过这种方式更快地完成它

0 , 1 , 4 , 7

这只需3步.

我考虑过这个问题并做了我想到的第一件事,但在思考了几天之后,我仍然不知道如何做得更好.

这是我的想法.从数组的末尾开始,跟踪从某个位置到结尾的最小移动次数.所以对于这个例子,moves[7] = 0因为它已经结束了.然后moves[6] = 1因为它需要一个动作才能结束.我的公式是

moves[i] = 1 + min(moves[i+1], moves[i+2], ... , moves[i+A[i]])

当我到达开始时,我知道移动的数量.

所以这是O(n ^ 2)我猜是好的,但可能有更快的方法？

给定的阵列n+1整数,每个范围1来n,发现反复的整数.

在面试时我被问到这个问题.这是我的答案:鸽笼原则说必须重复一遍.我尝试使用二进制搜索方法,所以我在Matlab中做了这个,因为这就是我所知道的:

top = 0;
bot = 0;
for i=1:n+1
  if P[i] > n/2 
    top = top+1;
  else
    bot = bot+1;
end

所以我认为其中一个,top或者bot,必须比n/2PhP 更大.取这个范围并重复.

我认为这是一个非常好的解决方案,但面试官有点暗示一个人可以做得更好.请发布您知道的更好的解决方案.

我试图解决我遇到问题的部分问题,这是我正在做的更大项目的一部分(不是家庭作业).我认为将它描述为游戏是最容易的(因为我需要它来完成我正在进行的游戏).这是一个单人游戏,就像我描述它一样.

开始您从以下两个职位之一开始:

• 重量(2,0,-1)和一个red游戏
• 重量(3,1,-1)和两个red戏剧

END时,你有没有更多的玩游戏结束.目标是以重量结束比赛(0,0,0).

有两种类型的戏剧red和blue.考虑到一个游戏,你可以选择四个部分中的一个:A,B,C,D这会给你额外的重量和可能的额外游戏.以下是规则:

• 在red戏剧上:

  • A增加了重量 (0,-2,-1)
  • B增加了重量(1,-1,-1)并增加了一个red游戏
  • C增加了重量(2,0,-1)和两个red游戏
  • D增加了重量(0,2,1)和两个blue游戏

blue播放的规则是相似的,但是权重的前两列是交换的,最后一列是反向的,并且播放的类型是相反的,所以你得到这个:

• 在blue戏剧上:

  • A增加了重量 (-2,0,1)
  • B增加了重量(-1,1,1)并增加了一个blue游戏
  • C增加了重量(0,2,1)和两个blue游戏
  • D增加了重量(2,0,-1)和两个red游戏

问题可以赢得这场比赛吗？

我正在尝试编写一个程序,通过选择游戏赢得游戏,以便最终的平衡是(0,0,0)你没有更多的游戏.只有我似乎无法做到这一点.所以现在我认为也许没有算法来赢得比赛.我真的很想知道为什么会这样.如果有人有任何想法我可以证明这一点,那么请让我知道!或者,如果你尝试并找到获胜的方法,那么请告诉我.谢谢!!

我正在尝试为以下排序问题找到最佳算法.

在礼堂中有N = K×M个座位,每个过道有一个过道,K行和M个座位.假设K大于M,但我认为这不是很重要.有N个人与座位(指定席位)进行双向投射.假设人们不喜欢等待,那么最快的方式是让他们尽快安排在座位上？

我进行了一些简单的experiements(使用随机排列),它似乎让他们随机排队要比拥有前三分之一的人(进一步下跌的走道)第一排队快,然后中间的三分之一,那么第三后侧.这对我来说似乎不对.

如果重要的话,我在MatLab中写这个.有什么想法或答案吗？

对于排列,给定N和k,我有一个函数,找到按字典顺序k排列的N排列.另外,给定一个排列perm,我有一个函数,可以在所有排列中找到排列的词典索引N.为此,我使用了本答案中建议的"因子分解" .

现在我想对整数分区做同样的事情N.例如,因为N=7,我希望能够在索引(左)和分区(右)之间来回:

 0 ( 7 )
 1 ( 6 1 )
 2 ( 5 2 )
 3 ( 5 1 1 )
 4 ( 4 3 )
 5 ( 4 2 1 )
 6 ( 4 1 1 1 )
 7 ( 3 3 1 )
 8 ( 3 2 2 )
 9 ( 3 2 1 1 )
10 ( …

我看到这篇文章:在数组中查找偶数数字,我在考虑如何在没有反馈的情况下完成它.这就是我的意思.

给定一个长度为n的数组,其中包含最多e偶数和一个函数isEven,如果输入为偶数则返回true,否则为false,编写一个函数,使用最少的调用次数打印数组中的所有偶数isEven.

帖子上的答案是使用二进制搜索,这是很整洁的,因为它并不意味着数组必须按顺序排列.的次数,你必须检查是否有数字为偶数的e log n,而是如果n因为你做一个二进制搜索(log n)找到一个甚至每一时间(数e倍).

但是这个想法意味着你将数组分成两半,测试均匀度,然后根据结果决定保留哪一半.

我的问题是你是否可以n在一个固定的测试方案上打电话,你可以在不知道结果的情况下检查你想要的所有数字,然后在你完成所有测试之后找出偶数的位置.结果.所以我猜这不是反馈或盲目或类似的术语.

我有一段时间在思考这个问题并且无法想出任何东西.二元搜索的想法在这个约束下根本不起作用,但也许其他的东西呢？即使是n/2打电话而不是n(是的,我知道他们是同一个大O)也会很好.

我有一个大矩阵,n!xn !,我需要采取决定因素.对于n的每个排列,我都联想到了

• 一个长度为2n的向量(这很容易计算)
• 2n个变量的多项式(在n上递归计算的线性因子的乘积)

矩阵是向量处的多项式的评估矩阵(被认为是点).因此,矩阵的sigma,tau入口(由置换索引)是在tau的向量处评估的sigma的多项式.

示例:对于n=3,如果第ith个多项式是(x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1)并且第jth个是(2,2,1,3,5,2),那么(i,j)矩阵的第th个条目将是(2 - 4)(1 - 5)(3 - 4)(2 - 1) = -8.这里n=3,所以点在R^(3!) = R^6,多项式有3!=6变量.

我的目标是确定矩阵是否是非奇异的.

我现在的方法是:

• 该函数point采用置换并输出向量
• 该函数poly采用置换并输出多项式
• 该函数nextPerm以字典顺序给出下一个排列

我的代码的删节伪代码版本是这样的:

B := [];
P := [];
w := [1,2,...,n];
while w <> NULL do
  B := B append poly(w);
  P := …

问题:开始一组S大小的2n + 1和一个子集A的S大小为n的.你具备的功能addElement(A,x),并removeElement(A,x)可以添加或删除的元素A.编写一个函数,S仅使用这两个操作循环遍历大小为n或n + 1的所有子集A.

我发现有(2n + 1选择n)+(2n + 1选择n + 1)= 2*(2n + 1选择n)子集我需要找到.所以这是我的功能结构:

for (int k=0; k<2*binomial(2n+1,n); ++k) {
    if (k mod 2) {
        // somehow choose x from S-A
        A = addElement(A,x);
        printSet(A,n+1);
    } else
        // somehow choose x from A
        A = removeElement(A,x);
        printSet(A,n);
    }
}

该函数binomial(2n+1,n)只给出二项式系数,函数printSet打印元素,A以便我可以看到我是否击中了所有集合.

不过,我不知道如何选择要添加或删除的元素.我尝试了很多不同的东西,但是我没有得到任何有效的东西.

对于n = 1,这是我找到的解决方案:

for (int k=0; …

这是傻瓜:

从三个阵列A,B和C开始,总共有2n+1条目.编写一个算法,仅使用以下两种方法对所有数组中的所有条目进行排序:

1. X = sort(X)用X排序的版本替换数组.

2. (X , Y) = doubleUp(X , Y)如果X有更多的元素Y,则不执行任何操作,否则它会删除第一个length(X)条目Y 并将它们附加到结尾X.

这是我到目前为止所尝试的内容.如果其中两个数组为空,则只需使用sort非空数组.

如果其中一个数组是空的,那么我认为我可以使用doubleUp一个数组只有一个而另一个数组拥有其他所有数据,如果该单例数组具有最小(或最大)的元素,则可行.所以我可以sort在doubleUp每次使用之后使用以确保这种情况发生.我在Maple中对此进行了编码,它适用于我检查过的所有情况.

我不知道如何用3个阵列做到这一点.有人有主意吗？

问题在于:给出4组大小为A,B,C和D的学生,以及总共k个伴侣,设计一种算法,以近乎相等的比例为学生分配伴侣.

您不能只给组k*A/N,k*B/N,k*C/N,k*D/N伴侣,因为伴侣的数量必须是正整数.你不能只是圆,因为那时你可能得不到合适数量的伴侣.所以我的想法是你扔出小数部分,并给每个组赋予整数部分,所以做整数除法.然后你可能会留下一些陪伴者,但最多只有3个,所以把它们交给剩下最多的群体.

然后,采访者指出这是一个问题.如果你添加另一个伴侣,所以将k增加到k + 1,那么可能会发生其中一个组实际上以这种方式失去伴侣.她给了我一个例子,但我不记得了.

任何人都可以想出一个避免这个问题的算法吗？