0070.climbing-stairs.md

0070.Climbing-Stairs

Description

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Tags: Math, String

题意

给你两个二进制串，求其和的二进制串。

题解

思路1

题意是爬楼梯，每次你只能爬一步或者两步，问到顶层共有多少种方案。我们假设到顶层共有 f(n) 种，那么 f(n) = f(n - 1) + f(n - 2) 肯定是成立的，意思就是我们迈向顶层的最后一步是在倒数第一级台阶或者在倒数第二级台阶。算法我对空间复杂度进行了优化，因为在迭代过程中只需要两个变量即可。

func climbStairs1(n int) int {
    if n <= 2 {
        return n
    }
    aux := make([]int, n+1)
    aux[1] = 1
    aux[2] = 2
    for i := 3; i <= n; i++ {
        aux[i] = aux[i-1] + aux[i-2]
    }
    return aux[n]
}

思路2

优化后： 只有2个变量

```go func climbStairs(n int) int { x, y := 1, 1 for i := 1; i < n; i++ { x, y = y, x+y } return y }

```

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm