- 1 Two Sum
思路：map - 2 Add Two Numbers
题意：两个数字按照链表表示，返回表示两个数字之和的链表
思路：直接求，考虑两个链表不同长度以及最后有进位的情况 - 3 Longest Substring Without Repeating Characters
题意：求字符串中最长无重复字母子序列的长度
思路：dp，一维表格，每个cell代表以当前字母结尾的无重复字母子串的长度 - 5 Longest Palindromic Substring
题意： 字符串中最长回文子串的长度
思路：构造特殊字符串，两个字母之间插入'#'，再加上开头和结尾标志，这样可以规避回文串是奇数还是偶数的问题
origin solution:
class Solution {
public:
string longestPalindrome(string s) {
if(s.size() == 0) return "";
string tool = "$#";
for(char a : s) tool = tool + a + '#';
tool = tool + '*';
int tmp_i = 2;
int tmp_j = 0;
for(int i = 2; i < tool.size() - 1; i ++){
int j = 1;
while(tool[i - j] == tool[i + j]){
j ++;
}
if(tmp_j < j){
tmp_i = i;
tmp_j = j;
}
}
string ret = "";
for(int i = tmp_i - tmp_j + 2;i <= tmp_i + tmp_j - 2;i += 2){
ret = ret + tool[i];
}
return ret;
}
};
但是，这种解法的时间复杂度是n方，使用马拉车算法，可以将时间复杂度控制在n。以下是马拉车算法的ac代码。对马拉车算法解释地比较好的：https://blog.csdn.net/liuwei0604/article/details/50414542
public class Solution {
public String longestPalindrome(String s) {
if(s.length()<=1){
return s;
}
// 预处理字符串，避免奇偶问题
String str = preProcess(s);
// idx是当前能够向右延伸的最远的回文串中心点，随着迭代而更新
// max是当前最长回文串在总字符串中所能延伸到的最右端的位置
// maxIdx是当前已知的最长回文串中心点
// maxSpan是当前已知的最长回文串向左或向右能延伸的长度
int idx = 0, max = 0;
int maxIdx = 0;
int maxSpan = 0;
int[] p = new int[str.length()];
for(int curr = 1; curr < str.length(); curr++){
// 找出当前下标相对于idx的对称点
int symmetryOfCurr = 2 * idx - curr;
// 如果当前已知延伸的最右端大于当前下标，我们可以用对称点的P值，否则记为1等待检查
p[curr] = max > curr? Math.min(p[symmetryOfCurr], max - curr):1;
// 检查并更新当前下标为中心的回文串最远延伸的长度
while((curr+p[curr])<str.length() && str.charAt(curr+p[curr])==str.charAt(curr-p[curr])){
p[curr]++;
}
// 检查并更新当前已知能够延伸最远的回文串信息
if(curr+p[curr]>max){
max = p[curr] + curr;
idx = curr;
}
// 检查并更新当前已知的最长回文串信息
if(p[curr]>maxSpan){
maxSpan = p[curr];
maxIdx = curr;
}
}
//去除占位符
return s.substring((maxIdx-maxSpan)/2,(maxSpan+maxIdx)/2-1);
}
private String preProcess(String s){
// 如ABC,变为$#A#B#C#
StringBuilder sb = new StringBuilder();
sb.append("$");
for(int i = 0; i < s.length(); i++){
sb.append("#");
sb.append(s.charAt(i));
}
sb.append("#");
return sb.toString();
}
}
c++版本的：
class Solution {
public:
string longestPalindrome(string s) {
string t = "$#";
for(auto a : s) t = t + a + '#';
// cout<<t<<endl;
int size = t.size();
vector<int> dp(size, 0);
int idx = 0, right = 0, maxIdx = 0, maxSpan = 0;
for(int curr = 1; curr < size; curr ++){
int flx = 2 * idx - curr;
dp[curr] = right > curr ? min(dp[flx], right - curr) : 1;
while((curr + dp[curr]) < size && t[curr - dp[curr]] == t[curr + dp[curr]]) dp[curr] ++;
if(curr + dp[curr] > right){
right = dp[curr] + curr;
idx = curr;
}
if(dp[curr] > maxSpan){
maxSpan = dp[curr];
maxIdx = curr;
}
}
// cout<<maxIdx<<' '<<maxSpan<<endl;
// for(auto a : dp) cout<<a<<' ';
// cout<<endl;
return s.substr((maxIdx-maxSpan)/2,(maxSpan - 1));
}
};
- 6 Zigzag Conversion
题意：按照一种奇怪的顺序读取字符串，但是不能创建二维数组，因为空间限制。
思路：按照每一行的顺序来进行读取，首先建立每个字母属于的行的映射。 - 7 Reverse Integer
题意：将整数reverse。注意负数和数字太大或者太小的情况。
思路：这种题目直接用long long 上就行了
class Solution {
public:
int reverse(int x) {
long long ret = 0;
while(x != 0){
ret = ret * 10 + x % 10;
x /= 10;
}
return (ret < INT_MIN || ret > INT_MAX) ? 0 : ret;
}
};
- 8 String to Integer
题意：将字符串转换成数字
思路：注意数字大小溢出的情况
有点东西：str.find_first_not_of()，isdigit() - 9 Palindrome Number
题意：判断整数是否是回文数
思路：reverse这个数字。需要考虑负数情况。
