笔试编程题

一时失言乱红尘 2022-06-10 14:39 244阅读 0赞

笔试编程题集合：

#### 常见的格式要求 ####

将结果保留后两位：

DecimalFormat df = new DecimalFormat("#0.00");
    System.out.println(df.format(1.2343));

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

#### 编程题目 ####

链家网：  
1. 牛站队问题：牛按照1,2,3的序号编号，要求以1,2,3顺序排队，现在给一个随机打乱的顺序给你，让你求按照1,2,3顺序站好最少的交换次数。  
2. 线性的动态规划  
3. 操作文件，没看懂。

补测  
1. 给一个长度为n的整数数组arr\[\]给你，求满足一定条件的最大和，条件：在字符串中求m个数的最大和，且满足每次取下一位数的时候要距离当前数大于等于k.  
示例：(n)4 (m) 2 (k)2 arr\[\]=\{1 , 2 , 4, 5\} 结果为7.

2.求两个字符串的最长公共子序列，如str1 = “12345”, str2 = “24345987”.最长公共子串为: “345” 。

滴滴出行 :

> 题目描述  
> 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。  
> 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。  
> 输入描述:  
> 输入为两行:  
> 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)  
> 第二行为n个正整数Ai，以空格隔开。  
> 输出描述:  
> 输出所求的方案数  
> 示例1  
> 输入  
> 5 15 5 5 10 2 3  
> 输出  
> 4

import java.util.Scanner;
    
    public class Main {
        //使用dp即可，dp[i][j]的意义：使用前数字组成j数字的个数
        public static void main(String[] args) {
    
            Scanner cin = new Scanner(System.in);
    
            int n = cin.nextInt();
            int m = cin.nextInt();
    
            int arr[] = new int[n+1];
            long dp[][] = new long[n + 1][m + 1];
            for (int i = 1; i <= n; i++) {
                arr[i] = cin.nextInt();
            }
    
            for (int i = 0; i < m; i++) {
                dp[0][i] = 0;
            }
    
            for (int i = 0; i < n; i++) {
                dp[i][0] = 1;
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (arr[i] <= j) {
                        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    
    }

好未来

> 题目描述  
> 输入两个整数 n 和 m，从数列1，2，3…….n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来  
> 输入描述:  
> 每个测试输入包含2个整数,n和m  
> 输出描述:  
> 按每个组合的字典序排列输出,每行输出一种组合  
> 示例1  
> 输入  
> 5 5  
> 输出  
> 1 4 2 3 5

这道题它要求输出每个组合，所以不好使用dp，这里使用回溯法（很容易溢出）。

import java.util.*;
    
    public class Main {
    
        static ArrayList<List<Integer>> res = new ArrayList<>();
    
        public static void main(String[] args) {
    
            Scanner cin = new Scanner(System.in);
    
            int N = cin.nextInt();
            int M = cin.nextInt();
            List<Integer> list = new ArrayList<>();
            //当n>m时，其实大于部分是不可能取到的
            int min = N < M ? N : M;
    
            printList(min, M, 0, 1, list);
    
            Collections.reverse(res);
            for (int i = 0; i < res.size(); i++)
                print(res.get(i));
    
        }
    
        private static void printList(int N, int M, int m, int n, List<Integer> list) {
    
            if (m == M) {
                ArrayList<Integer> result = new ArrayList<Integer>();
                result.addAll(list);
                res.add(result);
                return;
            }
    
            if (n > N || m > M) {
                return;
            }
            printList(N, M, m, n + 1, list);
            list.add(Integer.valueOf(n));
            printList(N, M, m + n, n + 1, list);
            list.remove(Integer.valueOf(n));
        }
    
        private static void print(List<Integer> list) {
    
            for (int i = 0; i < list.size(); i++) {
                if (i != 0)
                    System.out.print(" ");
                System.out.print(list.get(i));
            }
            System.out.println();
        }
    
    }

美团点评

> 题目描述  
> 给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N员（N为0-10000的非负整数）的不同组合的个数。  
> 输入描述:  
> 输入为一个数字N，即需要拼凑的面额  
> 输出描述:  
> 输出也是一个数字，为组成N的组合个数。  
> 示例1  
> 输入  
> 5  
> 输出  
> 2

import java.util.*;
    
    public class Main {
    
        // static ArrayList<List<Integer>> res = new ArrayList<>();
    
        public static void main(String[] args) {
    
            Scanner cin = new Scanner(System.in);
    
            int n = cin.nextInt();
    
            int [] arr = new int[]{
       1,5,10,20,50,100};
    
            System.out.println(countWays(arr,6,n));
    
        }
    
         public static long countWays(int[] penny, int n, int aim) {
            long[] dp = new long[aim+1];
            for(int i = 0;i <= aim;i++)
                if(i % penny[0] == 0)
                    dp[i] = 1;
    
            for(int i = 1;i<n; i++)
                for(int j = 1;j<=aim;j++)
                    if(j>=penny[i])
                        dp[j] += dp[j-penny[i]];
    
            return dp[aim];
        }
    }