面试算法准备
美团codetop¶
206. 反转链表¶
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *dummy = NULL;
ListNode *l = dummy, *r = head;
while (r) {
ListNode *tmp = r->next;
r->next = l;
l = r;
r = tmp;
}
return l;
}
};
88. 合并两个有序数组¶
从后向前的双指针
class Solution {
public:
// 类似于归并排序中的一个小部分
// 要会用
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int l = m - 1, r = n - 1;
int i = m + n - 1;
while (l >= 0 && r >= 0) {
if (nums1[l] > nums2[r]) {
nums1[i] = nums1[l];
i--;
l--;
}
else {
nums1[i] = nums2[r];
i--;
r--;
}
}
while (l >= 0) {
nums1[i] = nums1[l];
i--;
l--;
}
while (r >= 0) {
nums1[i] = nums2[r];
i--;
r--;
}
}
};
215. 数组中的第K个最大元素¶
class Solution {
public:
// int quick_select(vector<int>& nums, int l, int r, int k) {
// if (l == r) return nums[l];
// int x = nums[(l + r) >> 1];
// int i = l - 1, j = r + 1;
// while (i < j) {
// do i++; while (nums[i] > x);
// do j--; while (nums[j] < x);
// if (i < j) swap(nums[i], nums[j]);
// }
// if (k <= j) return quick_select(nums, l, j, k);
// else return quick_select(nums, j + 1, r, k);
// }
void maxHeapify(vector<int>& nums, int i, int heapsize) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < heapsize && nums[left] > nums[largest]) {
largest = left;
}
if (right < heapsize && nums[right] > nums[largest]) {
largest = right;
}
if (i != largest) {
swap(nums[i], nums[largest]);
maxHeapify(nums, largest, heapsize);
}
}
void buildMaxHeap(vector<int>& nums, int heapsize) {
for (int i = heapsize - -1; i >= 0; i--) {
maxHeapify(nums, i, heapsize);
}
}
int findKthLargest(vector<int>& nums, int k) {
int heapsize = nums.size();
buildMaxHeap(nums, heapsize);
for (int i = 0; i < k - 1; i++) {
swap(nums[0], nums[heapsize - 1]);
heapsize--;
maxHeapify(nums, 0, heapsize);
}
return nums[0];
}
};
146. LRU 缓存¶
#include <bits/stdc++.h>
using namespace std;
class LRUCache {
public:
struct Node {
int key, value;
Node *left, *right;
Node(int key, int value) : key(key), value(value), left(nullptr), right(nullptr) {};
};
Node *R, *L;
int n;
unordered_map<int, Node*> hash;
LRUCache(int capacity) {
n = capacity;
R = new Node(-1, -1);
L = new Node(-1, -1);
L->right = R;
R->left = L;
}
int get(int key) {
// 返回值
// 更新链表
if (hash.count(key)) {
Node *p = hash[key];
remove(p);
insert(p);
return p->value;
}
else return -1;
}
void put(int key, int value) {
if (hash.count(key)) {
Node *p = hash[key];
p->value = value;
remove(p);
insert(p);
}
else {
if (hash.size() == n) {
Node *p = R->left;
// 链表
remove(p);
// 哈希
hash.erase(p->key);
// 内存
delete(p);
}
Node *p = new Node(key, value);
insert(p);
hash[key] = p;
}
}
void remove(Node *p) {
p->left->right = p->right;
p->right->left = p->left;
}
void insert(Node *p) {
p->right = L->right;
p->left = L;
L->right = p;
p->right->left = p;
}
void check() {
Node *curr = L;
cout << "check!" << endl;
while (curr != nullptr) {
cout << curr->key << ' ';
curr = curr->right;
}
cout << endl;
}
};
int main () {
LRUCache cache(2);
cout << cache.get(1) << endl;
cache.put(3, 3);
// cache.check();
cache.put(4, 4);
// cache.check();
cache.put(5, 5);
// cache.check();
cout << cache.get(5) << endl;
cout << cache.get(3) << endl;
return 0;
}
141. 环形链表¶
快慢指针建议用fast和slow
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == nullptr) return false;
ListNode *fast = head, *slow = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) return true;
}
return false;
}
};
102. 二叉树的层序遍历¶
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
queue, 队列，先进先出，没有clear
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
q = queue<int>(); 能够直接清空q，而不需要用到clear
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// 语法！
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> tmp;
int n = q.size();
while (n--) {
TreeNode *curr = q.front();
tmp.push_back(curr->val);
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
q.pop();
}
ans.push_back(tmp);
}
return ans;
}
};
21. 合并两个有序链表¶
！！！！链表题不要忘记递归！！！！！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 最后实际上会合并成一条链表，所以可以使用递归
// 去重方法
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1->next && list1->val == list1->next->val) return mergeTwoLists(list1->next, list2);
if (list2->next && list2->val == list2->next->val) return mergeTwoLists(list2->next, list1);
if (list2->next && list2->val == list2->next->val) list2 = list2->next;
if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else if (list1->val > list2->val){
list2->next = mergeTwoLists(list2->next, list1);
return list2;
}
else {
return mergeTwoLists(list1->next, list2);
}
}
};
143. 重排链表¶
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
ListNode *fast = head, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow;
slow = nullptr;
while (fast) {
ListNode* tmp = fast->next;
fast->next = slow;
slow = fast;
fast = tmp;
}
fast = head;
while (fast->next && slow->next) {
ListNode* l = fast->next;
ListNode* r = slow->next;
fast->next = slow;
slow->next = l;
fast = l;
slow = r;
}
}
};
92. 反转链表 II¶
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head) return head;
ListNode *dummy = new ListNode(-1, head);
ListNode *curr = dummy;
for (int i = 0; i < left - 1; i++) curr = curr->next;
ListNode *l = dummy;
for (int i = 0; i < left; i++) l = l->next;
ListNode *r = l->next;
for (int i = 0; i < right - left; i++) {
ListNode *tmp = r->next;
r->next = l;
l = r;
r = tmp;
}
// l是起点，r是接上去的点
ListNode* tmp = curr->next;
curr->next = l;
tmp->next = r;
return dummy->next;
}
};
23. 合并 K 个升序链表¶
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 使用半个归并排序，自底向上归并
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
if (!a) return b;
if (!b) return a;
if (a->val < b->val) {
a->next = mergeTwoLists(a->next, b);
return a;
}
else {
b->next = mergeTwoLists(b->next, a);
return b;
}
}
ListNode* merge(vector<ListNode*>& lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
if (n == 0) return nullptr;
return merge(lists, 0, n - 1);
}
};
3. 无重复字符的最长子串¶
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;
if (!s.size()) return 0;
// 滑动窗口
// vector<int> cnt(26);
int ans = 0;
int j = 0;
int len = 0;
for (int i = 0; i < s.size(); i++) {
len++;
hash[s[i]]++;
while (hash[s[i]] > 1) {
hash[s[j]] --;
j++;
len--;
}
ans = max(len, ans);
}
return ans;
}
};
82. 删除排序链表中的重复元素 II¶
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *dummy = new ListNode(-1, head);
ListNode *curr = dummy;
while (curr && curr->next) {
while (curr->next && curr->next->next && curr->next->val == curr->next->next->val) {
int a = curr->next->val;
while (curr->next) {
if (curr->next->val == a) {
curr->next = curr->next->next;
}
else break;
}
}
// if (curr->next->next && curr->next->val != curr->next->next->val) {
curr = curr->next;
// }
// else continue;
}
return dummy->next;
}
};
142. 环形链表 II¶
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// x = a + b
// 2x = a + b + nc
// a = n - 1 * c + c - b
if (!head || !head->next || !head->next->next) return nullptr;
ListNode *fast = head, *slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) break;
}
if (slow != fast) return nullptr;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
};
124. 二叉树中的最大路径和¶
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 要么自己和左右两边构成一个路径，要么将左节点和自己或者右节点和自己的最大值向上传递
// 注意值会有负数
int ans = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root) {
if (!root) return 0;
int left = max(dfs(root->left), 0);
int right = max(dfs(root->right), 0);
ans = max(ans, left + right + root->val);
return max(left, right) + root->val;
}
};
15. 三数之和¶
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 首先要从小到大排列，然后再进行双指针
// 最后注意去重
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = n - 1;
for (; j < k; j++) {
// int sum = nums[i] + nums[j] + nums[k];
if (j >= i + 2 && nums[j] == nums[j - 1]) {
continue;
}
while (nums[i] + nums[j] + nums[k - 1] >= 0 && k - 1 > j) {
k--;
}
if (nums[i] + nums[j] + nums[k] == 0) {
ans.push_back({nums[i], nums[j], nums[k]});
}
}
}
return ans;
}
};
腾讯¶
53. 最大子数组和¶
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// f[i] = f[i - 1] + nums[i] // nums[i]
int n = nums.size();
int res = INT_MIN;
vector<int> f(n + 1);
for (int i = 1; i <= n; i++) {
f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
res = max(f[i], res);
}
return res;
}
};
415. 字符串相加¶
class Solution {
public:
vector<int> add(vector<int>& A, vector<int>& B) {
vector<int> C;
for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i ++ ) {
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
return C;
}
string addStrings(string a, string b) {
vector<int> A, B;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
auto C = add(A, B);
string c;
for (int i = C.size() - 1; i >= 0; i -- ) c += to_string(C[i]);
return c;
}
};
腾讯真题：寻找最长递增子序列，按字典序输出¶
#include <iostream>
#include <vector>
#include <algorithm>
void reconstruct_print(int end, const std::vector<int>& a, const std::vector<int>& p) {
int x = end;
std::vector<int> stack;
for (; p[x] >= 0; x = p[x]) stack.push_back(a[x]);
std::cout << a[x];
for (int i = stack.size() - 1; i >= 0; i--) {
std::cout << " " << stack[i];
}
std::cout << "\n";
}
int main() {
std::vector<int> a = {1, 2, 8, 6, 4};
int n = a.size();
std::vector<int> dp(n, 1), parent(n, -1);
int max_len = 0, best_end = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (a[j] < a[i]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
} else if (dp[j] + 1 == dp[i] && a[j] < a[parent[i]]) {
// 更新parent为字典序最小的选择
parent[i] = j;
}
}
}
if (dp[i] > max_len) {
max_len = dp[i];
best_end = i;
} else if (dp[i] == max_len && a[i] < a[best_end]) {
// 选择一个字典序最小的结束点
best_end = i;
}
}
std::cout << "Length of LIS: " << max_len << "\n";
std::cout << "LIS: ";
460. LFU 缓存¶
class LFUCache {
public:
struct Node {
Node *left, *right;
int key, val;
Node(int _key, int _val) {
key = _key, val = _val;
left = right = NULL;
}
};
struct Block {
Block *left, *right;
Node *head, *tail;
int cnt;
Block(int _cnt) {
cnt = _cnt;
left = right = NULL;
head = new Node(-1, -1), tail = new Node(-1, -1);
head->right = tail, tail->left = head;
}
~Block() {
delete head;
delete tail;
}
void insert(Node* p) {
p->right = head->right;
head->right->left = p;
p->left = head;
head->right = p;
}
void remove(Node* p) {
p->left->right = p->right;
p->right->left = p->left;
}
bool empty() {
return head->right == tail;
}
}*head, *tail;
int n;
unordered_map<int, Block*> hash_block;
unordered_map<int, Node*> hash_node;
void insert(Block* p) { // 在p的右侧插入新块，cnt是p->cnt + 1
auto cur = new Block(p->cnt + 1);
cur->right = p->right;
p->right->left = cur;
p->right = cur;
cur->left = p;
}
void remove(Block* p) {
p->left->right = p->right;
p->right->left = p->left;
delete p;
}
LFUCache(int capacity) {
n = capacity;
head = new Block(0), tail = new Block(INT_MAX);
head->right = tail, tail->left = head;
}
int get(int key) {
if (hash_block.count(key) == 0) return -1;
auto block = hash_block[key];
auto node = hash_node[key];
block->remove(node);
if (block->right->cnt != block->cnt + 1) insert(block);
block->right->insert(node);
hash_block[key] = block->right;
if (block->empty()) remove(block);
return node->val;
}
void put(int key, int value) {
if (!n) return;
if (hash_block.count(key)) {
hash_node[key]->val = value;
get(key);
} else {
if (hash_block.size() == n) {
auto p = head->right->tail->left;
head->right->remove(p);
if (head->right->empty()) remove(head->right);
hash_block.erase(p->key);
hash_node.erase(p->key);
delete p;
}
auto p = new Node(key, value);
if (head->right->cnt > 1) insert(head);
head->right->insert(p);
hash_block[key] = head->right;
hash_node[key] = p;
}
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/555766/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
704. 二分查找¶
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
int x = nums[mid];
if (x >= target) {
r = mid;
}
else l = mid + 1;
}
if (nums[r] == target) {
return r;
}
else return -1;
}
};
8. 字符串转换整数 (atoi)¶
C++中想要读取前导空格，读取一整行需要使用getlien(std::cin, string)
比如
string line;
getline(cin, line);
string string2;
cin >> string2;
cout << "answer:" << line << endl;
cout << "answer:" << string2 << endl;
输出分别是：
answer: string
answer:string
class Solution {
public:
int myAtoi(string s) {
int i = 0;
char f;
int res = 0;
while (s[i] == ' ') {
i++;
}
if (s[i] == '-' || s[i] == '+') {
f = s[i];
i++;
}
while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
int toAdd = s[i] - '0';
// res * 10 + toAdd < INT_MAX
if (res > (INT_MAX - toAdd) / 10) {
if (f == '-') return INT_MIN;
// 无论是前面没有符号或者有+的，都是正数
else return INT_MAX;
}
res = res * 10 + toAdd;
i++;
}
if (f == '-') return -res;
else return res;
}
};
300. 最长递增子序列¶
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// 使用动态规划来做：
// dp[i]代表的是以nums[i]为结尾的最长的递增子序列的长度
// 所以对于i就要去遍历从0 ~ i - 1, 来确定dp[i]的值
int res = 1;
int n = nums.size();
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
if (dp[i] > res) {
res = dp[i];
}
}
}
}
return res;
}
};
46. 全排列¶
class Solution {
public:
vector<bool> visited;
vector<vector<int>> ans;
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
visited = vector<bool>(n, false);
vector<int> path;
dfs(nums, path, 0);
return ans;
}
void dfs (vector<int>& nums, vector<int>& path, int n) {
if (n == nums.size()) ans.push_back(path);
for (int i = 0; i < nums.size(); i++) {
if (visited[i] == false) {
path.push_back(nums[i]);
visited[i] = true;
dfs(nums, path, n + 1);
visited[i] = false;
path.pop_back();
}
}
}
};
class Solution {
public:
// 第二种方法用来保证不会再dfs已经经过的点：
// 既然数组中的数字是定的，我们只需要每次dfs将我们想要的那个数字swap过来就行了
vector<vector<int>> ans;
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
void dfs(vector<int>& nums, int n) {
// n：正在确定nums的第几个位置
if (n == nums.size()) ans.push_back(nums);
for (int i = n; i < nums.size(); i++) {
// n之前的位置都已经确定好了，不能动
swap(nums[i], nums[n]);
dfs(nums, n + 1);
// 注意nums是动态维护的数组
// 不要忘记撤销掉动态维护的数组
swap(nums[i], nums[n]);
}
}
};
470. 用 Rand7() 实现 Rand10()¶
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution {
public:
int rand10() {
// 1234567
// 8910111213
// 保证在1 ~ 49之间完全是均匀的
int t = rand7() + (rand7() - 1) * 7;
if (t > 40) return rand10();
return t % 10 + 1;
}
};
25. K 个一组翻转链表¶
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *dummy = new ListNode(-1, head);
ListNode *curr = dummy;
while (curr) {
ListNode *tmp = curr;
for (int i = 0; i < k; i++) {
tmp = tmp->next;
if (!tmp) return dummy->next;
}
ListNode *left = curr->next, *right = curr->next->next;
for (int i = 0; i < k - 1; i++) {
ListNode *third = right->next;
right->next = left;
left = right;
right = third;
}
curr->next->next = right;
curr->next = left;
for (int i = 0; i < k; i++) {
curr = curr->next;
}
}
return dummy->next;
}
};
1. 两数之和¶
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i++) {
int aim = target - nums[i];
if (hash.find(aim) != hash.end()) {
return {hash[aim], i};
}
else hash[nums[i]] = i;
}
return {};
}
};
携程¶
5. 最长回文子串（需要重新刷）¶
dp法：
class Solution {
public:
string longestPalindrome(string s) {
// 动态规划f[i][j] = f[i + 1][j - 1]
int n = s.size();
if (n < 2) return s;
vector<vector<bool>> f(n, vector<bool>(n));
for (int i = 0; i < n; i++) {
// 所有一个字母的都是回文
f[i][i] = true;
}
int maxLen = 1;
int start = 0;
// 循环的话一定要从长度最小的开始
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] != s[j]) {
f[i][j] = false;
}
else {
if (len <= 3) {
f[i][j] = true;
}
else {
f[i][j] = f[i + 1][j - 1];
}
}
if (f[i][j] && len > maxLen) {
maxLen = len;
start = i;
}
}
}
return s.substr(start, maxLen);
}
};
中心扩展法：中心要么是1个要么是2个
class Solution {
public:
int palindrome(string &s, int l, int r, int n) {
while (l >= 0 && r < n && s[l] == s[r]) l--, r++;
return r - l - 1;
}
string longestPalindrome(string s) {
int n = s.size();
int start = 0, len = 0;
int i = 0, j = 0;
while (i < n && j < n) {
if (s[i] == s[j]) {
int l = palindrome(s, i, j, n);
if (l > len) {
start = i - (l - 1) / 2;
len = l;
}
}
if (i == j) j++;
else i++;
}
return s.substr(start, len);
}
};