20200510
Plan
leetcode 每日一题
Notes
今天做了三道题，都比较简单，之后打算从中等难度开始刷
- 字符串相加 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意： num1 和num2 的长度都小于 5100. num1 和num2 都只包含数字 0-9. num1 和num2 都不包含任何前导零。
解法：为了处理方便，先把短的字符串前面补0和长的字符串长度相同，然后从后往前挨个相加放入新字符串就可以。
- 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
解法：刚开始用递归写的，比较容易超时，后来就直接用数组记录就可以了。对第n阶台阶，可以从n-1爬1个台阶上来，或者从n-2爬两个台阶上来。那么dp[n]=dp[n-1]+dp[n-2],初始化dp[1]=1,dp[2]=2.循环即可
- 用队列实现栈 使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
解法：这个也比较简单，直接用一个数组模拟栈，定义一个size记录当前的元素个数，定义index记录当前栈顶元素的位置即可。