剑指offer第七章&第八章
1.把字符串转换成整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0
分析：思路在代码里已经体现
class Solution {
public:
int StrToInt(string str)
{
if(str.empty())
return ;
int symbol = ;//正负号初始化为1表示正数
if(str[] == '-')
{//处理负号
symbol = -;//表示是负数
str[] = ''; //这里是‘0’ 不是0
}
else if(str[] == '+')
{//处理正号
symbol = ;//表示是正数
str[] = '';
}
int sum = ;
for(int i=;i<str.size();++i)
{
if(str[i] < '' || str[i] > '')
{
sum = ;
break;
}
sum = sum * + str[i] - '';
}
return symbol * sum;//正负号乘以sum，即表示字符串所表示的整数
}
};2..数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
分析：注意到数组中的数字都在0——n-1的范围内。如果没有重复数字，那么排序之后数字i将出现在下标为i的位置
从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先比较这个数字（m）是不是等于i。如果是，接着扫描下一个数字。如果不是，再拿m和第m个数字比较。如果相等，就找到了一个重复数字。如果不等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来重复比较，直到找到重复数字。
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication)
{
if(numbers==NULL||length<=)
return false;
for(int i=;i<length;++i)
{
if(numbers[i]<||numbers[i]>length-)
return false;
}
for(int i=;i<length;++i)
{
while(numbers[i]!=i)
{
if(numbers[i]==numbers[numbers[i]])
{
*duplication=numbers[i];
return true;
}
int temp=numbers[i];
numbers[i]=numbers[temp];
numbers[temp]=temp;
}
}
return false;
}
};3.构建乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
分析：
B[i]的值可以看作下图的矩阵中每行的乘积。
下三角用连乘可以很容求得，上三角，从下向上也是连乘。
因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。
class Solution {
public:
vector<int> multiply(const vector<int>& A)
{
int n=A.size();
vector<int> B(n);
B[]=;
for(int i=;i<n;++i)
{
B[i]=B[i-]*A[i-];
}
double temp=;
for(int i=n-;i>=;--i)
{
temp*=A[i+];
B[i]*=temp;
}
return B;
}
};4.表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
分析：在代码里体现
class Solution {
public:
bool isNumeric(char* string)
{
if(string==NULL)
return false;
if(*string=='+'||*string=='-')//首先判断第一个字符是不是正负号
++string;
if(*string=='\0')//边界判断
return false;
bool numeric=true;
scanDigits(&string);//扫描数位
if(*string!='\0')
{
if(*string=='.')//小数
{
++string;
scanDigits(&string);
if(*string=='e'||*string=='E')//科学记数法
numeric=isExp(&string);
}
//整数
else if(*string=='e'||*string=='E')
numeric=isExp(&string);
else
numeric=false;
}
return numeric&&*string=='\0';
}
void scanDigits(char** string)//扫描字符串中0到9的数位
{
while(**string !='\0'&&**string>=''&&**string<='')
++(*string);
}
bool isExp(char** string)//用来匹配用科学记数法表示数值的结尾部分，结尾部分的第一个字符是‘e’或者‘E’，接下来可能有一个正负号
{
if(**string!='e'&&**string!='E')
return false;
++(*string);
if(**string=='+'||**string=='-')
++(*string);
if(**string=='\0')
return false;
scanDigits(string);
return (**string=='\0') ? true:false;
}
};5.字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述:：如果当前字符流没有存在出现一次的字符，返回#字符。
分析：
class Solution
{
public:
string s;
char hash[]={};
//Insert one char from stringstream
void Insert(char ch)
{
s+=ch;
hash[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
int size=s.size();
for(int i=;i<size;++i)
{
if(hash[s[i]]==)
return s[i];
}
return '#';
}
};
6.链表中环的入口结点
一个链表中包含环，请找出该链表的环的入口结点。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
//在链表中存在环的前提下找到一快一慢两个指针相遇的结点，一定在环内
ListNode* MeetingNode(ListNode* pHead)
{
if(pHead==NULL)
return NULL;
ListNode* pSlow=pHead->next;
if(pSlow==NULL)
return NULL;
ListNode* pFast=pSlow->next;
while(pFast!=NULL&&pSlow!=NULL)
{
if(pFast==pSlow)
return pFast;
pSlow=pSlow->next;
pFast=pFast->next;
if(pFast!=NULL)
pFast=pFast->next;
}
return NULL;
}
//找到环中任意一个结点之后，就能得出环中结点的数目，并找到环的入口结点
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* meetingNode=MeetingNode(pHead);
if(meetingNode==NULL)//没有环
return NULL;
//计算环中结点数
int nodesInLoop=;
ListNode* pNode1=meetingNode;
//从相遇的结点开始，一边继续向前移动一边计数，当再次回到这个结点，就统计出了环中节点数
while(pNode1->next!=meetingNode)
{
pNode1=pNode1->next;
++nodesInLoop;
}
//接下来找链表环的入口结点
//分三步：
//第一步：指针p1和p2初始化时都指向链表头结点
//第二步：由于环中有nodesInLoop个结点，指针p1先在链表上向前移动nodesInLoop步
//第三步：指针p1和p2以相同速度移动，直到相遇，相遇结点就是环的入口结点
pNode1=pHead;
for(int i=;i<nodesInLoop;++i)
pNode1=pNode1->next;
ListNode* pNode2=pHead;
while(pNode1!=pNode2)
{
pNode1=pNode1->next;
pNode2=pNode2->next;
}
return pNode1;
}
};
7.删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead==nullptr)
return pHead;
ListNode dummy(INT_MIN);//头结点
dummy.next=pHead;
ListNode *prev=&dummy,*cur=pHead;
while(cur!=nullptr){
bool duplicates=false;
while(cur->next!=nullptr&&cur->val==cur->next->val)
{
duplicates=true;
ListNode *tmp=cur;
cur=cur->next;
delete tmp;
}
if(duplicates)
{
//删除重复的最后一个元素
ListNode *tmp=cur;
cur=cur->next;
delete tmp;
continue;
}
prev->next=cur;
prev=prev->next;
cur=cur->next;
}
prev->next=cur;
return dummy.next;
}
};
8.二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析二叉树的下一个节点，一共有以下情况：
1.二叉树为空，则返回空；
2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { }
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==NULL)
return NULL;
TreeLinkNode* pNext=NULL;
if(pNode->right!=NULL)
{
TreeLinkNode* pRight=pNode->right;
while(pRight->left!=NULL)
pRight=pRight->left;
pNext=pRight;
}
else if(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;
}
};
9.对称二叉树
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/ class Solution {
public:
bool help(TreeNode *root1,TreeNode *root2)
{
if(root1==)
return root2==;
if(root2==)
return false;
return(root1->val==root2->val)&&help(root1->left,root2->right)&&help(root1->right,root2->left);
}
bool isSymmetrical(TreeNode *root)
{
if(root==){
return true;
}
return help(root->left,root->right);
}
};
10.按之字顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>> vv;
if(pRoot == NULL)
return vv;
deque<TreeNode *> q;
q.push_back(pRoot);
bool flag = true;//true表示从左向右存储层次遍历，否则是从右向左
int levelCnt = ;//上一层的节点数目
int curLevelCnt = ;//下一层节点数目
vector<int> v;
while(!q.empty())
{
TreeNode *cur;
if(flag)
{
cur = q.front();
q.pop_front();
}
else
{
cur = q.back();
q.pop_back();
}
if(flag)
{
if(cur->left)
{
q.push_back(cur->left);
++curLevelCnt;
}
if(cur->right)
{
q.push_back(cur->right);
++curLevelCnt;
}
}
else
{
if(cur->right)
{
q.push_front(cur->right);
++curLevelCnt;
}
if(cur->left)
{
q.push_front(cur->left);
++curLevelCnt;
}
}
v.push_back(cur->val);
--levelCnt;
if(levelCnt == )
{//这一层完毕
vv.push_back(v);
v.clear();
levelCnt = curLevelCnt;
curLevelCnt = ;
flag = !flag;
}
}
return vv;
}
};
11.把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int> > result;
queue<TreeNode*> current,next;
if(pRoot==NULL)
return result;
else
current.push(pRoot);
while(!current.empty()){
vector<int> level;//元素在一层
while(!current.empty()){
TreeNode* node=current.front();
current.pop();
level.push_back(node->val);
if(node->left!=NULL)
next.push(node->left);
if(node->right!=NULL)
next.push(node->right);
}
result.push_back(level);
swap(next,current);
}
return result;
}
};
12.二叉搜索树的第k个结点
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
//按照中序遍历的顺序遍历一颗二叉搜索树，遍历序列的数值是递增排序的
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot==NULL||k==)
return NULL;
return KthNodeCore(pRoot,k);
}
TreeNode* KthNodeCore(TreeNode* pRoot, int& k)
{
TreeNode* target=NULL;
if(pRoot->left!=NULL)
target=KthNodeCore(pRoot->left,k);
if(target==NULL)
{
if(k==)
target=pRoot;
k--;
}
if(target==NULL&&pRoot->right!=NULL)
target=KthNodeCore(pRoot->right,k);
return target;
}
};