剑指offer(刷题51-60)--c++，Python版本
文章目录
目录
第51题：
请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
解题思路：
解这题需要把题意仔细研究清楚，反正我试了好多次才明白的。
首先，考虑特殊情况：
1>两个字符串都为空，返回true
2>当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法
匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成
功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，
所以有可能匹配成功）
之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern
下一个字符可能是‘*’， 这里我们分两种情况讨论：pattern下一个字符为‘*’或
不为‘*’：
1>pattern下一个字符不为‘*’：这种情况比较简单，直接匹配当前字符。如果
匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的
“匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的
当前字符为‘.’,同时str的当前字符不为‘\0’。
2>pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。
这里把这些情况都考虑到：
a>当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，
跳过这个‘*’符号；
b>当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符
不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，
由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；
当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）
之后再写代码就很简单了。
代码实现：
c++
class Solution {
public:
bool match(char* str, char* pattern)
{
if (*str == '\0' && *pattern == '\0')
return true;
if (*str != '\0' && *pattern == '\0')
return false;
//if the next character in pattern is not '*'
if (*(pattern+1) != '*')
{
if (*str == *pattern || (*str != '\0' && *pattern == '.'))
return match(str+1, pattern+1);
else
return false;
}
//if the next character is '*'
else
{
if (*str == *pattern || (*str != '\0' && *pattern == '.'))
return match(str, pattern+2) || match(str+1, pattern);
else
return match(str, pattern+2);
}
}
};
运行时间：5ms
占用内存：480k
python
# -*- coding:utf-8 -*-
第52题：
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。
解题思路：
- 暂时想到的方式是遍历字符串，然后写一些规则判断是否符合数值表达式的写法，建议判断反例比较好。
代码实现：
c++
python
# -*- coding:utf-8 -*-
class Solution:
# s字符串
def isNumeric(self, s):
# write code here
if len(s) < 1:
return False
has_sign = False
has_dot = False
has_e = False
for i in range(len(s)):
if s[i]=="e" or s[i]=="E":
if has_e:
return False
else:
has_e = True
if i == len(s) - 1:
return False
elif s[i]=="+" or s[i] == "-":
if has_sign :
if s[i-1] != "e" and s[i-1] != "E":
return False
else:
has_sign = True
if i > 0 and s[i-1] != "e" and s[i-1]!= "E":
return False
elif s[i]==".":
if has_dot or has_e:
return False
else:
has_dot = True
if i>0 and (s[i-1]=="e" or s[i-1]=="E"):
return False
else:
if s[i]<"0" or s[i]>"9":
return False
return True
运行时间：28ms
占用内存：5728k
第53题：
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
解题思路：
- 使用一个保存到目前为止只出现一次的字符，如果随着字符流的输入，出现的相同的字符，则将相同的字符从栈中弹出，如果最后栈空了，则说明没有出现一次的字符，否则第一个只出现一次的字符则为栈底的元素。
- 使用hashmap来记录字符出现的次数，利用hashMap的有序性，第一个出现次数为1的则为我们想要的结果
代码实现：
c++
class Solution
{
private:
string s;
map<char , int> tempMap;
public:
//Insert one char from stringstream
void Insert(char ch)
{
s += ch;
tempMap[ch] ++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
for(int i=0; i < s.size() ; i++){
if(tempMap[s[i]] == 1) return s[i];
}
return '#';
}
};
运行时间：3ms
占用内存：360k
python
# -*- coding:utf-8 -*-
第54题：
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
解题思路：
- 使用快慢指针，一个指针一次走1步，一个指针一次走2步，如果最后慢指针走完了，没有出现快慢指针相等的情况下，则是不存在环，否则慢指针会追上快指针;在确定链表有环后，我们需要确定环中节点的个数，方法是让其中一个指针不动，另一个指针每次移动一步，看看最后两个指针相遇走了多少步；最后在让两个指针回到头结点，快指针先走环中节点的个数步，然后再让2个指针相同的速度走，则两个指针相遇的时候，慢指针所指向的节点为环的入口节点。
- 参考：
时间复杂度为O（n），两个指针，一个在前面，另一个紧邻着这个指针，在后面。
两个指针同时向前移动，每移动一次，前面的指针的next指向NULL。
也就是说：访问过的节点都断开，最后到达的那个节点一定是尾节点的下一个，
也就是循环的第一个。
这时候已经是第二次访问循环的第一节点了，第一次访问的时候我们已经让它指向了NULL，
所以到这结束。
代码实现：
c++
方法1：
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
ListNode fast = pHead;
ListNode slow = pHead;
while(fast != null && fast.next !=null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
break;
}
if(fast == null || fast.next == null)
return null;
fast = pHead;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
方法2
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (!pHead->next)
return NULL;
ListNode* previous = pHead;
ListNode* front = pHead ->next;
while (front)
{
previous->next = NULL;
previous = front;
front = front->next;
}
return previous;
}
};
运行时间：3ms
占用内存：484k
python
# -*- coding:utf-8 -*-
第55题：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
解题思路：
- 使用2个指针，一个指针在前，一个指针在后，同时移动两个指针，当两个指针相同时，同时删除两个指针，然后从新开始遍历，直至后指针遍历完整个链表。需要注意的是如果是链表的尾部元素相同，则需要将前面的链表的尾部置NULL。
代码实现：
c++
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if (pHead==NULL)
return NULL;
if (pHead!=NULL && pHead->next==NULL)
return pHead;
ListNode* current;
if ( pHead->next->val==pHead->val){
current=pHead->next->next;
while (current != NULL && current->val==pHead->val)
current=current->next;
return deleteDuplication(current);
}
else {
current=pHead->next;
pHead->next=deleteDuplication(current);
return pHead;
}
}
};
运行时间：4ms
占用内存：456k
python
# -*- coding:utf-8 -*-
第56题：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路：
- 分3种情况进行讨论，如果该节点存在右子树，则下一个节点就是它的右子树；如果没有右子树，且该节点是其父节点的左孩子节点，则下一个就是其父节点；如果该节点没有右孩子且不是其父节点的左孩子，则下一个节点为其父节点所在的子树的父节点。
代码实现：
c++
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == NULL)
{
return NULL;
}
TreeLinkNode *pNext = NULL;
// 如果当前结点有右子树, 那么其中序遍历的下一个结点就是其右子树的最左结点
if(pNode->right != NULL)
{
// 找到右子树的最左孩子
pNext = pNode->right;
while(pNext->left != NULL)
{
pNext = pNext->left;
}
}
else if(pNode->right == NULL && pNode->next != NULL)
{
TreeLinkNode *pCurrent = pNode;
TreeLinkNode *pParent = pNode->next;
// 如果当前结点是其父结点的左子结点那么其中序遍历的下一个结点就是他的父亲结点
//
// 如果当前结点是其父结点的右子结点，
// 这种情况下其下一个结点应该是当前结点所在的左子树的根
// 因此我们可以顺着其父节点一直向上遍历,
// 直到找到一个是它父结点的左子结点的结点
while(pParent != NULL && pCurrent == pParent->right)
{
pCurrent = pParent;
pParent = pParent->next;
}
pNext = pParent;
}
return pNext;
}
};
运行时间：5ms
占用内存：376k
python
# -*- coding:utf-8 -*-
第57题：
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
解题思路：
- 从题目的意思可以看出来，当树的左右子树相同的时候，则该树是对称的。所以可以通过判断树的左右子树是否相同来判断该树书否对称。
代码实现：
c++
class Solution {
public:
//判断2棵子树是否镜像相等
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == NULL)
{
return true;
}
return isSymmetricalRecursion(pRoot->left, pRoot->right);
}
bool isSymmetricalRecursion(TreeNode *pLeft, TreeNode *pRight)
{
if(pLeft == NULL && pRight == NULL)
{
return true;
}
if(pLeft == NULL || pRight == NULL)
{
return false;
}
if(pLeft->val != pRight->val)
{
return false;
}
// 左子树的左与右子树的右对称
// 左子树的右与右子树的左对称
return isSymmetricalRecursion(pLeft->left, pRight->right)
&& isSymmetricalRecursion(pLeft->right, pRight->left);
}
};
运行时间：4ms
占用内存：376k
python
# -*- coding:utf-8 -*-
第58题：
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
解题思路：
- 使用一个二维的数组保存层次遍历二叉树每一层的结果，每一层保存为一行，然后在输出的时候奇数行对数组中的元素反着打出即可。
代码实现：
c++
class Solution {
public:
vector< vector<int> > ans;
//只用层次遍历，将每一层的节点保存在一个二维数组中
void LevelOrder(TreeNode *pRoot,int p )
{
if(pRoot == NULL)
{
return;
}
if(ans.size( ) == p)
{
ans.push_back(vector<int>( ));
}
ans[p].push_back(pRoot->val);
LevelOrder(pRoot->left, p + 1); //将左子树的节点存入数组中
LevelOrder(pRoot->right, p + 1);//将右子树的节点存入数组中
}
vector< vector<int> > Print(TreeNode* pRoot)
{
LevelOrder(pRoot,0);
for(int i = 0; i <ans.size( ); i++)
{
if(i & 1)
{
reverse(ans[i].begin( ), ans[i].end( ));
}
}
return ans;
}
};
运行时间：5ms
占用内存：504k
python
# -*- coding:utf-8 -*-
第59题：
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
解题思路：
- 这个题目和上面的是类似的，只是这次不反着打印，而是在输出每一层后，输出一个回车即可。
代码实现：
c++
class Solution {
public:
vector< vector<int> > ans;
//只用层次遍历，将每一层的节点保存在一个二维数组中
void LevelOrder(TreeNode *pRoot,int p )
{
if(pRoot == NULL)
{
return;
}
//第一次遍历某一层时，需要创建一组内存
if(ans.size( ) == p)
{
ans.push_back(vector<int>( ));
}
ans[p].push_back(pRoot->val);
LevelOrder(pRoot->left, p + 1); //将左子树的节点存入数组中
LevelOrder(pRoot->right, p + 1);//将右子树的节点存入数组中
}
vector< vector<int> > Print(TreeNode* pRoot)
{
LevelOrder(pRoot,0);
return ans;
}
};
运行时间：3ms
占用内存：500k
python
# -*- coding:utf-8 -*-
第60题：
请实现两个函数，分别用来序列化和反序列化二叉树
解题思路：
- 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点
不为空时，在转化val所得的字符之后添加一个’ ， '作为分割。对于空节点则以 ‘#’ 代替。 - 对于反序列化：按照前序顺序，递归的使用字符串中的字符创建一个二叉树(特别注意：
在递归时，递归函数的参数一定要是char ** ，这样才能保证每次递归后指向字符串的指针会
随着递归的进行而移动！！！)
代码实现：
c++
python
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.flag = -1
def Serialize(self, root):
# write code here
if not root:
return '#,'
return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)
def Deserialize(self, s):
# write code here
self.flag += 1
l = s.split(',')
if self.flag >= len(s):
return None
root = None
if l[self.flag] != '#':
root = TreeNode(int(l[self.flag]))
root.left = self.Deserialize(s)
root.right = self.Deserialize(s)
return root
运行时间：24ms
占用内存：5856k