leetcode解题思路分析（一百五十）1305 - 1312 题

本文主要是介绍leetcode解题思路分析（一百五十）1305 - 1312 题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1305. 两棵二叉搜索树中的所有元素
      给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.

中序遍历之后，采用归并思想遍历二者。

/*** 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 {void inorder(TreeNode *node, vector<int> &res) {if (node) {inorder(node->left, res);res.push_back(node->val);inorder(node->right, res);}}public:vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {vector<int> nums1, nums2;inorder(root1, nums1);inorder(root2, nums2);vector<int> merged;auto p1 = nums1.begin(), p2 = nums2.begin();while (true) {if (p1 == nums1.end()) {merged.insert(merged.end(), p2, nums2.end());break;}if (p2 == nums2.end()) {merged.insert(merged.end(), p1, nums1.end());break;}if (*p1 < *p2) {merged.push_back(*p1++);} else {merged.push_back(*p2++);}}return merged;}
};

1306. 跳跃游戏 III
      这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。注意，不管是什么情况下，你都无法跳到数组之外。

DFS即可。

class Solution {
private:bool bFind;
public:bool canReach(vector<int>& arr, int start) {bFind = false;int size = arr.size();vector<bool> reach(size, false);reachNext(reach, arr, start);return bFind;}void reachNext(vector<bool>& reach, vector<int>& arr, int pos){int pos1 = 0, pos2 = 0;if (arr[pos] == 0){bFind = true;return;}if (bFind || reach[pos])return;reach[pos] = true;pos1 = pos + arr[pos];pos2 = pos - arr[pos];if (pos1 < arr.size())reachNext(reach, arr, pos1);if (pos2 >= 0)reachNext(reach, arr, pos2);}
};

1307. 口算难题
      给你一个方程，左边用 words 表示，右边用 result 表示。你需要根据以下规则检查方程是否可解：如果方程可解，返回 True，否则返回 False。

本题无法避免遍历，亮点在于如何寻找优秀的剪枝。这里的方法其实是把表达式合并，让每个字母只有一个参数，然后根据倍率优先级进行一些不可能出现的值的剪枝。

using PCI = pair<char, int>;class Solution {
private:vector<PCI> weight;vector<int> suffix_sum_min, suffix_sum_max;vector<int> lead_zero;bool used[10];public:int pow10(int x) {int ret = 1;for (int i = 0; i < x; ++i) {ret *= 10;}return ret;}bool dfs(int pos, int total) {if (pos == weight.size()) {return total == 0;}if (!(total + suffix_sum_min[pos] <= 0 && 0 <= total + suffix_sum_max[pos])) {return false;}for (int i = lead_zero[pos]; i < 10; ++i) {if (!used[i]) {used[i] = true;bool check = dfs(pos + 1, total + weight[pos].second * i);used[i] = false;if (check) {return true;}}}return false;}bool isSolvable(vector<string>& words, string result) {unordered_map<char, int> _weight;unordered_set<char> _lead_zero;for (const string& word: words) {for (int i = 0; i < word.size(); ++i) {_weight[word[i]] += pow10(word.size() - i - 1);}if (word.size() > 1) {_lead_zero.insert(word[0]);}}for (int i = 0; i < result.size(); ++i) {_weight[result[i]] -= pow10(result.size() - i - 1);}if (result.size() > 1) {_lead_zero.insert(result[0]);}weight = vector<PCI>(_weight.begin(), _weight.end());sort(weight.begin(), weight.end(), [](const PCI& u, const PCI& v) {return abs(u.second) > abs(v.second);});int n = weight.size();suffix_sum_min.resize(n);suffix_sum_max.resize(n);for (int i = 0; i < n; ++i) {vector<int> suffix_pos, suffix_neg;for (int j = i; j < n; ++j) {if (weight[j].second > 0) {suffix_pos.push_back(weight[j].second);}else if (weight[j].second < 0) {suffix_neg.push_back(weight[j].second);}sort(suffix_pos.begin(), suffix_pos.end());sort(suffix_neg.begin(), suffix_neg.end());}for (int j = 0; j < suffix_pos.size(); ++j) {suffix_sum_min[i] += (suffix_pos.size() - 1 - j) * suffix_pos[j];suffix_sum_max[i] += (10 - suffix_pos.size() + j) * suffix_pos[j];}for (int j = 0; j < suffix_neg.size(); ++j) {suffix_sum_min[i] += (9 - j) * suffix_neg[j];suffix_sum_max[i] += j * suffix_neg[j];}}lead_zero.resize(n);for (int i = 0; i < n; ++i) {lead_zero[i] = (_lead_zero.count(weight[i].first) ? 1 : 0);}memset(used, false, sizeof(used));return dfs(0, 0);}
};

1309. 解码字母到整数映射
      给你一个字符串 s，它由数字（‘0’ - ‘9’）和 ‘#’ 组成。我们希望按下述规则将 s 映射为一些小写英文字符：

字符（‘a’ - ‘i’）分别用（‘1’ - ‘9’）表示。
字符（‘j’ - ‘z’）分别用（‘10#’ - ‘26#’）表示。
返回映射之后形成的新字符串。

题目数据保证映射始终唯一。

很简单的遍历，可以一次看三个数以节约时间。

class Solution {
public:string freqAlphabets(string s) {char tmp;int size = s.size();string ret;for (int i = 0; i < size;){if (i + 2 < size && s[i + 2] == '#'){tmp = 'a' + (10 * (int)(s[i] - '0') + (int)(s[i + 1] - '0') - 1);ret += tmp;i += 3;}else{tmp = 'a' + (int)(s[i] - '0') - 1;ret += tmp;i++;}}return ret;}
};

1310. 子数组异或查询
      有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。并返回一个包含给定查询 queries 所有结果的数组。

类似于前缀和，存储一个前缀异或数组，第i位存储0到i-1的异或。那么Li, Ri的区间异或，就可以用0到Ri的结果，异或0到Li -1的结果。实际用+1更好。

class Solution {
public:vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {int n = arr.size();vector<int> preXOR(n + 1, 0);vector<int> ret;for (int i = 0; i < n; ++i){preXOR[i + 1] = preXOR[i] ^ arr[i]; }for (int i = 0; i < queries.size(); ++i){ret.push_back(preXOR[queries[i][0]] ^ preXOR[queries[i][1] + 1]);}return ret;}
};

1311. 获取你好友已观看的视频
      给定你的 id 和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按字母顺序从小到大排列。

本体其实是一个广度遍历图的问题，然后对指定level的变量再进行总结归类和返回。

using PSI = pair<string, int>;class Solution {
public:vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {int n = friends.size();vector<bool> used(n);queue<int> q;q.push(id);used[id] = true;for (int _ = 1; _ <= level; ++_) {int span = q.size();for (int i = 0; i < span; ++i) {int u = q.front();q.pop();for (int v: friends[u]) {if (!used[v]) {q.push(v);used[v] = true;}}}}unordered_map<string, int> freq;while (!q.empty()) {int u = q.front();q.pop();for (const string& watched: watchedVideos[u]) {++freq[watched];}}vector<PSI> videos(freq.begin(), freq.end());sort(videos.begin(), videos.end(), [](const PSI& p, const PSI& q) {return p.second < q.second || (p.second == q.second && p.first < q.first);});vector<string> ans;for (const PSI& video: videos) {ans.push_back(video.first);}return ans;}
};

1312. 让字符串成为回文串的最少插入次数
      给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让 s 成为回文串的 最少操作次数 。
      「回文串」是正读和反读都相同的字符串。

主要在于如何思考题意：如果我们先获取到了最长回文子串，然后在这个基础上进行左右的添加，即可得到最小的回文串。在左侧添加右侧没有的元素，以及右侧到左侧的操作，实际添加的量就是原串和最长回文子串的差值。

class Solution {
public:int minInsertions(string s) {int n = s.size();string t(s.rbegin(), s.rend());vector<vector<int>> dp(n + 1, vector<int>(n + 1));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if (s[i - 1] == t[j - 1]) {dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);}}}return n - dp[n][n];}
};

这篇关于leetcode解题思路分析（一百五十）1305 - 1312 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---