剑指Offer II --- 2021/9/6

超、凢脫俗 2022-09-10 08:14 114阅读 0赞

### 目录 ###

*  剑指 Offer II 048. 序列化与反序列化二叉树
 *  剑指 Offer II 049. 从根节点到叶节点的路径数字之和
 *  剑指 Offer II 063. 替换单词
 *  剑指 Offer II 061. 和最小的 k 个数对

# 剑指 Offer II 048. 序列化与反序列化二叉树 #

[剑指 Offer 37. 序列化二叉树][Offer 37.]

# 剑指 Offer II 049. 从根节点到叶节点的路径数字之和 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16]  
分析：  
  深度优先搜索找到根结点到叶子结点的所有路径，保存下来再求和。  
代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    private:
        vector<int> res;
        vector<int> temp;
        
        void dfs(TreeNode* root) { 
            if(root) { 
                temp.push_back(root->val);
                if(root->left == NULL && root->right == NULL) { 
                    long long t = 0, base = 1;
                    for(int i = temp.size() - 1; i >= 0; i--) { 
                        t += base * temp[i];
                        base *= 10;
                    }
                    res.push_back(t);
                }
                dfs(root->left);
                dfs(root->right);
                temp.pop_back();  //回溯
            }
        }
    public:
        int sumNumbers(TreeNode* root) { 
            dfs(root);
            int sum = 0;
            for(int x : res) { 
                sum += x;
            }
            return sum;
        }
    };

# 剑指 Offer II 063. 替换单词 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
分析：  
  将字典按照字符串长度从小到大排序，然后暴力枚举。  
代码：

class Solution { 
    public:
        static bool cmp(string x, string y) { 
            return x.size() < y.size();
        }
        string replaceWords(vector<string>& dictionary, string sentence) { 
            string res = "", word;
            vector<string> words;
            istringstream ss(sentence);
            while(ss >> word) { 
                words.push_back(word);
            }
            sort(dictionary.begin(), dictionary.end(), cmp);
            for(string x : words) { 
                bool flag = true;
                for(string y : dictionary) { 
                    if(x.find(y) == 0) { 
                        res += y;
                        flag = false;
                        break;
                    }
                }
                if(flag) { 
                    res += x;
                }
                res += " ";
            }
            res.pop_back();
            return res;
        }
    };

# 剑指 Offer II 061. 和最小的 k 个数对 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
分析：  
  小根堆。  
代码：

class Solution { 
    public:
        struct cmp { 
            bool operator()(const pair<int, int>& x, const pair<int, int>& y) { 
                return x.first + x.second > y.first + y.second;
    	    }
         };
    
        vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { 
            vector<vector<int>> res;
            priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> que;
            int n = nums1.size() < k ? nums1.size() : k;
            int m = nums2.size() < k ? nums2.size() : k;
            for(int i = 0; i < n; i++) { 
                for(int j = 0; j < m; j++) { 
                    que.push(make_pair(nums1[i], nums2[j]));
                }
            }
            n = que.size() < k ? que.size() : k;
            for(int i = 0; i < n; i++) { 
                pair<int, int> p = que.top();
                vector<int> temp;
                temp.push_back(p.first);
                temp.push_back(p.second);
                res.push_back(temp);
                que.pop();
            }
            return res;
        }
    };

[Offer 37.]: https://blog.csdn.net/Cyril_KI/article/details/119106309
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8b224b25030f44edbc0d1f80e5732767.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/02eed7bf657148d0afe1c15e2641c057.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/6dd5289aa68a4a6098be1105221a7718.png