Leetcode 150. 逆波兰表达式求值
题目描述
给你一个字符串数组 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) + 5
= 17 + 5
= 22
提示：
1 <= tokens.length <= 104
tokens[i] 是一个算符（“+”、“-”、“*” 或 “/”），或是在范围 [-200, 200] 内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
- 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
C语言题解和思路
int evalRPN(char** tokens, int tokensSize) {
int n = tokensSize, i;
int stk[n], top = 0;
for(i = 0; i < n; i++)
{
if(strlen(tokens[i]) > 1 || ('0' <= tokens[i][0] && tokens[i][0] <= '9'))
{
stk[top++] = atoi(tokens[i]);
}
else{
int num2 = stk[--top];
int num1 = stk[--top];
switch(tokens[i][0])
{
case '+':
stk[top++] = num1 + num2;
break;
case '-':
stk[top++] = num1 - num2;
break;
case '*':
stk[top++] = num1 * num2;
break;
case '/':
stk[top++] = num1 / num2;
break;
}
}
}
return stk[top - 1];
}
解题思路
栈与队列
创建一个整型数组 stk ，用于存放数组 tokens 中的数字。
遍历数组 tokens ，将数字通过 atoi 函数转化为整型的数字存入数组 stk 。
如果遇到非数字字符，从数组 stk 中取出最后的两个数字，然后通过 switch 判断是哪一种运算符，并用该运算符对从数组 stk 中取出的两个数字进行运算，将运算结果存入原倒数第二个数的位置，并将 top 指向数组原倒数第一个数的位置。
最后返回 stk 数组的 top 指向的前一个位置。
Leetcode 55. 跳跃游戏
题目描述
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 105
C语言题解和思路
bool canJump(int* nums, int numsSize){
int count = 0;
if(numsSize == 1)
{
return true;
}
for(int i = numsSize - 2; i >= 0; i--)
{
if(count != 0)
{
if(nums[i] >= count)
{
count = 0;
}
else{
count += 1;
}
}
else if(nums[i] == 0)
{
count = 2;
}
}
return count == 0;
}
解题思路
如果数组中只有一个数，直接返回 true 。
创建一个变量 count 并初始化为 0 ，用于记录至少需要多少步来到达某个位置。
从倒数第二个数往前遍历数组，如果 count 的值不为 0 ，继续判断数组当前位置是否大于 count ，如果是，说明在当前位置能跳跃到想要跳到的位置， count 初始化为 0 ，当前位置变成下一个需要到达的位置；如果不是，说明当前位置不能跳跃到想要的位置， count 加一，说明跳跃到想要的位置的条件增加了。
如果 count 的值为 0 ，但当前当前下标中在数组的值为 0 ，count 赋值为 2 ，说明 count 至少需要两步来跳过当前下标。
如果循环结束时， count 的值为 0 ，返回 true ，否则返回 false 。