Day 7, 数据结构知识点走起~
1
编程题
【剑指Offer】调整数组顺序使奇数放在偶数之前
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
思路: 首先我们很快会想到使用辅助数组,分别统计奇数和偶数,然后再将这两个数组合并起来!注意一点,我们不需要去建立两个数组,只使用一个数组就好,奇数数组可以使用原数组!
class Solution {
public:
void reOrderArray(vector<int> &array) {
vector<int> even(array.size());
int i = , j = ; // i为原数组索引,j为辅助数组索引
for(auto num: array){
if((num & ) == ){
array[i++] = num;
}else{
even[j++] = num;
}
}
for(int k=;k < j; k++){
array[i++] = even[k];
}
}
};
那我们能不是不使用额外的空间复杂度呢?当然可以,由于题目要求奇数和偶数的相对顺序保持不变,也就是排序的稳定性,而经过我们之前对常用排序算法的了解,知道插入排序是稳定的!因此我们可以遍历整个数组,如果为奇数,则与其前面的所有偶数交换位置,这样也可以达到我们的目的!
class Solution {
public:
// 类似于插入排序的方法,将奇数依次的插入到偶数的前面
void reOrderArray(vector<int> &array) {
for(int i = ;i < array.size(); ++i){
if((array[i] & ) == ){ // 如果当前值为奇数
for(int j = i-1; j >=; j--){
if((array[j] & ) == ){ // 遍历i的前面,如果为偶数,则交换
swap(array[j], array[j+]);
}
}
}
}
}
};
【剑指Offer】链表中倒数第K个节点
输入一个链表,输出该链表中倒数第k个结点。
思路: 如果使用常规思维,那么我们需要遍历一次链表,然后再返回倒数第K个结点。如果K为节点长度的话,就需要遍历两次节点了,显然这种方法是不可取的!因此我们可以使用两个指针(前指针和后指针),前指针先移动k个节点,然后两者再一起移动,则后指针指向的节点为所求节点!
/*
2struct ListNode {
3 int val;
4 struct ListNode *next;
5 ListNode(int x) :
6 val(x), next(NULL) {
7 }
8};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead == nullptr||k==)
return nullptr;
ListNode*pTail=pListHead,*pHead=pListHead;
for(int i = ;i < k;++i)
{
if(pHead->next!=nullptr)
pHead=pHead->next;
else
return nullptr;
}
while(pHead->next!=nullptr)
{
pHead=pHead->next;
pTail=pTail->next;
}
return pTail;
}
};
2
概念题
【数据结构】已知一张图的邻接矩阵,那么顶点V的度数怎么计算?
我们在实现图的创建和遍历算法时,提到了度的概念,对于图中的节点,度数=入度+出度,其中入度是指有多少个节点指向该节点,而出度是指从该节点出发指向了多少个节点!
因此其顶点V的度数就等于邻接矩阵第V行中1的个数(出度) + 第V列中1的个数(入度)
【数据结构】AOE图是什么?强连通图是指?
AOE(Activity On Edge)图一般用来表示活动发生的先后顺序,是一个有向无环图,其使用顶点表示活动,用有向边表示活动之间开始的先后顺序,有向边的权重表示完成活动所需要的时间。图结构如下所示:
前连通图是一个有向图,并且在这个有向图中任意两点v1,v2都存在从v1到v2,也存在v2到v1的情况!
【数据结构】线性循环队列怎么去建立?
队列也分为两种,一种是用数组的存储表示,一种是基于链表的存储表示。
基于数组的存储表示的队列被称为顺序队列。其数据成员包括,一维数组elements用来存储数据,指针front和rear用来指示队尾队头的位置,maxSize是数组的最大长度。
一开始,front和rear都指向0位置,因此可以使用front==rear进行判空,当进行插入操作时,rear需要加1,但由于是数组,因此有可能索引发生溢出,但对于循环队列来说,元素数量是可以任意的,因此需要取余操作!即rear =(rear+1)% maxSize.同理当删除操作时,则为front =(front+1)% maxSize.
最后呢,我们可以使用(rear+1) % maxSize == front来判断这个循环队列是否已经满了!