《剑指Offer》做题总结(四)
51.构建乘积数组
题目描述:
给定一个数组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]。不能使用除法。
思路:
这一题,我开始的基本思路比较简单,就是直接用双循环,然后增加一些判断条件,然后直接得出最终结果,结果发生了边界越界。剑指offer里面有比较好的解决办法,就是按照上下三角形,进行乘。也就是先把图画出来,先将下三角的各项乘起来,然后上三角是按照反方向,进行相乘,上下三角相加得到最终的结果。
感悟:
这个感悟最深的一个就是这个矩阵图的应用,还有一个就是vector的批量赋值,vector<int>B(n,1),这个B就是一个存储n个1的向量。简直就是matlab里面的zeros,ones函数一毛一样。
附上:Vector赋值方式
附上图
代码:
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int n=A.size();
vector<int>B0(n,1);
vector<int>B1(n,1);
for(int i=1;i<n;++i)
{
B0[i]=B0[i-1]*A[i-1];
}
for(int i=n-2;i>=0;--i)
{
B1[i]=B1[i+1]*A[i+1];
}
vector<int>B(n,1);
for(int i=0;i<n;++i)
{
B[i]=B0[i]*B1[i];
}
return B;
}
};
52.正则表达式匹配
题目描述:
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
思路:
代码:
class Solution {public:
bool match(char* str, char* pattern)
{
if(str==NULL || pattern==NULL)
return false;
return matchCore(str,pattern);
}
bool matchCore(char * str,char* pattern )
{
if(*str=='\0' && *pattern=='\0') return true;
if(*str!='\0' && *pattern=='\0') return false;
if(*(pattern+1)=='*')
{
if(*str==*pattern || (*pattern=='.' && *str!='\0'))
return matchCore(str+1,pattern)|| matchCore(str,pattern+2);
else
return matchCore(str,pattern+2);
}
if(*str==*pattern || (*pattern=='.' && *str!='\0'))
return matchCore(str+1,pattern+1);
return false;
}
};
53.表示数值的字符串
题目描述:
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+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;
int dot=0,num=0,nume=0; //用来标记小数点、整数部分和e指数是否存在
while(*string!='\0')
{
if(*string >= '0' && *string <='9')
{
string++;
num=1;
}else if(*string=='.')
{
if(dot>0 || nume>0)
return false;
string++;
dot=1;
}else if(*string=='e'|| *string=='E')
{
if(num==0 || nume>0)
return false;
string++;
nume++;
if(*string=='+' || *string=='-')
string++;
if(*string=='\0')
return false;
}else
return false;
}
return true;
}
};
54.字符流中第一个不重复的的字符
题目描述:
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
思路:
代码:
class Solution{
public:
//Insert one char from stringstream
//写的就是*啊~~~
void Insert(char ch)
{
++tongji_array[ch-'\0'];
if(tongji_array[ch-'\0']==1)
front_char.push_back(ch);
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
while(!front_char.empty() && tongji_array[front_char.front()]>=2)
front_char.pop_front();
if(front_char.empty())
return '#';
return front_char.front();
}
private:
unsigned char tongji_array[128];
deque<char>front_char;
};
总结:
做题做到这,其实要总结的有很多,比如我最想总结的就是 deque、vector、string这些C++中这些容器的用法:
1.deque、vector、string 、list、set、map基本用法
在STL中基本容器有: vector、list、deque、set、map
vector是可以快速地在最后添加删除元素,并可以快速地访问任意元素
list是可以快速地在所有地方添加删除元素,但是只能快速地访问最开始与最后的元素
deque在开始和最后添加元素都一样快,并提供了随机访问方法,像vector一样使用[]访问任意元素,但是随机访问速度比不上vector快,因为它要内部处理堆跳转
deque也有保留空间.另外,由于deque不要求连续空间,所以可以保存的元素比vector更大,这点也要注意一下.还有就是在前面和后面添加元素时都不需要移动其它块的元素,所以性能也很高。
因此在实际使用时,如何选择这三个容器中哪一个,应根据你的需要而定,一般应遵循下面
的原则:
1、如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector
2、如果你需要大量的插入和删除,而不关心随即存取,则应使用list
3、如果你需要随即存取,而且关心两端数据的插入和删除,则应使用deque。
在这一篇博客中,c++中容器总结,写的非常好,很全面,也很清楚。
55.删除链表中的重复
题目描述:
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表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==NULL || pHead->next==NULL)
return pHead;
//先为链表创建一个头节点
int firstNumber=pHead->val;
//假设我的头节点数值为-1
int myFirst=-1;
//万一链表的头结点也为-1 那么我就改成-2
if(myFirst==firstNumber)
{
myFirst=-2;
}
ListNode *head=new ListNode(myFirst);
head->next=NULL;
head->next=pHead;
ListNode *p=head;
ListNode *q=head->next;
while(q)
{
while(q->next && (q->next->val == q->val))
{
q=q->next;
}
if(p->next !q)
{
q=q->next;
p->next=q;
}else
{
p=q;
q=q->next;
}
}
//返回的时候 注意去掉头节点(自己创建的辅助节点)
return head->next;
}
};
56.二叉树的下一个节点
题目描述:
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
思路:
代码:
/*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;
if(pNode->right!=NULL)
{
pNode=pNode->right;
while(pNode->left!=NULL)
pNode=pNode->left;
return pNode;
}
while(pNode->next !=NULL)
{
TreeLinkNode* proot=pNode->next;
if(proot->left==pNode)
return proot;
pNode=pNode->next;
}
return NULL;
}
};
57.对称的二叉树
题目描述:
请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
思路:
代码:
/*struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* root)
{
if(root==NULL)
return true;
queue<TreeNode*>q1,q2;
TreeNode* left=root->left;
TreeNode* right=root->right;
q1.push(left);
q2.push(right);
while(!q1.empty() && !q2.empty() ){
left=q1.front();
q1.pop();
right=q2.front();
q2.pop();
if(left==NULL && right==NULL)
continue;
if(NULL==left || NULL==right)
return false;
if(left->val!=right->val)
return false;
q1.push(left->left);
q1.push(left->right);
q2.push(right->right);
q2.push(right->left);
}
return true;
}
};
58.按之字形顺序打印二叉树
题目描述:
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
思路:
代码:
/*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>> res;
if(pRoot==nullptr) return res;
stack<TreeNode *>stackL;
stack<TreeNode *>stackR;
TreeNode* popNode;
vector<int>tmp;
tmp.push_back(pRoot->val);
res.push_back(tmp);
tmp.clear();
stackL.push(pRoot);
while(!stackL.empty() || !stackR.empty() )
{
while(!stackL.empty())
{
popNode=stackL.top();
stackL.pop();
if(popNode->right)
{
stackR.push(popNode->right);
tmp.push_back(popNode->right->val);
}
if(popNode->left)
{
stackR.push(popNode->left);
tmp.push_back(popNode->left->val);
}
}
if(!tmp.empty())
{
res.push_back(tmp);
tmp.clear();
}
while(!stackR.empty()){
popNode=stackR.top();
stackR.pop();
if(popNode->left)
{
stackL.push(popNode->left);
tmp.push_back(popNode->left->val);
}
if(popNode->right)
{
stackL.push(popNode->right);
tmp.push_back(popNode->right->val);
}
}
if(!tmp.empty())
{
res.push_back(tmp);
tmp.clear();
}
}
return res;
}
};
59.把二叉树打印成多行
题目描述:
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
思路:
代码:
/*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;
vector<int>ve;
queue<TreeNode* >que;
queue<int>dque;
int depth=0;
que.push(pRoot);
dque.push(depth);
TreeNode* node;
while(!que.empty())
{
node=que.front();
if(depth!=dque.front())
{
vv.push_back(ve);
ve.clear();
depth=dque.front();
}
que.pop();
dque.pop();
if(node)
{
que.push(node->left);
que.push(node->right)
dque.push(depth+1);
dque.push(depth+1);
ve.push_back(node->val);
}
}
return vv;
}
};
60.序列化二叉树
题目描述:
请实现两个函数,分别用来序列化和反序列化二叉树
思路:
代码:
typedef
TreeNode node;
typedef
TreeNode* pnode;
typedef
int
* pint;
class
Solution {
vector<
int
> buf;
void
dfs(pnode p){
if
(!p) buf.push_back(0x23333);
else
{
buf.push_back(p -> val);
dfs(p -> left);
dfs(p -> right);
}
}
pnode dfs2(pint& p){
if
(*p == 0x23333){
++p;
return
NULL;
}
pnode res =
new
node(*p);
++p;
res -> left = dfs2(p);
res -> right = dfs2(p);
return
res;
}
public
:
char
* Serialize(TreeNode *p) {
buf.clear();
dfs(p);
int
*res =
new
int
[buf.size()];
for
(unsigned
int
i = 0; i < buf.size(); ++i) res[i]
= buf[i];
return
(
char
*)res;
}
TreeNode* Deserialize(
char
*str) {
int
*p = (
int
*)str;
return
dfs2(p);
}
};
61.二叉搜索树的第k个结点
题目描述:
给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。
思路:
代码:
/*
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<=0)return NULL;
vector<TreeNode *>vec;
Inorder(pRoot,vec);
if(k>vec.size())
return NULL;
return vec[k-1];
}
//中序遍历
void Inorder(TreeNode * pRoot,vector<TreeNode *>& vec)
{
if(pRoot==NULL) return;
Inorder(pRoot->left,vec);
vec.push_back(pRoot);
Inorder(pRoot->right,vec);
}
};
62.滑动窗口的最大值
题目描述:
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5};
针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
思路:
代码:
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int>res;
if(size<1 || size>num.size() || num.empty())
return res;
int temp;
for(int i=0;i<num.size()-size+1;i++)
{
temp=num[i];
for(int j=i+1;j<i+size;j++)
{
if(temp<num[j])
temp=num[j];
}
res.push_back(temp);
}
return res;
}
};
63.矩阵中的路径
题目描述:
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
思路:
代码:
class Solution {public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(str==NULL || rows<=0 || cols<=0)
return false;
bool *isOk=new bool[rows*cols]();
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(isHsaPath(matrix,rows,cols,str,isOk,i,j))
return true;
}
}
return false;
}
bool isHsaPath(char *matrix,int rows,int cols,char *str,bool *isOk,int curx,int cury)
{
if(*str=='\0')
return true;
if(cury==cols)
{
curx++;
cury=0;
}
if(cury==-1)
{
curx--;
cury=cols-1;
}
if(curx<0|| curx>= rows)
return false;
if(isOk[curx*cols+cury] || *str!=matrix[curx*cols+cury])
return false;
isOk[curx*cols+cury]=true;
bool sign=isHsaPath(matrix,rows,cols,str+1,isOk,curx-1,cury)
|| isHsaPath(matrix,rows,cols,str+1,isOk,curx+1,cury)
|| isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury-1)
|| isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury+1);
isOk[curx*cols+cury]=false;
return sign;
}
};
64.机器人的运动路径
题目描述:
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
思路:
代码:
class Solution {public:
int movingCount(int threshold, int rows, int cols)
{
bool *flag=new bool[rows*cols];
for(int i=0;i<rows*cols;i++)
{
flag[i]=false;
}
int count=moving(threshold,rows,cols,0,0,flag);
return count;
}
int moving(int threshold,int rows,int cols,int i,int j,bool* flag)
{
int count=0;
if(i>=0 && i<rows && j>=0 && j<cols && getsum(i)+getsum(j)<=threshold && flag[i*cols+j]==false)
{
flag[i*cols+j]=true;
count=1+moving(threshold,rows,cols,i+1,j,flag)
+moving(threshold,rows,cols,i-1,j,flag)
+moving(threshold,rows,cols,i,j-1,flag)
+moving(threshold,rows,cols,i,j+1,flag);
}
return count;
}
int getsum(int num)
{
int sum=0;
while(num){
sum+=num%10;
num/=10;
}
return sum;
}
};