文档介绍：招商银行第一届编程马拉松试题
2015 年 12 月 21 日 – 12 月 28 日
算法类
1、可变数组求和（30 分）
给定一个整数数组，sum_range(m, n) 函数给出指定下标 m, n 之间的数值之和（m<=n）
update(idx, value) 函数修改第 idx 位的数值为 value
nums = [2, 5, 8, 9]
sum_range(1, 3) -> 22
update(2, 1)
sum_range(1, 3) -> 15
要求：
• 你的代码需要定义一个 NumArray 类，它包括以上两个函数
• 数组只能通过 update 函数更新
1 / 16
2、给出数组计数结果（30 分）
给定一个整数数组 nums，你需要返回一个 等长的 counts 数组，count[i] 的取值是
nums[i] 右侧比它小的数值的个数。
nums = [3, 1, 8, 4, 2]
3 的右侧有 2 个数字比它小（1，2）
1 的右侧有 0 个数字比它小
8 的右侧有 2 个比它小（4，2）
4 的右侧有 1 个比它小（2）
2 的右侧有 0 个比它小
因此，counts 数组为 [2, 0, 2, 1, 0]
3、字符串求值运算（40 分）
给定一个由数字 0-9 组成的字符串 S，给定一个数值 N，请找出该字串内所含数字的所有
组成 N 的可能组合。
注意： 只能使用加、减、乘三种操作符号。
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
“3456237490”, 9191 -> ?
2 / 16
4、获得最多奖金（40 分）
给定 n 个小球，balls[n]，位置从 0 到 n-1 标定，每个球上都标定了一个正整数，用数组
nums[n] 表示。现在，你需要选定一个小球将它移除，于此同时，你将获得以它为中心、
相邻三个小球的数值的乘积值所对应的奖金。假设你选定的是第 k 个位置的小球，那么你获
得的奖金为 num[k-1] * num[k] * num[k+1]。
你的任务是，找出可能获得的最多的奖金值。
约束：
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
• nums[-1] = nums[n] = 1。这些特殊位置的球不存在，也不能被移除。
给定数组 [3, 1, 5, 8]
返回值 167
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
3 / 16
5、移除无效括号（40 分）
给定一个字符串，它包含了小括号字符。请你移除最少的小括号字符，使得剩余的小括号字
符能够成对匹配。
注意，字符串中可能包含其他的字符。
“( ) ( ) ) ( )" -> [“( ) ( ) ( )", “( ( ) ) ( )"]
“( a ) ( ) ) ( )" -> [“( a ) ( ) ( )", “(a ( ) ) ( )"]
“) (" -> [""]