2020-02-07 17:46:32问题描述：问题求解：解法一：BF看问题规模看似可以直接暴力解决。如果直接去解肯定是会超时的，因为每次将原空间划分成A区域，B区域和剩余区域的时间复杂度为O(3^n)。但是我们可以将问题进行一下转化，之前有个问题是能否将一个数组中的数划分成两个和相等的子区域那个题目是可以使...

2020-02-06 17:01:36问题描述：问题求解：非常经典的计数dp问题，思路就是统计以每个字符为结尾的个数，最后求和即可。dp[i]=sumof(dp[j])0<=j<=i；可以理解为将最后的一个字符追加到前面的字符串后面。问题是如何去重。当我们遇到相同的字符的时候，首先最后一个字符单独...

2020-02-03 17:46:04问题描述：问题求解：非常好的题目，和twothumb其实非常类似，但是还是有个一点区别，就是本题要求最后要到达(n-1,n-1)，只有到达了(n-1,n-1)才算是有效解，twothumb是一定会有解的，所以不用加特别判断。也是一种路径规划类的题目，难点依然是状态的表示，...

2020-01-12 18:28:13问题描述： 问题求解：本题还是非常困难的，至少我在看到这个题目的时候是没有想到怎么解决的。我当时联想到的题目是那条grid走两遍的题目，那条题目也很麻烦，使用的是dp。本题最难的地方在于如何定义状态，其实本题可以看作是个路径规划问题，所以状态就是左指在的位置和右...

2020-01-11 17:47:59问题描述：问题求解：本题和另一题targetsum非常类似。targetsum的要求是在一个数组中随机添加正负号，使得最终得到的结果是target，这个题目被证明和背包问题是同一个问题，只是需要进行一下转化。本题其实也是一个套壳题目，只是这次的壳套的更加隐蔽，对于本题来说...

2020-01-05 11:52:40问题描述：问题求解：好像多次碰到类似的lcs的变种题了，都是套上了回文的壳。这里再次记录一下。其实本质就是裸的lcs，就出结果了。publicintminInsertions(Strings){StringBuffersb=newStringBuffer(s);Strin...

2020-01-03 13:29:04问题描述：问题求解：经典的动态规划题目，一般来说dp题目是递推关系公式难想，但是实际代码量还是比较少的。有尝试过dfs来做，但是由于时间复杂度是指数级别的，所以会TLE。publicintnumDistinct(Strings,Stringt){intn1=s.lengt...

2019-11-09 10:31:09问题描述：问题求解：n=100，典型的O(n^3)的动规问题。一般来说这种O(n^3)的问题可以考虑使用区间dp来解决。区间dp是典型的三层结构，最外围枚举区间长度，中间层枚举起点，最里层枚举截断点，因此区间dp的时间复杂度往往为O(n^3)。publicintminim...

2020-05-31 18:00:06问题描述：给定长度为N的A数组，长度为K的BB数组你可以从A数组里取K个数规则如下，每次可以从A数组的最左边或者最右边取走一个数，取走的数从数组中移除将取出的A_iA​i​​按取出的顺序 组成C数组求B与C的内积最大值问题求解：主要难点在于状态的定义，可以将状态...

2020-05-17 16:31:41问题描述：给定一个正整数n，找出小于或等于n的非负整数中，其二进制表示不包含 连续的1 的个数。示例1:输入:5输出:5解释:下面是带有相应二进制表示的非负整数<=5：0:01:12:103:114:1005:101其中，只有整数3违反规则（有两...

2020-05-17 09:03:13问题描述：给定正整数 N，返回小于等于N 且具有至少1位重复数字的正整数的个数。 示例1：输入：20输出：1解释：具有至少1位重复数字的正数（<=20）只有11。示例2：输入：100输出：10解释：具有至少1位重复数字的正数（<=...

2020-05-16 18:35:01问题描述：我们有一组排序的数字D，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0'不包括在内。）现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D={'1','3'...

2018-10-2621:06:54问题描述：问题求解：方法一、BFS首先将使用BFS进行解空间的遍历，也就是将本问题转化成了搜索问题，但是有两个地方需要注意：1、状态保存的问题，每个位置的状态由其位置信息和速度信息构成，但是如果将所有的位置出现过的速度进行保存会MLE，这里进行了一步简化，只保存当前位置速度绝对值为1...

2018-09-2415:01:37动态规划(DP:DynamicProgramming)是算法设计方法之一，在程序设计竞赛中经常被选作题材。在此，我们考察一些经典的DP问题，来看看DP究竟是何种类型的算法。一、01背包问题问题描述：有n个重量和价值分别为wi，vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有...

2018-10-0319:29:43问题描述：问题求解：很有意思的题目，首先想到的是暴力遍历解空间，当然也用到了memo，可惜还是TLE，因为时间复杂度确实有点过高了，应该是O(n!)。Map<LinkedList,Integer>map=newHashMap<>();publicintmaxC...