题意整理。 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 假设K位同学均有对应的身高，合唱队形是指这K位同学的身高先严格递增，再严格递减。 方法一（动态规划） 1.解题思路 这道题本质上是求最长递增子序列，可以通过动态规划来做。只要先把每个位置结尾的最长递增子序列长度计算出来，再逆序遍历数组，求每个位置结尾的最长递增子序列长度（如果是正序，则是该位置开头的最长递减子序列长度），将两者相加再减1即是对应位置的最长合唱队长度。统计所有位置的最长合唱队即可。 状态定义：dp1[i]dp1[i]dp1[i]表示该位置结尾的最长递增子序列长度，dp2[...

题意整理。 删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。 方法一（Map） 1.解题思路 新建一个Map，用于记录字符出现次数。 遍历整个字符串，通过Map统计各个字符出现次数。 然后再遍历Map，找到最小的出现次数。 最后遍历字符串，如果当前字符出现次数不是最小出现次数，则加入到res。 图解展示： 2.代码实现 import java.util.Scanner; import java.util.HashMap; public class Main{ public static void main(String[] args){ /...

题意整理。 输入两个字符串，求它们之间的编辑距离。 Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 方法一（动态规划） 1.解题思路 状态定义：dp[i][j]dp[i][j]dp[i][j]表示字符串A长度为i，字符串B长度为j时，对应的编辑距离。 状态初始化：其中一个字符串为空时，编辑距离为另一个字符串的长度。即dp[i][0]=i,dp[0][j]=jdp[i][0]=i,dp[0][j]=jdp[i][0]=i,dp[0][j]=j。 状态转移：...

题意整理。 规定三个空汽水瓶换一满瓶汽水。并且可以向老板借汽水，兑换之后再还给老板。 如果小张手上有n个空汽水瓶，问他能换多少瓶汽水。 方法一（模拟） 1.解题思路 定义一个变量count，用于记录每次兑换之后获得的满瓶汽水数。定义一个变量yus，记录兑换之后，还剩余的空汽水瓶数目。 模拟整个兑换过程，直到剩余空汽水瓶数n为2或1。如果还剩2个空汽水瓶，则可以向老板借汽水，兑换之后再还给老板，count加1，并终止循环。如果还剩1个空汽水瓶，则无法再换取汽水。 图解展示： 2.代码实现 import java.util.Scanner; public class Main{ ...

题意整理。 输入一串明文，根据规则加密为密文。 如果是小写字母，按abc--2, def--3, ghi--4, jkl--5, mno--6, pqrs--7, tuv--8 wxyz--9的规则变换。如果是大写字母，转换为小写字母，再后移一位。如果是数字和其它字符，保持不变。 方法一（模拟） 1.解题思路 遍历字符串中所有字符。 如果是小写字母，按对应规则转换后加入到res。如果是大写字母，转小写再后移一位，加入到res。如果是数字和其它字符，直接加入到res。 图解展示： 2.代码实现 import java.util.Scanner; public class Main{ ...

题意整理。 输入一行字符串密码，验证是否合法。 合法的密码需满足三个要求：1.长度大于8；2.包含大小写字母、数字、其它字符中至少三种；3.没有长度大于2的不含公共元素的重复子串。 方法一（模拟） 1.解题思路 写3个方法，分别判断是否满足对应的三个要求。 对于要求1，只需判断长度是否大于8。对于要求2，定义一个变量，记录对应字符的种类数目即可，然后判断种类数是否大于等于3。对于要求3，只需判断是否有长度为3的重复子串，因为有长度为3的重复子串，必定也会有长度超过3的重复子串。 图解展示（验证重复子串）： 2.代码实现 import java.util.Scanner; publi...

题意整理。 开发一个错误记录功能的小模块，能够记录出错的代码所在的文件名称和行号。 输入字符串为“全路径名+空格+行号”的格式，输出字符串为“有效文件名+空格+行号+空格+出现次数”的格式。 有如下处理规则：1.只记录出错的最后8条记录，如果有重复的，则计数加一；2.长度超过16的文件名称，只保留最后16个有效字符；3.只要有效字符相同，则视为相同的文件名；4.以第一次出错的时间为准。 方法一（模拟） 1.解题思路 首先新建map，文件名+空格+行号作为键，对应的数量作为值。 然后通过字符串分割，得到文件名，如果长度大于16，则只取最后有效16个字符。利用文件名和行号构造map的键。将对...

题意整理。 开发一个坐标计算工具，按输入的字符串进行对应的坐标移动。 合法的输入字符串为：A(或者D或者W或者S)+数字（两位以内）。若输入不合法，直接丢弃。 方法一（模拟） 1.解题思路 首先通过分号将输入的字符串分割成字符串数组。 然后处理字符串数组的每一个字符串，如果长度不是2或3，表示不合法，直接跳过。 接着计算偏移量，遍历每个字符串除第一个字符外的所有字符，通过公式计算到偏移量。如果某个字符不在'0'-'9'范围内，将偏移量置为0，终止循环。 最后根据计算得到的偏移量，将坐标移动到对应的位置。 图解展示： 2.代码实现 import java.util.Scanner; ...

题意整理。 给定一堆物品，物品分为主件和附件，每件物品都有一个重要度以及一个价格，想买某个附件，必须先买对应的主件。 现在王强有N元的本金，问他在不超出预算的情况下，怎么购买物品，才能使得所买物品的价格与重要度之积的累加和最大。 方法一（动态规划） 1.解题思路 本题实际上是一个01背包问题，背包的容量是N元的预算，目标价值即是物品的价格与重要度之积的累加和。难点在于主件和附件的设定，所以在进行动态规划之前，需要先进行预处理，区分出主件和附件，然后动态规划部分，根据预处理的结果分情况进行处理。 状态定义:dp[i][j]dp[i][j]dp[i][j]表示总钱数为j，物品个数为i时价格与...

题意整理。 输入一个单向链表。 输出链表中倒数第k个节点。 方法一（双指针） 1.解题思路 首先进行特殊情况判断，如果k为0，直接返回空。 然后定义一个指针p指向head。让p先走k步，如果过程中走完链表，直接返回空。表示k大于链表长度。 当p走完k步后，让p和head一起往后走，直到p走完整个链表。head停留的位置即是倒数第k个节点。 图解展示： 2.代码实现 import java.util.Scanner; //链表类 class ListNode{ int val=0; ListNode next; public ListNode(int x){ ...

题意整理。 输入n个字符串。 对这n个字符串进行字典序排列，并输出。 方法一（调用sort） 1.解题思路 新建字符串数组，存储所有输入的字符串。 调用Arrays的sort方法对字符串数组进行排序，然后遍历字符串数组，输出所有的字符串。 图解展示： 2.代码实现 import java.util.Arrays; import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); ...

题意整理。 输入一行英文句子，单词间以空格隔开。 以单词为单位逆序处理，并输出。 方法一（反转） 1.解题思路 首先将输入的句子变为字符数组。 将字符数组整体反转，然后再反转每一个单词，即可得到预期的结果。最后将字符数组转化为字符串并输出。 图解展示： 2.代码实现 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); String s=sc.nex...

题意整理。 输入一行只包含小写字母的字符串。 反转该字符串，并输出。 方法一（利用StringBuilder） 1.解题思路 定义可变字符串res，将输入字符串加入到res。 反转res之后，再以字符串形式输出。 2.代码实现 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); String s=sc.nextLine(); //新建Strin...

题意整理。 输入一个整数。 以字符串形式逆序输出。 方法一（逆序遍历） 1.解题思路 首先将输入的整数转化为字符串。 逆序遍历字符串的每一位，并输出。 图解展示： 2.代码实现 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); //先转化为字符串 String s=String.val...