分类: LeetCode OJ

评分 5.00, 满分 5 星
1 票

可以感觉到,答案是有规律可循的,并且按照1,2,4,8...这样的长度分布,所以打了个表,在某次的试验中看到了如下的结果:

评分 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条是否相交的判断。时空复杂度均满足题目要求,但是判线段是否相交使用了叉乘等计算几何中常用的算法,因此代码较长。

评分 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 票

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

评分 0, 满分 5 星
0 票

O(26 * n^2)暴力来的。首先预处理出每个word是否包含某个字母,然后枚举每个单词对,O(26)判断出是否有相同字符,不相同更新答案。第一次提交的时候开了26个Hash Table判断,T了。看到Tags写的位运算,想想应该是把每个单词处理成26位然后&运算判断,这样就能优化掉26的常数从而使复杂度变为O(n^2)