前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日算法题:Day 7

每日算法题:Day 7

作者头像
算法工程师之路
发布2019-08-09 16:39:43
4660
发布2019-08-09 16:39:43
举报
文章被收录于专栏:算法工程师之路
作者:TeddyZhang,公众号:算法工程师之路

Day 7, 数据结构知识点走起~

1

编程题

【剑指Offer】调整数组顺序使奇数放在偶数之前

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

思路: 首先我们很快会想到使用辅助数组,分别统计奇数和偶数,然后再将这两个数组合并起来!注意一点,我们不需要去建立两个数组,只使用一个数组就好,奇数数组可以使用原数组!

代码语言:javascript
复制
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];
        }
    }
};

那我们能不是不使用额外的空间复杂度呢?当然可以,由于题目要求奇数和偶数的相对顺序保持不变,也就是排序的稳定性,而经过我们之前对常用排序算法的了解,知道插入排序是稳定的!因此我们可以遍历整个数组,如果为奇数,则与其前面的所有偶数交换位置,这样也可以达到我们的目的!

代码语言:javascript
复制
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个节点,然后两者再一起移动,则后指针指向的节点为所求节点!

代码语言:javascript
复制
/*
 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来判断这个循环队列是否已经满了!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法工程师之路 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 作者:TeddyZhang,公众号:算法工程师之路
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档