# LeetCode 热题 HOT 100Day1
- 前言
- 一、两数之和（简单）
- 二、两数相加（中等）
- 扩展-两数相加 II
- 三、无重复字符的最长子串（中等）
- 四、 寻找两个正序数组的中位数
- 五、最长回文子串
- 总结
前言
备战秋招，每天坚持，注意这不是题解，有的题我觉得简单的都没有注释，这相当于自己记录，督促自己的一个渠道。
提示：以下是本篇文章正文内容，下面案例可供参考
一、两数之和（简单）两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路很简单，直接哈希表，遍历数组，找出哈希表中存在target - nums[i] ，存在即得到答案。
class Solution {
public:
vector twoSum(vector& nums, int target) {
unordered_map hash;
for (int i = 0; i < nums.size(); i++) {
int find = target - nums[i];
if (hash.count(find) != 0) {
return vector {i, hash[find]};
}
hash[nums[i]] = i;
}
return {};
}
};
二、两数相加（中等）
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
这题主要注意，进位这个操作，我们设sum为俩个节点值之和，carry为进位，因为是个位数相加，所以进位为 carry = sum / 10能够得到进位，sum的话就是 sum %= 10
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* pre = head;
int carry = 0;
while (l1 || l2) {
int val1 = l1 ? l1 -> val : 0;
int val2 = l2 ? l2 -> val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
sum %= 10;
ListNode* cur = new ListNode(sum);
pre -> next = cur;
pre = pre -> next;
if (l1) {
l1 = l1 -> next;
}
if (l2) {
l2 = l2 -> next;
}
}
if (carry) {
pre -> next = new ListNode(carry);
}
return head -> next;
}
};
扩展-两数相加 II
这题来源于445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
和前一题差不多，区别在于需要反转（写个反转链表），因为数字最高位位于链表开始位置
class Solution {
public:
ListNode* reverseList(ListNode* head) {//反转链表
if (head == nullptr) return nullptr;
ListNode* cur = head;
ListNode* pre = nullptr;
while (cur) {
ListNode* tmp = cur -> next;
cur -> next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
//反转
l1 = reverseList(l1);
l2 = reverseList(l2);
ListNode* head = new ListNode(0);
ListNode* pre = head;
int carry = 0;
while (l1 || l2) {
int val1 = l1 ? l1 -> val : 0;
int val2 = l2 ? l2 -> val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
sum %= 10;
pre -> next = new ListNode(sum);
pre = pre -> next;
if (l1) {
l1 = l1 -> next;
}
if (l2) {
l2 = l2 -> next;
}
}
if (carry) {
pre -> next = new ListNode(1);
}
return reverseList(head -> next);
}
};
三、无重复字符的最长子串（中等）
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路很简单，滑动窗口做，分别枚举每个字符的能得到的最长子串。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set hash;
int n = s.size();
int r = -1;
int ans = 0;
for (int i = 0; i < n; i++) {
if (i != 0) {
hash.erase(s[i - 1]);
}
while (r + 1 < n && hash.count(s[r + 1]) == 0) {
hash.insert(s[r + 1]);
r++;
}
ans = max(ans, r - i + 1);
}
return ans;
}
};
四、 寻找两个正序数组的中位数
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
这题还是比较难的：
思路：二分 + 奇偶判断
如果某个有序数组长度是奇数，那么其中位数就是最中间那个，如果是偶数，那么就是最中间两个数字的平均值
奇偶问题上：我们分别找第 (m+n+1)/2个数，和(m+n+2)/2个数，然后求其平均值即可，这对奇偶数均适用。假如 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size();
int n = nums2.size();
int mid1 = (m + n + 1) / 2;
int mid2 = (m + n + 2) / 2;
return (getKthElement(nums1, 0, nums2, 0, mid1) + getKthElement(nums1, 0, nums2, 0, mid2)) / 2.0;
}
int getKthElement(vector& nums1, int i, vector& nums2, int j, int k) {
if (i >= nums1.size()) return nums2[j + k - 1];
if (j >= nums2.size()) return nums1[i + k - 1];
//递归出口
if (k == 1) {
return min(nums1[i], nums2[j]);
}
int mid1 = i + k / 2 - 1 < nums1.size() ? nums1[i + k / 2 - 1] : INT_MAX;
int mid2 = j + k / 2 - 1 < nums2.size() ? nums2[j + k / 2 - 1] : INT_MAX;
if (mid1 < mid2) {
return getKthElement(nums1, i + k / 2, nums2, j, k - k / 2);
} else {
return getKthElement(nums1, i, nums2, j + k / 2, k - k / 2);
}
}
};
五、最长回文子串
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
思路：中心扩散法
class Solution {
public:
string longestPalindrome(string s) {
int len = s.size();
if (len <= 1) return s;
int start = 0;
int end = 0;
int maxLen = 0;
for (int i = 0; i < len; i++) {
int len1 = getStrLen(s, i, i);//奇数
int len2 = getStrLen(s, i, i + 1);
maxLen = max(maxLen, max(len1, len2));
if (maxLen > end - start + 1) {
start = i - (maxLen - 1) / 2;
end = i + maxLen / 2;
}
}
return s.substr(start, maxLen);
}
int getStrLen(string &s, int left, int right) {
int L = left;
int R = right;
while (L >= 0 && R < s.size() && s[L] == s[R]) {
L--;
R++;
}
return R - L -1;
}
};
总结
总之，加油
