京东数据开发编程题2题AC代码
1.最优打印策略 动态规划
把大写和小写作为两个状态
输入是大写字母时：
1.当前是小写状态 = min(上一个输入是小写状态，按shift+字母(2个按键)，上一个是大写状态，按capslock+字母(2个按键))
2.当前是大写状态 = min(上一个输入是小写状态，按capslock+字母(2个按键)，上一个是大写状态，字母(1个按键))
输入是小写字母同理
n = int(input()) s = input() dp = [[0,0] for i in range(n)] if 'A' <= s[0] <= 'Z': dp[0][0] = 2 dp[0][1] = 2 else: dp[0][0] = 1 dp[0][1] = 2 for i in range(1,n): if 'A' <= s[i] <= 'Z': dp[i][0] = min(dp[i-1][0] + 2,dp[i-1][1] + 2) dp[i][1] = min(dp[i-1][0] + 2,dp[i-1][1] + 1) else: dp[i][0] = min(dp[i-1][0] + 1,dp[i-1][1] + 2) dp[i][1] = min(dp[i-1][0] + 2,dp[i-1][1] + 2) print(min(dp[-1][0],dp[-1][1]))2.合唱排队
计算前i个身高的最大值，存到一个N+1长数组qianzhui里
计算后i个身高的最小值，存到一个N+1长数组houzhui里
数组[i]代表前i个人中的身高最大值，或者后N-i个人中身高最小值
现在要找到符合题目要求的res个切分点，这就要求一个切分点前面的所有人中的身高最高的 ≤ 这个切分点后面身高最矮的
遍历一遍即可 O(N)
N = int(input()) H = list(map(int,input().split())) houzhui = [1000000000000] * N houzhui[-1] = H[-1] qianzhui = [0] * N qianzhui[0] = H[0] for i in range(N-2,-1,-1): if H[i] < houzhui[i+1]: houzhui[i] = H[i] else: houzhui[i] = houzhui[i+1] for i in range(1,N): if H[i] > qianzhui[i-1]: qianzhui[i] = H[i] else: qianzhui[i] = qianzhui[i-1] houzhui.append(0) qianzhui.insert(0,0) res = 0 for i in range(N+1): if qianzhui[i] <= houzhui[i]: res += 1 print(res)
查看15道真题和解析
