91.编码方式一串不加空格的数字，问可能的编码种数AmessagecontaininglettersfromA-Zisbeingencodedtonumbersus
91.编码方式
一串不加空格的数字，问可能的编码种数
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
可能的编码数字从1到26
注意0的位置！例如出现了00肯定不存在……
我的思路：先求出可能的最长的1,2组合且2后面不包含0的串子……（例如121215就返回（12121）的长度5，如果到最后一位就减少1，如果是0也要减少一位）
class Solution {
public:
int numDecodings(string s) {
if(s=="")return 0;
vectormap(20,1);
map[1]=2;
for(int i=2;i<20;++i){//假设最长连续不超过20
map[i]=map[i-2]+map[i-1];
}
int result=1;
for(int i=0;i int temp=0;
while(i+1
if(s[i+1]!='0') temp++;
else temp--;
i++;
}
if(s[i]=='0'){
if(i==0||s[i-1]>'2'||s[i-1]=='0')return 0;
}
if(temp>0)result*=map[temp];
}
return result;
}
};
92.逆转单链表
注意只需要两个temp以及一个局部temp指针
在m到n的位置逆转，其他不变
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode result(0);
ListNode *temp=&result;
for(int i=1;inext=head;temp=temp->next;head=head->next;}
ListNode *begin=head;
ListNode *temp1,*temp2;
temp1=head;temp2=head->next;
for(int i=m;inext;temp2->next=temp1;temp1=temp2;temp2=temp3;}
//注意这边只需要两个temp以及一个局部temp3,如果在外部到尾端会出错
temp->next=temp1;
begin->next=temp2;
return result.next;
}
};
93.IP地址转化
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
class Solution {
public:
vector restoreIpAddresses(string s) {
vectorheihei(4,-1);
vectorresult;
help(result,heihei,s,0);
return result;
}
void help(vector&result,vector&heihei,string s,int num){
if(num==4){if(s.size()==0)result.push_back(changetostring(heihei)); return;}
if(s.size()==0)return;
heihei[num]=change(s.substr(0,1));help(result,heihei,s.substr(1),num+1);
if(s.size()>=2&&change(s.substr(0,2))!=1000){heihei[num]=change(s.substr(0,2));help(result,heihei,s.substr(2),num+1);}
if(s.size()>=3&&change(s.substr(0,3))<=255){heihei[num]=change(s.substr(0,3));help(result,heihei,s.substr(3),num+1);}
heihei[num]=-1;
return;
}
string changetostring(vectorheihei){
string result="";
for(int i=0;i<3;++i)result+=(to_string(heihei[i])+".");
result+=to_string(heihei[3]);
return result;
}
int change(string s){
int l=s.size();
int result=0;
for(int i=0;i if(s[0]=='0'){if(s.size()>1)return 1000;}//防止出现001这种情况…不合法
return result;
}
};
94.中序遍历二叉树
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
/**
* 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 inorderTraversal(TreeNode* root) {
vectorresult;
help(result,root);
return result;
}
void help(vector&result,TreeNode * root){
if(root==NULL)return;
if(!root->left&&!root->right){result.push_back(root->val);return;}
if(root->left){help(result,root->left);}
result.push_back(root->val);
help(result,root->right);
return;
}
};
参考了别人的发现可以更简洁……
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vectorresult;
help(result,root);
return result;
}
void help(vector&result,TreeNode * root){
if(root==NULL)return;
help(result,root->left);
result.push_back(root->val);
help(result,root->right);
return;
}
};
利用while循环的方式：（需要用一个Stack来储存根节点）
vector inorderTraversal(TreeNode* root) {
vector nodes;
stack toVisit;
TreeNode* curNode = root;
while (curNode || !toVisit.empty()) {
if (curNode) {
toVisit.push(curNode);
curNode = curNode -> left;
}
else {
curNode = toVisit.top();
toVisit.pop();
nodes.push_back(curNode -> val);
curNode = curNode -> right;
}
}
return nodes;
}
Morris Traversal：这个空间复杂度为O(1)，其他本质上都是O(n)
vector inorderTraversal(TreeNode* root) {
TreeNode* curNode = root;
vector nodes;
while (curNode) {
if (curNode -> left) {
TreeNode* predecessor = curNode -> left;
while (predecessor -> right && predecessor -> right != curNode)
predecessor = predecessor -> right;
if (!(predecessor -> right)) {
predecessor -> right = curNode;
curNode = curNode -> left;
}
else {
predecessor -> right = NULL;
nodes.push_back(curNode -> val);
curNode = curNode -> right;
}
}
else {
nodes.push_back(curNode -> val);
curNode = curNode -> right;
}
}
return nodes;
}
95.生成二叉搜索树（真正意义上的第一道树的题！）
注意，再循环里如果不new空间出来会被干掉的！！ //废了老大劲儿…
clone函数的作用可以克隆一下根部及节点（我这种方法貌似没用到，只需要new一下就好……）
/**
* 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:
TreeNode* clone(TreeNode* root) {
if (root == nullptr)
return nullptr;
TreeNode* newroot = new TreeNode(root->val);
newroot->left = clone(root->left);
newroot->right = clone(root->right);
return newroot;
}
vector generateTrees(int n) {
return help(1, n);
}
vector help(int begin,int end) {
vectorresult;
if (begin > end)return result;
if (begin == end) {
TreeNode *temp = new TreeNode(begin);
result.push_back(temp);
return result;
}
for (int i = begin; i <= end; ++i) {
TreeNode *temp = new TreeNode(i);
if (i == begin) {
for (auto jj : help(i + 1, end)) {
TreeNode *temp2 = clone(temp);
temp2->right = jj;
result.push_back(temp2);
}
}
else if (i == end) {
for (auto ii : help(begin, i - 1)) {
TreeNode *temp2 = clone(temp);
temp2->left = ii;
result.push_back(temp2);
}
}
else if(ibegin){
for (auto ii : help(begin, i - 1)) {
for (auto jj : help(i + 1, end)) {
TreeNode *temp2 = clone(temp);
temp2->left = ii;
temp2->right = jj;
result.push_back(temp2);
}
}
}
}
return result;
}
};
或者不用clone函数……
vector generateTrees(int n) {
return help(1, n);
}
vector help(int begin,int end) {
vectorresult;
if (begin > end)return result;
if (begin == end) {
TreeNode *temp = new TreeNode(begin);
result.push_back(temp);
return result;
}
for (int i = begin; i <= end; ++i) {
TreeNode *temp = new TreeNode(i);
if (i == begin) {
for (auto jj : help(i + 1, end)) {
//TreeNode *temp2 = clone(temp);
TreeNode *temp2 =new TreeNode(i);
temp2->right = jj;
result.push_back(temp2);
}
}
else if (i == end) {
for (auto ii : help(begin, i - 1)) {
//TreeNode *temp2 = clone(temp);
TreeNode *temp2 =new TreeNode(i);
temp2->left = ii;
result.push_back(temp2);
}
}
else if(ibegin){
for (auto ii : help(begin, i - 1)) {
for (auto jj : help(i + 1, end)) {
//TreeNode *temp2 = clone(temp);
TreeNode *temp2 =new TreeNode(i);
temp2->left = ii;
temp2->right = jj;
result.push_back(temp2);
}
}
}
}
return result;
}
96.计算特殊二叉树的个数
惯例先用上一题的思路来做，发现超时了（n-19的时候超时了）……不得不用DP的思路……
class Solution {
public:
int numTrees(int n) {
vectordp(n, 0);
if (n == 1)return 1;
dp[0] = 1;
for (int j = 1; jint result = 0;
for (int i = 0; iif (i == 0)result += dp[j - 1];
else if (i == j )result += dp[j - 1];
else {
result += dp[i - 1] * dp[j-i-1];
}
}
dp[j] = result;
}
return dp[n - 1];
}
};
97.交叉string
相当于把s2插入到s1里看是否能形成s3
一开始的思路是利用substring,看s3的第一位是否和s1或者s2的第一位一样，如果一样把s1或者s2的第一位去掉再迭代（因为一个迭代里可能有调用两次自身，所有超时间了，毕竟是2的n次方）
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
DP问题……用DP[i][j]来储存s1的前i位以及s2的前j位能否组成s3……这就避免了2的N次方这种量级……
一开始的思路是用迭代……已经通过99个了只剩下俩。。最后还是没办法，超时间了……
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
//试试DP搜索
if(s1.empty()){if(s2==s3)return true;else return false;}
if(s2.empty()){if(s1==s3)return true;else return false;}
int m=s1.size(),n=s2.size(),l=s3.size();
if(l!=m+n)return false;
vector>dp(m+1,vector(n+1,false));
dp[0][0]=true;
for(int i=1;i for(int i=1;i for(int i=1;i for(int j=1;j if(dp[i-1][j]&&s1[i-1]==s3[i+j-1])dp[i][j]=true;
if(dp[i][j-1]&&s2[j-1]==s3[i+j-1])dp[i][j]=true;
}
}
return dp[m][n];
}
};
/*
//99/101些许不甘心……
if(s1.size()+s2.size()!=s3.size())return false;
if(s1.empty()){if(s2==s3)return true;else return false;}
if(s2.empty()){if(s1==s3)return true;else return false;}
bool judge1=false,judge2=false;
if(s1[0]==s3[0])judge1=isInterleave(s1.substr(1),s2,s3.substr(1));
if(judge1)return true;
if(s2[0]==s3[0])judge2=isInterleave(s1,s2.substr(1),s3.substr(1));
if(judge2)return true;
return false;
*/
/*
"bbbbbabbbbabaababaaaabbababbaaabbabbaaabaaaaababbbababbbbbabbbbababbabaabababbbaabababababbbaaababaa"
"babaaaabbababbbabbbbaabaabbaabbbbaabaaabaababaaaabaaabbaaabaaaabaabaabbbbbbbbbbbabaaabbababbabbabaab"
"babbbabbbaaabbababbbbababaabbabaabaaabbbbabbbaaabbbaaaaabbbbaabbaaabababbaaaaaabababbababaababbababbbababbbbaaaabaabbabbaaaaabbabbaaaabbbaabaaabaababaababbaaabbbbbabbbbaabbabaabbbbabaaabbababbabbabbab"
*/
98.判断二叉搜索树是否合法
需要注意9，8，10，7，11，null,null这种情况是不合法的，9左侧的全部都要小于9……
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree
[2,1,3]
, return true.
Example 2:
1
/ \
2 3
Binary tree
[1,2,3]
, return false.
/**
* 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:
bool isValidBST(TreeNode* root) {
return help(root,-2147483649,2147483648);
}
bool help(TreeNode* root,long long left,long long right) {
if(!root)return true;
if(root->left){
if(root->left->val>=root->val)return false;
if(root->left->val<=left)return false;
if(!help(root->left,left,root->val))return false;
}
if(root->right){
if(root->right->val<=root->val)return false;
if(root->right->val>=right)return false;
if(!help(root->right,root->val,right))return false;
}
return true;
}
};
99.二叉搜索树里有两个元素被交换，恢复其原来样子[hard]
想了好久，最后扫了一眼别人的提示，只要遍历一下二叉搜索树即可，然后果然如此……
思路如下：
遍历一遍，如果一个数字比后面的数字大，说明这是我们要交换的前一个元素
之后遍历的时候如果发现比这个元素大的，直接与前一位交换即可，如果遍历到最后就和最后一位交换……【01变成10这种特例】
/**
* 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:
void recoverTree(TreeNode* root) {
TreeNode *temp1=NULL;
TreeNode *temp2=NULL;//必须要赋予初值……
TreeNode *temp3=NULL;
help(root, temp1, temp2,temp3);
change(temp2,temp3);
}
bool goon=true;
void help(TreeNode* &root, TreeNode* &left, TreeNode* &first,TreeNode * &end) {
if (!root)return;
help(root->left, left, first,end);
if (!left || left->valval)left = root;
else first = left;
if (first) {
if(root->val>first->val)goon=false;
if(goon)end=root;
}
help(root->right, left, first,end);
return;
}
void change(TreeNode* root, TreeNode* first) {
int temp = root->val;
root->val = first->val;
first->val = temp;
return;
}
};
100.判断两个二叉树是否完全一样（包括结构和内容）
还是一样的思路，通过迭代，先左边再中间，最后右边
/**
* 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:
bool isSameTree(TreeNode* p, TreeNode* q) {
if((!p&&q)||(p&&!q))return false;
if(!p&&!q)return true;
if(!isSameTree(p->left,q->left))return false;
if(p->val!=q->val)return false;
if(!isSameTree(p->right,q->right))return false;
return true;
}
};
又刷了10道，好多树的题，啃得有些慢……
京公网安备 11010802041100号