leetcode刷题笔录6
leetcode刷题笔录-6
验证二叉查找树
给出一棵树，验证其是否是一棵二叉查找树。二叉查找树应当满足，对于每个节点：
左子树中的所有节点的值小于该节点的值；
右子树中的所有节点的值大于该节点的值；
左子树和右子树都必须是二叉查找树。
思路：递归检查每个节点的值是不是在某个区间 [min, max] 中，对根节点，检查其是不是在区间 [INT_MIN, INT_MAX] 中。对某个节点的检查区间，如此确定：如果该节点是父节点的左子结点，则 min 继承父节点检查区间的 min ，而 max 则为父节点的值；右子树类似。
实现：
/* *
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public :
bool isValidBST(TreeNode * root) {
return _isValidBST(root, INT_MIN, INT_MAX);
}
bool _isValidBST(TreeNode *root, int min, int max){
if (root== NULL){
return true ;
}
else {
if (root->val < min || root->val > max){
return false ;
}
return _isValidBST(root->left, min, root->val- 1 ) && _isValidBST(root->right, root->val+ 1 , max);
}
}
};
恢复二叉查找树
二叉查找树的两个节点被对调了，在不改变二叉树结构的情况下恢复之。
思路：这样考虑，如果一个递增排列的数组中有两个元素被对调了，试图恢复之是较为简单的，只要稍微考虑一下边界条件即可。而此处是二叉树，我们只需要像顺序数组一样访问二叉树即可，即通过中序遍历一次访问各节点。
实现：
/* *
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public :
void recoverTree(TreeNode * root) {
node1 = NULL;
node2 = NULL;
preNode = NULL;
inOrderDetect(root);
if (node2 == NULL){
node2 = root;
while (node2-> right){
node2 =node2-> right;
}
}
int tmp = node1-> val;
node1 ->val = node2-> val;
node2 ->val = tmp;
}
void inOrderDetect(TreeNode * root){
if (root == NULL){
return ;
}
inOrderDetect(root -> left);
if (preNode != NULL){
if (node1 == NULL){
if (root->val < preNode-> val){
node1 = preNode;
}
}
else if (node2 == NULL){
if (root->val > node1-> val){
node2 = preNode;
}
}
}
preNode = root;
inOrderDetect(root -> right);
}
TreeNode * node1;
TreeNode * node2;
TreeNode * preNode;
};
字符串交错
给出三个字符串 s1 和 s2 和 s3 ，判断 s3 是否是由 s1 和 s2 交错产生的。如 s1="aabcc"，s2="dbbca"，那么 s3=" aadbbcbcac " 就是由前两个字符串交错产生的。
思路：一看就知是动态规划问题。对于 s1[m1...m2]，s2[n1...n2] 和 s3[p1...p2] （最初m1，n1，p1都为0），s3是否由 s1 和 s2 交错产生取决于：
如果 s1[m1]!=s3[p1] 且 s2[m1]!=s3[p1]，那么s3就不是由s1和s2交错产生，返回false；
如果 s1[m1]==s3[p1] 且 s2[m1]!=s3[p1]，那么就看 s1[m1+1...m2] 和 s2[n1...n2] 是否能够交错产生 s3[p1+1...p2]；
如果 s1[m1]!=s3[p1] 且 s2[m1]==s3[p1]，和上一条类似。
如果 s1[m1]==s3[p1] 且 s2[m1]==s3[p1]，那么如果 s1[m1+1...m2] 和 s2[n1...n2] 能够交错产生 s3[p1+1...p2]，或者 s1[m1...m2] 和 s2[n1+1...n2] 能够交错产生 s3[p1+1...p2]，都返回 true。
实现
class Solution {
public :
bool isInterleave( string s1, string s2, string s3) {
int mp = s1.length();
int mq = s2.length();
int mk = s3.length();
if (mp+mq != mk){
return false ;
}
vector <vector< int >> s(
mp + 1 ,
vector < int >(mq+ 1 , - 1 )
);
return _isInterleave(s1, 0 , s2, 0 , s3, 0 , s);
}
bool _isInterleave( string s1, int p, string s2, int q, string s3, int k, vector<vector< int >>& s){
bool rslt = false ;
if (p==s1.length() && q== s2.length()){
return true ;
}
if (s[p][q] == 1 ){
return true ;
}
else if (s[p][q] == 0 ){
return false ;
}
if (p< s1.length()){
if (s3[k]== s1[p]){
rslt = _isInterleave(s1, p+ 1 , s2, q, s3, k+ 1 , s) || rslt;
}
}
if (q< s2.length()){
if (s3[k]== s2[q]){
rslt = _isInterleave(s1, p, s2, q+ 1 , s3, k+ 1 , s) || rslt;
}
}
s[p][q] = rslt ? 1 : 0 ;
return rslt;
}
};
唯一二叉查找树1
给出一个整数 n ，试问存储了 n 个不同的节点值的二叉查找树有多少种？比如给出3，返回5，因为有5种三个节点的二叉查找树，如下：
1 3 3 2 1
\ / / / \ 3 2 1 1 3 2
/ / \ 2 1 2 3
思路：动态规划，二叉查找树的种类数 f ( n ) = σ n i = 0 f ( i ) ? f ( n ? i ) ，且 f ( 0 ) = f ( 1 ) = 1 ，因为没有节点的二叉树和只有一个节点的二叉树都只有一种。
实现：
class Solution {
public :
int numTrees( int n) {
vector < int > nums;
nums.push_back( 1 );
nums.push_back( 1 );
for ( int i= 2 ; i<=n; i++ ){
int num = 0 ;
for ( int j= 0 ; j<i; j++ ){
num += nums[j- 0 ]*nums[i- 1 - j];
}
nums.push_back(num);
}
return nums[n];
}
};
唯一二叉查找树2
同上一题，只不过需要输出所有可能的二叉查找树。
思路：同上略。
实现：
/* *
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public :
vector <TreeNode *> generateTrees( int n) {
return _generateTrees( 0 , n- 1 );
}
vector <TreeNode *> _generateTrees( int n1, int n2){
vector <TreeNode *> trees;
if (n1> n2){
trees.push_back(NULL);
}
if (n1<= n2){
for ( int i=n1; i<=n2; i++ ){
vector <TreeNode *> leftTrees = _generateTrees(n1, i- 1 );
vector <TreeNode *> rightTrees = _generateTrees(i+ 1 , n2);
for ( int p= 0 ; p<leftTrees.size(); p++ ){
for ( int q= 0 ; q<rightTrees.size(); q++ ){
TreeNode * tree = new TreeNode(i+ 1 );
tree ->left = copyTree(leftTrees[p]);
tree ->right = copyTree(rightTrees[q]);
trees.push_back(tree);
}
}
}
}
return trees;
}
TreeNode * copyTree(TreeNode* target){
if (target== NULL){
return NULL;
}
TreeNode * node = new TreeNode(target-> val);
node ->left = copyTree(target-> left);
node ->right = copyTree(target-> right);
return node;
}
};
二叉查找树的中序遍历
不使用递归方法中序遍历输出二叉查找树
思路：如果是递归的方法，那就很简单了。题目要求不用递归，而用循环来解决，那就需要借助一个栈来实现。栈中先压入一个空节点，然后令当前节点为根节点，并如下循环处理，直到当前节点为空（即栈空）：
如果当前节点是新获得的节点（而不是从栈中弹出），那就将其压入栈中，然后：
如果该节点有左节点，那就令当前节点为左节点，进行下一次循环；
如果当前节点没有左节点，那就将其弹出，当前节点不变（只不过现在不是新获得的节点了，而是从栈中弹出的节点），进行下一次循环；
如果当前节点是从栈中弹出的节点，那就首先输出之（这是唯一输出该节点的地方，每个节点都经过这一步），然后：
如果该节点有右节点，那就再从栈中弹出一个节点作为当前节点，进行下一次循环；
如果该节点有有节点，就将当前节点设为有节点（注意该节点是新获得的节点），进行下一次循环。
实现：
/* *
* Definition for binary tree
* 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 > rslt;
stack <TreeNode*> stk;
stk.push(NULL);
TreeNode * node = root;
bool nodeIsPoped = false ;
while (node!= NULL){
if (nodeIsPoped){
rslt.push_back(node -> val);
if (node-> right){
node = node-> right;
nodeIsPoped = false ;
}
else {
node = stk.top();
stk.pop();
}
}
else {
stk.push(node);
if (node-> left){
node =node-> left;
}
else {
node = stk.top();
stk.pop();
nodeIsPoped = true ;
}
}
}
return rslt;
}
};
作者： 一叶斋主人
出处： www.cnblogs.com/yiyezhai
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
分类: leetcode 刷题笔录
验证二叉查找树 给出一棵树，验证其是否是一棵二叉查找树。二叉查找树应当满足，对于每个节点： 左子树中的所有节点的值小于该节点的值； 右子树中的所有节点的值大于该节点的值； 左子树和右子树都必须是二叉查找树。 思路：递归检查每个节点的值是不是在某个区间 [min, max] 中，对根节点，检查其是不是在区间 [INT_MIN, INT_MAX] 中。对某个节点的检查区间，如此确定：如果该节点是父节点的左子结点，则 min 继承父节点检查区间的 min ，而 max 则为父节点的值；右子树类似。 实现：
/* * * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public : bool isValidBST(TreeNode * root) { return _isValidBST(root, INT_MIN, INT_MAX); } bool _isValidBST(TreeNode *root, int min, int max){ if (root== NULL){ return true ; } else { if (root->val < min || root->val > max){ return false ; } return _isValidBST(root->left, min, root->val- 1 ) && _isValidBST(root->right, root->val+ 1 , max); } } };恢复二叉查找树 二叉查找树的两个节点被对调了，在不改变二叉树结构的情况下恢复之。 思路：这样考虑，如果一个递增排列的数组中有两个元素被对调了，试图恢复之是较为简单的，只要稍微考虑一下边界条件即可。而此处是二叉树，我们只需要像顺序数组一样访问二叉树即可，即通过中序遍历一次访问各节点。 实现：
/* * * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public : void recoverTree(TreeNode * root) { node1 = NULL; node2 = NULL; preNode = NULL; inOrderDetect(root); if (node2 == NULL){ node2 = root; while (node2-> right){ node2 =node2-> right; } } int tmp = node1-> val; node1 ->val = node2-> val; node2 ->val = tmp; } void inOrderDetect(TreeNode * root){ if (root == NULL){ return ; } inOrderDetect(root -> left); if (preNode != NULL){ if (node1 == NULL){ if (root->val < preNode-> val){ node1 = preNode; } } else if (node2 == NULL){ if (root->val > node1-> val){ node2 = preNode; } } } preNode = root; inOrderDetect(root -> right); } TreeNode * node1; TreeNode * node2; TreeNode * preNode; };字符串交错 给出三个字符串 s1 和 s2 和 s3 ，判断 s3 是否是由 s1 和 s2 交错产生的。如 s1="aabcc"，s2="dbbca"，那么 s3=" aadbbcbcac " 就是由前两个字符串交错产生的。 思路：一看就知是动态规划问题。对于 s1[m1...m2]，s2[n1...n2] 和 s3[p1...p2] （最初m1，n1，p1都为0），s3是否由 s1 和 s2 交错产生取决于： 如果 s1[m1]!=s3[p1] 且 s2[m1]!=s3[p1]，那么s3就不是由s1和s2交错产生，返回false； 如果 s1[m1]==s3[p1] 且 s2[m1]!=s3[p1]，那么就看 s1[m1+1...m2] 和 s2[n1...n2] 是否能够交错产生 s3[p1+1...p2]； 如果 s1[m1]!=s3[p1] 且 s2[m1]==s3[p1]，和上一条类似。 如果 s1[m1]==s3[p1] 且 s2[m1]==s3[p1]，那么如果 s1[m1+1...m2] 和 s2[n1...n2] 能够交错产生 s3[p1+1...p2]，或者 s1[m1...m2] 和 s2[n1+1...n2] 能够交错产生 s3[p1+1...p2]，都返回 true。 实现
class Solution { public : bool isInterleave( string s1, string s2, string s3) { int mp = s1.length(); int mq = s2.length(); int mk = s3.length(); if (mp+mq != mk){ return false ; } vector <vector< int >> s( mp + 1 , vector < int >(mq+ 1 , - 1 ) ); return _isInterleave(s1, 0 , s2, 0 , s3, 0 , s); } bool _isInterleave( string s1, int p, string s2, int q, string s3, int k, vector<vector< int >>& s){ bool rslt = false ; if (p==s1.length() && q== s2.length()){ return true ; } if (s[p][q] == 1 ){ return true ; } else if (s[p][q] == 0 ){ return false ; } if (p< s1.length()){ if (s3[k]== s1[p]){ rslt = _isInterleave(s1, p+ 1 , s2, q, s3, k+ 1 , s) || rslt; } } if (q< s2.length()){ if (s3[k]== s2[q]){ rslt = _isInterleave(s1, p, s2, q+ 1 , s3, k+ 1 , s) || rslt; } } s[p][q] = rslt ? 1 : 0 ; return rslt; } };唯一二叉查找树1 给出一个整数 n ，试问存储了 n 个不同的节点值的二叉查找树有多少种？比如给出3，返回5，因为有5种三个节点的二叉查找树，如下：
1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3思路：动态规划，二叉查找树的种类数 f ( n ) = σ n i = 0 f ( i ) ? f ( n ? i ) ，且 f ( 0 ) = f ( 1 ) = 1 ，因为没有节点的二叉树和只有一个节点的二叉树都只有一种。 实现：
class Solution { public : int numTrees( int n) { vector < int > nums; nums.push_back( 1 ); nums.push_back( 1 ); for ( int i= 2 ; i<=n; i++ ){ int num = 0 ; for ( int j= 0 ; j<i; j++ ){ num += nums[j- 0 ]*nums[i- 1 - j]; } nums.push_back(num); } return nums[n]; } };唯一二叉查找树2 同上一题，只不过需要输出所有可能的二叉查找树。 思路：同上略。 实现：
/* * * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public : vector <TreeNode *> generateTrees( int n) { return _generateTrees( 0 , n- 1 ); } vector <TreeNode *> _generateTrees( int n1, int n2){ vector <TreeNode *> trees; if (n1> n2){ trees.push_back(NULL); } if (n1<= n2){ for ( int i=n1; i<=n2; i++ ){ vector <TreeNode *> leftTrees = _generateTrees(n1, i- 1 ); vector <TreeNode *> rightTrees = _generateTrees(i+ 1 , n2); for ( int p= 0 ; p<leftTrees.size(); p++ ){ for ( int q= 0 ; q<rightTrees.size(); q++ ){ TreeNode * tree = new TreeNode(i+ 1 ); tree ->left = copyTree(leftTrees[p]); tree ->right = copyTree(rightTrees[q]); trees.push_back(tree); } } } } return trees; } TreeNode * copyTree(TreeNode* target){ if (target== NULL){ return NULL; } TreeNode * node = new TreeNode(target-> val); node ->left = copyTree(target-> left); node ->right = copyTree(target-> right); return node; } };二叉查找树的中序遍历 不使用递归方法中序遍历输出二叉查找树 思路：如果是递归的方法，那就很简单了。题目要求不用递归，而用循环来解决，那就需要借助一个栈来实现。栈中先压入一个空节点，然后令当前节点为根节点，并如下循环处理，直到当前节点为空（即栈空）： 如果当前节点是新获得的节点（而不是从栈中弹出），那就将其压入栈中，然后： 如果该节点有左节点，那就令当前节点为左节点，进行下一次循环； 如果当前节点没有左节点，那就将其弹出，当前节点不变（只不过现在不是新获得的节点了，而是从栈中弹出的节点），进行下一次循环； 如果当前节点是从栈中弹出的节点，那就首先输出之（这是唯一输出该节点的地方，每个节点都经过这一步），然后： 如果该节点有右节点，那就再从栈中弹出一个节点作为当前节点，进行下一次循环； 如果该节点有有节点，就将当前节点设为有节点（注意该节点是新获得的节点），进行下一次循环。 实现：
/* * * Definition for binary tree * 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 > rslt; stack <TreeNode*> stk; stk.push(NULL); TreeNode * node = root; bool nodeIsPoped = false ; while (node!= NULL){ if (nodeIsPoped){ rslt.push_back(node -> val); if (node-> right){ node = node-> right; nodeIsPoped = false ; } else { node = stk.top(); stk.pop(); } } else { stk.push(node); if (node-> left){ node =node-> left; } else { node = stk.top(); stk.pop(); nodeIsPoped = true ; } } } return rslt; } };
作者： 一叶斋主人
出处： www.cnblogs.com/yiyezhai
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
分类: leetcode 刷题笔录
如：-5,7,1,9，-12,15 变成 -5,-12,7,1,9,15。如何解？
题目要求：
空间复杂度O(1)，时间复杂度O(N)，排序稳定。空间上只能利用循环变量，标记变量等；时间上可以说是过一遍数组就完事了。
分治
用分治可以解决问题：首先把规模为 N 的问题划分成两个规模近似为 N/2 的子问题，两个子问题得到解决后进行合并得到整个问题的答案。对于本篇的问题，主要考虑合并该怎么解决，也就是假设：
将数组 arr 分成 arr1 和 arr2。设 arr1 为 [----++++]，arr2 为 [------+++]，如何得到 arr 为 [----------+++++++]。
显然， 只要将 arr1 的所有正数和 arr2 的所有负数交换就好了 ，为了不打乱原有正数/负数的次序，而且不借用任何其他的空间，考虑用《编程珠玑》中提到的 Doug Mcllroy 提出的翻手例子：
翻手代码在时间和空间上都很高效，而且代码非常的简短，很难出错。
于是方法是：将 arr1 中的正数 reverse 一次，arr2 中的负数 reverse 一次，紧接着 arr1 中的正数和 arr2 中的 负数结合起来 reverse 一次，由此完成 arr1 和 arr2 的合并。子问题就解决了。
void merge( int *arr, int left, int middle, int right)
{
/*全负数*/ /*全正数*/
if (!(arr[middle]>0 && arr[middle+1]<0))
return ;
// 找到 +++++ ----- 区域
int pos1 = left,pos2 = middle + 1;
for ( int i=left; i<=middle; i++)
if (arr[i] > 0) {pos1 = i; break ;}
for (i=middle+1; i<=right; i++)
if (arr[i] > 0) {pos2 = i-1; break ;}
// 翻手定律，你懂得
reverse(arr+pos1,middle - pos1+1);
reverse(arr+middle+1,pos2 - middle);
reverse(arr+pos1,pos2 - pos1 + 1);
}
迭代
另外，通过翻手方法同样可以迭代解决这个问题，也就是把 arr 走一遍就可以解决。同样，具体举例：
[……-+++--+-……]
刚开始扫描的时候如果一直是负数，那么不用作任何的动作 关键是遇上 [+++--] 的时候，需要作翻手处理，从而交换 [+++] 和 [--] 得到：[……---++++-……] 继续扫描得到 [+]，[……---++++-……]，不用处理 继续扫描得到 [-]，[……---++++-……]，需要对 [++++-] 作翻手处理，从而交换 [++++] 和 [-] 得到：[……----++++……]（此步骤和步骤 2 情况相同）
void myfunc( int *arr, int left, int right)
{
if (right <= left)
return ;
bool f = false ; // flag = true 表示需要进行翻转
int posbeg = -1, // 正数开始
posend, // 正数结束
negbeg, // 负数开始
negend, // 负数结束
negcount = 0; // 负数统计
for ( int i = 0; i<=right; i++)
{
if (arr[i]>0)
{
if (posbeg < 0)
posend = posbeg = i;
posend = i;
for ( int j=i+1; j<=right; j++)
if (arr[j]>0)posend++;
else break ;
f = true ;
i = posend + 1;
}
if (arr[i] < 0 && i <= right)
{
if (!f){negcount++; continue ;}
negend = negbeg = i;
for ( int j=i+1; j<=right; j++)
if (arr[j]<0)negend++,negcount++;
else break ;
i = negend;
reverse(arr+posbeg,posend-posbeg+1);
reverse(arr+negbeg,negend-negbeg+1);
reverse(arr+posbeg,negend-posbeg+1);
f = false ;print(arr,14);
posend = negend;
posbeg = negcount + 1;
}
} // while
}
算法复杂度
在空间上符合题目条件，但在时间上有待讨论，时间上的消耗主要在 for 循环里面的 reverse 操作。假设 arr 数组当中有 m 个正数和 n-m 的负数，在最坏的情况下，复杂度是 O(m(n-m))，平摊给 for 循环的 n 次操作，那么结果是 O(m-m^2/n))。 因此，此算法不稳定。
我们来看看根据 n 和 m 的不同模拟的函数图像，将函数写成 y = x-x^2/k：
由此，这种算法确实很不稳定。一开始以为平摊法可以解决复杂度分析问题，可以达到 O(N) 的效果，但无果而终。在 CSDN 上有这题的讨论： 腾讯面试题：把负数移动到正数之前，不能改变正负数原先的次序 和 微博的一个编程题 。如果你有什么好的想法，不忘给我和网友们分享一下 :)，据说「之前百度就出过这道题,讨论了1000楼都没有一个正确答案」。
http://daoluan.net
分类: Algorithm
面试题：把负数移动到正数之前，不能改变正负数原先的次序
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did45897