leetcode 6.08-6.14

2020-06-11

剑指offer46 把数字翻译成字符串
102 二叉树的层序遍历

剑指offer46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”

提示：

$0 <= num < 2^{31}$

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

典型的动态规划，如果第$i-1$个字符和第$i$个字符不能翻译成字母$dp[i] = dp[i-1]$，否则$ dp[i] = dp[i-1]+dp[i-2]$

AC代码：

class Solution(object):
    def translateNum(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num < 10:
            return 1
        dp = [1]
        nums = str(num)
        if '10' <= nums[0:2] <= '25':
            dp.append(2)
        else:
            dp.append(1)
        for i in range(2, len(nums)):
            if '10' <= nums[i-1:i+1] <= '25':
                dp.append(dp[i-1]+dp[i-2])
            else:
                dp.append(dp[i-1])
        return dp[-1]

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

/ \
9 20
/ \
15 7
返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：传统的宽度优先搜索每次遍历处理一个节点；如果每次遍历处理当前层的所有节点，即可按层次输出。当前层所有节点其实就是当前队列中的节点，可用数学归纳法证明正确性。

AC代码（python没队列要自己实现，用C++写了）：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) {
            return ret;
        }
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            vector<int> tmp;
            size_t current_size = q.size();
            while (current_size > 0) {
                TreeNode* p = q.front();
                q.pop();
                tmp.push_back(p->val);
                if (p->left)  q.push(p->left);
                if (p->right) q.push(p->right);
                current_size--;
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};