共计 4524 个字符，预计需要花费 12 分钟才能阅读完成。
一、给定一个字符串，返回它的最长回文子串。如果存在多个答案，返回任意一个即可。字符串长度 ≤≤ 1000。
算法:（暴力枚举）O(n2)O(n2)
因为字符串长度小于 1000，因而咱们能够用 O(n2)O(n2) 的算法枚举所有可能的状况。
首先枚举回文串的核心 ii，而后分两种状况向两边扩大边界，直到遇到不同字符为止:
- 回文串长度是奇数，则顺次判断 s[i−k]==s[i+k],k=1,2,3,…s[i−k]==s[i+k],k=1,2,3,…
- 回文串长度是偶数，则顺次判断 s[i−k]==s[i+k−1],k=1,2,3,…s[i−k]==s[i+k−1],k=1,2,3…
如果遇到不同字符，则咱们就找到了以 ii 为核心的回文串边界。
工夫复杂度剖析：一共两重循环，所以工夫复杂度是 O(n2)O(n2)。
C++ 代码演示：
class Solution {
public:
string longestPalindrome(string s) {
int res = 0;
string str;
for (int i = 0; i < s.size(); i ++ )
{for (int j = 0; i - j >= 0 && i + j < s.size(); j ++ )
if (s[i - j] == s[i + j])
{if (j * 2 + 1 > res)
{
res = j * 2 + 1;
str = s.substr(i - j, j * 2 + 1);
}
}
else break;
for (int j = i, k = i + 1; j >= 0 && k < s.size(); j -- , k ++ )
if (s[j] == s[k])
{if (k - j + 1 > res)
{
res = k - j + 1;
str = s.substr(j, k - j + 1);
}
}
else break;
}
return str;
}
};二、给定一个整型数组，要求返回两个数的下标，使得两数之和等于给定的目标值，要求同一个下标不能应用两次，数据保障有且仅有一组解。
算法：(暴力枚举) O(n2)O(n2)
暴力枚举办法很简略：两重循环枚举下标 i,ji,j，而后判断 nums[i]+nums[j]nums[i]+nums[j] 是否等于 targettarget。
工夫复杂度：因为有两重循环，所以复杂度是 O(n2)O(n2)。
C++ 代码演示：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int> res;
for (int i = 0; i < nums.size(); i++)
{for (int j = 0; j < i; j++)
{if (nums[i] + nums[j] == target)
{res = vector<int>({j, i});
break;
}
}
if (res.size() > 0) break;
}
return res;
}
};三、给你两个非空链表，别离示意两个非负整数。示意办法：链表中的每个节点，别离示意整数中的一位数字，程序从低位至高位。例如：2 -> 4 -> 3 示意 342. 请计算两个整数的和，并返回成链表的模式。数据保障两个整数均不蕴含前导 0（除了 0 之外），例如：不会呈现 0023。
算法：(模仿人工加法) O(n)O(n)
这是道模拟题，模仿咱们小时候列竖式做加法的过程：
- 从最低位至最高位，逐位相加，如果和大于等于 10，则保留个位数字，同时向前一位进 1.
- 如果最高位有进位，则需在最后面补 1.
做无关链表的题目，有个罕用技巧：增加一个虚构头结点：ListNode *head = new ListNode(-1);，能够简化边界状况的判断。
C++ 代码演示：
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{ListNode *res = new ListNode(-1); // 增加虚构头结点，简化边界状况的判断
ListNode *cur = res;
int carry = 0; // 示意进位
while (l1 || l2)
{
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + carry;
carry = sum / 10;
cur->next = new ListNode(sum % 10);
cur = cur->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (carry) cur->next = new ListNode(1); // 如果最高位有进位，则需在最后面补 1.
return res->next; // 返回真正的头结点
}
};四、给定一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0？找出所有满足条件且不反复的三元组。留神：答案中不能够蕴含反复的三元组。
算法：(两重枚举，汇合判重) O(n2)O(n2)
应用 C++ 中的汇合 unordered_set。
- 首先对 nums 进行从小到大排序。
- 两重循环枚举 nums 数组，第一重循环仅枚举不反复的数字。
- 第二重循环须要用两个汇合 hash 和 vis 记录某个数字是否存在，在循环体重咱们做两件事：
- 判断 -nums[st] − nums[i] 是否在 hash 汇合中；若存在，则能够记录进答案；并且须要向 vis 汇合增加数字 -nums[st] – nums[i]。若不存在，则向 hash 汇合中增加数字 nums[i]。
- 做完上一步后须要判断 vis 汇合中是否存在数字 -nums[st] – nums[i]（显然如果 1 中刚刚增加过肯定是存在的）；若存在，则删除 hash 汇合中数字 -nums[st] – nums[i]。
留神：应用 vis 汇合的目标是避免 -nums[st] – nums[i] 和 nums[i] 数对被反复计算入答案。
工夫复杂度：排序工夫复杂度是 O(nlogn)O(nlogn)，枚举的工夫简单的是 O(n2)O(n2)，每次须要用汇合操作均匀 O(1)O(1)，所以总工夫复杂度为 O(n2)O(n2)，但常数较大。
C++ 代码演示：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
unordered_set<int> hash, vis;
sort(nums.begin(), nums.end());
for (int st = 0; st < nums.size(); st++) {while (st != 0 && nums[st] == nums[st - 1])
st++;
hash.clear();
vis.clear();
for (int i = st + 1; i < nums.size(); i++) {auto got = hash.find(-nums[st] - nums[i]);
if (got == hash.end())
hash.insert(nums[i]);
else {res.push_back({nums[st], nums[i], -nums[st] - nums[i]});
vis.insert(-nums[st] - nums[i]);
}
if (vis.find(-nums[st] - nums[i]) != vis.end())
hash.erase(-nums[st] - nums[i]);
}
}
return res;
}
};五、实现 atoi 函数，将以字符串 (string) 模式示意的整数，转换成整型(int)。
aoti 函数须要满足的条件：
- 疏忽所有行首空格，找到第一个非空格字符，能够是‘+/−+/−’示意是负数或者正数，紧随其后找到最长的一串间断数字，将其解析成一个整数；
- 整数后可能有任意非数字字符，请将其疏忽；
- 从前往后遍历时，如果第一段间断数字为空，则返回 0；
- 如果整数大于 INT_MAX，请返回 int_MAX；如果整数小于 INT_MIN，请返回 INT_MIN；
算法：(模仿) O(n)O(n)
这道题的难点在于边界状况十分多，须要认真思考。
做这道题目时，举荐先写一个傻瓜版，而后提交，再依据 Wrong Case 去逐渐增加针对各种状况的解决。
工夫复杂度剖析：假如字符串长度是 nn，每个字符最多遍历一次，所以总工夫复杂度是 O(n)O(n)。
C++ 代码演示：
class Solution {
public:
int strToInt(string str) {
int res = 0;
int neg = 0;
int i = 0;
while (i < str.size() && str[i] == ' ') i++;
if (str[i] == '-') neg = -1;
if (str[i] == '+' || str[i] == '-') ++i;
for (; i < str.size(); ++i)
{if (str[i] < '0' || str[i] > '9') break;
else
{int x = str[i] - '0';
if (neg == -1)
{
x = -x;
if ((INT_MIN - x) / 10 <= res)
{
res *= 10;
res += x;
}
else return INT_MIN;
}
else
{if ((INT_MAX - x) / 10 >= res)
{
res *= 10;
res += x;
}
else return INT_MAX;
}
}
}
return res;
}
};6、给出两个排好序的单向链表，返回合并排序后新的单向链表。
链表结点的数据结构：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}};算法：(线性合并) O(n)O(n)
- 新建头部的爱护结点 dummy，设置 cur 指针指向 dummy。
- 若以后 l1l1 指针指向的结点的值 val 比 l2l2 指针指向的结点的值 val 小，则令 cur 的 next 指针指向 l1l1，且 l1l1 后移；否则指向 l2l2，且 l2l2 后移。
- 而后 cur 指针依照上一部设置好的地位后移。
- 循环以上步骤直到 l1l1 或 l2l2 为空。
- 将残余的 l1l1 或 l2l2 接到 cur 指针后边。
工夫复杂度：两个链表各遍历一次，所以工夫复杂度为 O(n)O(n)。
C++ 代码演示：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while (l1 != NULL && l2 != NULL) {if (l1 -> val < l2 -> val) {
cur -> next = l1;
l1 = l1 -> next;
}
else {
cur -> next = l2;
l2 = l2 -> next;
}
cur = cur -> next;
}
cur -> next = (l1 != NULL ? l1 : l2);
return dummy -> next;
}
};
材料收费支付
首先祝贺您，可能认真的浏览到这里，如果对局部了解不太明确，倡议先将文章珍藏起来，而后对不分明的知识点进行查阅，而后在进行浏览，相应你会有更深的认知。如果您喜爱这篇文章，就点个赞或者【关注我】吧！！
正文完
