【寒假第2天】LeetCode刷题-创新互联

🌈一、选择题 👿第1题：

下面给出的四种排序法中( )排序法是不稳定性排序法

A.插入排序                  B.冒泡排序
C.归并排序                  D.堆，希尔排序，快速排序

答案：D
创新互联服务项目包括清徐网站建设、清徐网站制作、清徐网页制作以及清徐网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，清徐网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到清徐省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

为啥堆排序是不稳定的？
关于堆排序有大堆排序和小堆排序，但是他俩的本质都是沿着根节点找到叶子节点并比较两者的值交换。因此对于相同的关键字可能存在后面的先被交换到前面，因而堆排序不是稳定的。
比如：3 27 36 27，(小堆排序)
如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。
为啥选择排序是不稳定的？
什么是选择排序？每一次从待排序的数据元素中选出最小（或大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
就比如：80*， 80， 60, （这个*代表两个相同数的顺序不一样。）
那第一次排序后的顺序是60，80， 80*
第2次排序后顺序不变60，80，80*,但是稳定的排序得到的结果是60，80*，80。就比如插入排序，它的区间是80*，80，60插入到两者之间，然后比较80*，60，最后交换，60，80*，80这个是稳定的，所以选择排序是不稳定的。
希尔排序之所以不稳定，也是犯了上面的毛病，希尔排序是插入排序的亚种，它把一个无序数组分好几块分别进行排序，如果有重复的数字，也会顺序错误。
快速排序也是一样的，他是先选择一个基数，然后小于等于这个基数的排在基数前面，大于的排在他后面。如果说A和B相等，A在前，但是我们选择A作为基数，那B=A是不是可以排在他前面，这是不是就造成不稳定了。
排序算法不稳定的含义是:
在排序之前,有两个数相等.但是在排序结束之后,它们两个有可能改变顺序。
只有以上4种排序是不稳定排序。

👿第2题：

对数据序列 { 15,9,7,8,20,-1,4 } 进行排序，
进行一趟后数据的排序变为 {9,15,7,8,20,-1,4 } ，
则采用的是( )算 法
A.直接选择排序          B.冒泡排序
C.直接插入排序          D.希尔排序

答案：C

答案解析：排序前到排序后，就15和9的位置发生了改变。

A选项：看到选择排序可以直接排除了，两头的数既不是大值也不是最小值。

B选项：要是冒泡排序的话9在前面，20在后面，排除。

C选项：15，9形成一个区间，第一步就是把他俩的顺序交换，没毛病，符合题目。然后第3个数看看在不在这个区间内，在的话就进去，不在就更新边界。

D选项：如果是希尔排序的话，间隔是1，不可能仅仅只是15，9的顺序变化20，-1的顺序也会变化。

👿第3题：

某学生信息表，设一组表示成绩的关键字序列 (24,15,32,28,19,10,40) 
采用直接插入排序时，当插入记录19到有序表时，
为找插入位置需比较次数为（ ）
A.2       B.3
C.4       D.5

答案：C

大概是：24直接放进去 24
第一趟 15比24小放到24前面，比较1次 15 24
第二趟 32比24大放24后面，比较1次 15 24 32
第三趟 28比32小，比24大，比较2次 15 24 28 32
第四趟，19比32小，比28小，比24小，比15大，比较4次 15 19 24 28 32.

👿第4题：

关于堆排序复杂度分析的叙述中正确的是( )
A.堆排序的时间复杂度为 O(nlogn)。
B.整个构建堆的时间复杂度为 O(n)。
C.堆排序的空间复杂度为 O(1)。
D.堆排序是一种不稳定的排序算法。

答案：D

解析看第一题图。

🌈二、编程 🐴第1题：检查两个字符串是否相同

解题思路：
看到这个题我就想到了用哈希表映射这个思路，不知道各位小伙伴想到没，在寒假第一天我们就用过这个思路。
把出现在word1中的字母映射到哈希表上，出现一次就+1，然后在把word2上的单词映射到哈希表上，出现一次就-1，让两者互相抵消，直到每一种字母的偏差都小于等于3就完成任务了。
注意：不是全部偏差不大于3，而是每一种字母的偏差不大于3就可以。它的条件更宽松了。

class Solution {
public:
    bool checkAlmostEquivalent(string word1, string word2) {
        vectorhashtable(26,0); //定义一个26位空间的哈希表
        for(size_t i=0;i3)
            return false;
          
        }
          return true;
    }
};

这个-‘a’是因为，我们开辟的的空间是26个，从0开始的，但是‘a’-‘z’的ascll码是从97开始的，-‘a’就是-97，可以使他们的顺序正好对应我们上面开辟的空间。

🐴第2题：字符串解码

提示：
1<= s.length<= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1, 300]

解题思路：
这个题说难也不难，最重要的一步是[]，怎么匹配的问题。也就是说[]中内容是一个整体，不能把[]中的内容分开这个是这里面的重中之难。
我想到的第一反应就是用栈，不知道各位的反应是啥，因为我做过一个配对'[' , ']'的问题，那个就是用栈的先进后出解决的，这个我也想到用栈来解决[]的配对问题。
这里我用了两个栈：数字栈tmp_stack, 字符栈str_stack,一个存的是数字，另一个存字符。
整体遍历一遍数组，这里面一共有四种情况：
遇到的是数字，但是不清楚数字的大小，所以第一步是求数字大小num+=num*10+s[i]-'0'这里面有两个小细节：num是临时的，方便我们求出现的数字，用完后，num=0，再用下一个；2.之所以出现-‘0’是因为，数组中出现的是字符，比如0,来说，数组中出现的是字符'0',不是数字‘0’，把字符转换为数字就是-'0'。
遇到的是'[',遇到'['就代表入栈，现阶段就可以把数字存入数字栈了。接下来num可以等于0了，以便处理下一个数字部分。然后把'['压入栈中。
遇到的是']'，遇到']'就代表出栈。此时就可以将字符栈中的字符弹出，直到弹出左括号结束，左括号代表结束的标志。接下来把弹出来的字符串进行一次完全的反转，然后弹出数字栈的栈顶元素tmp2_stack,并且重复拼接tmp2_stack次反转后的字符串。
遇到的是普通字符，这个最简单，直接压入符号栈。
这里我们用到了四个栈，
两个字符栈：str_stack和str2_stack,str2_stack主要的作用是储存反转后的字符串。
两个数字栈：tmp_stack和 tmp2_stack，tmp2_stack主要是存储栈顶的数字的。

class Solution {
public:
    string decodeString(string s) {
        stacktmp_stack;   //数字栈，存放出现的数字
        string str_stack;  //字符栈，存放出现的字符
        
        int num=0;
       for(int i=0;i='0'&&s[i]<='9')
           {
               num=num*10+s[i]-'0';    //把字符转化为数字
           }

            //2.出现的是'['
           else if(s[i]=='[')
            {
                tmp_stack.push(num);    //数字num进入数字栈中
                num=0;  //变成0，方便知道下一个数字的大小
                str_stack+=(s[i]);   //字符进入到字符栈中
            }

            //3.出现的是']'，出现这个就代表出栈了。
           else if(s[i]==']')
            {
                string str2_stack;  //临时字符栈，
               int  j=str_stack.size()-1;
               while(str_stack[j]!='[')
                {
                    str2_stack+=str_stack[j];
                    str_stack.pop_back();
                    j--;
                }
                str_stack.pop_back();  //把'['弹出去
                int tmp2_stack=tmp_stack.top();
                tmp_stack.pop();
                reverse(str2_stack.begin(),str2_stack.end());
                for(int q=0;q

特别注意：
栈的函数名称，出栈：pop，入栈:push,返回栈顶元素：top。

string容器也有出入栈的相关操作，push_back,pop_back，正好可以模拟字符栈。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

                

                当前标题：【寒假第2天】LeetCode刷题-创新互联                

                文章起源：http://www.wjwzjz.com/article/ceiidd.html

新网创想网站建设，新征程启航

【寒假第2天】LeetCode刷题-创新互联

其他资讯