蒟蒻的LeetCode刷题记录1~10

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++) { if (hash.count(target - nums[i])) return {hash[target - nums[i]], i}; hash[nums[i]] = i; } return {}; } };

2.两数相加

/** * 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* addTwoNumbers(ListNode* l1, ListNode* l2) { auto dummy = new ListNode(-1); auto cur = dummy; int t = 0; while (l1 || l2 || t) { if (l1) t += l1->val, l1 = l1->next; if (l2) t += l2->val, l2 = l2->next; cur->next = new ListNode(t % 10); cur = cur->next; t /= 10; } return dummy->next; } };

3.无重复字符的最长子串 定义两个指针 j,i(j<=i)，表示当前扫描到的子串是[j, i](闭区间)。扫描过程中维护一个哈希表unordered_map<char,int> hash，表示 [j, i]中每个字符出现的次数。线性扫描时，每次循环的流程如下：

指针 i 向后移一位, 同时将哈希表中 s[i] 的计数加一: hash[s[i]]++;假设 i 移动前的区间 [j, i]中没有重复字符，则 i 移动后，只有 s[i] 可能出现2次。因此我们不断向后移动 j，直至区间 [j,i]中 s[i] 的个数等于1为止；

复杂度分析：由于j均最多增加n次，且哈希表的插入和更新操作的复杂度都是 $O(1)$，因此，总时间复杂度 $O(n)$

class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, 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++]]--; res = max(res, i - j + 1); } return res; } };

4. 寻找两个正序数组的中位数 这一题还是比较困难的。推荐题解

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int tot = nums1.size() + nums2.size();//求总数 //偶数，中位数为中间两个数的平均数 if (tot % 2 == 0) { int left = find(nums1, 0, nums2, 0, tot / 2); int right = find(nums1, 0, nums2, 0, tot / 2 + 1); return (left + right) / 2.0; } else { return find(nums1, 0, nums2, 0, tot / 2 + 1);//奇数的情况 } } int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) { if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);//如果第一个数组长的话则交换，保证第一个数组短 //处理边界问题：k == 1,只有一个数的情况，那么取这两个数组前面的最小值即可 if (k == 1) { if (nums1.size() == i) return nums2[j];//特判一下，第一个数组为空，那么只能返回第二个数组 else return min(nums1[i], nums2[j]);//否则返回这两个数组的最小值 } if (nums1.size() == i) return nums2[j + k - 1];//第一个数组为空，直接返回第二个数组的第k个数 //上下两个数组都分给k/2个数后的下标,第一个数可能会越界，所以要取一个最小值 int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2; if (nums1[si - 1] > nums2[sj - 1])//都是第k/2个数的后一个数，所以要'-1' return find(nums1, i, nums2, sj, k - (sj - j));//第一个数组的中间>第二个数组的中间，则nums2的后半段没有用 else return find(nums1, si, nums2, j, k - (si - i)); } };

5. 最长回文子串

class Solution { public: string longestPalindrome(string s) { string res; for (int i = 0; i < s.size(); i++) { int l = i - 1, r = i + 1;//奇数情况 while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++; if (res.size() < (r - 1) - (l + 1) + 1) res = s.substr(l + 1, r - l - 1); 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; } };

6. Z 字形变换

class Solution { public: string convert(string s, int n) { string res; if (n == 1) return s;//行数为1的时候需要特判，否则2 * n - 2 = 0，会陷入死循环 //遍历打印输出即可 for (int i = 0; i < n; i ++ ) { if (i == 0 || i == n - 1) {//第一行和最后一行是公差为 2*(n−1)的等差数列，首项是 0 和 n−1 for (int j = i; j < s.size(); j += 2 * n - 2) res += s[j]; } else {//处理中间的行 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; } };

7. 整数反转 很简单的数学操作，主要就是边界的判断，根据下面的式子来写，其实就是一个等价变化。

class Solution { public: int reverse(int x) { int res = 0; while (x) { 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; } };

8. 字符串转换整数 (atoi) 之前刷剑指的时候有写过，本题的难点就是各种边界的判断

class Solution { public: int myAtoi(string str) { int k = 0; while (k < str.size() && str[k] == ' ') k ++ ;//删除前面的空格字符 if (k == str.size()) return 0; int minus = 1;//负号的问题 if (str[k] == '-') minus = -1, k ++ ;//负号需要记录一下 else if (str[k] == '+') k ++ ;//正号则直接往后走 int res = 0; while (k < str.size() && str[k] >= '0' && str[k] <= '9') { int x = str[k] - '0'; if (minus > 0 && res > (INT_MAX - x) / 10) return INT_MAX; if (minus < 0 && -res < (INT_MIN + x) / 10) return INT_MIN; if (-res * 10 - x == INT_MIN) return INT_MIN; res = res * 10 + x; k ++ ; if (res > INT_MAX) break; } res *= minus; return res; } };

9. 回文数 转化成字符串

class Solution { public: bool isPalindrome(int x) { if (x < 0) return 0; string s = to_string(x); return s == string(s.rbegin(), s.rend()); } };

数值方法

class Solution { public: bool isPalindrome(int x) { if (x < 0) return 0; int y = x; long long res = 0; while (x) { res = res * 10 + x % 10; x /= 10; } return res == y; } };

10. 正则表达式匹配

class Solution { public: bool isMatch(string s, string p) { int n = s.length(), m = p.length(); vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false)); s = " " + s; p = " " + p; f[0][0] = true; for (int i = 0; i <= n; i++) for (int j = 1; j <= m; j++) { if (i > 0 && (s[i] == p[j] || p[j] == '.')) f[i][j] = f[i][j] | f[i - 1][j - 1]; if (p[j] == '*') { if (j >= 2) f[i][j] = f[i][j] | f[i][j - 2]; if (i > 0 && (s[i] == p[j - 1] || p[j - 1] == '.')) f[i][j] = f[i][j] | f[i - 1][j]; } } return f[n][m]; } };