前言
今年准备考研想固定好每周刷10道算法题以上，特地开这个栏目来记录刷题过程，按序号来刷，每10题一篇文章
LeetCode 1. 两数之和
题目链接
思路1 暴力枚举
两重循环枚举下标 i,ji,j，然后判断 nums[i]+nums[j] 是否等于 target。
复杂度O（n^2）
AC代码1
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> {i, j};
}
}
if(res.size() > 0) break;
}
return res;
}
};
思路2 哈希表优化
使用哈希表边查找边存储
查找target - num[i]是否在哈希表中 存在则返回
将num[i]插入哈希表的插入和查询操作的复杂度O（1），总复杂度O（n）
AC代码2
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> hash;
// 边找边插入
for(int i = 0; i < nums.size(); i ++)
{
int another = target - nums[i];
if(hash.count(another))
{
res = vector<int> {hash[another], i};
break;
}
hash[nums[i]] = i;
}
return res;
}
};
LeetCode 2. 两数相加
题目地址
思路
- 从最低位至最高位，逐位相加，如果和大于等于10，则保留个位数字，同时向前一位进1.
- 如果最高位有进位，则需在最前面补1.
添加一个虚拟头结点：ListNode *head = new ListNode(-1);
- 时间复杂度O(n)
AC代码
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(carry);
return res->next;
}
};
LeetCode 3. 无重复字符的最长子串
题目地址
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
思路
- 双指针写法，看y总思路即可
- 时间复杂度O（n）
AC代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 使用双指针
unordered_map<int, int> hash;
int res = 0;
for(int i = 0, j = 0; i < s.size(); i ++)
{
hash[s[i]] ++;
while(hash[s[i]] > 1)
{
hash[s[j]]--;
j ++;
}
res = max(res, i - j + 1);
}
return res;
}
};
LeetCode 4. 寻找两个正序数组的中位数
题目地址
思路
此题乍一看很简单，实则难度很大，建议看y总的题解
https://www.acwing.com/solution/content/50/
AC代码 递归
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if(total % 2 == 0)
{
int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
return (left + right) / 2.0;
}
else
{
return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
}
}
// nums1的长度一定比nums2的小
int findKthNumber(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)
{
// 此处使nums1一定比nums2小
if(nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
if(nums1.size() == i) return nums2[j + k - 1];
if(k == 1) return min(nums1[i], nums2[j]);
int s1 = min(i + k / 2, (int)nums1.size()), s2 = j + k / 2;
if(nums1[s1 - 1] > nums2[s2 - 1])
{
return findKthNumber(nums1, i, nums2, s2, k - (s2 - j));
}
else
{
return findKthNumber(nums1, s1, nums2, j, k - (s1 - i));
}
}
};
LeetCode 5. 最长回文子串
题目地址
思路
使用双指针 比较简单的了，注意处理好字符串长度奇数和偶数的情况
- 奇数：l = i, r = i;
- 偶数：l = i, r = i + 1;
AC代码 递归
class Solution {
public:
string longestPalindrome(string s) {
string res;
for(int i = 0; i < s.size(); i ++)s
{
// s长度为奇数
int l = i, r = i;
while (l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
// s长度为偶数
l = i, r = i + 1;
while(l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
}
return res;
}
};
LeetCode 6. Z 字形变换
题目地址
https://leetcode.cn/problems/zigzag-conversion/submissions/
思路
找规律问题 可以看y总的解释
https://www.acwing.com/solution/content/75/
下面ac代码也有超级详细注释
AC代码
class Solution {
public:
string convert(string s, int n) {
string res;
// 如果只有一个字符 则为原字符串
if (n == 1) return s;
for (int i = 0; i < n; i ++)
{
// 第一行和最后一行 是首项为i 公差为2n-2的等差数列
if (i == 0 || i == n - 1)
{
for (int j = i; j < s.size(); j += 2 * n - 2)
res += s[j];
}
else // 其他每一行都是由两个等差数列交叉 一个是首项为i公差为2n-2-i 一个是首项为2n-2-i公差为
{
for (int j = i, k = 2 * n - 2 - i; j < s.size() || k < s.size(); j += 2 * n - 2 , k += 2 * n - 2)
{
if (j < s.size()) res += s[j];
if (k < s.size()) res += s[k];
}
}
}
return res;
}
};
LeetCode 7. 整数反转
题目地址
https://leetcode.cn/problems/reverse-integer/
思路
比较简单看代码即可
注意：有两种方法一种用long long res不会溢出，题目说明好像有规定不让long long，使用int的时候注意判断溢出情况
AC代码
// 使用long long
class Solution {
public:
int reverse(int x) {
long long res = 0;
while (x)
{
res = res * 10 + x % 10;
x /= 10;
}
if (res > INT_MAX) return 0;
if (res < INT_MIN) return 0;
return res;
}
};
// 使用int
class Solution {
public:
int reverse(int x) {
int res = 0;
while (x)
{
// 检测res会不会溢出
if (res > 0 && res > (INT_MAX - x % 10) / 10) return 0;
if (res < 0 && res < (INT_MIN - x % 10) / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};
LeetCode 8. 字符串转换整数 (atoi)
题目地址
https://leetcode.cn/problems/string-to-integer-atoi/
思路
跟上一题一样 使用long long 和 int存储
AC代码
// 使用long long
class Solution {
public:
int myAtoi(string s) {
int k = 0; // 移动指针
// 先去除空格
while (k < s.size() && s[k] == ' ') k ++;
if (k == s.size()) return 0;
// 判断数字前面的正负
int minus = 1;
if (s[k] == '+') k ++;
else if (s[k] == '-') minus = -1, k++;
// 数字部分
long long res = 0;
while (k < s.size() && s[k] >= '0' && s[k] <= '9')
{
res = res * 10 + s[k] - '0';
k ++;
if (res > INT_MAX) break;
}
res *= minus;
// 判断溢出
if (res > INT_MAX) res = INT_MAX;
if (res < INT_MIN) res = INT_MIN;
return res;
}
};
// 使用int
class Solution {
public:
int myAtoi(string s) {
int k = 0; // 移动指针
// 先去除空格
while (k < s.size() && s[k] == ' ') k ++;
if (k == s.size()) return 0;
// 判断数字前面的正负
int minus = 1;
if (s[k] == '+') k ++;
else if (s[k] == '-') minus = -1, k++;
// 数字部分 使用int处理好溢出
int res = 0;
while (k < s.size() && s[k] >= '0' && s[k] <= '9')
{
int x = s[k] - '0';
// 正数和负数溢出情况
if (minus > 0 && res > (INT_MAX - x) / 10) return INT_MAX;
if (minus < 0 && -res < (INT_MIN + x) / 10) return INT_MIN;
// 注意int正数的最大值是2^31-1 int负数的最小值是-2^31 比正数多译
// 这里得判断 如果刚好等于负数最小值的情况
if (- res * 10 - x == INT_MIN) return INT_MIN;
res = res * 10 + x;
k ++;
if (res > INT_MAX) break;
}
res *= minus;
// 判断溢出
if (res > INT_MAX) res = INT_MAX;
if (res < INT_MIN) res = INT_MIN;
return res;
}
};
LeetCode 9. 回文数
题目地址
https://leetcode.cn/problems/palindrome-number/
思路
两种做法 一种需要额外开辟tmp存储x 另一种不用
AC代码
// 需要存储x 这种好像快一点
class Solution {
public:
bool isPalindrome(int x) {
int tmp = x;
// 负数直接返回
if ( x < 0 ) return false;
long long y = 0;
while (x)
{
y = y * 10 + x % 10;
x /= 10;
}
return tmp == y;
}
};
// 不需要存储x
class Solution {
public:
bool isPalindrome(int x) {
// 负数直接返回
if ( x < 0 ) return false;
long long y = 0;
for (int i = x; i; i /= 10)
{
y = y * 10 + i% 10;
}
return x == y;
}
};
LeetCode 10. 正则表达式匹配
题目地址
https://leetcode.cn/problems/regular-expression-matching/
思路
本题难度有点大 建议看y总讲解
AC代码
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p;
vector<vector<bool>> f(n + 1, vector<bool> (m + 1));
f[0][0] = true;
for (int i = 0; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (j + 1 < m && p[j + 1] == '*') continue;
if (i && p[j] != '*')
{
f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
}
else if (p[j] == '*')
{
f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
}
}
return f[n][m];
}
};
