题意整理  给定个字符串组成的字符串数组，以及个字符串组成的字符串数组。 对于中的每一个字符串，如果s数组中存在某个字符串的前缀与单匹配，但不满足双匹配，求这样的字符串有多少个。  方法一（暴力匹配） 1.解题思路  首先固定t数组的某一个字符串，然后遍历s数组，将s数组中的每一个字符串与t数组固定的那一个字符串带入match函数，如果匹配，则对应结果集加一。 match函数主要检查s串是否是t串的单匹配串而不是t串的双匹配串，由于只检查是否有满足条件的s的前缀，所以只需遍历t串长度，如果奇数项不匹配，说明不是单匹配，直接排除，如果偶数项匹配，说明是双匹配，也直接排除，到最后仍然满足条件的，返...

题意整理  牛妹和牛牛在玩掷骰子游戏，看谁能够获胜。 得分规则为，给定每一次所掷的骰子点数，这些点数可以随意组合相加得到一些数，从1开始计算，如果某个数不在这些组合得到的数中，则这个数就是他的得分。  方法一（有序哈希） 1.解题思路  首先定义一个TreeSet，用于存放所有可能的累加和，并保证累加和是有序的。 然后遍历整个数组，将可能的累加和放入TreeSet。 最后遍历TreeSet，看其中是否包含不能得到的累加和，由于是有序排列的，所以第一个不能得到的累加和，即是所求的分数。  2.代码实现 import java.util.*; public class Solution { /**...

题意整理  牛妹要安排m名员工到n条生产线生产口罩。 每条生产线有一个策略数组，对于这条生产线，牛妹要么一个员工也不给安排，要么按策略数组的某条策略进行安排。 求怎么样安排每天生产的口罩最多，最多是多少。  方法一（动态规划） 1.解题思路  状态定义： 表示i条生产线，j名员工每天产多少口罩。 状态初始化：所有状态值初始化为0。 状态转移：每增加一条生产线，当前增加的生产线有两种选择，一种是选择闲置，另一种是在对应策略数组选择一个最佳策略。如果选择闲置，则相较于之前没有变化，即 ;如果选择某种策略，则需要当前人手大于等于策略需要人手，如果满足，则从所有选择中挑出一种产能最高的，即 。  2....

题意整理  只要牛妹的炮，将，车，兵的任意一个能吃到牛牛的将，则牛妹获胜。 将、兵只有在相邻的时候才能吃。 炮、车在同行和同列都可以吃，炮需要隔一个棋子，车不能有棋子挡在中间。  方法一（模拟搜索） 1.解题思路  首先找到牛牛的将在什么位置。 以牛牛将的位置为起点，沿着四个方向进行搜索，当与起点位置相邻，并且当前位置是牛妹的将或兵时，说明牛妹可以赢，直接返回"Happy";当与起点位置之间的棋子数为0个，并且当前位置是牛妹的车时，说明牛妹可以赢，直接返回"Happy"；当与起点位置之间的棋子数只有一个，并且当前位置是牛妹的炮时，说明牛妹可以赢，直接返回...

题意整理  输入正整数 。 在 到 之间，有多少个数字不包含连续的 ，则输出多少。  方法一（记忆化递归） 1.解题思路  递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。 递归如何推进：当前位（第i位）可以选择6，也可以不选择6。如果选择6，那么i-1位必须不选择6（共9种选择），此时可由i-2层得到i层，共 种情况；如果不选择6，那么直接由i-1层得到i层，共 种情况。 每一层返回值：返回当前层可能数 。  由于普通递归，会有很多重复计算的情况，可以用一个记忆数组记录之前计算过的情况。 2.代码实现 import java.util....

题意整理  有n个同学，每个同学都有一个聪明值和一个勤奋值。 从这个n个同学中选出若干同学，使得总的聪明值累加和和勤奋值累加和最大，但是聪明值累加和、勤奋值累加和必须大于0。  方法一（单调栈） 1.解题思路  牛妹想选择一些同学作为同事，如果最终有N个同学，那么总的组合数就是 （每个同学，要么选，要么不选）。同学数限定小于100，直接暴力递归进行搜索，最多有 次，肯定会超时。所以在每次选择时，要找出淘汰策略。 我们用一个list记录所有可能的聪明值累加和与勤奋值累加和，假设当前累加和组合数为n，每新增一位同学，就多出n种组合，如果能提前淘汰不可能是最大总和的组合，就会减少很多无用搜索。当我们...

题意整理  给定一个数组。 求数组中只出现一次的数。  方法一（哈希表） 1.解题思路 记录数组中每一个数出现的次数，并将数组中的数作为键，出现次数作为值添加到哈希表中，然后遍历哈希表，当某个键对应的值为1时，直接返回对应的键，即找到了只出现一次的数。 动图展示：  2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr int一维数组 * @param k int * @return int */ public int foun...

方法一（递归） 1.解题思路  递归终止条件：向左寻找时，寻找到索引0终止；向右寻找时，到索引nums.length-1终止。 递归如何推进：向左寻找时，如果大于左边元素，直接由左边索引子序列加一，否则重置为1；向右寻找时，如果小于右边元素，直接由右边索引子序列加一，否则重置为1。 每一层递归返回什么：当前层的最长子序列长度。  2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int ...

题意整理  给定字符串。 求这个字符串的最长回文子序列。 回文序列是指，如果将原序列翻转后与原序列相等，那么这个序列是回文序列。  方法一（记忆化递归） 1.解题思路  递归终止条件：左边界和右边界之间只含一个元素，或只含两个元素。 递归如何推进：如果左边界和右边界相等，则可以将两边分别向中间压缩一步，并且长度减二；否则，要么向左压缩，要么向右压缩，取两者较大值。 每一层递归返回什么：当前层的最长回文子序列长度。  由于普通的递归会有很多重复的计算，可以用记忆数组记录已知的情况。 2.代码实现 import java.util.*; public class Solution { /** * ...

题意整理  给定n个信封。 将长和宽较大的信封套在长和宽较小的信封上（必须严格大于）。  方法一（动态规划） 1.解题思路 当信封长度从小到大排列的时候，我们只需要让对应的宽度也从小到大就能完成信封嵌套，而让宽度从小到大排列，可以转化为求宽度序列的最长递增子序列。但是如果信封长度相同，宽度如何处理呢？如果长度相同，宽度从小到大排列，那所求的递增子序列在长度相同时，可能会选两个宽度，这样就不能完成嵌套。所以我们可以在长度相同时，让宽度从大到小排列，这种情况下，相同长度，只能选一个宽度。  状态定义： 表示以索引i结束的最长递增子序列长度 状态初始化：将所有可能的序列长度初始化为1 状态转移：如果...

题意整理  给定一个整数n和一个整数k，将n分成k份。 每份不能为空，问有多少种分法（组合相同，排列不同的算同一种分法）。  方法一（暴力递归） 1.解题思路  递归终止条件：已经分了k份。 递归如何推进：份数加一，剩余的数字rest要减去已经分配的，而use是当前尝试分配的（只要小于rest，都可以尝试）。  2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int 被划分的数 * @param k int 化成k份 * @r...

题意整理  输入整数a和b。 求a和b的最大公约数。  方法一（暴力法） 1.解题思路 由于是a和b的最大公约数，那么它的范围一定在1到 之间，我们逆序遍历这个区间，找到能同时被a和b整除的数即可。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 求出a、b的最大公约数。 * @param a int * @param b int * @return int */ public int gcd (int a, int b) { // 首先求出a和b...

题意整理  给定一颗节点个数为n的二叉树，二叉树中序遍历单调递增。 求有多少种这样的二叉树。  方法一（记忆化递归） 1.解题思路 由于该二叉树中序遍历单调递增，所以可以假设n个节点的值分别为1，2，……n。这与其他单调递增的情况相比，二叉树的树形数目一样多。我们任意取一个节点为根节点，然后左子树的树形数目加上右子树的树形数目即为这种情况下总的树形数目。我们假设这个任意的根节点是i，那么左子树总共有i-1个节点，右子树总共有n-i个节点。我们遍历树中所有的节点，将每一个节点为根的情况累加，即可得到总的树形数目。  递归终止条件:树为空，或只有一个节点的时候，只有一种树形。 递归如何传递：拆解为...

题意整理  给定模式串S和主串T。 求模式串S在主串T中出现的次数。  方法一（朴素模式匹配） 1.解题思路  首先进行特殊情况判断，如果模式串长度大于主串，或者主串为空，返回0。 然后分别遍历主串和模式串，只要当前字符相等，模式串和主串均后移一位，如果不相等，模式串重新回退到索引0的位置，同时主串索引i回退到上次匹配开头的位置。 当模式串索引达到长度m时，说明全部匹配上了。此时将匹配次数加一，同时主串索引i回退到上次匹配开头的下一位，模式串索引j回到0。  2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、...