个人网站例子,域名网站建设流程,鞍山58同城官网,长治视频制作1逆波兰表达式求值
给你一个字符串数组 tokens #xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意#xff1a;
有效的算符为 、-、* 和 / 。每个操作数#xff08;运算对象#xff09;都可以是一个整数或…1逆波兰表达式求值
给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意
有效的算符为 、-、* 和 / 。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是 向零截断 。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位 整数表示。 示例 1
输入tokens [2,1,,3,*]
输出9
解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9示例 2
输入tokens [4,13,5,/,]
输出6
解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6示例 3
输入tokens [10,6,9,3,,-11,*,/,*,17,,5,]
输出22
解释该算式转化为常见的中缀算术表达式为((10 * (6 / ((9 3) * -11))) 17) 5((10 * (6 / (12 * -11))) 17) 5((10 * (6 / -132)) 17) 5((10 * 0) 17) 5(0 17) 517 522 提示
1 tokens.length 104tokens[i] 是一个算符、-、* 或 /或是在范围 [-200, 200] 内的一个整数 逆波兰表达式
逆波兰表达式是一种后缀表达式所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式如 ( 1 2 ) * ( 3 4 ) 。该算式的逆波兰表达式写法为 ( ( 1 2 ) ( 3 4 ) * ) 。
逆波兰表达式主要有以下两个优点
去掉括号后表达式无歧义上式即便写成 1 2 3 4 * 也可以依据次序计算出正确结果。适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中 思路
使用一个栈来模拟计算过程。遍历输入的逆波兰表达式如果遇到操作数则压入栈中如果遇到运算符则从栈中取出两个操作数进行相应的运算然后将结果压入栈中。最终栈中的唯一元素即为表达式的结果。 代码
class Solution {
public:int evalRPN(vectorstring tokens) {// 使用长整型栈因为LeetCode修改了测试数据需要更大的数据范围stacklong long st; for (int i 0; i tokens.size(); i) {if (tokens[i] || tokens[i] - || tokens[i] * || tokens[i] /) {// 如果是运算符则取出栈顶两个元素进行运算long long num1 st.top();st.pop();long long num2 st.top();st.pop();// 根据运算符进行计算并将结果压入栈中if (tokens[i] ) st.push(num2 num1);if (tokens[i] -) st.push(num2 - num1);if (tokens[i] *) st.push(num2 * num1);if (tokens[i] /) st.push(num2 / num1);} else {// 如果是数字则将其转换为长整型并压入栈中st.push(stoll(tokens[i]));}}// 最终栈中的唯一元素即为结果int result st.top();st.pop(); // 把栈里最后一个元素弹出其实不弹出也没事return result;}
};
2 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。 示例 1
输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
解释
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2
输入nums [1], k 1
输出[1]提示
1 nums.length 105-104 nums[i] 1041 k nums.length
思路 在滑动窗口最大值问题中给定一个数组 nums 和一个大小为 k 的滑动窗口窗口从数组的最左侧移动到最右侧每次移动一个位置。你需要找到每个窗口中的最大值。
为了解决这个问题代码中使用了一个名为 MyQueue 的私有内部类实现了单调队列的功能。单调队列可以在 O(1) 的时间复杂度内获取当前队列中的最大值。 维护一个递减的队列这样队首元素始终是当前窗口的最大值。当新元素进入窗口时从队列尾部开始弹出比新元素小的元素以保持队列的递减性质。这样每次窗口滑动时只需将窗口左侧出队的元素从队列中删除再将窗口右侧进入的元素依次入队即可。
在代码中首先处理前 k 个元素构建初始的窗口。然后从第 k 个元素开始依次处理剩余元素每次都更新单调队列并将当前窗口的最大值加入结果数组中。
代码
class Solution {
private:// 定义一个私有内部类 MyQueue用于实现单调队列的功能class MyQueue {private:dequeint que; // 使用 deque 作为底层容器public:// 弹出队首元素如果队首元素等于给定值则弹出void pop(int value) {if (!que.empty() value que.front()) {que.pop_front();}}// 将值压入队列保持队列单调递减void push(int value) {// 循环弹出队列末尾比当前值小的元素保持单调递减性质while (!que.empty() value que.back()) {que.pop_back();}// 将当前值压入队列que.push_back(value);}// 返回队首元素int front() {return que.front();}};public:// 滑动窗口最大值vectorint maxSlidingWindow(vectorint nums, int k) {MyQueue que; // 创建 MyQueue 实例vectorint result; // 存放结果的数组// 先处理前 k 个元素for (int i 0; i k; i) {que.push(nums[i]); // 将元素压入队列}result.push_back(que.front()); // 将队首元素当前窗口的最大值放入结果数组// 处理剩余元素for (int i k; i nums.size(); i) {que.pop(nums[i - k]); // 弹出窗口左侧元素que.push(nums[i]); // 压入窗口右侧新元素result.push_back(que.front()); // 将当前窗口的最大值放入结果数组}return result; // 返回结果数组}
};
3前 K 个高频元素
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1:
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]示例 2:
输入: nums [1], k 1
输出: [1] 提示
1 nums.length 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的
思路 统计元素出现频率首先遍历数组使用一个哈希表 map 存储每个元素及其出现的次数。 对频率排序定义一个小顶堆 priority_queue堆中的元素是键值对 {元素, 频率}。自定义了一个比较类 mycomparison使得堆按照频率升序排序。然后遍历哈希表将元素和对应出现的次数存入小顶堆中。如果堆的大小超过了 K就弹出堆顶元素保持堆的大小为 K。 找出前 K 个高频元素最后从小顶堆中依次取出前 K 个元素因为小顶堆的特性是先弹出频率最小
代码
class Solution {
public:// 自定义比较类用于小顶堆的排序class mycomparison {public:// 重载 () 运算符实现小顶堆的比较规则bool operator()(const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second; // 按照频率升序排序}};// 返回前 K 个高频元素vectorint topKFrequent(vectorint nums, int k) {// 统计元素出现频率unordered_mapint, int map; // 使用哈希表存储元素和对应出现的次数for (int i 0; i nums.size(); i) {map[nums[i]]; // 更新元素出现次数}// 对频率排序// 定义一个小顶堆大小为 kpriority_queuepairint, int, vectorpairint, int, mycomparison pri_que;// 遍历哈希表将元素和对应出现的次数存入小顶堆中for (unordered_mapint, int::iterator it map.begin(); it ! map.end(); it) {pri_que.push(*it); // 将元素和出现次数对压入小顶堆if (pri_que.size() k) { // 如果堆的大小超过了 k则弹出堆顶元素保持堆的大小为 kpri_que.pop(); // 弹出堆顶元素频率最小的}}// 找出前 K 个高频元素因为小顶堆先弹出的是频率最小的所以需要倒序输出到数组中vectorint result(k);for (int i k - 1; i 0; i--) {result[i] pri_que.top().first; // 将堆顶元素频率最小的放入结果数组中pri_que.pop(); // 弹出堆顶元素}return result; // 返回前 K 个高频元素}
};
4无效的推文
表Tweets
-------------------------
| Column Name | Type |
-------------------------
| tweet_id | int |
| content | varchar |
-------------------------
在 SQL 中tweet_id 是这个表的主键。
这个表包含某社交媒体 App 中所有的推文。 查询所有无效推文的编号ID。当推文内容中的字符数严格大于 15 时该推文是无效的。
以任意顺序返回结果表。
查询结果格式如下所示 示例 1
输入
Tweets 表
--------------------------------------------
| tweet_id | content |
--------------------------------------------
| 1 | Vote for Biden |
| 2 | Let us make America great again! |
--------------------------------------------输出
----------
| tweet_id |
----------
| 2 |
----------
解释
推文 1 的长度 length 14。该推文是有效的。
推文 2 的长度 length 32。该推文是无效的。
代码
selecttweet_id
fromTweets
wherechar_length(content) 15;
5每天的领导和合伙人
表DailySales
----------------------
| Column Name | Type |
----------------------
| date_id | date |
| make_name | varchar |
| lead_id | int |
| partner_id | int |
----------------------
该表没有主键(具有唯一值的列)。它可能包含重复项。
该表包含日期、产品的名称以及售给的领导和合伙人的编号。
名称只包含小写英文字母。 对于每一个 date_id 和 make_name找出 不同 的 lead_id 以及 不同 的 partner_id 的数量。
按 任意顺序 返回结果表。
返回结果格式如下示例所示。 示例 1:
输入
DailySales 表
-------------------------------------------
| date_id | make_name | lead_id | partner_id |
-------------------------------------------
| 2020-12-8 | toyota | 0 | 1 |
| 2020-12-8 | toyota | 1 | 0 |
| 2020-12-8 | toyota | 1 | 2 |
| 2020-12-7 | toyota | 0 | 2 |
| 2020-12-7 | toyota | 0 | 1 |
| 2020-12-8 | honda | 1 | 2 |
| 2020-12-8 | honda | 2 | 1 |
| 2020-12-7 | honda | 0 | 1 |
| 2020-12-7 | honda | 1 | 2 |
| 2020-12-7 | honda | 2 | 1 |
-------------------------------------------
输出
-----------------------------------------------------
| date_id | make_name | unique_leads | unique_partners |
-----------------------------------------------------
| 2020-12-8 | toyota | 2 | 3 |
| 2020-12-7 | toyota | 1 | 2 |
| 2020-12-8 | honda | 2 | 2 |
| 2020-12-7 | honda | 3 | 2 |
-----------------------------------------------------
解释
在 2020-12-8丰田toyota有领导者 [0, 1] 和合伙人 [0, 1, 2] 同时本田honda有领导者 [1, 2] 和合伙人 [1, 2]。
在 2020-12-7丰田toyota有领导者 [0] 和合伙人 [1, 2] 同时本田honda有领导者 [0, 1, 2] 和合伙人 [1, 2]。
代码
selectdate_id,make_name,COUNT(distinct lead_id) as unique_leads,COUNT(distinct partner_id) as unique_partners
fromDailySales
group by date_id, make_name;
