乐趣区

关于golang:golangleetcode中级两整数之和逆波兰表达式求值

jiezi

第一题 两整数之和

题目

解题思路

本题要求咱们实现加法

失去了编写代码过程中最根底的运算符
咱们只能在更底层的实现中寻求帮忙

在数电中咱们学过半加器电路计算加法

半加器电路是指对两个输出数据位相加，输入一个后果位和进位，没有进位输出的加法器电路。是实现两个一位二进制数的加法运算电路。半加器是通过异或门来具体实现的。

凑巧，golang 中 ^ 算符作为二元运算符的时候也提供了异或性能
能够发现，对于整数 a 和 b：

在不思考进位的状况下，其无进位加法后果为 a⊕b。
而所有须要进位的位为 a & b，进位后的进位后果为(a & b) << 1。

代码实现

func getSum(a, b int) int {
    for b != 0 {// 因为 b 存储低位的进位信号，将 b 设为循环终止条件
        c := uint(a&b) << 1
        a ^= b
        b = int(c)
    }
    return a
}

复杂度剖析

工夫复杂度：O(log(max_int))，其中咱们将执行位运算视作原子操作。

空间复杂度：O(1)。

第二题 逆波兰表达式求值

题目

思路

逆波兰表达式的长处为咱们的解答提供了思路

应用栈实现求值计算

代码

func evalRPN(tokens []string) int {stack := []int{}
    for _, token := range tokens {
        // 读取字符
        val, err := strconv.Atoi(token)
        if err == nil {
            // 转换成数字胜利，是数字
            stack = append(stack, val)
        } else {
            // 是算符，取出两个数计算并将后果入栈
            num1, num2 := stack[len(stack)-2], stack[len(stack)-1]
            stack = stack[:len(stack)-2]
            switch token {
            case "+":
                stack = append(stack, num1+num2)
            case "-":
                stack = append(stack, num1-num2)
            case "*":
                stack = append(stack, num1*num2)
            default:
                stack = append(stack, num1/num2)
            }
        }
    }
    return stack[0]
}

复杂度剖析

工夫复杂度：O(n)，其中 n 是数组 tokens 的长度。须要遍历数组 tokens 一次，计算逆波兰表达式的值。

空间复杂度：O(n)，其中 n 是数组 tokens 的长度。应用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度。

退出移动版