评分 0, 满分 5 星
0 票

动态规划,dp[i]表示到扫描第i个数字时的方法数,若s[i-1]s[i]可以组成字母,那么dp[i] = dp[i - 1] + dp[i - 2],否则dp[i] = dp[i - 1],注意初始化以及对出现0时非法情况的判断。

评分 0, 满分 5 星
0 票

操作系统助教...抽空5分钟码了码,bug free,每个点有选和不选两种状态,dfs暴力搜了过去。开个空间,记忆化搜索肯定能大幅优化时间,改天补写...

评分 5.00, 满分 5 星
1 票

使用字符哈希卡着时间过的,时间复杂度是max(O(K), O(n^2)),K是所有字符串的长度和,n是字符串的个数。处理出每个字符串的正向和逆向哈希值,拼接的时候相当分配一个幂指数的权重,若正、逆哈希值相等则判相等。因此可以O(n^2)枚举,O(1)判断。tag中提到了Trie,改天会写一个Trie的版本。

Comments Off on [LeetCode]Palindrome Pairs

评分 0, 满分 5 星
0 票

贪心,当结果集有只有1个数字时,如果接下来遇到的数不比它大,就替换,反之就加入结果集,当有2个数字时,对于遇到的第三个数,除了可能对数字2进行替换,还存在可能与遇到的第四个数组成新序列替换原数字1,2,写程序的时候把状态画了下来:

Comments Off on [LeetCode]Increasing Triplet Subsequence

评分 0, 满分 5 星
0 票

最初的想法:判断当前线段与它前面第3条或者第5条线段是否相交,相交会发生在横线和竖线之间,3、5分别对应收缩型和扩张型的结构。这时漏掉了2、1、2、1、1这种同为竖线的情况,因此又在代码中加上了与前面第4条是否相交的判断。时空复杂度均满足题目要求,但是判线段是否相交使用了叉乘等计算几何中常用的算法,因此代码较长。

评分 4.67, 满分 5 星
3 票

就像写字楼里的Mark也要挤火车回到铁岭变回狗蛋儿一样,生活充满了合情合理的无可奈何。就像我在一个属于我的假期却无法支配自己的时间,得到半晌闲暇还以为是时光给予的温柔。

Comments Off on 这是一个温暖且温柔的午后

评分 5.00, 满分 5 星
1 票

假设a[n - 1]表示第n个这样的数,则a[0] = 1,显然,更大的丑数只能由小的丑数通过乘以2,3,5得到。维护三个头指针,一个尾指针,头指针h1,h2,h3分别指向a[h1],a[h2],a[h3]分别乘以2,3,5能够比目前得到的最大丑数稍大的最小丑数,尾指针则指向目前最大的丑数。显然,如果乘积小于最大的丑数,那就将头指针后移,否则选择三个值中最小的那个加入队尾,直到尾指针到达目标。

评分 0, 满分 5 星
0 票

暴力打出了前几个数字的结果,规律一下子就出来了。