个人中心
gpt4 book ai didi

java - Java 中的欧拉项目 215

转载 作者：行者123 更新时间：2023-11-30 05:55:50 25 4
gpt4 key购买 nike

<分区>

我把这个解决方案写给了Project Euler #215在 java 。它不会在不到一分钟的时间内完成 W(32,10) 的计算，但它需要这样做。我希望我能得到一些关于如何让它更快的建议。我想知道添加线程是否合适，或者是否有办法缓存 buildWall() 方法中每一行的结果。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.HashMap;
import java.util.Map;

class BlockCombos
{
    static ArrayList<String> possibleRows = new ArrayList<String>();
    static long validWalls = 0;
    static Map<Integer, List> map = new HashMap<Integer, List>();
    static int[][] cache;

    public static void main(String[] args) 
    {
        if (args.length != 2) 
        {
            System.out.println("Error: You need to enter a height and width.");
        }
        else
        {
            int height = Integer.parseInt(args[1]);
            int width = Integer.parseInt(args[0]);

            //numbers proportionate to block widths
            //reduced for less overhead (actual widths do not matter)
            ArrayList<Integer> numbers = new ArrayList<Integer>();
            numbers.add(new Integer(2));
            numbers.add(new Integer(3));

            startGetBlockCombos(numbers,width);

            int i = 0; //initial row
            for(String row : possibleRows)
            {
                //possible rows
                char[] rowArr = row.toCharArray();
                List<Integer> compatiblerows = new ArrayList<Integer>();
                int k = 0; //rowtocheck index
                for(String rowToCheck : possibleRows)
                {
                    char[] rowToCheckArr = rowToCheck.toCharArray();
                    for(int x = 0; x < rowToCheckArr.length-1; x++)
                    {   

                        if(rowArr[x] == '1' && rowToCheckArr[x] == '1')
                        {
                            //set not compatible
                            break;
                        }
                        else if (x == rowToCheckArr.length-2)
                        {
                            compatiblerows.add(k);
                        }
                    }
                    k ++; //rowtocheck index
                }
                Integer key = new Integer(i);
                map.put(key, compatiblerows);
                i++; //row index
            }

            possibleRows.clear(); //a little clean up
            cache = new int[map.size()][height];
            startBuildWalls(height);
            System.out.print(validWalls);
        }
    }

    static void startBuildWalls(int height)
    {
        height = height-1;
        for(int x = 0; x < map.size(); x++)
        {
            buildWalls(x, height);
        }
        //testing threads from static method

    }
    static void buildWalls(int currentRow, int rowsToGo)
    {
        rowsToGo -=1;
        if(rowsToGo > 0)
        {
            @SuppressWarnings("unchecked")
            List<Integer> nextRows = (List<Integer>)map.get(Integer.valueOf(currentRow));

            for(int row : nextRows)
            {
                buildWalls(row,rowsToGo);
            }
        }
        else
        {
            validWalls++;
            return;
        }
    }

    static void startGetBlockCombos(ArrayList<Integer> numbers, int target) 
    {
        ArrayList<Integer> part = new ArrayList<Integer>();
        getBlockCombos(numbers,target,part);
    }

    static void getBlockCombos(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) 
    {
        int s = 0;
        for (int x: partial)
        {
            s += x;
        }
        if (s == target)
        {
            Integer row[] = new Integer[partial.size()];
            row = partial.toArray(row);
            String rowString = "";

            for (int b : row)
            {
                if (b == 2)
                {
                    rowString = rowString +"01";
                }
                else
                {
                    rowString = rowString + "001";
                }
            }

            BlockCombos.possibleRows.add(rowString);
        }
        else if (s > target)
        {
            return;
        }
        for(int i=0;i<2;i++) 
        {
            int n = numbers.get(i);
            ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
            partial_rec.add(n);
            getBlockCombos(numbers,target,partial_rec);
        }
    }
}

25 4 0
文章推荐： java - 将 java 控制台附加到文件
文章推荐： javascript - TinyMCE 向粗体和斜体按钮添加另一个事件？
文章推荐： javascript - 如何在没有初始刷新的情况下从服务器准备好 Angular.js 应用程序
文章推荐： java - 如何在 Java 中引用匿名或嵌套类的包含类
行者123
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com