import java.util.*; public class Main { /** * 解题思路: (深度优先算法dfs) * 还是那句总结的话: * 寻找最优多用动态规划 * 输出所有情况多用dfs * 因为本题是需要按字典序排序输出,因此我们在dfs之前对于要穷举的元素按字典序进行排序即可, * 只不过本题是数字,因此我们不需要进行排序,因为按从 1 递增的顺序就是按字典序的顺序穷举 * @param args */ public static void main(String[] arg...

import java.util.*; public class Solution { /** * 解法一 * 时间复杂度: O(N^3) * 空间复杂度: O(N) * 以下以 [x,y] 表示 s 的第 x 个字符到第 y 个字符的字串 * 这里主要考虑的是动态规划 * 状态定义: dp[i] = [1,i]的最小切割数 * 状态转移: 设 任意 a <= i * 当[a,i]是回文串: dp[i] = min(dp[i],dp[a-1]+1) * ...

import java.util.Scanner; /** * 解题思路: * 首先对于修改字符串子类的题,第一时间应该想到动态规划 * 首先我们假定是将 A 编辑为 B * 因此要将 A[0,...i-1] 编辑为 B[0,...j-1] 有如下两种情况 * 1. A[i-1] == B[j-1] * 显而易见 A[0,...i-1] 编辑为 B[0,...j-1] == A[0,...i-2] 编辑为 B[0,...j-2] * 2. A[i-1] != B[j-1] (这个情况下又分为三种情况) * (1)插入: A[0,...i-1] 编辑为 B[0,...j-2],...

import java.util.*; public class Solution { private static class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } /** * @param preorder 根左右 * @param inorder 左根右 * ...

import java.util.*; public class Solution { /** * 本题的解题思路很值得学习 * 简单的方法就是每个滑动窗口我们都遍历一遍来寻找最大值 * 可是这样子的时间复杂度就为 O(len*size) 时间复杂度太高了,因此我们就只能能改进方法 * 改进后的方法:因为我们只需要知道每个滑动窗口中的最大值,因此同一个滑动窗口中的比最大值 * 小的值均没有意义,即我们不需要他们,因此我们这里通过一个双端队列(看答案学的,这里的 * 思想很重要)来维护,双端队列中存的是元素对应在 num 数组...

import java.util.*; /** * 动态规划 * 思路：我们先不考虑 * 的存在。假如没有 * 的话，我们判断两个字符串是否匹配就非常简单， * 即 s 和 t 是否匹配当且仅当 s 的每一个字符和 t 对应位置字符是否可以匹配即可，之后 * 再考虑加入 * 的情况，因为 * 的存在，导致其可以有不确定的情况，即匹配 0 || 1 || 多 * 个字符，因此这就导致我们需要进行动态规划了。 * 我们定义 dp[i][j] 为 s 的前 i 个字符和 t 的前 j 个字符是否可以匹配， * 其中状态转移方程为 * 当 t 的第 j 个字符为 * 时：dp[i][...

import java.util.*; /** * 解题思路：（当每一种颜色的左手或者右手手套个数均大于零的时候） * 主要思路就是让一只手的手套每个颜色的都至少拿一只，之后另一只手随便拿一个就至少可以配对出一双手套， * 即求出左手手套个数为 leftSum ，其中个数最少的为 leftMin ，之后要满足左手手套每个颜色的都至少 * 有一个的条件，即最少需要拿 leftSum-leftMin+1 个左手手套，之后右手手套再拿 1 个即可，而对应 * 的另一种情况就是拿 rightSum-rightMin+1 ，之后再拿左手手套一个即可。 * 即最少需要拿的手套数为 min(l...

import java.util.*; /** * 解题步骤如下： * 1. 将原号码从小到大排序 * 2. 从第一个号码开始穷举，其中穷举的终止条件是当前号码与前面的号码无法组成幸运的袋子，且当前号码不为 1 * 此时就直接返回即可，因为数组已经是排好序的，后面的数字只会越来越大。 * 3. 进行下一个循环的时候，要把 sum 和 multi 的值均恢复 * 特殊情况：1. 当当前号码为 1 的时候，尽管 sum <= multi,也要继续向下一层列举，只是本次不算幸运的袋子 * 2. 循环列举的时候记得去除相同的号码的重复统计 */ publi...