西南交通建设集团股份有限公司网站,深圳市专业网站建设,网站系统繁忙是什么原因,网站首页排名seo搜索优化本期四道题全考过#xff0c;题解在网上也都搜得到。。。没有想法#xff0c;顺手水一份题解吧。 第一题#xff1a;奇偶排序 给定一个存放整数的数组#xff0c;重新排列数组使得数组左边为奇数#xff0c;右边为偶数。 输入描述#xff1a;第一行输入整数n。(1n题解在网上也都搜得到。。。没有想法顺手水一份题解吧。 第一题奇偶排序 给定一个存放整数的数组重新排列数组使得数组左边为奇数右边为偶数。 输入描述第一行输入整数n。(1n1000)表示数组大小第二行输入n个整数a.(1n100) 输出描述输出重排之后的数组。 示例 示例输入6 3 34 67 89 90 58输出3 67 89 34 90 58分析
超级大水题直接遍历一遍数组把奇数和偶数分开成两个数组最后再把两个数组返回即可时间复杂度 。
如果想加点花比如降低空间复杂度上面需要借助外部空间存储奇数和偶数数组可以在原数组遍历如果遇到奇数就和它前面的数交换位置直到前面为空或不是偶数位置。类似冒泡排序时间复杂度 很没必要。
本题因为要求奇数间和偶数间的相对位置不变所以不能使用不稳定的排序方法比如快排。
参考代码
n int(input().strip())
arr [int(item) for item in input().strip().split()]
odd list()
even list()
for i in arr:if i%2: odd.append(i)else: even.append(i)
print(*odd, *even) 第二题小艺改编字符串 已知字符串str。添加至少多少字符可以使得str变成回文串。 输入描述输入字符串s.(1len(str)100000) 输出描述输出最小需要添加字符的数量。 示例 示例输入abab输出 1 分析
很久以前考过不过还是值得一说。思路还是动态规划好像递归也可以没有试过。
问哥觉得关于字符串的动态规划常常有点抽象不太好理解所以保险起见我们还是画图来看。
首先对于任意一个长度大于 1 的字符串长度等于 1 的字符串本身就是回文串不需要添加字符如果我们观察它的左右两端只有下面两种可能
最左端和最右端的字符相同最左端和最右端的字符不同。
我们可以用 和 表示左右两端字符串的下标用 表示从下标 到 的字符串如下图所示 然后对于左右端字符相同的字符串我们可以把它们剥掉得到一个新的子串 很显然只要子串 是回文串那么原来的 必定也是回文串。所以原问题就转变成一个子问题需要添加多少字符可以使得子串 变成回文串 而对于左右端字符不同的字符串我们有两种选择
如果子串 是回文串我们可以在左边添加一个和最右端相同的字符使原字符串 变成回文串如果子串 是回文串则我们也可以在右边添加一个和最左端相同的字符使原字符串 变成回文串。那么只要在这两种选择中取较小的作为答案即可。
于是动态转移过程就很清楚了。我们定义一个二维数组 表示需要添加多少字符使得字符串 变成回文串则可得状态转移方程如下 和 分别表示字符串 左右两端的字符
如果 则 如果 则
先给个递归的写法就是直接把上面的转移公式套进来。
参考代码一
def fun(s):n len(s)if n 1: return 0i, j 0, n-1if s[i] s[j]: return fun(s[i1:j])return min(fun(s[i:j]), fun(s[i1:j1]))1
s input().strip()
print(fun(s))
但是因为字符串长度达到1e5递归极有可能超时。
但是递归给我们的顺序值得参考所有递归到最终的字符串长度必定为 1 或 0 空字符串。
所以如果我们使用动态规划原字符串的答案必须按子字符串的长度从小到大递推过来。也就是说我们必须先得到所有长度为 1 或 0 的子串的答案再递推到长度为 2 的然后是长度为 3 的。。。直到长度等于原字符串。
所以我们在传统的 双循环中必须加一个变量 用来表示子字符串的长度。而一旦 的长度确定了所以还是双循环。循环次数也很好计算就是所有子串数量之和
时间复杂度是 但是因为除以 2所以计算量级还是 1e9勉强可以接受。
参考代码二
s input().strip()
n len(s)
dp [[0]*n for _ in range(n)]
for k in range(1, n):for i in range(n - k):j i kif s[i] s[j]: dp[i][j] dp[i1][j-1]else: dp[i][j] min(dp[i1][j], dp[i][j-1]) 1
print(dp[0][n-1]) 第三题公司新表 公司里为了凸显公司的特性。安装了一个n进制表。已知新的表的时间是”H:M”。时间合法的定义为H23 M59。时间有多少种进制定义的方式依次打印出来。如果有无数种解输出”-1”不存在输出”0”。 输入描述输入一行字符串a:b形式。 输出描述输出答案。 示例 示例输入11:20输出3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22分析
13期考过。
不难但是因为要分析字符串既抽象又繁琐所以本题参考代码不想给了问哥写得很繁琐大部分时间浪费在这题看到就烦 。
简单说说思路先把给定的字符串按冒号一分为二左边为小时数右边为分钟数。
先特判什么样的情况是有无数种解呢因为字符串中可以含有字母那么假定字母代表了一个数字只要不进位字符串长度为 1就可以代表无数种解。比如一个字母 A可以代表11进制以上的所有进制因为 A 就代表了10按照顺序是合法的小时小于24或分钟小于60数。同样很显然如果代表小时的一个字母表示了24以上的十进制数字或代表分钟的一个字母表示60以上的十进制数字则必定是没有解返回 0。
而如果进了一位答案必定有限比如 11最多只能代表22进制该进制中11代表十进制的23。所以只要检查分割后的代表小时和分钟的字符串的长度小于等于1且代表十进制数字小于24或小于60就必定是无数种解直接返回-1。
然后就是穷举了从小时和分钟数所能代表的最小进制开始比如字符串AB不可能代表12进制及以下的进制。然后循环加一每次计算小时和分钟翻译成十进制是否小于24和小于60。知道不满足此条件为止。
如果一个都没找到很显然直接返回 0。否则就把所有答案打印出来即可。 第四题选择客栈 丽江河边有 n 家很有特色的客栈客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰总共 k 种用整数 0 ~ k-1 表示且每家客栈都设有一家咖啡店每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游他们喜欢相同的色调又想尝试两个不同的客栈因此决定分别住在色调相同的两家客栈中。晚上他们打算选择一家咖啡店喝咖啡要求咖啡店位于两人住的两家客栈之间包括他们住的客栈且咖啡店的最低消费不超过 p 。他们想知道总共有多少种选择住宿的方案保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。 输入描述共n1 行。第一行三个整数 n ,k ,p 每两个整数之间用一个空格隔开分别表示客栈的个数色调的数目和能接受的最低消费的最高值接下来的 n 行第 i1 行两个整数之间用一个空格隔开分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。 输出描述一个整数表示可选的住宿方案的总数。 示例 示例输入5 2 3 0 5 1 3 0 2 1 4 1 5输出3分析
15期考过。还是动态规划可以参考我以前的题解详细记录了思考过程写得可能有些繁琐这里不再赘述了。
