@thousfeet
2018-02-22T22:51:05.000000Z
字数 9947
阅读 1331
LeetCode
You're now a baseball game point recorder.
Given a list of strings, each string can be one of the 4 following types:
Integer (one round's score): Directly represents the number of points you get in this round.
"+" (one round's score): Represents that the points you get in this round are the sum of the last two valid round's points.
"D" (one round's score): Represents that the points you get in this round are the doubled data of the last valid round's points.
"C" (an operation, which isn't a round's score): Represents the last valid round's points you get were invalid and should be removed.Each round's operation is permanent and could have an impact on the round before and the round after.
You need to return the sum of the points you could get in all the rounds.
Example 1:
Input: ["5","2","C","D","+"]
Output: 30
Explanation:
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get 2 points. The sum is: 7.
Operation 1: The round 2's data was invalid. The sum is: 5.
Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.
Round 4: You could get 5 + 10 = 15 points. The sum is: 30.Example 2:
Input: ["5","-2","4","C","D","9","+","+"]
Output: 27
Explanation:
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get -2 points. The sum is: 3.
Round 3: You could get 4 points. The sum is: 7.
Operation 1: The round 3's data is invalid. The sum is: 3.
Round 4: You could get -4 points (the round 3's data has been removed). The sum is: -1.
Round 5: You could get 9 points. The sum is: 8.
Round 6: You could get -4 + 9 = 5 points. The sum is 13.
Round 7: You could get 9 + 5 = 14 points. The sum is 27.Note:
The size of the input list will be between 1 and 1000.
Every integer represented in the list will be between -30000 and 30000.
【思路】
栈的模拟orz，因为tag是stack所以连想都不用想了...
【代码】
int calPoints(char** ops, int opsSize) {int score[1001];int top = -1;for(int i = 0; i < opsSize; i++){if(ops[i][0] == 'C') top--;else if(ops[i][0] == 'D') score[++top] = score[top-1]*2;else if(ops[i][0] == '+') score[++top] = score[top-1]+score[top-2];else score[++top] = atoi(ops[i]);}int ans = 0;for(int i = 0; i <= top; i++) ans += score[i];return ans;}
题目本身是没啥特别的，倒是学到了c语言字符串和数字互转的函数（头文件是stdlib.h）
字符串转化为数字
● atof()：将字符串转换为双精度浮点型值。
● atoi()：将字符串转换为整型值。
● atol()：将字符串转换为长整型值。
● strtod()：将字符串转换为双精度浮点型值，并报告不能被转换的所有剩余数字。
● strtol()：将字符串转换为长整值，并报告不能被转换的所有剩余数字。
● strtoul()：将字符串转换为无符号长整型值，并报告不能被转换的所有剩余数字。
int num_int;
double num_double;
char str_int[30] = "435"; //将要被转换为整型的字符串
char str_double[30] = "436.55"; //将要被转换为浮点型的字符串
num_int = atoi(str_int); //转换为整型值
num_double = atof(str_double); //转换为浮点型值
数字转化为字符串
● itoa()：将整型值转换为字符串。
● ltoa()：将长整型值转换为字符串。
● ultoa()：将无符号长整型值转换为字符串。
● gcvt()：将浮点型数转换为字符串，取四舍五入。
● ecvt()：将双精度浮点型值转换为字符串，转换结果中不包含十进制小数点。
● fcvt()：指定位数为转换精度，其余同ecvt()。
还可以使用sprintf系列函数把数字转换成字符串，其比itoa()系列函数运行速度慢。
int num_int = 435;
double num_double = 435.10f;
char str_int[30];
char str_double[30];
itoa(num_int, str_int, 10); //把整数num_int转成字符串str_int 参数10表示按十进制类型进行转换
gcvt(num_double, 8, str_double); //把浮点数num_double转成字符串str_double 参数8表示精确位数
参考链接：https://www.cnblogs.com/sddai/p/5774121.html
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty.Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
【思路】
用栈模拟队列。数据结构无脑模拟题。
【代码】
class MyQueue {private:stack<int> sta;stack<int> tmp;public:/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {sta.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {while(!sta.empty()){int a = sta.top();sta.pop();tmp.push(a);}int ans = tmp.top();tmp.pop();while(!tmp.empty()){int a = tmp.top();tmp.pop();sta.push(a);}return ans;}/** Get the front element. */int peek() {while(!sta.empty()){int a = sta.top();sta.pop();tmp.push(a);}int ans = tmp.top();while(!tmp.empty()){int a = tmp.top();tmp.pop();sta.push(a);}return ans;}/** Returns whether the queue is empty. */bool empty() {return sta.empty();}};
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty.Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
【思路】
用队列模拟栈。无脑模拟++
【代码】
class MyStack {private:queue<int> que;queue<int> tmp;public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int ans;while(!que.empty()){int a = que.front();que.pop();if(que.empty()) ans = a;else tmp.push(a);}while(!tmp.empty()){int a = tmp.front();tmp.pop();que.push(a);}return ans;}/** Get the top element. */int top() {return que.back();}/** Returns whether the stack is empty. */bool empty() {return que.empty();}};
C++STL stack
定义stack对象：
stack<int>s1;
stack<string>s2;
stack的基本操作有：
s.push(x)s.pop() 注意：出栈操作只是删除栈顶的元素，并不返回该元素。s.top()s.empty() 当栈空时返回true。s.size()C++STL queue
定义queue 对象：
queue<int> q1;
queue<double> q2;
queue 的基本操作有：
q.push(x) 将x 接到队列的末端。q.pop() 弹出队列的第一个元素，注意，并不会返回被弹出元素的值q.front()，即最早被压入队列的元素。q.back()，即最后被压入队列的元素。q.empty()，当队列空时，返回true。q.size()Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:
Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.Example 2:
Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].Example 3:
Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
前面看错题意打了个GG- -...
要寻找一个“132模式”的子序列（不一定要连续），就是串里面的三个数 i < j < k 满足 ai < ak < aj 。
【思路】
考虑已经拿到了 a b 两个数一个小一个大，当又遇到一个数 num 时，将有三种情况：
num 介于a、b之间，那太好了返回 true
num 很大，超过了 b，那其实完全可以取代掉 b
num 很小，小于 a，那要想办法把它存起来以便作为下一个区段中小的那个数字
所以维护两个数组，一个 min 一个 max，来存每一个段里的最小值和最大值（显然每个段是单调递增的）。越往后的 min 只可能是越来越小（因为如果比它大的话那就已经可以返回true了），所以只要跟最末尾的那个 min 比一下，比它小就要存起来。但是如果比最末尾的 max 大却未必就要马上把它替换掉，因为 max 数组是没有规律的，这个数仍有可能介于之前的某个段之间。
因此做法如下：
拿去跟之前所有区段比对一下，如果都不能满足，则进入以下：
1. 如果已有一个只开了个头的区段（top1 > top2），并且它 > min[top1]，就存入 max[++top2]
2. 如果它比最末尾的 max 大，那就替换掉 max[top2]; 否则如果它比末尾的 min 小，那就把它存进 min
突然发现好像漏考虑了如果来了好几个比末尾的 min 小的，岂不是 min 多了一长串在那里，跟所有区段去比的时候会出事……其实似乎应该要判一下 if(top1 > top2 && nums[i] < min[top1]) min[top1] = nums[i]; 的，讲道理 top1 最多应该也就比 top2 多一个才对……可能是case太弱了
【代码】
bool find132pattern(int* nums, int numsSize) {if(numsSize < 3) return false;int min[15001];int top1 = 0;int max[15001];int top2 = 0;int begin = -1;for(int i = 0; i < numsSize-1; i++){if(nums[i] < nums[i+1]){min[0] = nums[i];max[0] = nums[i+1];begin = i+1;break;}}if(begin == -1) return false;for(int i = begin+1; i < numsSize; i++){for(int j = 0; j <= top2; j++)if(nums[i] > min[j] && nums[i] < max[j]) return true;if(top1 > top2 && nums[i] > min[top1]) max[++top2] = nums[i];if(nums[i] > max[top2]) max[top2] = nums[i];else if(nums[i] < min[top2]) min[++top1] = nums[i];}return false;}
试了一下，果然 input 如果是 [1,4,0,-1,-2,-3,-1,-2] 的时候会出事……我要去交一个case……
（其实我的做法跟栈真的没半毛钱关系...）
【更正后的代码】
bool find132pattern(int* nums, int numsSize) {if(numsSize < 3) return false;int min[15001];int top1 = 0;int max[15001];int top2 = 0;int begin = -1;for(int i = 0; i < numsSize-1; i++){if(nums[i] < nums[i+1]){min[0] = nums[i];max[0] = nums[i+1];begin = i+1;break;}}if(begin == -1) return false;for(int i = begin+1; i < numsSize; i++){for(int j = 0; j <= top2; j++)if(nums[i] > min[j] && nums[i] < max[j]) return true;if(top1 > top2){if(nums[i] > min[top1]) max[++top2] = nums[i];else min[top1] = nums[i];}else{if(nums[i] > max[top2]) max[top2] = nums[i];else if(nums[i] < min[top1]) min[++top1] = nums[i];}}return false;}
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero.Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
还有 10200 删掉 1 连 0 也一起带走的骚操作？？那但凡有这种一串 0 前面的先导数字那我必须优先删它啊，只要 k >=这串数字那直接删光美滋滋。
Given a chemical formula (given as a string), return the count of each atom.
An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.
1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.
Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula.
A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.
Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.
Example 1:
Input:
formula = "H2O"
Output: "H2O"
Explanation:
The count of elements are {'H': 2, 'O': 1}.Example 2:
Input:
formula = "Mg(OH)2"
Output: "H2MgO2"
Explanation:
The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.Example 3:
Input:
formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
Explanation:
The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.Note:
All atom names consist of lowercase letters, except for the first character which is uppercase.
The length of formula will be in the range [1, 1000].
formula will only consist of letters, digits, and round parentheses, and is a valid formula as defined in the problem.
【思路】
其实想法真的不难啊，用栈来维护左右括号匹配已经是经典的经典了。但就是…去得到一串数字一串字母的打的好迷啊……最后奔溃去看了discuss……他维护栈的方法和我想的不太一样，但是…！打的真好看啊…… C++ iterative solution
里面用到了一个move函数不懂是为啥……
有空回头再来打吧！…哇 每天做hard都状态迷之迷……