一、输入一串数字,找到其中包含的最大递增数。
题目简介:
描述:输入一串数字,找到其中包含的最大递增数。
递增数是指相邻的数位从小到大排列的数字。
如: 2895345323,递增数有:289,345,23, 那么最大的递减数为345。
运行时间限制:无限制内存限制:无限制输入:
输入一串数字,默认这串数字是正确的,即里面不含有字符/空格等情况输出
:输出最大递增数样例输入:123526897215样例输出:2689
题目解答:
其实我觉得这个题目还是比较简单的,没有必要写那么复杂的代码。
定义两个变量,result保存每一轮的递增数,如123526897215中,第一轮result=1235,第二轮result=2689,第三轮result=15。
另外一个变量,maxResult保存迄今几轮递增数的最大值,初始化为0,,第一轮maxResult = 1235, 第二轮maxResult = 2689, 第三轮maxResult = 2689。
这是主体的思想,还有一个小问题,怎么求递增数?
这个其实以前也用到过,首先将result初始化为str[0]-’0′在本例中等于1,判断如果str[i+1]>str[i],那么result=result*10+str[i+1]-’0′=12,后面‘3’>’2′,所以result=result*10+‘3’-‘0’=12*10+3=123,以此类推。。。。。
完整代码请见:http://www.anycodex.com/blog/?p=210二、地铁换乘
题目简介:
描述:已知2条地铁线路,其中A为环线,B为东西向线路,线路都是双向的。经过的站点名分别如下,两条线交叉的换乘点用T1、T2表示。编写程序,任意输入两个站点名称,输出乘坐地铁最少需要经过的车站数量(含输入的起点和终点,换乘站点只计算一次)。
地铁线A(环线)经过车站:A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18
地铁线B(直线)经过车站:B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10 T2 B11 B12 B13 B14 B15
输入:输入两个不同的站名
输出:输出最少经过的站数,含输入的起点和终点,换乘站点只计算一次
输入样例:A1 A3
输出样例:3
题目解答:
如图所示(原谅懒惰的我。。。),定义两个关联数组,A,B使用每个站点的名字为键值,以i为值。如A[A1]=1, A[A2]=2。。。。。A[A18] = 20, 依次类推。
我们根据输入的两个站名在A线还是在B线,分为四种情况:
1、两站点均在A线上;
2、两站点均在B线上;
3、起点在A线,终点在B线;
4、起点在B线,终点在A线。
其中第一种最为简单,第二种情况次之,第三第四种情况最复杂。并且本质来说第三种和第四种情况应该是一样的,所以分析我们也只以第三种情况为例来分析。
第一种情况:
两个站点都在A线上,但由于A为环线,环线上求两点之间的最短距离问题
min = min(|A[Ai]-A[j]|+1, 20-|A[Ai]-A[j]|+1)
第二种情况:
两个站点都在B线上,我们可能理所当然的想到,这种情况就是下标只差再加一啦?事实上,不是这么简单的。因为有可能经过A线转一下,所需要乘坐的站数更少。比如从B5到B11站,直接全部坐B线的话,是需要坐九站,而如果在T1站开始换乘,坐到T2,再转成B线坐到B11站,那么这样就只需要8站。所以最小的站数为
min = min(只坐B线,换乘)
第三四种情况:
两个站点一个在A线,一个在B线,我们假设起点在A线,终点在B线。这种情况是肯定需要换乘的,而换乘只有两种情况,一种是先换到T1,另一种是换到T2。那么全程就分为两段,Ai ——> T1(T2) ————-> Bj,每一段的最小值实际上在第一第二种情况里面都有体现,所以
min = min(Ai ——> T1 ————-> Bj, Ai ——> T2 ————-> Bj)
完整代码请见:http://www.anycodex.com/blog/?p=207
三、麻将番数
麻将游戏越来越受到大家喜爱,也在网络上盛行。本题目是给定一组已经和牌的麻将,编写一个函数计算这组麻将的番数。为简化题目,假设麻将只有筒子和条子两种花型,能翻番的规则也只有以下三种,当一组牌中没有下述三种情况中的一种或多种,则这组牌为0番,每种番数是加的关系,例如一组牌既有卡2条又有四归一,则番数为3番。
1.卡2条为一番,即有一局牌是 1条2条3条;
2.四归一为两番,即有4张一样的牌(花色和数字都一样);
3.巧七对为两番,即一组牌恰好是7对牌;
一些约定:
1.一组已经和牌的麻将由多局牌组成,一局牌可以是一对牌、3张连续同样花色的牌、3张一样的牌、4张一样的牌。
2.一组已经和牌一般有14张牌,最多可以有18张牌(当有四归一的时候)。
一字符串表示已经和牌的麻将(由输入者保证,编程人员无需考虑没有和牌),如1T2T3T,4T5T6T,7T8T9T,1D2D3D,4D4D.
说明:
1.”1T”表示1条,T表示条子,前面跟数字几表示几条,数据范围1~9,输入者保证,编程无需考虑输入规范性;
2.”4D”表示4筒,D表示筒子,前面跟数字几表示几筒,数据范围是1~9, 输入者保证,编程无需考虑输入规范性;
3.每局牌之间由’,’隔开,输入者保证每局牌都是正确的且按照数字由小到大排序,编程人员无需判断每局牌的正确性;
4.一组牌以’.’号结束,由输入者保证,编程人员无需考虑是否有”.”号。
5.输入保证有番数的牌在一局中,编程人员无需考虑排序,即有番数的牌不会分散在多局牌中。
输出:
麻将的番数,整型类型。
样例输入: 1T2T3T,4T5T6T,7T8T9T,1D2D3D,4D4D.
样例输出: 1
题目解答:
其实这道题目很长,其实很简单啦,也不要说不会打麻将什么的就不会做,这个好像没多大关系吧?哈哈,我是会打麻将的啦,小小高手一个,哈哈。。
说这道题很简单,是因为所有的输入都由输入者来保证,不需要进行各种检查。我们以逗号作为分隔符,将用户输入的排分为n部分啦,n不可能大于10啦,定义一个数组a[10],记录用户输入n部分的每一部分的字符串的长度。如
1T2T3T,4T5T6T,7T8T9T,1D2D3D,4D4D.
我们可以得到a[0] = 6, a[1] = a[2] =a[3] = 6, a[4] = 4。
其实想想和牌,a数组里面的值只有三种可能,一对的那么a[i] = 4,一个就子(如一条二条三条)的那么a[i] = 6, 四归一的a[i] = 8。当然a[i] 可能= 0,我们就不考虑了。所以正对我们需要检测的三种番数情况:
1. 七对 《 ========》 a[i] = 4的个数等于7;
2. 四归一 《 ========》存在a[i] == 8;
3. 卡2条为一番,即有一局牌是 1条2条3条 《 ========》存在str[i] == ’1′ && str[i] ==’T’ && str[i] == ’2′ && str[i] ==’T’
完整代码请见:http://www.anycodex.com/blog/?p=214