"有道难题"题解

简介:
第一道算法题(250分)
      话说你在走路上班时,经过一片种植萝卜的农田。这块田地的形状是一个矩形的网格。field的第i个元素的第j个字符,表示田地的第i 行第j列的格子里包含的萝卜的数目。我们定义一个格子的特殊程度为它周围所有格子的萝卜个数的和; 它周围的格子包含它上下左右以及对角相邻的格子,最多有8个,在田地的边界上的格子会少一些。如果一个格子周围没有别的格子,则它的特殊程度为0。 
请返回田地中特殊程度在A和B之间的所有格子的数目(包含A,B)。

下面是我的解法,由于不懂C#,所以就使用与其相近的Java来编写,简单说明下,就是引入一个辅助标记二维数组,若数组中某一个数其值大于范围的最大值,则说明其本身和周围位置(最多八个)都是不再需要进行统计的,所以这里进行一个剪枝操作,设置标记值表示此处不需要进行判断,减少搜索的范围,从而提高算法速度,最后测试运算10万次,用时为937毫秒,具体的测试用例见原帖中。

复制代码

/**
 * @author phinecos
 * @since 2009-6-1
 */
public class NumberField 
{
    private static int min;
    private static int max;
    private static int height;
    private static int width;
    private static boolean flag[][];//辅助标志
    
    private static void markNoSpecial(String[] field, int i, int j)
    {//设置false标记,无需再对其周围进行检测
        int k,m;
        int num;
        for (k = i-1; k <= i+1 && k < height; ++k)
        {
            if (k < 0)
            {//越过边界
                k = i;
            }
            String tmp = field[k];
            for (m = j-1; m <= j+1 && m < width; ++m)
            {
                if (m < 0)
                {//越过边界
                    m = j;
                }
                if (k != i || m != j)
                {
                    num = tmp.charAt(m) - '0'; 
                    if (num > max && flag[k][m] != false)
                    {
                        flag[k][m] = false;
                    }
                }
            }
        }
    }
    private static int getSpecialNumber(String[] field, int i,int j)
    {//计算field[i][j]的特殊程度
        int count = 0;
        int height = field.length;//高度
        int width  = field[0].length();//宽度
        int num = 0;
        int k,m;
        for (k = i-1; k <= i+1 && k < height; ++k)
        {
            if (k < 0)
            {//越过边界
                k = i;
            }
            String tmp = field[k];
            for (m = j-1; m <= j+1 && m < width; ++m)
            {
                if (m < 0)
                {//越过边界
                    m = j;
                }
                if (k != i || m != j)
                {
                    num = tmp.charAt(m) - '0'; 
                    if (num >=max)
                    {//比最大值要大,肯定不行的,置为false标记
                        flag[k][m] = false;
                    }
                    count += num;
                }
            }
        }
        return count;
    }
    public static int countSpecialNumbers(String[] field,int A,int B)
    {
        int count = 0;
        int i,j,num = 0;
        for (i = 0; i < field.length; ++i)
        {
            for (j = 0; j < field[i].length(); ++j)
            {
                if (flag[i][j] != false)
                {//不是false标记
                    num = getSpecialNumber(field,i,j);
                    if (num >= A && num <= B)
                        ++count;
                }
                else 
                {//本身是false标记,则将其周围都置为false标记
                    markNoSpecial(field,i,j);
                }
            }
        }
        return count;
    }

    /**
     * @param args
     */
    public static void main(String[] args) 
    {
        String[] data = {"1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890",
                 "1234567890"};

       long begin = System.currentTimeMillis();
        height = data.length;
        width = data[0].length();
        flag = new boolean[height][width];
               int i,j;
        for (i = 0; i < height; ++i)
        {
            for (j = 0; j < width; ++j)
            {
                flag[i][j] = true;
            }
        }
        min = 3;
        max = 18;
        System.out.println(countSpecialNumbers(data,min,max));

    
        for (i = 0; i < 100000; i++)
        {
            countSpecialNumbers(data, min, max);
        }
        long end = System.currentTimeMillis();
        long time = end - begin;
        System.out.println("耗时"+time);

    }
}


复制代码
第二道算法题(500分)

题目要求:双倍超立方数是指一个正整数可以正好被拆分为两种不同的a^3+b^3的方式,其中a,b均为整数且0<a<=b。对于任何一个指定的 int n, 返回所有的小于等于n的双倍超立方数的个数。

复制代码
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;


public class TwiceSuperCubic 
{
    private static Map<Integer,Integer> cache = new Hashtable<Integer, Integer>();//键为立方和,值为次数
 
     public static int count(int n)
     {
            if (n<1 || n>1000000000) 
                return 0;
            int count = 0;
            int max = (int) java.lang.Math.pow(n, 1.0f/3.0f);
            for (int a = 1; a <= max; a++)
            {
                for (int b = a; b <= max; b++)
                {
                    int tmp = a * a * a + b * b * b;
                    if (cache.get(tmp) == null)
                    {
                        cache.put(tmp, 1);
                    }
                    else
                    {
                        int num = cache.get(tmp);
                        cache.put(tmp, num+1);
                    }
                }
            }
          
            Set<Entry<Integer,Integer>> entrys = cache.entrySet();
       
            for (Entry<Integer,Integer> entry : entrys)
            {
                int key = entry.getKey();
                int value = entry.getValue();
                if (key <= n && value==2)
                   ++count;
            }
            return count;
        }


    /**
     * @param args
     */
    public static void main(String[] args) 
    {
        long t1 = System.currentTimeMillis();
        int n = 1000000000;
        System.out.println(count(n));
        long t2 = System.currentTimeMillis();
        System.out.println(t2-t1);
        
    }

}
复制代码



本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2009/06/01/1494007.html,如需转载请自行联系原作者
目录
相关文章
|
Kubernetes 开发者 Docker
构建高效微服务架构:Docker与Kubernetes的协同
在当今快速迭代和部署应用程序的背景下,微服务架构已成为企业开发的首选模式。此文章通过深入分析Docker容器化技术和Kubernetes集群管理工具,探讨了如何利用这两者协同工作以构建和维护一个高效的微服务系统。我们将剖析Docker和Kubernetes的核心原理,并展示它们如何简化部署流程、提高系统的可伸缩性和可靠性。本文旨在为开发者提供一套实践指南,帮助其在云原生时代下,构建出既灵活又强大的后端服务。
238 3
|
安全 搜索推荐
下载软件别再被套路!教你避开流氓下载器的坑!
安装之前,可以看到界面中明显的提示:“使用360安全导航”、“ABC看图”,这两处旁边还有复选框,细心的你肯定知道要把这两个复选框去掉。
346 0
下载软件别再被套路!教你避开流氓下载器的坑!
|
数据格式 索引 Python
python学习之pandas库的使用总结
python学习之pandas库的使用总结
185 0
|
人工智能 监控 前端开发
你要了解的2种AI思维链
我们使用的AI助手,一般是经过了预训练和微调这2个步骤,尽管训练出的模型能回答许多通用类问题,但是在遇到复杂问题时还是束手无策。
你要了解的2种AI思维链
|
前端开发
|
算法
算法题 — 整数转二进制,查找其中1的数量
算法题 — 整数转二进制,查找其中1的数量
115 0
ECS服务保活和宕机启动
学习ECS服务保活、宕机启动的配置方法,并体验其实现效果。通过应用程序配置保活和宕机启动策略,可以确保关键服务在遇到各种问题时保持运行,从而为用户和企业提供稳定和可靠的服务。
|
存储 前端开发 开发者
Scss 基本使用(变量、嵌套)
Scss 基本使用(变量、嵌套)
561 0
Scss 基本使用(变量、嵌套)
|
程序员 C语言
|
监控 Java 分布式数据库
Flink/Hbase - Sink 背压100% 与 hbase.util.RetryCounter.sleepUntilNextRetry 异常分析与排查
Flink-hbase 任务 hbase.util.RetryCounter.sleepUntilNextRetry 堆栈问题分析与排查。
580 0
Flink/Hbase - Sink 背压100% 与 hbase.util.RetryCounter.sleepUntilNextRetry 异常分析与排查