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

2023-10-09 07:12
文章标签 leetcode 分析 解题 思路 1305 1312 一百五十

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

  1. 两棵二叉搜索树中的所有元素
    给你 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;}
};
  1. 跳跃游戏 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);}
};
  1. 口算难题
    给你一个方程，左边用 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);}
};
  1. 解码字母到整数映射
    给你一个字符串 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;}
};
  1. 子数组异或查询
    有一个正整数数组 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;}
};
  1. 获取你好友已观看的视频
    给定你的 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;}
};
  1. 让字符串成为回文串的最少插入次数
    给你一个字符串 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 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/171213。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型，它综合考虑了土壤-水分-大气以及植被间的相互作用；是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程，使其能够精确的模拟土壤中水分的运动，而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者
阅读更多...
MOLE 2.5 分析分子通道和孔隙

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用，例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具，该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明，MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能，MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
衡石分析平台使用手册-单机安装及启动

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境，如果是隔离环境，无法连接互联网时，请先按照 离线环境安装依赖的指导进行依赖包的安装，然后按照本文的指导继续操作。如果网络环境可以连接互联网，请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud
阅读更多...
线性因子模型 - 独立分量分析（ICA）篇

线性因子模型 - 独立分量分析（ICA）篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型，它们通过引入潜变量（ latent variables \text{latent variables} latent variables）来更好地表征数据。其中，独立分量分析（ ICA \text{ICA} ICA）作为线性因子模型的一种，以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2