星晨

分类

题解(9)

/ 注册

全部文章（共9篇）

是否能完美的拼成矩形

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

2020-11-29

0 678

加油站良好出发点问题

常规解法常规思路需要 O(n*n) 的时间复杂度才能计算出来具体做法就是穷举，从 0-n 不停的作为出发点测试基于常规进行优化模拟常规代码 for i~ n { can[i] = 0 for j=i;j<i+n;j++ { j = j %n ...

2020-11-28

0 811

打印两个升序链表的公共部分

解题思路首先题意没有提最长，也没有提公共所以可以理解我只要有相同的都可以打印两个链表进行逐渐对比，指针如何移动呢？相同则移动两个指针的指针不同的时候由于链表是升序值小的指针后移备注fmt.Scanf 获取数据，测试用例没有问题，就是提示超时，通过率75%换成 bufio 获取数据即可 packag...

2020-11-27

0 579

数字字符转换为字母组合的种数

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

2020-11-18

0 798

龙与地下城游戏问题

典型的动态规划从左上角触发，每次向右或向下走，最后到达右下角，我们要求的是初始值的血 dp[i][j] 从arr[i][j] 位置到右下角最少需要多少血 dp[m-1][n-1] = arr[m-1][n-1] > 0 ? 1:-arr[m-1][n-1] +1 //能到达的下一个位置 -去...

2020-11-16

1 913

字符串的交错组成

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

2020-11-15

0 493

最小编辑代价

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

2020-11-15

0 694

子数组异或和为0的最多划分

如果一段连续子数组异或和为0 边界两端的异或和必然相等如：arr[i~j ] 异或和为为0 则至少说明【-i）异或和等于【0-j) 异或和我们假设dp[i] 标示 0-i 的所求，则我们按照异或和维度存储下来一份映射关系 mapTmp[eor] = i eor => idp[i]...

2020-11-15

0 701

边界都是1的最大正方形大小

题目描述给定一个N \times NN×N的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度、例如0 1 1 1 10 1 0 0 10 1 0 0 10 1 1 1 10 1 0 1 1其中，边框全是1的最大正方形的大小为4 \times 44×4，所以返回4...

2020-11-15

0 710