草庐IT

java - 用 C 和 Java 解决数字难题

coder 2024-03-21 原文

这个问题是我从另一个论坛翻译成英文的，我觉得很有趣，然后就写了一个Java解决方案。并发现在处理像 10000000 这样的大数字时存在一些堆大小问题。与我自己的解决方案相比，我想寻求一些真正聪明的解决方案。

原帖为中文。我根据自己的理解对它进行了一些修改，使其更清晰。 http://zhidao.baidu.com/question/1637660984282265740.html?sort=6&old=1#here

下面是拼图:

10000 rows of numbers;
1 row: 2,4,6,8...2K(2K<=10000000); (numbers no repeats for this row)
2 row: 3,3,6,6,9,9...3K(3K<=10000000); (starting from this row, each number repeats 2 times and a multiple which has something to do with row number (2XrowNumber-1) to be specificaly)
3 row: 5,5,10,10,15,15...5K(5K<=10000000);
and following 7K,9K,11K,13K....until
10000 row: 19999,19999,39998,39998....19999K,19999K (19999K<=10000000);

这就是接下来部分要用到的所有行。现在我们将计算从第 1 行和第 2 行开始的数字的重复次数:

整数w1是第1行和第2行数字的重复次数。例如，考虑第 1 行编号 2、4、6 和第 2 行编号 3、3、6、6。那么到目前为止的重复次数将是 3，因为 6 已经在第 1 行中并且在第 2 行中出现了 2 次，而 3 在第 2 行中出现了 2 次； 

Integer w2 is the repeat times of numbers in row 1 and row 2 and row 3. 
Integer w3 is the repeat times of numbers in row 1 and row 2 and row 3 and row 4. 
......
Integer w9999 is the repeat times of numbers of row 1,row 2,row 3 .....row 10000.

现在打印出所有整数，w1,w2....w9999;

我想出了一个 Java 解决方案，但我遇到了堆大小问题，因为 10000000 太大并且内存不足。所以我只用10000而不是10000000，用10而不是10000。下面是我用Java写的。我猜应该是对的(如果不对请指出):

    Set nums = new HashSet();
    int max = 10000;
    int row = 10;
    for (int i=2;i<=max;i+=2){
        nums.add(new Integer(i));
    }
    int nums_size = nums.size();
    int w = 0;
    for (int i=2;i<=(row);i++){
        int tmp_count = 0;
        int self_count = 0;
        for (int j=(2*i-1);j<=max;j+=(2*i-1)){
            nums.add(new Integer(j));
            self_count++;
            if (nums.size()==nums_size){
                tmp_count++;
            } else {
                nums_size = nums.size();
            }
        }           
        w += tmp_count;
        w += self_count;
        System.out.println("w"+(i-1)+": "+w);
    }

我的问题是

  1. 如何在 Java 中获得更好的解决方案(如果有的话)？
  2. 如何用 C 实现 因为我记得 C 中没有 Set 类。 (导入第 3 派对图书馆不是首选)？

谢谢。

最佳答案

这是您的代码的简化版本。由于它不使用 HashSet，因此从中创建 C 版本应该没问题了。

int max = 10000;
int row = 10;
boolean[] seen=new boolean[max+1];
for(int i=2;i<=max;i+=2) seen[i]=true;
int w = 0;
for(int i=2;i<=(row);i++) {
    int self_count = 0;
    for(int j=(2*i-1);j<=max;j+=(2*i-1)) {
        self_count++;
        if(seen[j]) w++; else seen[j]=true;
    }
    w += self_count/2;
    System.out.println("w"+(i-1)+": "+w);
}

关于java - 用 C 和 Java 解决数字难题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19925252/

javarowintsectioncalgorithmmathpuzzle

有关java - 用 C 和 Java 解决数字难题的更多相关文章

  1. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  2. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  3. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  4. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  5. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  6. 屏幕录制为什么没声音？检查这2项，轻松解决 - 2

    相信很多人在录制视频的时候都会遇到各种各样的问题，比如录制的视频没有声音。屏幕录制为什么没声音？今天小编就和大家分享一下如何录制音画同步视频的具体操作方法。如果你有录制的视频没有声音，你可以试试这个方法。 一、检查是否打开电脑系统声音相信很多小伙伴在录制视频后会发现录制的视频没有声音，屏幕录制为什么没声音？如果当时没有打开音频录制，则录制好的视频是没有声音的。因此，建议在录制前进行检查。屏幕上没有声音，很可能是因为你的电脑系统的声音被禁止了。您只需打开电脑系统的声音，即可录制音频和图画同步视频。操作方法：步骤1：点击电脑屏幕右下侧的“小喇叭”图案，在上方的选项中，选择“声音”。 步骤2：在“声

  7. 【高数】用拉格朗日中值定理解决极限问题 - 2

    首先回顾一下拉格朗日定理的内容：函数f(x)是在闭区间[a,b]上连续、开区间(a,b)上可导的函数，那么至少存在一个，使得:通过这个表达式我们可以知道，f(x)是函数的主体，a和b可以看作是主体函数f(x)中所取的两个值。那么可以有，  也就意味着我们可以用来替换 这种替换可以用在求某些多项式差的极限中。方法： 外层函数f(x)是一致的，并且h(x)和g(x)是等价无穷小。此时，利用拉格朗日定理，将原式替换为 ，再进行求解，往往会省去复合函数求极限的很多麻烦。使用要注意：1.要先找到主体函数f(x)，即外层函数必须相同。2.f(x)找到后，复合部分是等价无穷小。3.要满足作差的形式。如果是加

  8. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  9. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  10. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

随机推荐