滴滴笔试题——小试牛刀

蔚落 2022-01-05 11:29 403阅读 0赞

题目：寻找丑数，把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

##### **输入描述: **整数N #####

##### **输出描述:**第N个丑数 #####

## 输入 ##

## 输出 ##

6
    思路：此题目中关键在于分析出新的丑数都是由现有的丑数乘以2,3,5得来的，如果现在的丑数为M，则将之前的丑数都乘以2，可以得出第一个大于M的丑数M2;
    同理，可以得出第一个大于M的M3和M5，即接下来的丑数即为M2,M3,M5中的最小值。
    前面分析中需要将所有的丑数都乘以2,3,5，实际上是没必要的，因为丑数都是排序好的，我们只需要记住第一次大于M的M2的位置，之后再对比乘以2的丑数的
    时候，仅对其之后的一个丑数乘以2即可，对于乘以3和5的操作，类似。
    代码：

1 import java.util.*;
     2 public class Main_1{
     3     public static void main(String args[]){
            //输入操作
     4         Scanner scanner = new Scanner(System.in);
     5         //Main_1 test = new Main_1();
     6         while (scanner.hasNext()){
     7             int n = scanner.nextInt();
     8             System.out.println(isUgly(n));
     9         }
    10     }
    11     public static int isUgly(int index){
            //判断是否是丑数
    12         if (index<0)
    13             return 0;
    14         int [] ugly = new int [index];
    15         ugly[0] = 1;
    16         int ugly2 = 0;
    17         int ugly3 = 0;
    18         int ugly5 = 0;
    19         for(int i =1; i<index;i++){
    20             int min = min(ugly[ugly2]*2,ugly[ugly3]*3,ugly[ugly5]*5);
    21             ugly[i] = min;
    22             while(ugly[ugly2]*2==ugly[i]){
    23                 ugly2++;
    24             }
    25             while(ugly[ugly3]*3==ugly[i]){
    26                 ugly3++;
    27             }
    28             while(ugly[ugly5]*5==ugly[i]){
    29                 ugly5++;
    30             }
    31         }
    32         return ugly[index-1];
    33     }
    34     public static int min(int a,int b,int c){
            //对比三个值的最小值函数
    35         int min = (a>b)?b:a;
    36         return (min>c)?c:min;
    37     } 
    38 }

题目：给出n个数字 a\_1,...,a\_n，问最多有多少不重叠的非空区间，使得每个区间内数字的xor都等于0。

**输入描述:**第一行一个整数ｎ； 第二行ｎ个整数　a\_1,...,a\_n； 对于30%的数据，n<=20； 对于100%的数据，n<=100000, a\_i<=100000；

**输出描述:**一个整数表示最多的区间个数；

示例1

## 输入 ##

3 0 2 2

## 输出 ##

感觉自己做了一道让自己觉得自己连题目都读不懂的题。。。

思路分析：即针对输入的数组array，按顺序将数据进行组合，组合成的一个区间，若区间中所有数字异或的结果为0，则该区间记为一个符合要求的区间。。。看这个array中共有多少个这种区间。**感觉题目中应该将区间改为集合。。。**

代码：

1 import java.util.Scanner;
     2 public class Main{
     3     public static void main (String [] args){
     4         Scanner sc = new Scanner(System.in);
     5         while(sc.hasNext()){
     6             int n = sc.nextInt();
     7             int arr[] = new int[n];
     8             for(int i =0;i<n;i++){
     9                 arr[i] = sc.nextInt();
    10             }
    11             int num = 0;//存放已经有的区间数
    12             int start = 0;//存放可以向前搜索的位置
    13             for(int i =0;i<n;i++){
    14                 int tmp = 0;
    15                 for(int j = i;j>=start;j--){
    16                     tmp^=arr[j];
    17                     if(tmp==0){
    18                         num++;
    19                         start = i+1;
    20                         break;
    21                     }
    22                 }
    23             }
    24             System.out.println(num);
    25         }
    26     }
    27 }

之后的选择题还没仔细看，大概看了一下，发现在数字规律方面还有考二进制的题目，对于15瓶可乐，只有一瓶有毒，问有几只小白鼠可以得出有毒的饮料，同样为二进制转换，最后为4只，我只能说顶礼膜拜。。。

转载于:https://www.cnblogs.com/10081-AA/p/10816534.html