1、翻转单词序列
本题考点:子串划分,子串逆置 牛客链接
题目描述:
牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“nowcoder. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
数据范围:1≤n≤100
进阶:空间复杂度 O(n) ,时间复杂度 O(n) ,保证没有只包含空格的字符串
解题思路:
以空格作为分隔将子串进行划分进行逆置,然后在对子串整体进行逆置。
代码:
class Solution {
public:void Reverse(string& str, int begin, int end){while(begin < end){char temp = str[begin];str[begin] = str[end];str[end] = temp;begin++;end--; }}string ReverseSentence(string str) {if(str.empty())return "";int j = 0;int i = 0;int len = str.size();while(i < len){while(i < len && str[i] != ' ') i++;Reverse(str, j, i - 1);while(i < len && str[i] == ' ') i++;j = i;}Reverse(str, j, i - 1);Reverse(str, 0, str.size() - 1);return str;}
};
2、按之字形顺序打印二叉树
本题考点:树遍历,stack,queue结合使用
题目描述:
给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)
数据范围:0≤n≤1500,树上每个节点的val满足∣val∣<=1500
要求:空间复杂度:O(n),时间复杂度:O(n)
解题思路:
代码:
class Solution {
public:vector<vector<int> > Print(TreeNode* pRoot) {vector<vector<int>> result;if(pRoot == nullptr)return result;stack<TreeNode* > st;queue<TreeNode* > qe;int dir = 1; / 1从左向右 2从右向左 (控制方向)st.push(pRoot);while(!st.empty()){vector<int> v;while(!st.empty()){TreeNode* cur = st.top();st.pop();v.push_back(cur->val);/控制左右子树顺序TreeNode* first = dir == 1 ? cur->left : cur->right;TreeNode* second = dir == 1 ? cur->right : cur->left;/入队列暂存if(first != nullptr)qe.push(first);if(second != nullptr)qe.push(second);}/移到栈中while(!qe.empty()){st.push(qe.front());qe.pop();}dir == 1 ? dir = 2 : dir = 1; /改变方向result.push_back(v);}return result;}};
3、二叉搜索树的第k个节点
本题考点:二叉搜索树的理解 牛客链接
题目描述:
给定一棵结点数为n 二叉搜索树,请找出其中的第 k 小的TreeNode结点值。
1.返回第k小的节点值即可
2.不能查找的情况,如二叉树为空,则返回-1,或者k大于n等等,也返回-1
3.保证n个节点的值不一样
数据范围:0≤n≤1000,0≤k≤1000,树上每个结点的值满足0≤val≤1000
进阶:空间复杂度O(n),时间复杂度 O(n)
解题思路:
1、方法一:递归中序遍历。
2、方法二:迭代借助栈来完成中序遍历。
方法一比较简单,这里说下方法二的解题思路。
(1)将左子树全部入栈,出栈的时候判断其右子树是否为空。若不为空则把右子树当做新的树来将其左子树也全部入栈。
(2)这里的判断条件确实不太容易想,正常容易想到的就是栈不为空,但并不是这样,如图。
代码:
class Solution {
public:/方法一:void levelNode(TreeNode* proot, int& k, int& find){if(proot == nullptr || k <= 0)return;levelNode(proot->left, k, find);k--;if(k == 0){find = proot->val;return;}levelNode(proot->right, k, find);}int KthNode(TreeNode* proot, int k) {if(proot == nullptr)return -1;int find = -1;levelNode(proot, k, find);return find;}/方法二:int KthNode(TreeNode* proot, int k) {if(proot == nullptr)return -1;stack<TreeNode* > st;TreeNode* node = proot;do{while(node != nullptr){st.push(node);node = node->left;}if(!st.empty()){TreeNode* front = st.top();st.pop();k--;if(k == 0)return front->val;/右子树不为空,将其作为根节点继续入栈if(front->right) node = front->right;}}while(node != nullptr || !st.empty());return -1;}
};