华为机试练习汇总记录

华为笔试题牛客网

为了准备华为的机试，专门进行了一些专项训练，主要训练一些中等和难题

主要涵盖以下相关内容的题目：

• 动态规划
• DFS
• 背包问题
• 贪心问题
• 二叉树
• 回溯剪枝

HJ1 字符串最后一个单词的长度==字符串==

• 题目

• 题解(816)

• 讨论(2k)

• 排行

• 面经

  new

简单 通过率：36.37% 时间限制：1秒 空间限制：32M

知识点字符串

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）

输入描述：

输入一行，代表要计算的字符串，非空，长度小于5000。

输出描述：

输出一个整数，表示输入字符串最后一个单词的长度。

示例1

输入：

hello nowcoder

输出：

8

说明：

最后一个单词为nowcoder，长度为8   

题解

直接使用split分割，然后输出字符串数组最后一个字符串的长度

import java.util.*;

public class Main{
    public  static void  main(String [] args) throws Exception{
        Scanner scanner = new Scanner(System.in);
        String[] strs = scanner.nextLine().split(" ");
        System.out.println(strs[strs.length - 1].length());

    }
}

另一种方式是直接从字符串末尾查找第一个空格，设置一个count记录查找了多少个字符，查找到第一个空格直接返回

import java.util.*;

public class Main{
    public  static void  main(String [] args) throws Exception{
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int count = 0;
        for (int i = str.length() - 1; i >= 0; i--) {
            if (str.charAt(i) == ' ')
                break;
            count++;
        }
        System.out.println(count);

    }
}

HJ2 计算某字符出现次数==字符串==

• 题目

• 题解(829)

• 讨论(2k)

• 排行

• 面经

  new

简单 通过率：33.72% 时间限制：1秒 空间限制：32M

知识点字符串哈希

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）

数据范围： 1 \le n \le 1000 \1≤n≤1000

输入描述：

第一行输入一个由字母和数字以及空格组成的字符串，第二行输入一个字符。

输出描述：

输出输入字符串中含有该字符的个数。（不区分大小写字母）

示例1

输入：

ABCabc
A

输出：

2

题解

如果是字母，需要判断大小写，如果是数字，直接判断是否相等，最后返回计数值

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        char ch = scanner.nextLine().charAt(0);
        ch = Character.isLowerCase(ch) ? Character.toUpperCase(ch) : ch;
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            int temp = str.charAt(i) - ch;
            if (temp == 0 || (Character.isLetter(ch) && temp == 32))
                count++;
        }
        System.out.println(count);
    }
}

HJ3 明明的随机数==字符串==

• 题目

• 题解(832)

• 讨论(2k)

• 排行

• 面经

  new

较难 通过率：25.09% 时间限制：1秒 空间限制：32M

知识点数组

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

明明生成了NN个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。

数据范围： 1 \le n \le 1000 \1≤n≤1000 ，输入的数字大小满足 1 \le val \le 500 \1≤val≤500

输入描述：

第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数，代表明明生成的随机数。 具体格式可以参考下面的”示例”。

输出描述：

输出多行，表示输入数据处理后的结果

示例1

输入：

3
2
2
1

输出：

1
2

说明：

输入解释：
第一个数字是3，也即这个小样例的N=3，说明用计算机生成了3个1到500之间的随机整数，接下来每行一个随机数字，共3行，也即这3个随机数字为：
2
2
1
所以样例的输出为：
1
2     

题解

直接利用HashSet去重并排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++)
            set.add(scanner.nextInt());

        for (Integer s : set)
            System.out.println(s);
        
    }
}

HJ4 字符串分隔==字符串==

• 题目

• 题解(914)

• 讨论(2k)

• 排行

• 面经

  new

简单 通过率：31.34% 时间限制：1秒 空间限制：32M

知识点字符串

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

•输入一个字符串，请按长度为8拆分每个输入字符串并进行输出；

•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。

输入描述：

连续输入字符串(每个字符串长度小于等于100)

输出描述：

依次输出所有分割后的长度为8的新字符串

示例1

输入：

abc

输出：

abc00000

题解

首先先将前面字符串8个换行输出，后面的补零输出

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        pring(str);

    }

    public static void pring(String str) {
        if (str.length() == 0)
            return ;
        for (int i = 0; i < str.length() / 8; i++)
            System.out.println(str.substring(i*8, (i+1) * 8));
        System.out.print(str.substring(str.length() - str.length() % 8, str.length()));
        if (str.length() % 8 != 0)
            for (int i = 0; i < 8 - str.length() % 8; i++)
                System.out.print("0");
    }
}

HJ5 进制转换==字符串==

• 题目

• 题解(605)

• 讨论(1k)

• 排行

• 面经

  new

简单 通过率：37.38% 时间限制：1秒 空间限制：32M

知识点字符串

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

数据范围：保证结果在 1 \le n \le 2^{31}-1 \1≤n≤231−1

输入描述：

输入一个十六进制的数值字符串。

输出描述：

输出该数值的十进制字符串。不同组的测试用例用\n隔开。

示例1

输入：

0xAA

输出：

170

题解

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        System.out.println(hexToInteger(str.substring(2, str.length())));
    }

    public static long hexToInteger(String str) {
        long ans = 0;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch >= 'A' && ch <= 'F')
                ans = ans * 16 + (ch - 'A' + 10);
            else
                ans = ans * 16 + (ch - '0');
        }
        return ans;
    }
}

HJ16 购物单==背包问题-01背包==

中等 通过率：23.60% 时间限制：1秒 空间限制：32M

知识点动态规划

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。

每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。

王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。

满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第ii件物品的价格为v[i]v[i]，重要度为w[i]w[i]，共选中了kk件物品，编号依次为j_1,j_2,…,j_kj1,j2,…,j**k，则满意度为：v[j_1]w[j_1]+v[j_2]w[j_2]+ … +v[j_k]w[j_k]v[j1]∗w[j1]+v[j2]∗w*[j2]+…+v[j**k]∗w[j**k]。（其中 * 为乘号）

请你帮助王强计算可获得的最大的满意度。

输入描述：

输入的第 1 行，为两个正整数N，m，用一个空格隔开：

（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q

（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 **~** 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）

输出描述：

输出一个正整数，为张强可以获得的最大的满意度。

示例1

输入：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出：

2200

示例2

输入：

50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

输出：

130

说明：

由第1行可知总钱数N为50以及希望购买的物品个数m为5；
第2和第3行的q为5，说明它们都是编号为5的物品的附件；
第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；
所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130       

题解

0-1背包问题

这道题是经典的背包问题，首先是0-1背包问题

有一个背包可以装物品的总重量为W现有N个物品，每个物品W[i]，价值在v[i]，用背包装物品，能装的最大价值是多少

可以定义一个状态转移数组dp[i][j]，表示前i个物品，背包总量为j的情况下能装的最大价值

状态转移方程为
$$
dp[i][j]=\max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
$$
也就是说要么当前物品不放入背包dp[i-1][j]，或者当前物品放入背包dp[i-1][j-w[i]] + v[i]

购物车思路

这道题本质上还是0-1背包问题，不过多了主件和附件，可以将主件和附件放在一起考虑，即考虑每个物品的时候要考虑每种可能出现的情况

• 主件
• 主件+附件1
• 主件+附件2
• 主件+附件1+附件2

可以使用一维数组优化状态转移方程空间复杂度，并用两个m+1行3列的数组分别存储物品的价格和满意度，代码如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[][] price = new int[m + 1][3];
        int[][] importance = new int[m + 1][3];
        for (int i = 1; i <= m; i++) {
            int v = scanner.nextInt(), p = scanner.nextInt(), q = scanner.nextInt();
            int im = v * p;
            if (q == 0) {
                price[i][0] = v;
                importance[i][0] = im;
            } else {
                if (price[q][1] == 0) {
                    price[q][1] = v;
                    importance[q][1] = im;
                } else {
                    price[q][2] = v;
                    importance[q][2] = im;
                }
            }
        }

        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            if (price[i][0] == 0)
                continue;
            for (int j = n; j >= price[i][0]; j--) {
                int a = price[i][0];
                int a1 = importance[i][0];
                int b = price[i][1];
                int b1 = importance[i][1];
                int c = price[i][2];
                int c1 = importance[i][2];

                if (j >= a) {
                    dp[j] = Math.max(dp[j], dp[j-a] + a1);
                }

                if (j >= a + b)
                    dp[j] = Math.max(dp[j], dp[j-a-b] + a1 + b1);

                if (j >= a + c)
                    dp[j] = Math.max(dp[j], dp[j-a-c] + a1 + c1);

                if (j >= a + b + c)
                    dp[j] = Math.max(dp[j], dp[j-a-b-c] + a1 + b1 + c1);
            }
        }

        System.out.println(dp[n]);
        
    }
}

HJ24 合唱队==动态规划-最长递增子序列==

中等 通过率：29.00% 时间限制：1秒 空间限制：32M

知识点动态规划队列

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

设KK位同学从左到右依次编号为 1，2…，K ，他们的身高分别为T_1,T_2,…,T_KT1,T2,…,T**K ，若存在i(1\leq i\leq K)i(1≤i≤K) 使得T_1<T_2<……<T_{i-1}<T_iT*1<*T*2<……<*T**i*−1<*T**i* 且 T_i>T_{i+1}>……>T_KTi*>*Ti*+1>……>T**K，则称这KK名同学排成了合唱队形。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

例子：

123 124 125 123 121 是一个合唱队形

123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求

123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

数据范围： 1 \le n \le 3000 \1≤n≤3000

输入描述：

用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开

输出描述：

最少需要几位同学出列

示例1

输入：

8
186 186 150 200 160 130 197 200

输出：

4

说明：

由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130  

题解

可以看做是最长递增子序列的变种题，对于第i个元素，其0到i-1的元素的最长递增子序列的长度和i+1到n-1元素的最长递减子序列长度的和就是可以满足合唱队的最长长度length，那么需要出列的同学就是n-length

可以设置一个数组l[n]表示当前n位同学的最长递增子序列长度，那么当i>j && nums[i] > nums[j] 时，可以得到 l[i] = max(l[i], l[j] + 1)，其中初始化l[i] = 1，对于i之后的最长递减子序列只需要i < j同样的操作即可

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        int[] l = new int[n], r = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    l[i] = Math.max(l[i], l[j]);
            }
            l[i] = l[i] + 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j])
                    r[i] = Math.max(r[i], r[j]);
            }
            r[i] = r[i] + 1;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, l[i] + r[i] - 1);
        }
        System.out.println(n - ans);
    }
}

HJ32 密码截取==动态规划-最长回文子串==

中等 通过率：33.53% 时间限制：1秒 空间限制：32M

知识点字符串动态规划

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

数据范围：字符串长度满足 1 \le n \le 2500 \1≤n≤2500

输入描述：

输入一个字符串（字符串的长度不超过2500）

输出描述：

返回有效密码串的最大长度

示例1

输入：

ABBA

输出：

4

示例2

输入：

ABBBA

输出：

5

示例3

输入：

12HHHHA

输出：

4

题解

可以考虑中心扩散法查找回文子串，可以看到有两种情况的回文字符串

• ABA
• ABBA

所以需要计算两种情况下的最长回文子串

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        char[] chars = str.toCharArray();

        System.out.println(getAns(chars));
    }

    public static int getAns(char[] chars) {
        int ans = 0;
        for (int i = 0; i < chars.length; i++) {
            int len1 = getLongest(chars, i, i);
            int len2 = getLongest(chars, i, i+1);
            ans = Math.max(ans, Math.max(len1, len2));
        }
        return ans;
    }

    public static int getLongest(char[] chars, int l, int r) {
        while(l >= 0 && r < chars.length && chars[l] == chars[r]) {
            r++;l--;
        }
        return r - l - 1;
    }
}

HJ43 迷宫问题==DFS递归回溯==

中等 通过率：39.32% 时间限制：1秒 空间限制：32M

知识点查找dfs广度优先搜索(BFS)

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围： 2 \le n,m \le 10 \2≤n,m≤10 ， 输入的内容只包含 0 \le val \le 1 \0≤val≤1

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

示例1

输入：

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出：

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

示例2

输入：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

输出：

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

说明：

注意：不能斜着走！！    

题解

直接使用dfs递归回溯的模板解决

import java.util.*;

public class Main {
    static int[][] directions = new int[][]{{1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}};
    static List<int[]> ans = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[][] nums = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                nums[i][j] = scanner.nextInt();

        List<int[]> path = new ArrayList<>();
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        path.add(new int[]{0, 0});
        dfs(nums, 0, 0, path, visited);
        for (int[] a : ans) {
            System.out.println("(" + a[0] + "," + a[1] + ")");
        }
    }




    public static void dfs(int[][] nums, int i, int j, List<int[]> path, boolean[][] visited) {
        if (i == nums.length - 1 && j == nums[0].length - 1) {
            ans = new ArrayList<>(path);
            return ;
        }


        for (int[] direct : directions) {
            int newi = i + direct[0], newj = j + direct[1];
            if (newi >= 0 && newi < nums.length && newj >= 0 && newj < nums[0].length && nums[newi][newj] == 0 && !visited[newi][newj]) {
                path.add(new int[]{newi, newj});
                visited[newi][newj] = true;
                dfs(nums, newi, newj, path, visited);
                visited[newi][newj] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

HJ45 名字的漂亮度==字符串贪心==

中等 通过率：45.29% 时间限制：1秒 空间限制：32M

知识点字符串贪心

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

给出一个字符串，该字符串仅由小写字母组成，定义这个字符串的“漂亮度”是其所有字母“漂亮度”的总和。
每个字母都有一个“漂亮度”，范围在1到26之间。没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。

给出多个字符串，计算每个字符串最大可能的“漂亮度”。

本题含有多组数据。

数据范围：输入的名字长度满足 1 \le n \le 10000 \1≤n≤10000

输入描述：

第一行一个整数N，接下来N行每行一个字符串

输出描述：

每个字符串可能的最大漂亮程度

示例1

输入：

2
zhangsan
lisi

输出：

192
101

说明：

对于样例lisi，让i的漂亮度为26，l的漂亮度为25，s的漂亮度为24，lisi的漂亮度为25+26+24+26=101.  

题解

通知字符串中字符出现频率，然后按照出现频率排序，之后频率最高的设置漂亮度为26，然后为25，依次递减，输出计算的漂亮度之和

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            String str = scanner.nextLine();
            System.out.println(getBeautiful(str));
        }
    }

    public static long getBeautiful(String str) {
        int[][] counts = new int[26][2];
        for (int i = 0; i < 26; i++)
            counts[i][0] = i;

        for (int i = 0; i < str.length(); i++) {
            int ch = str.charAt(i) - 'a';
            counts[ch][1]++;
        }

        Arrays.sort(counts, (a, b)->b[1] - a[1]);
        long ans = 0L;
        for (int i = 0; i < 26; i++) {
            if (counts[i][1] == 0)
                break;
            ans += (long) (26 - i) * counts[i][1];
        }
        return ans;
    }
}

HJ52 计算字符串的编辑距离==编辑距离-动态规划==

中等 通过率：40.74% 时间限制：1秒 空间限制：256M

知识点字符串动态规划

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

例如：

字符串A: abcdefg

字符串B: abcdef

通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

要求：

给定任意两个字符串，写出一个算法计算它们的编辑距离。

数据范围：给定的字符串长度满足 1 \le len(str) \le 1000 \1≤len(str)≤1000

输入描述：

每组用例一共2行，为输入的两个字符串

输出描述：

每组用例输出一行，代表字符串的距离

示例1

输入：

abcdefg
abcdef

输出：

1

题解

类似于leetcode72.编辑距离

设置一个二维数组dp[i][j]表示A的前i个字母和B的前j个字母之间的编辑距离

对于dp[i][j]可以有三种情况的变化：

• dp[i][j-1]+1，即在B字符串后添加一个和A[i]相同的字符
• dp[i-1][j] + 1 ，在A字符串后添加一个和B[j]相同的字符
• 如果A[i]=B[j]，那么可以dp[i][j]=dp[i-1][j-1]，如果不相等，那么dp[i][j] = dp[i-1][j-1]，即修改A[i]=B[j]或者B[j]=A[i]

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine(), str2 = scanner.nextLine();
        int ans = levenshteinDistance(str1, str2);
        System.out.println(ans);
    }

    public static int levenshteinDistance(String words1, String words2) {
        int n = words1.length(), m = words2.length();

        if (n * m == 0)
            return n + m;

        int[][] dp = new int[n + 1][m + 1];

        for (int i = 0; i < n + 1; i++)
            dp[i][0] = i;

        for (int j = 0; j < m + 1; j++)
            dp[0][j] = j;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = dp[i-1][j]+1;
                int down = dp[i][j-1]+1;
                int left_down = dp[i-1][j-1];
                if (words1.charAt(i - 1) != words2.charAt(j - 1))
                    left_down += 1;
                dp[i][j] = Math.min(Math.min(left, down), left_down);
            }
        }
        return dp[n][m];
    }
}

HJ54 表达式求值==后缀表达式取巧做法==

简单 通过率：57.95% 时间限制：1秒 空间限制：32M

知识点字符串基础数学栈

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

给定一个字符串描述的算术表达式，计算出结果值。

输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *, /, (, )” ， ”0-9” 。

数据范围：运算过程中和最终结果均满足 |val| \le 2^{31}-1 \∣val∣≤231−1 ，即只进行整型运算，确保输入的表达式合法

输入描述：

输入算术表达式

输出描述：

计算出结果值

示例1

输入：

400+5

输出：

405

题解

奇技淫巧，时间复杂度太高了，先mark一下，还是考虑一下

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws ScriptException {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        str = str.replace("[", ")");
        str = str.replace("{", "(");
        str = str.replace("}", ")");
        str = str.replace("]", ")");
        ScriptEngine scriptEngine = new ScriptEngineManager().getEngineByName("nashorn");
        System.out.println(scriptEngine.eval(str));
    }
}

HJ61 放苹果==动态规划==

简单 通过率：51.69% 时间限制：1秒 空间限制：32M

知识点递归动态规划

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围：0 \le m \le 10 \0≤m≤10 ，1 \le n \le 10 \1≤n≤10 。

输入描述：

输入两个int整数

输出描述：

输出结果，int型

示例1

输入：

7 3

输出：

8

题解

同样地可以使用动态规划，主要是要理清楚这个思路

设置一个二维数组dp[i][j]表示将i个苹果放在j个盘子中

可以得知两个初始条件：

• 将0个苹果或者一个苹果放在n个盘子里面只能有一种分法即dp[0][i] = dp[1][i] = 1
• 将n个苹果放在一个盘子也只有一种情况dp[i][1] = 1

对于状态转移可以考虑，如果多加了一个盘子，有两种情况：

• 苹果数不小于盘子数，有两种情况：

  • 至少有一个盘子可以不放，因此可以有dp[i][j-1]中方法
  • 至少每个盘子都有一个苹果，摆放完之后还剩下i-j个苹果，那么剩下的苹果i-j放在j个盘子里面有``dp[i-j][j]`种分法

  将两者相加得到dp[i][j] = dp[i][j-1] + dp[i-j][j]

• 另一种情况是苹果数小于等于盘子数，一定有j-i个盘子空着，每个盘子都是一样的，所以没有多的分法，即dp[i][j]=dp[i][j-1]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();

        int[][] dp = new int[n + 1][m + 1];
        // 初始化
        for (int i = 1; i <= m; i++) dp[0][i] = dp[1][i] = 1;
        for (int i = 1; i <= n; i++) dp[i][1] = 1;

        // 状态转移
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                dp[i][j] = dp[i][j - 1] + (i - j < 0 ? 0 : dp[i-j][j]);
            }
        }

        System.out.println(dp[n][m]);
    }
}