出现过最多次数的数
题解:由于输入的整数在范围较小,直接用数组记录每个数出现的次数,从左扫到右,出现次数最多的数即为答案。
1 |
|
ISBN号码
题解:输入识别码后遇到 ‘-’ 便跳过,然后计算总和,再模11,注意因为是模11,所以还要注意X的情况。
1 |
|
最大的矩形
题解:这道题以前也碰到过,好像是维护一个left[]和right[]数组记录每个矩形左右不小低于它的坐标然后瞎搞反正一直也没理解那个做法到现在也还不会(丢人),这道题还有二维升级版,讲的是市长圈地的故事。本来觉得这道题凉了然而看到数据范围只有1000和10000就恶向胆边生决定直接暴力。因为高都是整数,所以就直接枚举每一种可能的高,然后更新最大值。
1 |
|
有趣的数
题解:看到这题第一反应是递推,就是n从x可以推出x+1的值,模拟了从4推到5和从5推到6,不要慌问题很大 ,首先要确定增加的那个数是几,然后还要位置选择,注意前导0,注意判重,凉了凉了,不行不行。然后又开始瞎猜:首先,01和23之间的位置并不相影响,那么我们可以将其分为两组。重要的是两组各组内两个数的位置,而组间的位置可以随便安排。显而易见的是第一个数字一定是2,那么在长度为n的情况下,假设我们给01安排了x个位置,那么这就有Cxn-1种情况,然后在x个位置里0的个数取值范围为[1,x-1],n-x个位置中2个数的取值范围为[1,n-x-1],所以在长度为n的情况下有趣的数个数有Cxn-1
组合数打表计算即可,注意取模。
1 |
|
I’m stuck!
题解:题目一眼看成了I’m suck!迷宫问题,麻烦的是每个一点的行走方式不同,这就可能形成从我们起点出发能到达终点,但是不能从终点原路返回到起点请。要找的点是从起始点可以到但是不可以从此方格到终点的位置。首先,我们用bfs根据规则来搜索从起点出发可以到达的位置,如果终点没被访问到,则直接打印“I’m stuck!”。我们依次从可以被起点访问到的点出发,看它能不能访问到终点,并在过程中记录访问路径,一旦这个点能访问到终点,则沿路的点都被打上可达的标记,不用做为出发点再次考察。这个过程由dfs实现比较方便。最后输出符合标准的点的个数。
1 |
|