题意整理 输入一棵节点数为n的二叉树，判断该二叉树是否是平衡二叉树。 方法一（暴力递归） 1.解题思路 首先用一个函数计算二叉树的高度。 然后判断当前节点的左右子树高度差的绝对值，如果不超过1，同时递归地判断当前节点的左右子树。如果这些条件都满足，则是平衡二叉树。 2.代码实现 public class Solution { public boolean IsBalanced_Solution(TreeNode root) { //如果为空，直接返回true if(root==null) return true; //当前节点满足...

题意整理 给出一个整型数组 numbers 和一个目标值 target，在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。 数组下标从1开始算。 方法一（暴力） 1.解题思路 利用两层循环遍历所有可能的两个数的组合，第一层遍历所有元素，第二层遍历当前元素之后的所有元素，如果满足两数之和等于target，直接返回对应的下标。 2.代码实现 import java.util.*; public class Solution { /** * * @param numbers int整型一维数组 * @param target int整...

题意整理 给定一颗二叉树，判断该二叉树是否为搜索二叉树和完全二叉树。 二叉树中节点无重复值。 方法一（递归+层序遍历） 1.解题思路 判断搜索二叉树（BST）： 考虑搜索二叉树的定义，每一个节点的值应该大于等于左子树中的最大值，小于等于右子树中的最小值。所以我们可以利用递归遍历每一个节点，如果某个节点不满足定义，则不合法，直接返回false。 图解展示： 判断完全二叉树（CST）： 完全二叉树是严格按照顺序从上到小，从左到右排列的二叉树，只有上一层满了，才可以在下一层从左到右开始排。所以可以利用层序遍历模拟这个过程，如果遍历的过程中，发现之前出现过空节点，而当前节点不是叶子节点，则不合法...

题意整理 给定一个n∗mn*mn∗m大小矩阵，每个单元格有一个数字。 求从左上角单元格出发，走到右下角时最短的路径和。 方法一（动态规划） 1.解题思路 状态定义：dp[i][j]dp[i][j]dp[i][j]表示从起点走到（i,j）（i,j）（i,j）位置的最小路径和。 状态初始化：走到起点位置的路径和等于矩阵中该点的数字的值，即dp[0][0]=matrix[0][0]dp[0][0]=matrix[0][0]dp[0][0]=matrix[0][0]。 状态转移：第0列的路径只能由前一行向下走得到，所以dp[i][0]=dp[i−1][0]+matrix[i][0]dp[i][0...

题意整理 给出两个字符串s和t，要求在s中找出最短的包含t中所有字符的连续子串。 方法一（暴力循环） 1.解题思路 首先统计T中所有字符出现次数，记录在map1中。 然后两层循环遍历S中所有连续子串，对每一个子串，统计字符出现次数，记录在map2中。 每次判断某个子串是否包含t中所有字符，如果包含，则更新子串长度len和起始点start。 2.代码实现 import java.util.*; public class Solution { /** * * @param S string字符串 * @param T string字符串 ...

题意整理 有一个没有重复元素的整数集合S，求S的所有子集。 要求子集升序排列，并且没有重复子集。 方法一（mask枚举） 1.解题思路 对S排序。 利用子集对应的二进制编码mask枚举所有的子集。 mask总共有n位，0表示不选取当前下标对应的字符，1表示选取当前下标对应的字符。 图解展示： 2.代码实现 import java.util.*; public class Solution { //记录所有子集 ArrayList<ArrayList<Integer>> res=new ArrayList<>(); //记录...

题意整理 给出n对括号，要求生成所有的由n对括号组成的合法组合。 合法的组合必须是对于每一个左括号，都有一个右括号与之对应。即所有左右括号能相互抵消掉。 方法一（暴力递归） 1.解题思路 利用递归遍历所有可能的组合。 对于每一个可能的组合，验证其是否合法，如果合法，则加入到res中。 图解展示： 2.代码实现 import java.util.*; public class Solution { /** * * @param n int整型 * @return string字符串ArrayList */ //记录最终的结果...

题意整理 有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。 Ip地址由四段组成，每段用"."隔开，每一段对应的数值范围在0-255之间。 方法一（四层循环） 1.解题思路 利用四层循环访问所有可能的情况，当每一段长度之和等于字符串总长度时，排除掉不合法的情况（比如某一段的值大于255，或者拼接后的ip长度不等于字符串总长度加3）。将可能的加过加入到res，每次加入之后都要重置ip为空。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * * @param...

题意整理 已知股票每一天的价格波动。 最多持有一只股，也就是买入时必须卖出之前持有的股。 只能买入和卖出股票一次，求最大收益。 方法一（暴力） 1.解题思路 只需两层循环，第一层遍历所有元素，第二层遍历当前元素之后所有元素，记录后者与前者之间差值的最大值，取最大的差值即是最大收益。 2.代码实现 import java.util.*; public class Solution { /** * * @param prices int整型一维数组 * @return int整型 */ public int maxProfit (i...

题意整理 有n个小朋友围成一圈，编号分别是0到n-1。 每次报道第m-1个小朋友，则第m-1个小朋友出圈，求最后剩下的那个小朋友的编号。 方法一（链表模拟） 1.解题思路 一种最容易想到的方法是用链表模拟这个过程。首先将0到n-1这n个数依次加入到list链表，每次模拟题目要求，删除指定位置的元素，剩下的那一个即是最后的数字。 由于每次报数list容量就减一，所以即将出环的那个数对应的索引也要前移一位，故每次删除的索引为 index=(index+m−1)mod(list.size())index=(index+m-1)mod(list.size())index=(index+m−1)mo...

题意整理。 输入一行字符串，包含两个字符串以空格隔开，对这两个字符串按指定规则进行处理。 规则如下：第一步，合并这两个字符串。第二步，对合并后的字符串进行排序，要求分别对奇数位置和偶数位置的数进行排序， 排序后的数仍然放回原来的奇数位或偶数位。第三步，对排序后的字符串中的'0'-'9'、'A'-'F'和'a'-'f'字符，需要进行转换操作。首先转换为对应的四位二进制数，然后反转，在转换为对应的十六进制数。 方法一（模拟） 1.解题思路 首先新建两个list容器，用于存储奇数位置的数，和偶数位置的数。然后将两个字符串合并，遍历整个字符串，将对应位置的数放到list容器odds和events...

题意整理。 输入两行字符串，对其中一行加密，对另一行进行解密。 加密方式为：如果是小写字母，则转化为大写，右移一位；如果是'z'，则直接变为'A'。如果是大写字母，则转化为小写，右移一位；如果是'Z'，则直接变为'a'。如果是数字，右移一位；如果是'9'，直接变为'0'。 解密方式为加密的逆操作。 方法一（模拟） 1.解题思路 加密： 首先将输入的字符串转为字符数组。 按照给定的加密方式，改变对应位置字符的值。主要利用了ascii码，大写字母和小写字母的ascii码相差32，比如'a'的ascii码为97，'A'的ascii码为65。另外0的ascii码为48。 解密： 首先将输入的...

题意整理。 输入N（N为偶数）个正整数，从其中挑选出若干对组成“素数伴侣”。 问怎么挑选，可以使得“素数伴侣”的对数最多。 如果两个正整数的和为素数，则这两个正整数称之为“素数伴侣”。 方法一（匈牙利算法） 1.解题思路 首先定义两个list容器，分别存储输入整数中的奇数和偶数。 然后利用匈牙利算法找到“素数伴侣”对数最多时的配对数。匈牙利算法的核心思想是先到先得，能让就让。 最后输出“素数伴侣”最多时的对数。 图解展示（匈牙利算法）： 举例说明：如图所示，首先A1和B2配对（先到先得），然后轮到A2，A2也可以和B2配对，这时候B2发现A1还可以和B4配对，所以放弃了A1，选择和A...

题意整理。 输入一个字符串数组以及一个待查找的单词。 求该单词的所有兄弟单词中的第k个。 定义一个单词的“兄弟单词”为：交换该单词字母顺序，而不添加、删除、修改原有的字母就能生成的单词。 方法一（计数+排序） 1.解题思路 首先定义一个方法，用于检查是否是兄弟单词。该方法需要定义一个计数数组，字符串s1中对应字符出现次数加1，字符串s2中对应字符出现次数减1，然后遍历整个计数数组，如果某个位置的值不为0，说明不是兄弟单词。 根据定义的检查方法，遍历输入的字符串数组，将所有的兄弟单词加入到一个list容器。list容器的大小即是兄弟单词的个数。 最后对list容器进行排序，输出索引位置k对...