6. 交叉队列
题目
- 描述：给出三个队列 s1，s2，s3 ，判断 s3 是否是由 s1 和 s2 交叉得来。 如：s1 为 aabcc ， s2 为 dbbca。 当 s3 为 aadbbcbcac 时，返回 true（即将 s1 拆成三部分： aa，bc，c 分别插入 s2 对应位置） 否则返回 false。
- 输入：aabcc,dbbca,aadbbcbcac
- 输出：true
思路
先判断s1、s2、s3队列长度的关系，如果len(s1) + len(s2) != len(s3)，那么肯定为false。接着按顺序判断s3队列的每个数字是否在s1或s2队列中，并且注意s1、s2队列的数字要按顺序依次进行比较。因为涉及s1和s2队列的优先级问题（哪个队列先和s3比较），所以要更换优先级顺序，因此需要判断两次。
代码
import sys
for line in sys.stdin:
[s1, s2, s3] = line.strip().split(',')
if len(s1)+len(s2) != len(s3):
print('false')
exit(0)
for i in range(2):
s1_index = s2_index = 0
for num in s3:
if s1_index < len(s1) and num == s1[s1_index]:
s1_index += 1
elif s2_index < len(s2) and num == s2[s2_index]:
s2_index += 1
else:
if i == 1:
print('false')
break
else:
print('true')
break
s1, s2 = s2, s1
7. 第一个缺失正数
题目
- 描述：给出一个无序的数列，找出其中缺失的第一个正数，要求复杂度为 O(n) 如：[1,2,0]，第一个缺失为3。 如：[3,4,-1,1]，第一个缺失为2。
- 输入：1,2,0
- 输出：3
思路
从数字1开始判断是否在数列中，若在数列中就加1继续判断，反之即为第一个缺失的正数。
代码
import sys
for line in sys.stdin:
s = line.strip.split(',')
num = '1'
while True:
if num in s:
num = str(int(num)+1)
else:
print(num)
break
8. 最少交换次数
题目
- 描述：给出一个无序数列，每次只能交换相邻两个元素，求将原数列变成递增数列的最少交换次数。 如：数列：2,3,1，交换3和1后变成：2,1,3；交换1和2之后变成：1,2,3。总共交换2次。
- 输入：逗号隔开的正整数数列
- 输出：正整数
思路
冒泡排序，在每次交换的时候交换次数加1即可。
代码
import sys
for line in sys.stdin:
s = line.strip().split(',')
cnt = 0
for i in range(len(s)-1):
for j in range(len(s)-i-1):
if int(s[j]) > int(s[j+1]):
s[j], s[j+1] = s[j+1], s[j]
cnt += 1
print(cnt)
9. 移除K位得到最小值
题目
- 描述：有一行由 N 个数字组成的数字字符串，字符串所表示的数是一正整数。移除字符串中的 K 个数字，使剩下的数字是所有可能中最小的。假设：字符串的长度一定大于等于 K；字符串不会以 0 开头。
- 输入：一行由 N 个数字组成的数字字符串（0 < N < 20），和一个正整数 K（K < N），两个数据由空格隔开，如：1432219 3。
- 输出：移除 K 位后可能的最小的数字字符串。 如 1432219 移除 4, 3, 2 这 3 个数字后得到 1219，为所有可能中的最小值。
思路
以移除K位后的最小值长度为循环次数，然后遍历相应范围的字符串依次从高位到低位找出各位的最小值。
代码
import sys
for line in sys.stdin:
[s, K] = line.strip().split()
final_lenth = len(s)-int(K)
final_num=[]
start = 0
for n in range(final_lenth):
final_num.append('9')
for index in range(start, int(K)+n+1):
if int(final_num[n]) > int(s[index]):
final_num.pop()
final_num.append(s[index])
min_index = index
start = index+1
minimum = ''
for i in final_num:
minimum +=i
minimum = int(minimum) # 去除高位的0
print(str(minimum))
10. 爬楼梯
题目
- 描述：在你面前有一个n阶的楼梯，你一步只能上1阶或2阶。 请问计算出你可以采用多少种不同的方式爬完这个楼梯。
- 输入：一个正整数，表示这个楼梯一共有多少阶
- 输出：一个正整数，表示有多少种不同的方式爬完这个楼梯
思路
此题的答案为缺少第一项的斐波那契数列（Fibonacci Sequence），因此可直接用递归来解。只是递归的执行效率有点低。
代码
import sys
for line in sys.stdin:
n = line.strip()
def climb(n):
if n<2:
return 1
else:
return climb(n-1)+climb(n-2)
print(climb(int(n)))