每日算法题：Day 7
作者：TeddyZhang，公众号：算法工程师之路
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来判断这个循环队列是否已经满了！
腾讯云开发者
