0%

剑指Offer算法题-求和

Posted on In

####题目：
求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及三目运算符

通常求 1+2+…+n 除了用公式 n(n+1)/2 之外，无外乎循环和递归两种思路。由于已经明确限制 for 和 while 的使用，循环已经不能再用了。同样，递归函数也需要用 if 语句或者条件判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。

####思路 1
利用函数指针实现递归。
由于不能用 if 语句来终止递归，但是我们可以定义两个函数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况。然后在根据情况在两个函数二选一，可以这么做，把递归过程中传进来的 n 转成 bool 类型，非 0 的话就是 true，然后再把 bool 类型转成 Int 类型，也就是 1，同时若 n 为 0，先把 n 转成 bool 类型在转回来还是 0，也就是相当于说可以把非 0 的 n 转成 1，0 还是 0.这样我们可以把两个函数放到一个数组里，根据 n 转换之后的值去数组里取函数就行了.

代码实现
1
func sumTeminator(number:UInt) -> UInt {
2
    return 0
3
}
4
func sum(number:UInt) -> UInt {
5
    let funcs = [sumTeminator,sum]
6
    let isTeminator = Bool(truncating: NSNumber(value: number - 1))
7
    let funcIndex = Int(truncating: NSNumber(value: isTeminator))
8
    let sumFunc = funcs[funcIndex]
9
    return number + sumFunc(number - 1)
10
}
11
print(sum(number: 100))

####思路 2
利用 KVC 里的 sum 进行求和
首先初始化一个 0 到 n 的数组，然后利用 KVC 里的 sum 进行求和,初始化数组用到了 Swift 的 Stride 这个函数。

代码实现
1
func sum1(number:UInt) -> UInt {
2
    let array = Array(stride(from: 0, to: number + 1, by: 1))
3
    let sum = (array as NSArray).value(forKeyPath: "@sum.integerValue") as! UInt
4
    return sum
5
}
6
print(sum1(number: 100))