代码编织梦想

150. 逆波兰表达式求值(中等)

题目:

根据逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

  • 整数除法只保留整数部分;
  • 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2:

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6
示例 3:

输入: ["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

题目中给定的字符串为有效的逆波兰表达式, 在进行计算之前首先要解决两个问题:

  • 判断字符串是否为数字字符串,若为数字字符串,将其转化为数字,压入数字栈
  • 若字符串不为数字字符串,则从数字栈中弹出两个元素,进行计算后将结果重新压入栈中

通过分析之后,将主要解决问题划分为3个子问题进行处理:

  1. 判断字符串是否为数字
    此问题不能简单的通过调用isalnum来判断,因为一旦出现两位数“10”,或者负数“-1”,将不能判断
  2. 数字字符串转为int类型数字
  3. 计算

在解决这些问题后,就可以进行对逆波兰表达式的计算过程

class Solution {
public:
	//	判断是否为数字字符串
    bool isNum(string &str){
        for(auto ch: str){
            if(isalnum(ch)){
                return true;
            }
        }

        return false;
    }

	//	数字字符串转int数字
    int strToNum(string &str){
        int res = 0;
        bool negative = false;
        if(str[0] == '-'){
            negative = true;
            for(int i = 1; i < str.size(); i++){
                res = res*10 + str[i]-'0';
            }
        }
        else{
            for(int i = 0; i < str.size(); i++){
                res = res*10 + str[i]-'0';
            }
        }

        return negative? -res: res;
    }

	//	计算
    int caculate(int &a, int &b, char operat){
        int res = 0;
        switch(operat){
        	//	注意,由于除法中除数与被除数的位置关系,将从数字栈中弹出的第一个元素作为被除数
        	//	第二个元素为除数, 其它运算同样遵循此法则
            case'+': res = b + a; break;
            case'-': res = b - a; break;
            case'*': res = b * a; break;
            case'/': res = b / a; break;
            default: break;   
        }

        return res;
    }

    int evalRPN(vector<string>& tokens) {
        int target = 0;
        if(tokens.empty()){
            return target;
        }

        stack<int> st;

        for(int i = 0; i < tokens.size(); i++){
            if(isNum(tokens[i])){
                st.push(strToNum(tokens[i]));
            }
            else{
                int a = st.top(); st.pop();
                int b = st.top(); st.pop();
                st.push(caculate(a, b, tokens[i][0]));
            }
        }

        return st.top();
    }
};

144. 二叉树的前序遍历(中等)

题目:

给定一个二叉树,返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

作为一道基础的二叉树问题,递归的解法自然不同多说。

从题目本质的性质来说,二叉树的前序遍历,中序遍历以及后序遍历都属于深度优先搜索算法的一种变形形式,正因如此,才要一定使用的结构来存储父节点的数据,以此达到类似于路径搜索的目的。

另外,前序遍历的顺序为根->左子树->右子树,这就意味着栈首先压入根节点,再压入左子树节点,再压入右子树节点。

至此,迭代方式来完成二叉树的前序遍历的准备工作已经完成。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        while(root || st.size()){
            while(root){
            	//	节点非空,将节点的左子树压入栈中,作为下一个将要搜索的节点
            	//	通俗来说,这个while 循环的作用在于,遍历完一个节点左子树的的所有左节点
            	//	在保证左子树的左节点全部遍历过后,“最左节点”的左节点一定为NULL, 此时循环跳出
                res.push_back(root->val);
                st.push(root);
                root = root->left;
            }
			
			//	左子树的“左节点”遍历结束,之后开始遍历左子树的“右节点”
			//	同理,当左子树遍历结束,开始遍历右子树;
			//	之后,右子树的“最左节点”,每一个左节点的左右子树,以此类推
            root = st.top();
            st.pop();
            root = root->right;
        }

        return res;
    }
};

94. 二叉树的中序遍历(中等)

题目:

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

中序遍历的顺序为左子树->根节点->右子树,从前序遍历的方法中可以大致推导出基本框架为:

while(root || st.size()){
	while(root){
		//	这个while循环保证最终到达的二叉树“最左”的节点
		st.push(root);
		root = root->left;
	}

	//	while结束,表明已经抵达该子树的“最左”节点,目前栈顶元素就是“最左”节点的地址
	//	毫无疑问,“最左节点”的左右子树均为NULL
	root = st.top();
	st.pop();
	res.push_back(root->val);
	//	正因“最左节点”的左右子树均为NULL,且“最左节点”已经确定,因此“最左节点”的右子树,就成了“回溯”的关键条件
	root = root->right;
}

一句话来总结,就是不断确定目前节点的“最左节点”,并以“最左节点”的右子树是否为NULL为回溯的条件。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        while(root || st.size()){
            while(root){
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qq_41028985/article/details/105777587

leetcode 23. 合并K个排序链表(二分查找+动态合并)-爱代码爱编程

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 题解: 1.k个链表 2.这k个链表本身是有序的 3.合并这k个链表 4.合并后的链表也应当是有序的 示例: 输入: [1->4->5,   1->3->4,   2->6] 输出: 1->1->2->3->4

ML_Task3 EM-爱代码爱编程

前言 EM算法是机器学习十大算法之一,它很简单,但是也同样很有深度,简单是因为它就分两步求解问题, E步:求期望(expectation)M步:求极大(maximization)深度在于它的数学推理涉及到比较繁杂的概率公式等,所以本文会介绍很多概率方面的知识,不懂的同学可以先去了解一些知识,当然本文也会尽可能的讲解清楚这些知识,讲的不好的地方麻烦大家评

A*算法——解经典八数码问题-爱代码爱编程

题目连接 问题引入:在进行bfs搜索的过程中,只能说明起始状态距离该状态的代价最小,但是在未来的搜索中,该状态到目标状态的可能会花费更高的代价,导致最优解的搜索量增大。 为了提高搜索效率,可以让那些代价大的方案尽可能的在后面进行搜索,此时就需要引入A*算法。 做法:设计一个估值函数f(state),估值函数必须满足,在未来的搜索过程中,估值不能大于未

操作系统面试_五大板块-爱代码爱编程

刚好额这学期正在上操作系统这门课 同时我也在准备学习下学期的实习面试了,所以开个专栏,总结下我读操作系统的心得吧~ 过程中大量翻阅书籍资料,融合自己的理解,只会让你更懂“Operating System" 文章目录 Part1_OS简介Part2_多进程(线程)Part3_内存管理Part4_文件管理Part5_IO管理 P

day03 EM-爱代码爱编程

前言 EM算法是机器学习十大算法之一,它很简单,但是也同样很有深度,简单是因为它就分两步求解问题, E步:求期望(expectation)M步:求极大(maximization)深度在于它的数学推理涉及到比较繁杂的概率公式等,所以本文会介绍很多概率方面的知识,不懂的同学可以先去了解一些知识,当然本文也会尽可能的讲解清楚这些知识,讲的不好的地方麻烦大家评

常见4种查找算法详解以及Java代码的实现-爱代码爱编程

查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。本文详细介绍了常见的数据查找算法,比如顺序查找/线性查找、二分查找/折半查找、插值查找、斐波那契查找等,并且提供了相应的Java代码实现。 文章目录 1 查找概述2 顺序查找3 二分查找3.1 二分查找概述3.2 二分查找实现4 插

二叉树相关处理,包含递归和非递归方法-爱代码爱编程

1.简介 熟悉二叉树的各种特性,包括前序、中序、后序遍历,以及还原二叉树等等主要搜集了递归和非递归方案,可以对比研究下学习这个也是为了再leetcode上刷题下面程序运行结果 <*>{1 <*>{2 <*>{0 <*>{3 <*>{4 <*>{0 <*>{5 }}}}}}

C++实现二叉树后序遍历-爱代码爱编程

二叉树的后续遍历,是先遍历左子树,在遍历右子数,最后遍历根节点。后续遍历的过程中我们需要借助栈来辅助 #include<iostream> #include<stack> //先构建一个二叉树结构体 struct BTreeNode{ int data; BTreeNode* lchild; BTreeNode* rchil

剑指offer-----item18 二叉树的镜像-爱代码爱编程

题干 输入一个二叉树,输出其二叉树的镜像。 注:镜像为二叉树的所有左右节点交换。 思路 二叉树的镜像这种题目在面试中经常会被考到,划重点啦!!!这种题目经典的思路有两种。其一是传统递归;第二种就是非递归解法。 方法一 传统递归 递归法没有什么太好说的,既然是左右两个节点交换,那么就是所见即所得,利用递归实现交换就完事儿了。代码见下: publi

关于C/C++二叉树的数据结构-爱代码爱编程

关于C/C++二叉树的数据结构 首先简单的说明一下什么是二叉树,就是每个节点都最多只包含两个子节点,因此个人感觉是树里边查找和建树相对比较方便的。 二叉树的排序有三种: ​ 1.前序遍历(根-左-右) ​ 2.中序遍历(左-根-右) ​ 3.后序遍历(左-右-根) [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-s

二叉树的绽放-爱代码爱编程

在这里插入代码片 ```BTNode* BinaryTreeCreate(BTDataType* a, int* pi) { if (a[*pi] != '#') { BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->_data = a[*pi]; ++(*pi); roo

leetcode_117.填充每个节点的下一个右侧节点指针II(C++,递归思路)-爱代码爱编程

题目 原题链接 给定一个二叉树 struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。 初始状态下,所有 next 指针都被设置为 N