由一道百度之星题目写起 谈谈编程中的分类的思想

简介:

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛。他所考试的题目,全部都是算法的题目。

鄙人虽然是一个非主流的.net程序员,在工作之余,喜爱算法。 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用。 更重要想谈一谈算法中的分治算法。

首先,题目是那样的:

请编写程序,找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。

对一个正整数n,如果n在数据文件中某行的两个正整数(假设为A和B)之间,即A<=n<=B或A>=n>=B,则n属于该行;如果n同时属于行i和j,则i和j有重叠区间;重叠区间的大小是同时属于行i和j的整数个数。

例如,行(10 20)和(12 25)的重叠区间为[12 20],其大小为9;行(20 10)和(12 18)的重叠区间为[10 12],其大小为3;行(20 10)和(20 30)的重叠区间大小为1。

输入数据:程序读入已被命名为input.txt的输入数据文本文件,该文件的行数在1到1,000,000之间,每行有用一个空格分隔的2个正整数,这2个正整数的大小次序随机,每个数都在1和2^32-1之间。(为便于调试,您可下载测试input.txt文件,实际运行时我们会使用不同内容的输入文件。) 输出数据:在标准输出上打印出输入数据文件中最大重叠区间的大小,如果所有行都没有重叠区间,则输出0。

评分标准:程序输出结果必须正确,内存使用必须不超过256MB,程序的执行时间越快越好。

这是一个很简单的算法(初中的不等式知识),可以说球最大子串的一个但里面的将一个分类的思想体现的淋漓尽致。

老样子,还是第一步,分析解决问题的思路。

 一个区间是[a,b](a<b),一个区间是[c,d](c<d).    

第一步如果b<c的时候,其相连的区间是0.

第二步如果d<a的时候,其相连的区间是0。

第三步 如果a,b是c→d子链。其相连的区间是b-a+1

第四步 如果c,d是a→b子链。其相连的区间是c-d+1

第五步 如果相交的 其相连的区间是b-c+1

第六步 如果是相交 其相连的区间是d-a+1

 

那思路写出来了,源代码如下:


 1             //string 的变量
 2             string str = string.Empty;
 3             //string到 泛型数组
 4             List<string> strs=new List<string>();
 5             int i = 0;
 6             while (i<3)
 7             {
 8                 Console.WriteLine("请你输入的下列格式");
 9                 Console.WriteLine("10 20(前面的数字必须小于后面的数字)");
10                 str = Console.ReadLine();
11                 strs.Add(str);
12                 i++;
13             }
14             int count = 0;
15             int[] counts = new int[i];
16             for (int j = 0; j < strs.Count; j++)
17             {
18                 for (int k = j+1; k < strs.Count; k++)
19                 {
20                     int temp1 = Convert.ToInt32(strs[j].Split(' ')[0]);
21                     int temp2 = Convert.ToInt32(strs[j].Split(' ')[1]);
22                     int temp3 = Convert.ToInt32(strs[k].Split(' ')[0]);
23                     int temp4 = Convert.ToInt32(strs[k].Split(' ')[1]);
24                        //第一种的方法
25                     if (CheckInt(temp3,temp2)<0)
26                     {
27                         counts[count] = 0;
28                         count++;
29                     }
30                      //第二种的方法
31                     else if (CheckInt(temp4,temp1)>0)
32                     {
33                         counts[count] = 0;
34                         count++;
35                     }
36                      //第三种的方法
37                     else if (CheckInt(temp2, temp4)>=1&&CheckInt(temp3,temp1)>=1)
38                     {
39                         counts[count] = CheckInt(temp1, temp2);
40                         count++;
41                     }
42          //第四种的方法
43                     else if (CheckInt(temp2, temp4)<=1 && CheckInt(temp3, temp1) <= 1)
44                     {
45                         counts[count] = CheckInt(temp3, temp4);
46                         count++;
47                     }
48            //第五种的方法
49                     else if (CheckInt(temp2, temp4) >=1 && CheckInt(temp3, temp1) <= 1)
50                     {
51                         counts[count] = CheckInt(temp3, temp2);
52                         count++;
53                     }
54                     else if (CheckInt(temp2, temp4) <=1 && CheckInt(temp3, temp1) >= 1)
55                     {
56                         counts[count] = CheckInt(temp1, temp4);
57                         count++;
58                     }           
59                 }
60             }
61                //打印情况
62             for (int j = 0; j < counts.Length; j++)
63 64                 Console.WriteLine(counts[j]); 
65             }
66             Console.ReadKey();

               public static int CheckInt(int a,int b)               {                return b - a + 1;                }

 checkInt方法用来返回两个区间的之差。

 我这道题目,考虑各种的情况。 应用了分类的情况。   这个分类的思想了不光在这个题目中有了,可以说在编程过程中遍地都是。

先不来说,那个题目好吗?你看看了,编程的最基本的三种结构,顺序,选择,循环。这个选择中的无论是if.........else  结构,还是switch..................case 结构。这个结构,就是分类思想。

在比如项目中,一个登录的时候,  你要考检测用户名是否存在,  还要检测登录是否成功的情况,  如果登录不成功的情况,就跳转不同的页面。如果登录成功,又跳转到那个页面。 等等多种情况,都是要你考虑各种各样的情况。

   这就是我的一点点的感悟。

 

目录
相关文章
|
算法 Java
这是3位同学写的同一段代码逻辑
**问题**:提取“整数订单号”隐藏的机房路由规则,看一下我们这几位同学的实现,槽点自寻: **规则**:订单号后四位隐藏了机房路由规则,路由规则就是订单号的倒数第4、3位和倒数第2、1位的排列顺序交换一下,例如:订单号“1234”,路由规则就是“3412”。 - **A同学** (浪费公
4745 0
|
10天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1210 5
|
9天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1172 87
|
9天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1767 12
|
19天前
|
人工智能 运维 安全
|
2天前
|
资源调度
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
230 127

热门文章

最新文章