- 2.3数据结构
- 2.3.1-数组
- 2.3.2-字符串
- 2.3.3-链表
- 2.3.4-树
- 2.3.5-栈
- 2.3.5-队列
//Offer_03 剑指offer面试题3：数组中重复的数字
class Offer_03 {
// 剑指offer面试题3：数组中重复的数字
// 使用位置交换的算法，时间复杂度O(n),空间复杂度O(1)
std::vector nums={2, 3, 1, 0, 2, 5, 3};
public:
int findRepeatNumber(vector& nums) {
int n=nums.size();
int i=0;
while(i
if(i==nums[i])
i++;
else
{
if(nums[i]==nums[nums[i]])
return nums[i];
else
{ int temp=nums[i];
nums[i]=nums[temp];
nums[temp]=temp;
}
}
}
return 0;
}
};
//Offer_04 剑指offer面试题4：二维数组中的查找
class Offer_04 {
// 剑指offer面试题4：二维数组中的查找
public:
bool findNumberIn2DArray(vector>& matrix, int target) {
int n=matrix.size();
if(n==0)
return false;
int m=matrix[0].size();
int i=0,j=m-1;
while(i=0)
{
if(matrix[i][j]==target)
return true;
else if(matrix[i][j]>target)
{
j--;
}
else{
i++;
}
}
return false;
}
};
2.3.2-字符串
//Offer_05 剑指offer面试题5：替换空格
class Offer_05 {
// 剑指offer面试题5：替换空格
// char s1[]="we are happy.";
public:
void replaceSpace(char s[],int len) {
int count=0;
for(int i=0;i
if(s[i]==' ')
count++;
}
int len_after=len+count*2;
int left=len-1;
int right=len_after-1;
s[len_after]=s[len];
s[len]=' ';
while(left>=0)
{
if(s[left]!=' ')
{
s[right--]=s[left];
}
else{
s[right--]='0';
s[right--]='2';
s[right--]='%';
}
left--;
}
cout<
此处注意区分字符string和字符数组的区别char* [];
字符串以‘ ’为结束符，对其进行长度修改时可以使用string.resize();
2.3.3-链表
链表结构
struct ListNode
{
int value;
ListNode* next;
ListNode():value(0),next(nullptr){}
ListNode(int x): value(x),next(nullptr){}
ListNode(int x, ListNode *next):value(x),next(next){}
};
//leetcode_02:两数相加
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class leetcode_02 {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// if(l1->val==0&&l2->val==0&&l1->next==nullptr&&l2->next==nullptr)
// return l1;
// else if(l1->val==0&&l2->val!=0&&l1->next==nullptr)
// return l2;
// else if(l1->val!=0&&l2->val==0&&l2->next==nullptr)
// return l1;
//以先处理第一个节点的方法，可以避免对数字为0的值的判断；避免上面的各种判断语句的写法
ListNode *newNode=new ListNode();
newNode->val=(l1->val+l2->val)%10;
int flag=(l1->val+l2->val)/10;
ListNode *head=new ListNode(0,newNode);
ListNode *curNode=newNode;
l1=l1->next;
l2=l2->next;
while(l1!=nullptr&&l2!=nullptr)
{
ListNode *newNode=new ListNode();
newNode->val=(l1->val+l2->val+flag)%10;
flag=(l1->val+l2->val+flag)/10;
curNode->next=newNode;
curNode=newNode;
l1=l1->next;
l2=l2->next;
}
while(l1!=nullptr)
{
ListNode *newNode=new ListNode();
newNode->val=(l1->val+flag)%10;
flag=(l1->val+flag)/10;
curNode->next=newNode;
curNode=newNode;
l1=l1->next;
}
while(l2!=nullptr)
{
ListNode *newNode=new ListNode();
newNode->val=(l2->val+flag)%10;
flag=(l2->val+flag)/10;
curNode->next=newNode;
curNode=newNode;
l2=l2->next;
}
if(flag==1)
{
ListNode *newNode=new ListNode(1);
curNode->next=newNode;
curNode=newNode;
}
return head->next;
}
};
//Offer_06 剑指offer面试题6：从尾到头打印链表
class Offer_06 {
public:
vector reversePrint(ListNode* head) {
stack s1;
while(head!=nullptr)
{
s1.push(head->val);
head=head->next;
}
vector res;
while(!s1.empty())
{
int x=s1.top();
res.push_back(x);
s1.pop();
}
return res;
}
};
2.3.4-树
2.3.5-栈
//初始化栈： stack s1;
//入栈： s1.push(x);
//出栈： s1.pop();
//访问栈顶元素： x=s1.top();
//栈是否为空： s1.empty();
//栈的大小： s1.size();
//Offer_09 剑指offer面试题9：用两个栈实现队列
class CQueue {
stack s1,s2;
public:
CQueue() {
while(!s1.empty())
s1.pop();
while(!s2.empty())
s2.pop();
}
void appendTail(int value) {
s1.push(value);
}
int deleteHead() {
if(!s2.empty())
{
int x=s2.top();
s2.pop();
return x;
}
else{
if(!s1.empty())
{
while(!s1.empty())
{
int y=s1.top();
s2.push(y);
s1.pop();
}
return deleteHead();
}
else{
return -1;
}
}
}
};
2.3.5-队列
队列基本操作
queue q1;
q1.empty(); //判断队列是否为空
q1.front(); //返回第一个元素
q1.back(); //返回最后一个元素
q1.push(10); //在队列末尾加入一个元素
q1.pop(); //删除第一个元素
q1.size(); //返回队列中元素的个数
//Offer_09 剑指offer面试题：两个队列实现一个栈
class MyStack {
queue q1,q2;
public:
MyStack() {
// 初始化，清空两个队列
while(!q1.empty())
q1.pop();
while(!q2.empty())
q2.pop();
}
void push(int x) {
//在两个队列里面寻找非空的队列，在其尾部追加元素，若均空，则添加到第一个队列
if(!q1.empty())
q1.push(x);
else if(!q2.empty())
q2.push(x);
else
q1.push(x);
}
int pop() {
//若第一队列非空，则从第一个队列依次出队添加到第二个队列中，最后一个元素则为出栈元素；
if(!q1.empty()&&q2.empty())
{
while(q1.size()>1)
{
int x=q1.front();
q2.push(x);
q1.pop();
}
int x=q1.front();
q1.pop();
return x;
}
//若第二个队列非空，则从第二个队列依次出队添加到第一个队列中，最后一个元素则为出栈元素；
else if(!q2.empty()&&q1.empty())
{
while(q2.size()>1)
{
int x=q2.front();
q1.push(x);
q2.pop();
}
int x=q2.front();
q2.pop();
return x;
}
//两个队列均空，返回-1；
else
{
return -1;
}
}
int top() {
//两个队列中非空一个返回最后一个元素；
if(!q1.empty()&&q2.empty())
return q1.back();
else if(q1.empty()&&!q2.empty())
return q2.back();
else
return -1;
}
bool empty() {
if(q1.empty()&&q2.empty())
return true;
else
return false;
}
};
