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)

题目要求：

题目分析：

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

字符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）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

冒泡排序O(n^2)

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

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

15. 洗牌

题目链接：洗牌_牛客题霸_牛客网 (nowcoder.com)

题目要求：

题目分析：

上代码

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)

题目要求：

题目分析：

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

可以使用 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);
        }
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87307.html