笔试题总结6.14

港控/mmm° 2022-01-14 10:47 244阅读 0赞

1.序列找数

题目描述：从非负整数序列0,1,2，….，n中给出包含其中n个数的子序列，请找出未出现在该子序列中的那个数。  
输入描述：输入为n+1个非负整数，用空格分开。  
其中：首个数字为非负整数序列的最大值n，后面n个数字为子序列中包含的数字。  
输出描述：输出为1个数字，即未出现在子序列中的那个数。  
示例：  
输入：  
3 3 0 1  
输出：  
2

package org.buptdavid.datastructure.array;

import java.util.Scanner;

/\*\*  
 \* 序列找数  
 \* Created by ZD on 2018/4/10.  
 \*/  
public class Main\_Z1 \{  
    public static void main(String\[\] args)\{  
        Scanner sc = new Scanner(System.in);  
        int n = sc.nextInt();  
        if (n >= 0)\{  
            StringBuilder b = new StringBuilder();  
            for (int i = 0; i < n; i++)\{  
                b.append(sc.nextInt());  
            \}  
            findNoNumber(b.toString());  
        \}  
    \}

/\*\*  
     \* 找到未出现在该子序列中的数  
     \* @param s  
     \*/  
    private static void findNoNumber(String s) \{  
        if (s == null || s.length() == 0)  
            return;  
        for (int i = 0; i <= s.length(); i++)\{  
            if (!s.contains(" "+i+" "))\{  
                System.out.println(i);  
                return;  
            \}  
        \}  
    \}  
\}

2.小招喵跑步

题目描述：  
小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：  
1.数轴上向前走一步，即n=n+1;  
2.数轴上向后走一步，即n=n-1;  
3.数轴上使劲跳跃到当前点的两倍，即n=2\*n  
现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？  
输入描述：  
小招喵想去的位置x  
输出描述：  
小招喵最少需要的步数  
示例：  
输入：  
3  
输出：  
3

import java.util.Scanner;

/\*\*  
 \* 小招猫跑步  
 \* Created by ZD on 2018/4/10.  
 \*/  
public class Main\_Z2 \{  
    public static void main(String\[\] args)\{  
        Scanner sc = new Scanner(System.in);  
        while (sc.hasNext()) \{  
            long x = sc.nextLong();//目的地  
            System.out.println(countQuickSteps(x));  
        \}  
    \}

/\*\*  
     \* 计算最快走法需要多少步  
     \* @param x  
     \*/  
    private static long countQuickSteps(long x) \{  
        if (x < 0)  
            x = -x;  
        long quickSteps;  
        if (x == 0)  
            return 0;  
        if (x == 1)  
            return 1;  
        if (x == 2)  
            return  2;  
        if (x % 2 == 0)\{  
            quickSteps = countQuickSteps(x/2) + 1;  
        \}else \{  
            quickSteps = countQuickSteps(x / 2) + 2;  
        \}  
      return quickSteps;  
    \}  
\}

3.满足条件的数字

题目描述：  
如果一个正整数，它的质因数只包含2,3,5，那么这个数满足条件。  
同时，特别规定1也是满足条件的数字。  
示例：前10个满足条件的数字是1,2,3,4,5,6,8,9,10,12  
请编写一个函数，返回第n个满足条件的数  
输入描述：  
输入为n  
输出描述：  
输出为第n个满足条件的数  
示例：  
输入：  
5  
输出：  
5

package org.buptdavid.datastructure.array;

import java.util.Scanner;

/\*\*  
 \* Created by ZD on 2018/4/10.  
 \*/  
public class Main\_Z3 \{  
    public static void main(String args\[\])\{  
        Scanner sc = new Scanner(System.in);  
        while (sc.hasNext()) \{  
            int n = sc.nextInt();  
            countN(n);  
        \}

/\*\*  
     \* 打印出第n个满足条件的数  
     \* @param n  
     \*/  
    private static void countN(int n) \{  
        if (n <= 0)  
            return;  
        int count = 1;  
        int number = 1;  
        while (count < n)\{  
            number++;  
            int temp = number;  
            boolean flag1 = true;  
            while (temp != 1 && flag1) \{  
                if (temp % 2 == 0) \{  
                    temp = temp / 2;  
                    flag1 = true;  
                    continue;  
                \}else \{  
                    flag1 = false;  
                \}  
                if (temp % 3 == 0) \{  
                    temp = temp / 3;  
                    flag1 = true;  
                    continue;  
                \}else \{  
                    flag1 = false;  
                \}  
                if (temp % 5 == 0) \{  
                    temp = temp / 5;  
                    flag1 = true;  
                    continue;  
                \}else \{  
                    flag1 = false;  
                \}  
            \}  
            if (temp == 1)  
                count++;  
            \}  
        System.out.println(number);  
        \}

作者：Violet-Zhao  
来源：CSDN  
原文：https://blog.csdn.net/Demodan/article/details/79888460  
版权声明：本文为博主原创文章，转载请附上博文链接！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1][]

import java.util.\*;

public class Main \{

public static void main(String\[\] args)\{  
        Scanner sc=new Scanner(System.in);  
        while (sc.hasNext())\{  
            List<Integer> stoma=new ArrayList<>();  
            List<Integer> bag=new ArrayList<>();  
            String tmp1=sc.nextLine();  
            String\[\] tmp11=tmp1.split(" ");  
            for (int i=0;i<tmp11.length;i++)  
                stoma.add(Integer.parseInt(tmp11\[i\]));

String tmp2=sc.nextLine();  
            String\[\] tmp22=tmp2.split(" ");  
            for (int i=0;i<tmp22.length;i++)  
                bag.add(Integer.parseInt(tmp22\[i\]));

Collections.sort(stoma);  
            Collections.sort(bag);

int res=0;  
            boolean flag=false;  
            for (int i=0;i<stoma.size();i++)\{  
                int tmp=stoma.get(i);  
                flag=false;  
                for (int j=bag.size()-1;j>=0;j--)\{  
                    if (bag.get(j)>=tmp)\{  
                        flag=true;  
                        bag.remove(j);  
                        break;  
                    \}  
                    if (bag.get(j)<tmp)  
                        break;  
                \}  
                if (flag)  
                    res++;  
            \}  
            System.out.println(res);  
        \}  
    \}  
\}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 3][]

/\*\*  
 \* Created by dcp on 2018/9/16.  
 \*/  
/\*\*  
 \* Created by dcp on 2018/9/16.  
 \*/  
/\*\*  
 \* Created by dcp on 2018/09/16.  
 \*/  
var readline=require("readline");  
var r1=readline.createInterface(\{  
    input:process.stdin,  
    output:process.stdout  
\});

r1.on("line",function(data)\{

console.log(jumpFloor(data))

\});  
function jumpFloor(number)  
\{  
    // write code here  
    if(number==0)\{  
        return 0;  
    \}  
    if(number==1)\{  
        return  1;  
    \}  
    if(number==2)\{  
        return 2;  
    \}  
    var a=1,b=2,temp=0;  
    for(var i=3;i<=number;i++)\{  
        temp=a+b;  
        a=b;  
        b=temp;  
    \}  
    return temp;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 5][]

import java.util.Scanner;

public class Main \{

public static String res="";  
    public static void main(String\[\] args)\{  
        Scanner sc=new Scanner(System.in);  
        while (sc.hasNext())\{  
            int N=sc.nextInt();  
            int count=0;  
            for (int i=1;i<=N;i++)\{  
                if (goodNumber(i))\{  
                    int now=Integer.valueOf(res);  
                    if (now!=i)\{  
                        count++;  
                    \}  
                \}  
            \}  
            System.out.println(count);  
        \}  
    \}

private static boolean goodNumber(int n)\{  
        String a=String.valueOf(n);  
        res="";  
        for (int i=0;i<a.length();i++)\{  
            if (a.charAt(i)=='0'||a.charAt(i)=='1'||a.charAt(i)=='8')\{  
                res+=a.charAt(i);  
            \}else if (a.charAt(i)=='2')\{  
                res+="5";  
            \}else if (a.charAt(i)=='5')\{  
                res+="2";  
            \}else if (a.charAt(i)=='6')\{  
                res+="9";  
            \}else if (a.charAt(i)=='9')\{  
                res+="6";  
            \}else return false;  
        \}  
        return true;  
    \}  
\}

题目大意：一排人站成一队，共有n个人，每个人有各自的身高，用一个数组表示。然后AB两个人参与游戏，每次可以从队伍最左侧选择一个或者两个人加入自己的队列，最后将两人的队列的人的身高总和进行比较，总和大的人获得胜利，A先手，且A和B每个人都足够机智（每手都是最优），求A是否可以必胜。

首先这题只是看上去像个博弈，但是由于每个人的身高不同（题目并没有给出身高范围，理论上可以出现一个人顶其它人总和的情况），所以博弈很难解决。

由于两人都是足够机智的，所以可以用dp\[i\]表示从位置i取可以获得的最大值（A和B都可以表示），而队伍末尾的值可以确定，即dp\[n\]=n;所以可以从最后进行反推，状态转移方程为：

dp\[i\]=max(a\[i\]+sum\[n\]-sum\[i\]-dp\[i+1\],a\[i\]+a\[i+1\]+sum\[n\]-sum\[i+1\]-dp\[i+2\]);

（sum\[i\]表示队列从1到i的身高总和）

\#include <iostream>  
\#include <cstdio>  
\#include <cmath>  
\#include <cstring>  
using namespace std;  
int main()\{  
    int n;  
    int a\[10000\];  
    int dp\[10000\];  
    int sum\[10000\];  
    scanf("%d",&n);  
    memset(dp,0,sizeof(dp));  
    memset(sum,0,sizeof(sum));  
    for(int i=1;i<=n;i++)\{  
        scanf("%d",&a\[i\]);  
        sum\[i\] = sum\[i-1\]+a\[i\];  
    \}  
    dp\[n\]=n;  
    for(int i=n-1;i>=1;i--)\{  
        dp\[i\]=max(a\[i\]+sum\[n\]-sum\[i\]-dp\[i+1\],a\[i\]+a\[i+1\]+sum\[n\]-sum\[i+1\]-dp\[i+2\]);  
    \}  
    if(dp\[1\]>dp\[2\]||dp\[1\]>dp\[3\])\{  
        puts("true");  
    \}  
    else\{  
        puts("false");  
    \}  
    return 0;  
\}  
\---------------------  
作者：丶聂小白  
来源：CSDN  
原文：https://blog.csdn.net/q295657451/article/details/77980495  
版权声明：本文为博主原创文章，转载请附上博文链接！

某公司年会上，组织人员安排了一个小游戏来调节气氛。游戏规则如下：

N个人参与游戏，站成一排来抢工作人抛来的M个小玩偶。为了增加游戏的趣味和难度，规则规定，参与游戏的人抢到的礼物不能比左右两边的人多两个或以上，否则会受到一定的惩罚。游戏结束时拥有玩偶最多的人将获得一份大奖。

假设大家都想赢得这份大奖，请问站在第K个位置的小招在赢得游戏时，最多能拥有几个玩偶？

解答：

![70][]

[https://www.nowcoder.com/questionTerminal/1bca71cd733048f890d36724f3c695eb?orderByHotValue=1&page=1&onlyReference=false][https_www.nowcoder.com_questionTerminal_1bca71cd733048f890d36724f3c695eb_orderByHotValue_1_page_1_onlyReference_false]  
来源：牛客网  
  
位置k的小朋友领p颗糖果，理想情况下越靠边的人比k位置的小朋友少一颗糖，正好领完m颗糖，即曲线阴影部分为m，加上直线阴影部分的糖果数s=((n - k + 1)(n - k) /2) + (k (k - 1) /2)等于n\*p，即长方形的面积。  
如果多出来i颗糖果的话，显然只需要考虑i小于n了，否则每个人就能多发一颗糖果还能有剩。这i颗糖果已经不能发给k位置的小朋友了，只能从边上开始发，一人一颗。那反过来求得的p就是代码中的 (m + s - i) / n。

代码：

\#include <iostream> using namespace std;

int main()

int n, m, k;

cin >> n >> m >> k;

if (n && (k>=1 && k<=n))

int s = ((n - k + 1)\*(n - k) >> 1) + (k \* (k - 1) >> 1); //\*、+优先级大于>>

for (int i = 0; i < n; i++)

if ((m + s - i) % n == 0)

cout << (m + s - i) / n << '\\n'; break;

else cout << "0" << '\\n';

return 0;

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20220114/e0e1a43b6273441d9b6c07efb42c0460.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1]: /images/20220114/46ef835e585a47b7b140bc9c5c8d6fab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 2]: /images/20220114/ca0ba8d59c034326bab2a2b0dd7cef61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 3]: /images/20220114/ada9820a581743fc81b82f5fc316af68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 4]: /images/20220114/73ac0c338b5d4072bad3872b803e6840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 5]: /images/20220114/17aca28b6e2940dfa4904a6684d814ff.png
[70]: /images/20220114/4224652534f34955b1d2186413a7cbf7.png
[https_www.nowcoder.com_questionTerminal_1bca71cd733048f890d36724f3c695eb_orderByHotValue_1_page_1_onlyReference_false]: https://www.nowcoder.com/questionTerminal/1bca71cd733048f890d36724f3c695eb?orderByHotValue=1&page=1&onlyReference=false