leetcode比较重要的题(always updating)

对leetcode比较重要的题做下记录。
“重要”的条件:
1.没能想到解法的题
2.没能想到最优解的题
3.虽想到最优解,但是面试现场容易出错的题
关于第三点易出错是指完成时间较长,或者对代码修改多次。
注意,建议读者在做题时不要使用编译器编译,而是用肉眼和纸笔进行debug,毕竟面试时不可能让你用编译器。
10 Regular Expression Matching(hard)
这题虽然知道用递归,但是还是没想出来。。

Shortest Palindrome

leetcode的一道题
题意:给出一个字符串,只能在首部加上字符使其成为回文串,求所加字符数最少的方案。
这题以前搞acm的时候碰到过,如果是以前,就直接上KMP了。但是前面有道题是用manacher算法求字符串的最长回文子串。突然发现这题也可以用manacher来做,时间复杂度也是O(n)。
manacher确实是一种思路巧妙,代码简短的算法。
https://leetcode.com/problems/shortest-palindrome/

bestcoder#64 div1

还是做出两题。。
1001(hdu5586) Sum
题意:给出n个数,给出函数f(x),现在可以对连续的一段区间的数使用f(x)转换,也可以不用。问最后这n个数之和最大是多少.
简单dp。可以先对这n个数都使用f(x)得到新的数组b(设原数组为a),b[]-a[],得到数组c。对c[]求最大子串和,这个最大子串和就是对某一段数施加f(x)之后可以达到的最大增益。如果是负的,那么显然不应该进行f(x)的转换。a数组的和加上这个增益就是答案。

bestcoder#63 div1

第一次做div1,解出两道题,能做的也只有两道。但是第一题罚时有点厉害,一直不太相信需要高精度(因为output里写了integer。。)
1001(hdu5568) sequence2
一个整数序列有多少种长度为k的不同的递增子序列,两个子序列只要有一个元素对应位置不同就算不同。
如1 2 2有两个长度为2的不同子序列1 2和1 2(这两个2位置不同)
简单的dp题。dp[i][j]表示前i个数组成的序列中有多少个长度为j的不同子序列。
dp[i][j]=sigma(dp[t][j-1]),其中a[i]>a[t]。