language-agnostic - 与语言无关的随机洗牌问题

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center提供指导。




9年前关闭。




不久前，我在接受采访时要求解决两个非常有趣的问题。我很好奇您将如何解决这些问题。

问题1:

除当前外的所有产品的乘积

编写一个函数，该函数将长度为len的两个整数数组，输入和索引作为输入，并生成第三个数组，结果如下:
result [i] =输入中除input [index [i]]以外的所有内容的乘积

例如，如果使用len = 4，input = {2,3,4,5}和index = {1,3,2,0}调用函数，则结果将设置为{40,24,30 ，60}。

重要说明:您的算法必须在线性时间内运行。

问题2 :(该主题在Jeff的一篇文章中)

随机播放卡组

Design(使用C++或C#)设计一个Deck类来表示有序纸牌，其中纸牌包含52张纸牌，分为13个等级(A，2、3、4、5、6、7、8、9 ，四，十，J，Q，K):黑桃(？)，心形(？)，菱形(？)和球杆(？)。

基于此类，设计并实现一种有效的算法来洗牌。纸牌必须均匀地混洗，也就是说，原始纸牌中的每张纸牌必须具有相同的概率才能出现在纸牌中的任何可能位置。
该算法应在Deck类的shuffle()方法中实现:
无效shuffle()

您的算法的复杂度是多少(取决于卡组中n张牌的数量)？

解释如何测试卡是否被您的方法均匀洗净(黑盒测试)。

P.S.我有两个小时编写解决方案的代码

最佳答案

第一个问题:

int countZeroes (int[] vec) {
int ret = 0;
foreach(int i in vec) if (i == 0) ret++;

return ret;
}

int[] mysticCalc(int[] values, int[] indexes) {
    int zeroes = countZeroes(values); 
    int[] retval = new int[values.length];
    int product = 1;

    if (zeroes >= 2) { // 2 or more zeroes, all results will be 0
        for (int i = 0; i > values.length; i++) {
            retval[i] = 0;      
        }
        return retval;
    }
    foreach (int i in values) {
        if (i != 0) product *= i; // we have at most 1 zero, dont include in product;
    }
    int indexcounter = 0;
    foreach(int idx in indexes) {
        if (zeroes == 1 && values[idx] != 0) {  // One zero on other index. Our value will be 0
            retval[indexcounter] = 0;
        }
        else if (zeroes == 1) { // One zero on this index. result is product
            retval[indexcounter] = product;
        }
        else { // No zeros. Return product/value at index
            retval[indexcounter] = product / values[idx];
        }
        indexcouter++;
    }   
    return retval;
}

最坏的情况是，该程序将一次遍历3个向量。

关于language-agnostic - 与语言无关的随机洗牌问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56215/

上一篇：ruby-on-rails - 无法批量分配 protected 属性以使用设计创建 has_many 嵌套模型

下一篇：entity-framework - Entity Framework 中的 View 不会更新

相关文章：

language-agnostic - 如何处理霍夫施塔特定律？

algorithm - 有效地从集合中检索最近元素的数据结构

php - 从邮件服务器获取响应(如果电子邮件已发送)

algorithm - 判断两个三角形是否相交

language-agnostic - TDD 测试是否应该总是先失败？

algorithm - 如何生成 float 的随机分区并且每个部分都有最小值pMin？

algorithm - 尖峰时刻 - 解决游戏

algorithm - "Flip"仅使用 +1/-1 而不使用 if/else 的简单循环的输出

oop - 如何使队列从 FIFO 模式切换到优先模式？

language-agnostic - 哪个先出现 - 接口(interface)或类

Answer 1

第一个问题:

int countZeroes (int[] vec) {
int ret = 0;
foreach(int i in vec) if (i == 0) ret++;

return ret;
}

int[] mysticCalc(int[] values, int[] indexes) {
    int zeroes = countZeroes(values); 
    int[] retval = new int[values.length];
    int product = 1;

    if (zeroes >= 2) { // 2 or more zeroes, all results will be 0
        for (int i = 0; i > values.length; i++) {
            retval[i] = 0;      
        }
        return retval;
    }
    foreach (int i in values) {
        if (i != 0) product *= i; // we have at most 1 zero, dont include in product;
    }
    int indexcounter = 0;
    foreach(int idx in indexes) {
        if (zeroes == 1 && values[idx] != 0) {  // One zero on other index. Our value will be 0
            retval[indexcounter] = 0;
        }
        else if (zeroes == 1) { // One zero on this index. result is product
            retval[indexcounter] = product;
        }
        else { // No zeros. Return product/value at index
            retval[indexcounter] = product / values[idx];
        }
        indexcouter++;
    }   
    return retval;
}

最坏的情况是，该程序将一次遍历3个向量。