第一题 两整数之和
题目
解题思路
本题要求咱们实现加法
失去了编写代码过程中最根底的运算符
咱们只能在更底层的实现中寻求帮忙
在数电中咱们学过半加器电路计算加法
半加器电路是指对两个输出数据位相加，输入一个后果位和进位，没有进位输出的加法器电路。 是实现两个一位二进制数的加法运算电路。半加器是通过异或门来具体实现的。凑巧，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 的长度。应用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度。