刷题笔记之十 (小易的升级之路+找出字符串中第一个只出现一次的字符+洗牌+MP3光标位置)

曾经终败给现在 2023-09-25 12:50 19阅读 0赞

**目录**

1.存取任意指定序号的元素和在最后进行插入和删除运算,利用顺序表存储最节省时间

2. 数据结构中具有记忆功能的是栈

3. 递归程序的优化一般为 尾递归优化

4.二叉树遍历,前中后序遍历用到的是栈,而层序遍历用到的队列

5. 将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是n

6. 每经过一次元素的交换会产生新的逆序的是快速排序

7. 小易的升级之路

8. 找出字符串中第一个只出现一次的字符

9. 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度（D）

10. 给定下列程序，那么执行printf("%d\\n", foo(20, 13));的输出结果是（D）

11. 循环链表不是循环队列的存储结构,数组才是

12. 堆(大根堆/小根堆)是从任意结点出发到根路径上所经过的结点序列按其关键字有序

13. 堆排序是一个非常稳定的O(nlogn)

14. 将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是（C）

15. 洗牌

16. MP3光标位置

--------------------

## 1.存取任意指定序号的元素和在最后进行插入和删除运算,利用顺序表存储最节省时间 ##

若某线性表最常用的操作是存取任意指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间

A. 顺序表 B. 双链表 C. 带头结点的双循环链表 D. 单循环链表

存取任意指定序号,如果是数组取元素的话是O(1)

如果是在数组末尾的插入和删除那也是O(1),所以最好是数组,也就是顺序表存储最节省时间选A

--------------------

## 2. 数据结构中具有记忆功能的是栈 ##

下列数据结构具有记忆功能的是? C

A. 队列 B. 循环队列 C. 栈 D. 顺序表

记忆功能比如, 浏览器的回退功能,文本编辑器的撤销功能,都属于记忆功能

而栈的LIFO特性,A函数调用B函数,B函数调用C函数,然后最后一层一层返回,这也具有记忆功能

--------------------

## 3. 递归程序的优化一般为 尾递归优化 ##

对递归程序的优化的一般的手段为(A)

A. 尾递归优化 B. 循环优化 C. 堆栈优化 D. 停止值优化

比如快速排序和归并排序,在递归的终止条件是 l 是区间最左侧,r 是区间最右侧

//终止条件

(l >= r)\{return ;\}

//在递归终止条件处进行优化

//当区间个数较小时,采用插入排序来优化

(r - l <= 15) ---> 采用插入排序

所以这种对递归的优化一般都是 尾递归优化

--------------------

## 4.二叉树遍历,前中后序遍历用到的是栈,而层序遍历用到的队列 ##

将一颗二叉树的根结点放入队列,然后递归的执行如下操作,将出队结点所有子结点加入队.以上操作可以实现哪种遍历? D

A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历

题中是将二叉树的根结点放入队列中,在这几种遍历中,只有层序遍历会用到队列,

而前中后序遍历用到的是栈 ,所以选D

--------------------

## 5. 将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是n ##

将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是(D)

A. 2n B. 2n-1 C. n-1 D. n

两个有序的子区间个数都为n,最好的情况为第二个区间都要比第一个子区间要大

这样只需要比较n次即可(归并排序)

--------------------

## 6. 每经过一次元素的交换会产生新的逆序的是快速排序 ##

下列排序法中,每经过一次元素的交换会产生新的逆序的是(A)

A. 快速排序 B. 冒泡排序 C. 简单插入排序 D. 简单选择排序

数组的逆序:每当一次元素交换后,当前元素之后还有比当前元素还小的元素,就构成了一次逆序

而快排就是扫描到一个arr\[i\] < key,就把arr\[i\]交换到 < key 的区间中

每当交换一次,相对于元素key来将,就产生了一组新的逆序对

而冒泡,简单插入,简单选择排序都是交换相邻元素,不一定会产生逆序对(减少逆序对)

--------------------

## 7. 小易的升级之路 ##

**题目链接：**[小易的升级之路\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

**题目要求：**

![2948b78ccf0b494e940ddfa68a65e00f.png][]

![821b98e4d807438a8d1ce6b1ae23513e.png][]

**题目分析：**

**这道题就是根据c和b的大小来分情况讨论**

**c = a;**

**c >= bi 时, 那 c += bi**

**c < bi 时, 那 c += gcd(c,bi) 输出最后的c就可以了**

**只要会写 gcd(c,bi)求最大公约数那就没啥问题**

**最大公约数用辗转相除法,记住这个公式,下次看着这个写就可以了**

**gcd(a,b) = gcd(b,a%b) 最后返回a就可以**

**有两种,递归和非递归的**

![b7ef872029ff4926b81e4eec76da666c.png][]

**上代码**

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while(scan.hasNext()) {
                int n = scan.nextInt();
                int a = scan.nextInt();
                int[] b = new int[n];
                for (int i = 0; i < n; i++) {
                    b[i] = scan.nextInt();
                }
    
                int c = a;
                for (int i = 0; i < n; i++) {
                    if(b[i] <= c ) {
                        c += b[i];
                    }else {
                        c += gcd(b[i],c);
                    }
                }
                System.out.println(c);
            }
        }
    
        private static int gcd1(int a, int b) {
            if(b == 0) {
                return a;
            }
            int r = a%b;
            return gbc(b,r);
        }
        private static int gcd(int a, int b) {
            int c;
            while((c = a % b) != 0) {
                a = b;
                b = c;
            }
            return b;
        }
    }

--------------------

## 8. 找出字符串中第一个只出现一次的字符 ##

**题目链接：**[找出字符串中第一个只出现一次的字符\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com 1]

**题目要求：**

![0293c2c580a644c6bb29d5e7f3308aca.png][]

**题目分析：**

可以利用哈希的思想来做这道题

字符ascii码表是0-127,这里可以定义一个数组大小为128的数组 arr

然后根据每个字符的ascii对应arr数组位置,然后存入1,遇到相同字符,就给对应字符下标存储的元素+1

arr\['a'\]:1 arr\['s'\];1 arr\['d'\];1 arr\['f'\];1 arr\['a'\];2 arr\['s'\];2 arr\['d'\];2 arr\['f'\];2 arr\['0'\];1

**上代码**

import java.io.*;
    import java.util.*;
    
    public class Main {
        public static void findFirstChar(String str) {
            int[] count = new int[128];
            char[] arr = str.toCharArray();
            //遍历字符统计数组
            for(int i = 0; i < arr.length; i++) {
                count[arr[i]]++;
            } 
            //找到第一个只出现一次的字符
            boolean ret = false;
            for(int i = 0; i < arr.length; i++) {
                if(count[arr[i]] == 1) {
                    System.out.println(arr[i]); 
                    ret = true;
                    break;
                }
            }
            if(!ret) {
                System.out.println(-1);
            }
        }
    
        public static void main(String[] args) throws Exception{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String str;
            while((str = br.readLine()) != null) {
                findFirstChar(str);
            }
        }
    }

**方法二**

有两个方法是根据字符串中的字符来返回对应下标的

indexof() 是从前往后找,根据字符返回其下标

lastIndexof() 是从后往前找,根据字符返回其下标

如何可以通过遍历字符串来,来根据这两个方法其返回的下标是否一样来判断字符串中只出现一次的字符.

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.*;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String str;
            while ((str = br.readLine()) != null) {
                findFirstChar(str);
            }
        }
    
        private static void findFirstChar(String a) {
            int ret = 0;
            for (int i = 0; i < a.length(); i++) {
                //从前往后找,从后往前找,只有遍历完字符下标是一样的
                if(a.indexOf(a.charAt(i)) == a.lastIndexOf(a.charAt(i))) {
                    ret = 1;
                    System.out.println(a.charAt(i));
                    break;
                }
            }
            if(ret == 0) {
                System.out.println(-1);
            }
        }
    }

--------------------

## 9. 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度（D） ##

![b30f88cbc6ae42378136a4c2c2f59127.png][]

最坏情况 2-3-4-5-6 插入新结点1(尾插)

2-3-4-5-6-1,移动n次,所以最坏情况下O(n),选D

--------------------

## 10. 给定下列程序，那么执行printf("%d\\n", foo(20, 13));的输出结果是（D）  ##

![502eefa7b3a546a2a56a1c0eb5b7fd4d.png][]

![31258a2b7a3846b6b95b6b4472f0e64c.png][]

--------------------

## 11. 循环链表不是循环队列的存储结构,数组才是 ##

![9faa94c48fdb479e871320d3360f502b.png][]

循环链表不是循环队列的存储结构,数组才是

--------------------

## 12. 堆(大根堆/小根堆)是从任意结点出发到根路径上所经过的结点序列按其关键字有序 ##

![3cb0258de1dd456b9898d25c935776db.png][]

关键字有序是升序或者降序

哈夫曼树:是带权值的树(与元素大小顺序无关)

二叉排序树(BST)的特点是:

（1）若左子树不空，则左子树上所有[结点][Link 1]的值均小于它的[根结点][Link 2]的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

![fdf1bd05e4ef476abc3691e0d6c51919.png][]这个就是一个二叉排序树,可以看到从根节点走下去,不是有序的

AVL是平衡二叉查找树,它的特点是,树中任意结点的两个子树高度最大差为1,所以也叫高度平衡树

堆,如果是大根堆,那么堆中的所有结点都是,根节点大于左右孩子,同样小根堆是根节点小于左右孩子,所以堆是有序的选D

--------------------

## 13. 堆排序是一个非常稳定的O(nlogn) ##

![51f42cbc892247c1b23f160d7f8ee3f7.png][]

堆排序是一个非常稳定的O(nlogn)

快速排序,当出现大量重复元素或者数组几乎有序时,递归数退化为链表O(n^2)

冒泡排序O(n^2)

希尔排序本质上是插入排序的优化,而插入排序是O(n^2),优化为希尔排序后至少是比O(nlogn)

--------------------

## 14. 将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是（C）  ##

![0b48c7864e254b73af06d1cf6c0dfa14.png][]

![aac13e3b42b94d90a5dc0d4c0fd83f1b.png][]

--------------------

## 15. 洗牌 ##

**题目链接：**[洗牌\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com 2]

**题目要求：**

![251ac7e2718f4809a039e4f803267594.png][]

**题目分析：**

![3e4d92d75d6644a39195febd8614cda0.png][]**上代码**

import java.util.*;
    
    public class Main {
        // 左: i -->  2*i;
        // 右: i+n --> 2*i + 1;
        private static void playCard(int[] cards, int n,int k ) {
            for(int i = 0; i < k; i++) {
                //一次洗牌的顺序
                int[] newCards = new int[cards.length];
                //遍历编号为0-n-1
                for(int j = 0; j < n; j++) {
                    newCards[2*j] = cards[j];
                    newCards[2*j+1] = cards[j+n];
                }
                cards = newCards;
            }
            //从上往下打印
            printCard(cards);
        }
        private static void printCard(int[] cards) {
            for(int i = 0; i < cards.length-1; i++) {
                System.out.print(cards[i] + " ");
            }
            System.out.println(cards[cards.length-1]);
        }
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int group = scan.nextInt();
            for(int i = 0; i < group; i++) {
                //读入每组数据
                int n = scan.nextInt();
                int k = scan.nextInt();
                int[] arr = new int[2*n];
                for(int j = 0; j < 2*n; j++) {
                    arr[j] = scan.nextInt();
                }
                //洗牌
                playCard(arr,n,k);
            }
        }
    }

--------------------

## 16. MP3光标位置 ##

**题目链接：**[MP3光标位置\_牛客题霸\_牛客网 (nowcoder.com)][MP3_ _nowcoder.com]

**题目要求：**

![f0569a04a7334d648885ade0d78bd986.png][]

![671a782214d5411dbb9a571bb359234e.png][]

![77d2f1d7b3024b1d90aa02cb2c9c0070.png][]

**题目分析：**

这道题需要多注意每个条件

可以使用 first来表示列表的起始位置,使用mouse来表示光标的位置

所以每个判断条件也就是来写 first mouse 和U/D 的值和关系

只有一个地方需要注意

当 n > 4 时

//屏幕显示的不是第一页时,光标在当前屏幕最后一首歌时,按Down键显示下一首歌,

正常根据这个是写这样的条件 first != 1 && mouse == first+3 && order\[i\] == 'D'

但是这里要注意,如果是最后一页的话,按D就会到第一首歌

所以应该是 first != n-3 && mouse == first+3 && order\[i\] == 'D'

**上代码**

import java.util.Scanner;
    import java.io.*;
    
    public class Main {
        private static void mouseMove(String numStr, String orderStr) {
            //歌曲数量
            int n = Integer.parseInt(numStr);
            //指令数组: ud
            char[] order = orderStr.toCharArray();
            //当前鼠标所在的位置
            int mouse = 1;
            //显示列表所在的起始位置
            int first = 1;
    
            //指令处理
            // n <= 4
            if(n <= 4) {
                for(int i = 0; i < order.length; i++) {
                    if(mouse == 1 && order[i] == 'U') {
                        mouse = n;
                    }else if(mouse == n && order[i] == 'D') {
                        mouse = 1;
                    }else if(order[i] == 'U') {
                        mouse--;
                    }else if(order[i] == 'D') {
                        mouse++;
                    }
                }
                //输出
                //打印当前显示列表
                for(int i = 1; i < n; i++) {
                    System.out.print(i + " ");
                }
                System.out.println(n);
                //打印当前歌曲
                System.out.println(mouse);
            } else {
                // n>4
                for (int i = 0; i < order.length; i++) {
                    if(first == 1 && mouse == 1 && order[i] == 'U') {
                        first = n-3;
                        mouse = n;
                    }else if (first == n-3 && mouse == n && order[i] == 'D') {
                        first = 1;
                        mouse = 1;
                    }else if (first != 1 && mouse == first && order[i] == 'U') {
                        first--;
                        mouse--;
                        //屏幕显示的不是第一页时,光标在当前屏幕最后一首歌时,按Down键显示下一首歌,这里要注意,如果是最后一页的话,按D就会到第一首歌
                    }else if (first != n-3 && mouse == first+3 && order[i] == 'D') {
                        first++;
                        mouse++;
                        //其他情况只移动光标
                    }else if (order[i] == 'U') {
                        mouse--;
                    }else if (order[i] == 'D') {
                        mouse++;
                    }
                }
                //输出
                //打印当前显示列表
                for(int i = first; i < first+3; i++) {
                    System.out.print(i + " ");
                }
                System.out.println(first+3);
                //打印当前歌曲
                System.out.println(mouse);
            }
        }
        public static void main(String[] args) throws Exception{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String numStr;
            while((numStr = br.readLine()) != null) {
                String orderStr = br.readLine();
                mouseMove(numStr,orderStr);
            }
        }
    }

[_nowcoder.com]: https://www.nowcoder.com/practice/fe6c73cb899c4fe1bdd773f8d3b42c3d?tpId=122&tqId=33649&ru=/exam/oj
[2948b78ccf0b494e940ddfa68a65e00f.png]: https://img-blog.csdnimg.cn/2948b78ccf0b494e940ddfa68a65e00f.png
[821b98e4d807438a8d1ce6b1ae23513e.png]: https://img-blog.csdnimg.cn/821b98e4d807438a8d1ce6b1ae23513e.png
[b7ef872029ff4926b81e4eec76da666c.png]: https://img-blog.csdnimg.cn/b7ef872029ff4926b81e4eec76da666c.png
[_nowcoder.com 1]: https://www.nowcoder.com/practice/e896d0f82f1246a3aa7b232ce38029d4?tpId=37&tqId=21282&ru=/exam/oj
[0293c2c580a644c6bb29d5e7f3308aca.png]: https://img-blog.csdnimg.cn/0293c2c580a644c6bb29d5e7f3308aca.png
[b30f88cbc6ae42378136a4c2c2f59127.png]: https://img-blog.csdnimg.cn/b30f88cbc6ae42378136a4c2c2f59127.png
[502eefa7b3a546a2a56a1c0eb5b7fd4d.png]: https://img-blog.csdnimg.cn/502eefa7b3a546a2a56a1c0eb5b7fd4d.png
[31258a2b7a3846b6b95b6b4472f0e64c.png]: https://img-blog.csdnimg.cn/31258a2b7a3846b6b95b6b4472f0e64c.png
[9faa94c48fdb479e871320d3360f502b.png]: https://img-blog.csdnimg.cn/9faa94c48fdb479e871320d3360f502b.png
[3cb0258de1dd456b9898d25c935776db.png]: https://img-blog.csdnimg.cn/3cb0258de1dd456b9898d25c935776db.png
[Link 1]: https://baike.baidu.com/item/%E7%BB%93%E7%82%B9/9794643?fromModule=lemma_inlink
[Link 2]: https://baike.baidu.com/item/%E6%A0%B9%E7%BB%93%E7%82%B9/9795570?fromModule=lemma_inlink
[fdf1bd05e4ef476abc3691e0d6c51919.png]: https://img-blog.csdnimg.cn/fdf1bd05e4ef476abc3691e0d6c51919.png
[51f42cbc892247c1b23f160d7f8ee3f7.png]: https://img-blog.csdnimg.cn/51f42cbc892247c1b23f160d7f8ee3f7.png
[0b48c7864e254b73af06d1cf6c0dfa14.png]: https://img-blog.csdnimg.cn/0b48c7864e254b73af06d1cf6c0dfa14.png
[aac13e3b42b94d90a5dc0d4c0fd83f1b.png]: https://img-blog.csdnimg.cn/aac13e3b42b94d90a5dc0d4c0fd83f1b.png
[_nowcoder.com 2]: https://www.nowcoder.com/practice/5a0a2c7e431e4fbbbb1ff32ac6e8dfa0?tpId=85&&tqId=29848&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
[251ac7e2718f4809a039e4f803267594.png]: https://img-blog.csdnimg.cn/251ac7e2718f4809a039e4f803267594.png
[3e4d92d75d6644a39195febd8614cda0.png]: https://img-blog.csdnimg.cn/3e4d92d75d6644a39195febd8614cda0.png
[MP3_ _nowcoder.com]: https://www.nowcoder.com/practice/eaf5b886bd6645dd9cfb5406f3753e15?tpId=37&&tqId=21287&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
[f0569a04a7334d648885ade0d78bd986.png]: https://img-blog.csdnimg.cn/f0569a04a7334d648885ade0d78bd986.png
[671a782214d5411dbb9a571bb359234e.png]: https://img-blog.csdnimg.cn/671a782214d5411dbb9a571bb359234e.png
[77d2f1d7b3024b1d90aa02cb2c9c0070.png]: https://img-blog.csdnimg.cn/77d2f1d7b3024b1d90aa02cb2c9c0070.png