完美矩形： N 个小矩形可以完美拼接成一个大矩形，不缺，不重重点在于如何保证不缺和不重复 先对所有的输入进行遍历找到 最终的左下角，右上角 检查如果有超越，左右点的边界的 则舍弃 检查是否为完美矩形（除了标记，每个端点必然完全重合，而且是两次） package main import ( "fmt" "os" "bufio" "strconv" "strings" ) type node struct { x1 int y1 int x2 int y2 int } func main(){ var n ...

常规解法 常规思路需要 O(n*n) 的时间复杂度 才能计算出来具体做法就是 穷举，从 0-n 不停的作为出发点测试 基于常规进行优化 模拟常规代码 for i~ n { can[i] = 0 for j=i;j<i+n;j++ { j = j %n sum += oil[j] - dis[j] if sum < 0 { break } } if j == i+n { can[i] = 1 } }我们发现 其实我们在反复探测从不同出发点是否能够...

解题思路 首先题意没有提最长，也没有提公共所以可以理解我只要有相同的都可以打印两个链表进行逐渐对比，指针如何移动呢？相同则移动两个指针的指针不同的时候由于链表是升序值小的指针后移备注fmt.Scanf 获取数据，测试用例没有问题，就是提示超时，通过率75%换成 bufio 获取数据即可 package main import ( "fmt" "bufio" "os" "strconv" ) type linkNode struct{ val int next *linkNode } func main(){ var m,n int ...

要求多少种不同的转换结果每个位置我们都应该去两种选择 当前位 当前位和下一位 但是要求 O（n） 和 O（1）就绝不可能是动态规划了我们可先不考虑空间复杂度分解一下问题假设 dp[i] 标示前i个子串转化为字母组合的方案则 如果第i个字母可以单独转换，则 dp[i] = dp[i]-1 如果第i个字母与i-1 可以组合成一个字母则可以表述为2.1 第i个字母组合数= 前一个字符的组合数（单个转换）+ 前两个字符的组合数（组合转换） dp[i] = dp[i-1]+dp[i-2] 为了方便处理我们定义 dp 数组范围 从 0 - n+1 如 ：dp[0~n+1]dp[0] = 1 //...

典型的动态规划 从左上角触发，每次向右或向下走，最后到达右下角，我们要求的是初始值的血 dp[i][j] 从arr[i][j] 位置到右下角最少需要多少血 dp[m-1][n-1] = arr[m-1][n-1] > 0 ? 1:-arr[m-1][n-1] +1 //能到达的下一个位置 -去当前位置的值，如果为-标示要加血，如果为正标示要减学 dp[m-1][j] = max( dp[m-1][j+1] -arr[m-1][j],1 ) dp[i][n-1] = max( dp[i+1][n-1] - arr[i][n-1] ,1) dp[i][j] = min( max(dp[i][...

注意理解本题str1 ， str2 交错组成的 aim 字符串等价于 str1 按照顺序在aim 出现 && str1 按照顺序在aim 中出现时间复杂度:O(N+M)空间复杂度:O(1) package main import ( "fmt" ) func main(){ var str1,str2,aim string fmt.Scanf("%s",&str1) fmt.Scanf("%s",&str2) fmt.Scanf("%s",&aim) isOk := helper(str1,aim) &am...

最小代价，毋庸置疑 动态规划和之前的最小次数比，区别点在 插入，删除，替换 这几个代价是不同的，所以就需要区分出来那种可以实现当前的效果，然后找最小我们先不考虑状态压缩来进行分析 dp[i][j] 标示 str1[0,i] 变为 str2[0,j] 的最小代价 则 dp[i][j] = dp[i-1][j-1] {str1[i] == str2[i]} dp[i][j] = min( //替换 ： 删除+ 插入 dp[i-1][j-1]+ dc +ic, //替换 （两个都不要） dp[i-1][j-1]+rc, //删除 ? dp[i - 1][j] ...

如果一段连续子数组异或和为0 边界两端的异或和必然相等 如：arr[i~j ] 异或和为为0 则至少说明 【-i）异或和 等于 【0-j) 异或和我们假设dp[i] 标示 0-i 的所求，则我们按照异或和维度存储下来一份映射关系 mapTmp[eor] = i eor => idp[i] = dp[map[eor]]+1dp[0] = arr[0] == 0?1:0最后我们是求最大，dp[i] = max(dp[i-1],dp[i]) package main import ( "fmt" "os" "bufio" "strconv" ) func ...