网易2020校招笔试- 大数据开发工程师（正式批）

深藏阁楼爱情的钟 2022-11-25 11:36 88阅读 0赞

### 目录 ###

*  一、翻倍
 *   *  方法一：暴力
     *  方法二：递归
 *  二、跳柱子
 *   *  方法一：暴力，寻找能到达的最高柱子，方便我下次跳
     *  方法二：动态规划dp
 *  三、人数统计
 *   *  方法：哈希表
 *  四、积木
 *   *  方法

> 如果你从本文中学习到丝毫知识，那么请您点点**关注、点赞、评论和收藏**  
> 大家好，我是[爱做梦的鱼][Link 1]，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：[爱做梦的鱼https://zihao.blog.csdn.net/][https_zihao.blog.csdn.net]，微信公众号、微信视频号为[【程序猿干货铺】][Link 2]，qq交流群为：[1107710098][]，  
> ![程序猿干货铺][Image 1]

> [本题出处——牛客链接：https://www.nowcoder.com/test/20791044/summary][https_www.nowcoder.com_test_20791044_summary]

# 一、翻倍 #

**时间限制：** C/C++ 2秒，其他语言4秒  
**空间限制：** C/C++ 256M，其他语言512M

小易给定你数字  A ， B ( A < B ) A，B (A<B) A，B(A<B) 和系数  p ， q p，q p，q。每次操作你可以将 A 变成  A + p A+p A\+p 或者 p 将变成  p × q p\\times q p×q 。问至少几次操作使得  B ≤ A B \\leq A B≤A 。

**输入描述:**  
第一行数据组数  T T T，对于每组数据，一行四个整数  A ， B ， p ， q A，B，p，q A，B，p，q。  
 1 ≤ A , p , B ≤ 1 0 9 1\\leq A,p,B \\leq10^9 1≤A,p,B≤109,  2 ≤ q ≤ 10 2\\leq q \\leq10 2≤q≤10,  1 ≤ T ≤ 5 1\\leq T \\leq5 1≤T≤5  
.  
**输出描述:**  
对于每组数据，输出一个数字表示答案

输入例子1:
    2
    1 5 7 2
    3 5 1 2
    
    输出例子1:
    1
    2

输入例子2:
    2
    1 15 4 2
    12 19 3 2
    
    输出例子2:
    3
    3

## 方法一：暴力 ##

import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/8/7 * @Time: 15:00 * @Version: 1.0 * @Description: Description */
    public class Doubled { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt();
            for (int i = 0; i < T; i++) { 
                System.out.println(count(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt()));
            }
            sc.close();
        }
    
        public static int count(int A, int B, long p, int q) { 
            int res = 1;
            while (A < B) { 
                if (A + p >= B) { 
                    return res;
                } else { 
                    p = p * q;
                    res++;
                }
            }
            /*while (A + p < B) { p = p * q; res++; }*/
            return res;
        }
    }

## 方法二：递归 ##

import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/8/7 * @Time: 16:51 * @Version: 1.0 * @Description: Description */
    
    public class Doubled2 { 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int t = in.nextInt();
            for (long i = 0; i < t; i++) { 
                long a = in.nextLong();
                long b = in.nextLong();
                long p = in.nextLong();
                long q = in.nextLong();
                long nums = getDoubling(a, b, p, q, 0);
                System.out.println(nums);
            }
    
        }
    
        private static long getDoubling(long a, long b, long p, long q, long nums) { 
            if (a + p >= b)
                return nums + 1;
            else if (a + p * q >= b)
                return nums + 2;
            else return getDoubling(a, b, p * q * q, q, nums + 2);
    
        }
    }

# 二、跳柱子 #

**时间限制：** C/C++ 2秒，其他语言4秒

**空间限制：** C/C++ 256M，其他语言512M

小易有  n n n 根柱子，第i根柱子的高度为  h i h\_i hi 。一开始小易站在第一根柱子上。小易能从第  i i i 根柱子跳到第  j j j 根柱子，当且仅当且  h j ≤ h i h\_j \\leq h\_i hj≤hi 且  1 ≤ j − i ≤ k 1\\leq j-i \\leq k 1≤j−i≤k 。其中为指定的一个数字。  
另外小易拥有一次释放超能力的机会。这个超能力能让小易从柱子 i 跳到任意满足  1 ≤ j − i ≤ k 1\\leq j-i \\leq k 1≤j−i≤k 的柱子 j 而无视柱子高度的限制。  
现在小易想知道，小易是否能到达第 n 根柱子。

**输入描述:**  
第一行数据组数  T T T  
对于每组数据，第一行数字  n , k n , k n,k ，接下来一行  n n n 个数字表示  h i h\_i hi.  
 1 ≤ n ≤ 1000 1\\leq n \\leq 1000 1≤n≤1000 ,  1 ≤ h i ≤ 1 0 9 1\\leq h\_i \\leq 10^9 1≤hi≤109 ,  1 ≤ T ≤ 10 1\\leq T \\leq 10 1≤T≤10 ,  1 ≤ k ≤ n 1\\leq k \\leq n 1≤k≤n

**输出描述:**  
对于每组数据，输出YES或NO

输入例子1:
    1
    5 3
    6 2 4 3 8
    
    输出例子1:
    YES

输入例子2:
    1
    5 2
    1 8 2 3 4
    
    输出例子2:
    NO

## 方法一：暴力，寻找能到达的最高柱子，方便我下次跳 ##

/** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/8/8 * @Time: 10:28 * @Version: 1.0 * @Description: Description */
    
    import java.util.Scanner;
    
    public class JumpPillar5_Violence { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt();
            int n = 0, k = 0;
            for (int i = 0; i < T; i++) { 
                n = sc.nextInt();
                k = sc.nextInt();
                int[] nums = new int[n];
                for (int j = 0; j < n; j++)
                    nums[j] = sc.nextInt();
                System.out.println(solution(n, k, nums));
            }
        }
    
        public static String solution(int n, int k, int[] nums) { 
            int big = 1;
            int index = 0;
            while (index < nums.length - 1) { 
                int tmp = index;
                int max = 0, max_index = index;
                for (int j = index + 1; j < index + 1 + k && j < nums.length; j++) { 
                    if (nums[j] < nums[index]) { 
                        max_index = (max > nums[j]) ? max_index : j;
                        max = Math.max(nums[j], max);
                    }
                }
                index = max_index;
                if (tmp == index && big > 0) { 
                    big--;
                    max = 0;
                    max_index = index;
                    for (int j = index + 1; j < index + 1 + k && j < nums.length; j++) { 
                        max_index = (max > nums[j]) ? max_index : j;
                        max = Math.max(nums[j], max);
                    }
                    index = max_index;
                } else if (tmp == index && big <= 0)
                    return "NO";
            }
            return "YES";
        }
    }

## 方法二：动态规划dp ##

/** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/8/8 * @Time: 9:54 * @Version: 1.0 * @Description: Description */
    
    import java.util.Scanner;
    
    public class JumpPillar3 { 
        public static void main(String[] args) { 
    
            Scanner sc = new Scanner(System.in);
    
            int m = sc.nextInt();
    
            while (m-- > 0) { 
                int n = sc.nextInt();
                int k = sc.nextInt();
    
                int[] a = new int[n];
                for (int i = 0; i < n; i++) { 
                    a[i] = sc.nextInt();
                }
    
                int[] dp = new int[n];
                dp[0] = 1;
    
                for (int i = 0; i < n; i++) { 
                    if (dp[i] > 0) { 
                        for (int j = i + 1; j <= i + k && j < n; j++) { 
                            if (a[i] >= a[j]) { 
                                if (dp[j] == 0 || dp[j] > dp[i])
                                    dp[j] = dp[i];
                            } else if (dp[i] == 1 && dp[j] == 0)
                                dp[j] = 2;
                        }
                    }
                }
    
                System.out.println(dp[n - 1] > 0 ? "YES" : "NO");
            }
    
        }
    }

# 三、人数统计 #

**时间限制：** C/C++ 2秒，其他语言4秒

**空间限制：** C/C++ 256M，其他语言512M

小易的公司一共有 n 名员工, 第个人每个月的薪酬是  x i x\_i xi 万元。  
现在小易的老板向小易提了次询问, 每次询问老板都会给出一个整数 k 小易要快速回答老板工资等于 k 的员工的数量。

**输入描述:**  
第一行，两个空格间隔的整数 n 和 m ,表示人数和提问的次数  
第二行，n 个用空格间隔的整数  x i x\_i xi ，表示每名员工的薪酬  
接下来有 m 行，每行一个整数，表示老板的一次提问。  
 1 ≤ m ≤ 80000 1\\leq m \\leq 80000 1≤m≤80000 ,  1 ≤ n ≤ 100000 1\\leq n \\leq 100000 1≤n≤100000 ,  1 ≤ x i ≤ 500 , 000 , 000 1\\leq x\_i \\leq 500,000,000 1≤xi≤500,000,000

**输出描述:**  
m 行，每行一个整数，表示对应提问的答案

输入例子1:
    7 4
    6 2 1 2 6 2 5
    6
    5
    8
    2
    
    输出例子1:
    2
    1
    0
    3

## 方法：哈希表 ##

import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/8/7 * @Time: 22:19 * @Version: 1.0 * @Description: Description */
    public class PeopleCount { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) { 
                int x = sc.nextInt();
                map.put(x, map.getOrDefault(x, 0) + 1);
            }
            for (int i = 0; i < m; i++) { 
                int k = sc.nextInt();
                if (map.get(k) == null) { 
                    System.out.println(0);
                } else { 
                    System.out.println(map.get(k));
                }
            }
            sc.close();
        }
    }

# 四、积木 #

**时间限制：** C/C++ 2秒，其他语言4秒

**空间限制：** C/C++ 256M，其他语言512M

小易有 n 堆积木，第 i 堆积木有  h i h\_i hi 块。小易还拥有一个容量无限的背包。  
一开始小易站在第一堆积木旁边。每次小易可以选择进行下列三种操作中的一种：  
1、从背包里掏出一块积木（如果有的话）放到当前这一堆里  
2、从当前这一堆积木里掏出一块塞到背包里(如果当前积木堆不为空的话)  
3、从当前这一堆走到下一堆。  
一开始小易的背包里有 m 块积木。小易希望把这些个积木变成严格递增的（即  h 1 < h 2 < h 3 ⋅ ⋅ ⋅ < h n h\_1 < h\_2 < h\_3 ··· <h\_n h1<h2<h3⋅⋅⋅<hn 。小易希望知道这是否有可能能完成。（所有操作结束后不需要保证背包里没有积木了，可以有积木堆为空）。

**输入描述:**  
第一行数据组数 T  
对于每组数据，第一行数字 n , m，接下来一行 n 个数字表示  h i h\_i hi .  
 1 ≤ n ≤ 100000 1\\leq n \\leq 100000 1≤n≤100000 ,  0 ≤ h i ≤ 1 0 9 0\\leq h\_i \\leq 10^9 0≤hi≤109 ,  1 ≤ T ≤ 10 1\\leq T \\leq 10 1≤T≤10 ,  1 = 0 ≤ m ≤ 1 0 9 1=0\\leq m \\leq 10^9 1=0≤m≤109

**输出描述:**  
对于每组数据输出一行，输出结果 YES 或 NO

输入例子1:
    1
    5 3
    2 2 3 3 1
    
    输出例子1:
    YES

输入例子2:
    1
    5 2
    0 0 1 2 1
    
    输出例子2:
    NO

## 方法 ##

package nowcoder;
    
    import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/8/8 * @Time: 11:26 * @Version: 1.0 * @Description: Description */
    public class BuildingBlock { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt();
            for (int i = 0; i < T; i++) { 
                int n = sc.nextInt();
                long sum = sc.nextInt(); //m
                boolean flag = true;
                int[] arr = new int[n];
                for (int j = 0; j < n; j++) { 
                    arr[j] = sc.nextInt();
                }
                for (int j = 0; j < n; j++) { 
                    sum += arr[j];
                    if (sum < j * (j + 1) / 2) { 
                        System.out.println("NO");
                        flag = false;
                        break;
                    }
                }
                if (flag) { 
                    System.out.println("YES");
                }
            }
            sc.close();
        }
    }

[Link 1]: https://blog.csdn.net/weixin_43124279
[https_zihao.blog.csdn.net]: https://zihao.blog.csdn.net/
[Link 2]: https://s1.ax1x.com/2020/06/11/tHUSvq.png
[1107710098]: https://s1.ax1x.com/2020/06/26/NroKrd.jpg
[Image 1]: 
[https_www.nowcoder.com_test_20791044_summary]: https://www.nowcoder.com/test/20791044/summary