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

每日算法题:Day 14(数据结构)

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

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

1

编程题

【剑指Offer】字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路:

如上图所示,树状图的第一层其实质就是下一个递归子问题入口str的值,也就是0与j(0,1,2…str.length())

交换后str的值,并且每次进入递归函数时,在i 之前字母将会被固定,其后面的数进行全排列(交换元素的位置)。然后一直递归下去,从而得到最后的全排列!一般我们写递归函数如果需要动态保存数据,如vector res, 我们可以把它当作一个参数,并使用引用传递的形式来修改res这个变量!

递归的结束条件为,索引i等于了str.length()时,递归结束!

代码语言:javascript
复制
class Solution {
public:
    void process(vector<string>& res, string str, int i){
        if(i == str.length()){
            res.push_back(str);
        }
        set<char> ss;
        for(int j = i;j < str.length(); j++){
            if(ss.find(str[j]) == ss.end()){
                ss.insert(str[j]);
                swap(str[i], str[j]);
                process(res, str, i+);
            }
        }
    }

    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.length() == ) return res;

        process(res, str, );
        return res;
    }
};

【剑指Offer】数组中超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

思路: 首先,第一个思路,我们不考虑空间复杂度,这种在笔试时最好用,使用一个哈希表,然后遍历,由于unordered_map中不允许重复的key,因此每遍历到相同的key,value就加一。然后判断这个值大不大于数组的一半,如果大于,直接返回即可,否则返回零。

代码语言:javascript
复制
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> hash_map;
        if(numbers.size() == ) return ;
        for(auto i: numbers){
            hash_map[i]++;
            if(hash_map[i] > (numbers.size() / )){
                return i;
            }
        }
        return ;
    }
};

另一种思路时,先对整个序列进行排序操作,如果数组中一个数的数量超过这个数组的一半,那么对整个数组排序后,这个数一定位于数组的中间位置!那么既然要排序,我们这里使用快排对数组进行排序,O(Nlogn),虽然有人可以优化到O(n),但是代码太多太复杂了!经过排序后,我们首先获得中间位置的值,然后遍历整个排序数组,统计这个值的个数,如果确实大于size/2,则返回这个数的个数!既然你要学算法,就尽量别调库了,老老实实自己写个快排!

代码语言:javascript
复制
class Solution {
public:
    vector<int> qs_partition(vector<int>& list, int L, int R){
        int more = R;   // 选取最后一个数为分界点
        int less = L - ;
        int cur = L;
        vector<int> res();
        while(cur < more){
            if(list[cur] < list[R]){
                swap(list[++less], list[cur++]);
            }else if(list[cur] > list[R]){
                swap(list[--more], list[cur]);  
                // 交换后cur有可能小于中间值,还需要再次交换,因此cur不进行自加
            }else{
                cur++;
            }
        }
        swap(list[more], list[R]);
        res[] = less+;
        res[] = more;
        return res;
    }
    // 经典快排
    void QuickSort(vector<int>& list, int L, int R){
        if(list.size() < ) return;
        if(L < R){
            vector<int> p = qs_partition(list, L, R);
            QuickSort(list, L, p[]-1);
            QuickSort(list, p[]+, R); // 递归处理其他部分
        }
    }

    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == ) return ;
        int size = numbers.size();
        QuickSort(numbers, , size-1);
        int mid = size / ;   // 获得中间位置的值
        int count = ;
        for(auto num: numbers){
            if(num == numbers[mid]){
                count++;     // 统计中间位置值的数量 
                if(count > (size / )){
                    return num;
                }
            }
        }
        return ;
    }
};

2

概念题

【数据结构】在一个单链表中,若p所指的结点不是最后结点,在p所指结点之后插进s所指结点,则应执行操纵

首先改变s的next指针的指向:s->next = p->next; 然后改变p的next指针的指向:p->next = s;

【数据结构】对于双向循环链表,每个结点有两个指针域next和prior,分别指向前驱和后继。在p指针所指向的结点之后插入s指针所指结点的操作应为?

双向链表稍微复杂些,主要分为以下步骤:

  • 对插入节点s的前驱和后继进行赋值:s->prior=p; s->next=p->next;
  • 修改p->next的前驱为s: p->next->prior = s;
  • 修改p->next的指向:p->next = s; 注意:最后两步不可以颠倒,如果先修改p->next,那么就找不到原来的next节点,也就无法修改其前驱指针了!

【数据结构】STL中vector详解?

在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacituy()函数返回的大小,当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。 优点:

  • 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组进行动态操作。通常体现在push_back() pop_back()
  • 随机访问方便,即支持[ ]操作符和vector.at()

缺点:

  • 在内部进行插入删除操作效率低。
  • 只能在vector的最后进行push和pop,不能在vector的头进行push和pop。
  • 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放

3

资源分享

欢迎关注我的个人公众号 (算法工程师之路),公众号内有大量视频资料和电子书资料以及算法笔记,回复关键字即可获取!

公众号简介:分享算法工程师必备技能,谈谈那些有深度有意思的算法,主要范围:C++数据结构与算法/深度学习(CV),立志成为Offer收割机!坚持分享算法题目和解题思路(Day By Day)

号外,算法刷题群已经建立,但由于人数超出限制,无法扫码添加,可以加号主微信(Leopard7319538)说明来意,可以加入到算法刷题群,每天2道编程题3道概念题,晚9点打卡,我们一起坚持下去!!!

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 作者:TeddyZhang,公众号:算法工程师之路
  • 欢迎关注我的个人公众号 (算法工程师之路),公众号内有大量视频资料和电子书资料以及算法笔记,回复关键字即可获取!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档